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. 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.

 

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

 

 
We can easily solve this problem by following a Greedy approach. The idea is very simple. We consider each task in decreasing 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

 
Below is C++ and Java implementation of Job sequencing problem:

C++

Download   Run Code

Output:

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

Java

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:

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Spammer
Guest

Good post!!

Tanmay Jha
Guest

Nice greedy algorithm.

ibra_99
Guest

Could you explain why do we put any task with max profit only at the latest possible slot and not anywhere else? I understand it intuitively but I’m not able to frame an explanation

Ankit
Guest

It’s greedy algorithm..