Activity Selection Problem

Greedy Algorithm are known for creating the optimum solution of the problem. Greedy Algorithm are best when the solution that we are trying to achieve has no definite best solution, at that point greedy algorithm fulfils our demand for optimum solution but not the best solution. And because no other solution to that particular algorithm exists therefore greedy algorithm solution will even serve as the best method that solves that problem. Also, sometimes greedy algorithm fails to solve the problem such as it is able to solve the Fractional Knapsack problem but it cannot solve the 0-1 knapsack problem.

Their exists many algorithm that has resulted from the Greedy Algorithm such as Minimum spanning Tree, Dijkstra’s shortest path, travelling salesman, activity selection problem and many more.  Let’s us continue with the Activity Selection Problem.

The Activity Selection problem is a way of selecting an optimized solution for the non-conflicting activities that has to be completed by either some individual or with the assistance of planned computer program in a specified time frame.

Theoretical Analysis  

Activity selection problem is a problem where a machine or the person is provided with the list of the task that has to done, and each of the task consists of the starting time and the ending time or the deadline in which the task is valid to be completed. The work of the activity selection algorithm is to schedule the tasks in the list in such a manner that the person is able to complete most of the task or able to finish maximum number of activities. As because of the presence of the deadline it will not be possible for completing all the activities in hand as the timing of each activity can collapse because of the deadline. Therefore As It is impossible to complete each and every task on the list we have to schedule the task such that the maximum number of the activity can be completed.

Now we want to adjust the task on the list on the basis for maximum number of completion of the activities. So, one approach to the our adjusting of the tasks in the list is that we can first choose the activity that will take minimum time for completion and this will give us the maximum amount of time that we adjust in our list later. This is one way of the greedy approach which involves finishing off the tasks which takes minimum amount of the completion time. Now, after this it comes the time to verify that our intuition based approach is effective or not.

Now when we have verified that our intuition based approach is able to provide us with the required solution. Now our first task will begin to for sorting the activities on the basis of the completion time. Now for this we have to iterate over and over on our list that contains the deadline and select the activity the complete in the minimum time possible and then again iterate on the list to find the next activity and then other.

Developing the Solution

We require information about the task to be completed for example in our case is the time required for the completion of the activity. We can start our solution by passing the information through array that contains the starting and the finishing time of our task.

We are making the assumption that these array are sorted out on the basis of the time required to finish the activity. So, we are going to sort those activities beginning from the first task. We will have to make an array which will have our all activity as the optimum solution and we have start by adding the first activity into the array.

Also we have to keep a check on the last element of the array to select the next activity that has to be started when the previous finishes of.  In the Similar way the iteration will begin for choosing the next activity when the previous ends and it will keep on until the array becomes filled completely and then we will have our desired optimum solution by the activity selection problem and the application of the greedy approach algorithm.

Real Life Problem Solving

There are also many real life application of the Activity Selection problem and some of the following shows its real life usability:

With the automation industry is rising the more need of this algorithm is increasing, It helps to run the automated programs and the coordination of these programs is done with the activity scheduling problem with in turn helps in smooth completion of the automated task like in data analysis where when the raw data has received it has to converted into readable format and then analysis can be done and the scheduling of these task can occur with the activity scheduling algorithm.

The use in the manufacturing industry, the operation lines is capable to produce more than one product on the same manufacturing machine, and for the product to be manufactured smoothly a scheduling algorithm plays a great deal in setting the right production timelines.

And activity selection problem is made for the real life business because it uses greedy approach and that is to maximize the output with the best solution possible the same approach is applied with the help of the activity selection problem to maximize the profits by the right selection of the maximum profit providing consumer with a real life deadline.

 

One thought on “Activity Selection Problem

  • October 24, 2020 at 2:49 pm
    Permalink

    Can activity selection problem solved by branch and bound

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *