Job Sequencing Problem with Deadlines

Given a set of tasks with deadlines and total profit earned on completion of a task, find maximum profit earned by executing the tasks within the specified deadlines. Assume any task will take one unit of time to execute and any task can’t execute beyond its deadline. Also, only one task can be executed at a time.


For example, consider below set of tasks that have a deadline and profit associated with it,

Tasks Deadlines Profit
1 9 15
2 2 2
3 5 18
4 7 1
5 4 25
6 2 20
7 5 8
8 7 10
9 4 12
10 3 5

If we choose tasks 1, 3, 4, 5, 6, 7, 8 and 9, we can achieve maximum profit of 109. Note that task 2 and task 10 are left out.
 


 

We can easily solve this problem by following a Greedy approach. The idea is very simple. We consider each task in increasing order of their profits and schedule it in the latest possible free slot that meets its deadline. If no such slot is there, don’t schedule the task.

Below table shows the tasks arranged based on their associated profits. Here task 5 has maximum priority associated with it as it has maximum profit of 30. Similarly, task 4 has least priority. Greedy approach will consider the tasks in decreasing order of their priority.

Tasks Deadlines Profit (Maximum first)
5 4 25
6 2 20
3 5 18
1 9 15
9 4 12
8 7 10
7 5 8
10 3 5
2 2 2
4 7 1

To demonstrate the greedy approach, lets consider the deadlines in form of circular structure as shown below. Each slot can be filled by a given task. Now lets start allocated the tasks based on the deadlines. We will start with task 5 having deadline 4 and fill it empty slot 3-4.
  job-scheduling-2

Next consider task 6 having deadline 2 and fill it empty slot 1-2.
  job-scheduling-3

Next consider task 3 having deadline 5 and fill it empty slot 4-5.
  job-scheduling-4

Next consider task 1 having deadline 9 and fill it empty slot 8-9.
  job-scheduling-5

Next consider task 9 having deadline 4. As slot 3-4 is already filled with task 5, we will consider next free slot 2-3 and assign task 9 to it.
  job-scheduling-6

Next consider task 8 having deadline 7 and fill it empty slot 6-7.
  job-scheduling-7

Next consider task 7 having deadline 5. As slot 4-5 is already filled with task 3, we will consider next free slot 0-1 and assign task 7 to it.
  job-scheduling-8

Next consider task 10 having deadline 3. Since all slots before deadline 3 are filled, we ignore the task. Similarly, we ignore next task 2 having deadline 2.

The last task is task 4 having deadline 7 which gets next empty slot 6-5.
  job-scheduling-9

 
C++ implementation –
 

Download   Run Code

Output:

The Scheduled jobs are – 7 6 9 5 3 4 8 1
Total Profit is 109

 
Time complexity of above solution is O(n2).

References:

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂