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 − Selects the jobs with highest profits, their time periods not exceeding the maximum deadline. 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

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

dm = 4.

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

The maximum deadline, dm, is 4. Therefore, all the tasks must end before 4.

Choose the job with highest profit, J4. It takes up 3 parts of the maximum deadline.

Therefore, the next job must have the time period 1.

Total Profit = 100.

The next job with highest profit is J5. But the time taken by J5 is 4, which exceeds the deadline by 3. Therefore, it cannot be added to the output set.

The next job with highest profit is J2. The time taken by J5 is 2, which also exceeds the deadline by 1. Therefore, it cannot be added to the output set.

The next job with higher profit is J3. The time taken by J3 is 1, which does not exceed the given deadline. Therefore, J3 is added to the output set.

Total Profit: 100 + 40 = 140

Since, the maximum deadline is met, the algorithm comes to an end. The output set of jobs scheduled within the deadline are with the maximum profit of 140.

Example

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

#include #include #include // A structure to represent a Jobs typedef struct Jobs < char id; // Jobs Id int dead; // Deadline of Jobs int profit; // Profit if Jobs is over before or on deadline >Jobs; // This function is used for sorting all Jobss according to // profit int compare(const void* a, const void* b)< Jobs* temp1 = (Jobs*)a; Jobs* temp2 = (Jobs*)b; return (temp2->profit - temp1->profit); > // Find minimum between two numbers. int min(int num1, int num2) < return (num1 >num2) ? num2 : num1; > int main()< Jobs arr[] = < < 'a', 2, 100 >, < 'b', 2, 20 >, < 'c', 1, 40 >, < 'd', 3, 35 >, < 'e', 1, 25 >>; int n = sizeof(arr) / sizeof(arr[0]); printf("Following is maximum profit sequence of Jobs: \n"); qsort(arr, n, sizeof(Jobs), compare); int result[n]; // To store result sequence of Jobs bool slot[n]; // To keep track of free time slots // Initialize all slots to be free for (int i = 0; i < n; i++) slot[i] = false; // Iterate through all given Jobs for (int i = 0; i < n; i++) < // Find a free slot for this Job for (int j = min(n, arr[i].dead) - 1; j >= 0; j--) < // Free slot found if (slot[j] == false) < result[j] = i; slot[j] = true; break; >> > // Print the result for (int i = 0; i

Output

Following is maximum profit sequence of Jobs: c a d
#include #include using namespace std; struct Job < char id; int deadLine; int profit; >; bool comp(Job j1, Job j2) < return (j1.profit >j2.profit); //compare jobs based on profit > int min(int a, int b) < return (aint main()< Job jobs[] = < < 'a', 2, 100 >, < 'b', 2, 20 >, < 'c', 1, 40 >, < 'd', 3, 35 >, < 'e', 1, 25 >>; int n = 5; cout =0; j--) < //search from last free slot if (slot[j]==false) < jobSeq[j] = i; // Add this job to job sequence slot[j] = true; // mark this slot as occupied break; >> > for (int i=0; i

Output

Following is maximum profit sequence of Jobs: c a d
import java.util.*; public class Job < // Each job has a unique-id,profit and deadline char id; int deadline, profit; // Constructors public Job() <>public Job(char id, int deadline, int profit) < this.id = id; this.deadline = deadline; this.profit = profit; >// Function to schedule the jobs take 2 arguments // arraylist and no of jobs to schedule void printJobScheduling(ArrayList arr, int t) < // Length of array int n = arr.size(); // Sort all jobs according to decreasing order of // profit Collections.sort(arr,(a, b) ->b.profit - a.profit); // To keep track of free time slots boolean result[] = new boolean[t]; // To store result (Sequence of jobs) char job[] = new char[t]; // Iterate through all given jobs for (int i = 0; i < n; i++) < // Find a free slot for this job (Note that we // start from the last possible slot) for (int j = Math.min(t - 1, arr.get(i).deadline - 1); j >= 0; j--) < // Free slot found if (result[j] == false) < result[j] = true; job[j] = arr.get(i).id; break; >> > // Print the sequence for (char jb : job) System.out.print(jb + " "); System.out.println(); > // Driver code public static void main(String args[]) < ArrayListarr = new ArrayList(); arr.add(new Job('a', 2, 100)); arr.add(new Job('b', 2, 20)); arr.add(new Job('c', 1, 40)); arr.add(new Job('d', 3, 35)); arr.add(new Job('e', 1, 25)); // Function call System.out.println("Following is maximum profit sequence of Jobs: "); Job job = new Job(); // Calling function job.printJobScheduling(arr, 3); > >

Output

Following is maximum profit sequence of Jobs: c a d
arr = [ ['a', 2, 100], ['b', 2, 20], ['c', 1, 40], ['d', 3, 35], ['e', 1, 25] ] print("Following is maximum profit sequence of Jobs: ") # length of array n = len(arr) t = 3 # Sort all jobs according to # decreasing order of profit for i in range(n): for j in range(n - 1 - i): if arr[j][2] < arr[j + 1][2]: arr[j], arr[j + 1] = arr[j + 1], arr[j] # To keep track of free time slots result = [False] * t # To store result (Sequence of jobs) job = ['-1'] * t # Iterate through all given jobs for i in range(len(arr)): # Find a free slot for this job # (Note that we start from the # last possible slot) for j in range(min(t - 1, arr[i][1] - 1), -1, -1): # Free slot found if result[j] is False: result[j] = True job[j] = arr[i][0] break # print the sequence print(job)

Output

Following is maximum profit sequence of Jobs: ['c', 'a', 'd']