FOR FREE MATERIALS
Job sequencing with deadline (Greedy Algorithm)
Back to ProgrammingDescription
Overview:
Job Sequencing problem:Given a set of jobs N to be processed on a machine where each job i ∈ N has a profit pi ≥ 0and deadline di≥ 0. Given each job takes an unit time for processing,pi is earned if it is processed before its deadline di . The objective is to find an optimal sequence of jobs such that it gives maximum profit within a given time T.
Greedy Algorithm: An algorithm paradigm that generates a solution by selecting local optimal solutions at each step i.e. it selects the best alternative solution at each step.
Greedy Approach to Job sequencing problem:The set of jobs are sorted in descending order of their profit. For each job n i, a unit of time slot t is given for processing such that tis empty, t≤ di and t is maximum.
Procedure:
Consider the following set of jobs and their associated profit and deadline in the table below,
Next, the jobs are sorted in descending order of their profit in the table below.
Consider a time slot of 4 units with each unit divided into separate slots as shown below. The jobs will be scheduled in these slots which are initially empty.
From Table 2, we see that j1 has a deadline dj1= 2 so it is scheduled in Time slot 2 as it is the maximum possible free time slot for j1 as shown below,
Next, j4 has a deadline dj4= 1of 1 so it is scheduled in Time slot 1 as shown below,
Remaining job j3 and j4 all have their deadline passed. So they can’t be scheduled. Hence, the optimal sequence of jobs: j4 -> j1 with a total profit of dj4+ dj1= 100 + 27 = 127.
Algorithm
Algorithm:
Input:
1. An array of Jobs consisting of Job ID, Deadline & Profit.
Output:
1. Displays the Job IDs of the jobs in the order of sequencing.
Algo:
Step 1: Start <=
Step 2: Define user defined structure Job with jobID, deadline & profit
Step 3: Defining the Sort function
void sort(struct Job job[], int jobSize
for i = 0 to i < (jobSize-1) repeat
for j = 0 to j < (jobSize-i-1) repeat
Check if(job[j+1].profit > job[j].profit)
Set temp <= job[j+1]
Set job[j+1] <= job [j]
Set job[j] <= temp
Step 4: Defining displayScheduledjobs function
void displayScheduledJobs(struct Job job[], int timeSlot[])
for i = 0 to i < slotSize repeat
Check if(timeSlot[i] ≠ -1)
Display job[timeslot[i]].jobID
Step 5: Defining scheduleJobs function
void scheduleJobs(struct Job job[], int jobSize, int timeSlot[])
Set countTimeSlot <= 0
for i = 0 to i < slotSize repeat
Set timeSlot[i] <= -1
for i = 0 to i < jobSize repeat
Check if(slotSize < job[i].deadline)
Set min <= slotSize
Otherwise
Set min <= job[i].deadline
for j = (min-1) to j <= 0 repeat
Check if(timeSlot[j] == -1)
Set timeSlot[j] <= i
countTimeSlot <= countTimeSlot + 1
break
Check if(countTimeSlot = slotSize)
break
Step 6: Defining main function
Display “"Enter the number of jobs”
Read jobSize
Set Job job[jobSize] = null
Display “"Enter the time slot size”
Read slotSize
Set timeSlot[slotSize] = null
call sort(job, jobSize);
call scheduleJobs(job, jobSize, timeSlot);
call displayScheduledJobs(job, timeSlot);
Step 7: Stop
Code
Characteristics of Job sequencing problem with deadline:
● It requires the jobs to be sorted in descending order of profit.
● It requires an extra space for storing the scheduled jobs and hence, its space complexity is O(n) where n is the size of the array in which it is stored
● The algorithm follows greedy algorithm paradigm
Application:
Sequencing jobs on a uniprocessor system with deadline constraints is an application of job sequencing with deadline problem.
Advantage:
● The solution to the Job sequencing problem follows a greedy algorithm paradigm which makes it easier to implement than other paradigms such as dynamic programming or divide and conquer.
Disadvantage:
● The jobs must be sorted in descending order of their profit which may increase the additional computational time.
Complexity:
Time Complexity:
For every job in the job array we are iterating the timeSlot array to find the free time slot. Hence, the time complexity is O(nm) where n is the number of jobs and m is the time slot size. If m = n, we have the time complexity as O(n2). Sorting the job array takes O(n2) time. Hence, the total time complexity is O(n2). Sorting can be further optimized by using Quick sort to make it O(nlogn), but the overall time complexity remains O(n2).
Space Complexity:
The scheduled jobs’s indexes are stored in an array which is the extra space required in the algorithm. Hence, the space complexity is O(n) where n is the size of the array in which it is stored.
