Job Sequencing with Deadline

Job scheduling algorithm is applied to schedule the jobs on a single processor to maximize the profits.

The greedy approach of the job scheduling algorithm states that, Given n number of jobs with a starting time and ending time, they need to be scheduled in such a way that maximum profit is received within the maximum deadline.

Job Scheduling Algorithm

Set of jobs with deadlines and profits are taken as an input with the job scheduling algorithm and scheduled subset of jobs with maximum profit are obtained as the final output.

Algorithm

Step1 −  Find the maximum deadline value from the input set 
of jobs.
Step2 −  Once, the deadline is decided, arrange the jobs 
in descending order of their profits.
Step3 −  For each job in the sorted order, find the latest 
available time slot that is less than or equal to its deadline 
and assign the job to that slot.
Step4 −  The selected set of jobs are the output.

Examples

Consider the following tasks with their deadlines and profits. Schedule the tasks in such a way that they produce maximum profit after being executed −

S. No.	1	2	3	4	5
Jobs	J1	J2	J3	J4	J5
Deadlines	2	2	1	3	4
Profits	20	60	40	100	80

Step 1

Find the maximum deadline value, d_m, from the deadlines given.

dm = 4

This means we have 4 time slots available: [1], [2], [3], [4]

Step 2

Arrange the jobs in descending order of their profits.

S. No.	1	2	3	4	5
Jobs	J4	J5	J2	J3	J1
Deadlines	3	4	2	1	2
Profits	100	80	60	40	20

Step 3

Select jobs greedily, placing each in the latest available time slot that does not exceed its deadline.

Iteration 1: J4 (Profit = 100, Deadline = 3)

Find the latest free slot ≤ 3. Slot 3 is free, so assign J4 to slot 3.

Slots: [_, _, J4, _]
Total Profit = 100

Iteration 2: J5 (Profit = 80, Deadline = 4)

Find the latest free slot ≤ 4. Slot 4 is free, so assign J5 to slot 4.

Slots: [_, _, J4, J5]
Total Profit = 100 + 80 = 180

Iteration 3: J2 (Profit = 60, Deadline = 2)

Find the latest free slot ≤ 2. Slot 2 is free, so assign J2 to slot 2.

Slots: [_, J2, J4, J5]
Total Profit = 180 + 60 = 240

Iteration 4: J3 (Profit = 40, Deadline = 1)

Find the latest free slot ≤ 1. Slot 1 is free, so assign J3 to slot 1.

Slots: [J3, J2, J4, J5]
Total Profit = 240 + 40 = 280

Iteration 5: J1 (Profit = 20, Deadline = 2)

Find the latest free slot ≤ 2. Slots 1 and 2 are already occupied. J1 cannot be scheduled.

Step 4

All jobs have been considered. The algorithm terminates.

Final Result:

The optimal sequence of jobs scheduled within their deadlines is {J3, J2, J4, J5} (executed in time slots 1, 2, 3, 4 respectively) with the maximum profit of 280.

Time Slot	1	2	3	4
Job	J3	J2	J4	J5
Profit	40	60	100	80

Maximum Profit: 40 + 60 + 100 + 80 = 280

Example

Following is the final implementation of Job sequencing Algorithm using Greedy Approach −

CC++JavaPython

#include <stdbool.h>#include <stdio.h>#include <stdlib.h>// A structure to represent a JobtypedefstructJob{char id[3];// Job Id (e.g., "J1", "J2")int deadline;// Deadline of Jobint profit;// Profit if Job is completed before or on deadline} Job;// Comparison function for sorting jobs by profit in descending orderintcompare(constvoid* a,constvoid* b){
   Job* job1 =(Job*)a;
   Job* job2 =(Job*)b;return(job2->profit - job1->profit);}// Find minimum between two numbersintmin(int num1,int num2){return(num1 < num2)? num1 : num2;}intmain(){// Jobs from the example: J1, J2, J3, J4, J5// Deadlines: 2, 2, 1, 3, 4// Profits: 20, 60, 40, 100, 80
   Job arr[]={{"J1",2,20},{"J2",2,60},{"J3",1,40},{"J4",3,100},{"J5",4,80}};int n =sizeof(arr)/sizeof(arr[0]);// Find maximum deadlineint maxDeadline =0;for(int i =0; i < n; i++){if(arr[i].deadline > maxDeadline)
         maxDeadline = arr[i].deadline;}printf("Maximum Deadline: %d\n", maxDeadline);printf("Number of time slots available: %d\n\n", maxDeadline);// Sort jobs by profit in descending orderqsort(arr, n,sizeof(Job), compare);printf("Jobs sorted by profit (descending):\n");for(int i =0; i < n; i++){printf("%s (Deadline: %d, Profit: %d)\n", arr[i].id, arr[i].deadline, arr[i].profit);}printf("\n");int result[maxDeadline];// To store result sequence of jobs
   bool slot[maxDeadline];// To keep track of free time slots// Initialize all slots to be freefor(int i =0; i < maxDeadline; i++)
      slot[i]= false;int totalProfit =0;// Iterate through all given jobsfor(int i =0; i < n; i++){// Find a free slot for this job (start from the last possible slot)for(int j =min(maxDeadline, arr[i].deadline)-1; j >=0; j--){// Free slot foundif(slot[j]== false){
            result[j]= i;
            slot[j]= true;
            totalProfit += arr[i].profit;printf("Scheduled %s in slot %d (Profit: %d)\n", arr[i].id, j +1, arr[i].profit);break;}}}// Print the resultprintf("\nFollowing is the maximum profit sequence of Jobs:\n");for(int i =0; i < maxDeadline; i++){if(slot[i])printf("Slot %d: %s\n", i +1, arr[result[i]].id);}printf("\nTotal Maximum Profit: %d\n", totalProfit);return0;}

Output

Maximum Deadline: 4
Number of time slots available: 4

Jobs sorted by profit (descending):
J4 (Deadline: 3, Profit: 100)
J5 (Deadline: 4, Profit: 80)
J2 (Deadline: 2, Profit: 60)
J3 (Deadline: 1, Profit: 40)
J1 (Deadline: 2, Profit: 20)

Scheduled J4 in slot 3 (Profit: 100)
Scheduled J5 in slot 4 (Profit: 80)
Scheduled J2 in slot 2 (Profit: 60)
Scheduled J3 in slot 1 (Profit: 40)

Following is the maximum profit sequence of Jobs:
Slot 1: J3
Slot 2: J2
Slot 3: J4
Slot 4: J5

Total Maximum Profit: 280