What is Job Sequencing with Deadlines?
In a job sequencing with deadlines problem, the objective is to find a sequence of jobs completed within their deadlines, giving a maximum profit. Let us consider the set of n given jobs associated with deadlines, and profit is earned if a job is completed by its deadline. These jobs need to be ordered so that the maximum profit is earned.
It may happen that all the given jobs can not be completed within their deadlines. Assume that the deadline of ith job J_{i} is d_{i} and the profit received from job J_{i} is p_{i}. Hence, the optimal solution of job sequencing with deadlines algorithm is a feasible solution with maximum profit.
Points to Remember for Job Sequencing with Deadlines
- Each job has deadline d_{i} & it can process the job within its deadline; only one job can be processed at a time.
- Only one CPU is available for processing all jobs.
- CPU can take only one unit at a time for processing any job.
- All jobs arrived at the same time.
Job Sequencing with Deadlines Algorithm
Suppose there are jobs J(i) with the deadline D(i) and profit P(i) where 0≤i≤1. These jobs are ordered according to profit p_{1}⩾p_{2}⩾p_{3}⩾...⩾p_{n}.
Job-Sequencing-With-Deadline (D, J, n, k)
D(0) := J(0) := 0
k:= 1
J(1) := 1 // means first job is selected
for i = 2 … n do
r:= k
while D(J(r)) > D(i) and D(J(r)) ≠ r do
r:= r – 1
if D(J(r)) ≤ D(i) and D(i) > r then
for l = k … r + 1 by -1 do
J(l + 1): = J(l)
J(r + 1): = i
k:= k + 1
Job Sequencing with Deadlines Example
Let us consider a given job sequencing problem, as shown in the table below. We have to find the sequence of jobs completed within their deadlines and give the maximum profit. Each job is associated with the deadline and profit as given below:
Job | J_{1} | J_{2} | J_{3} | J_{4} | J_{5} |
Deadline | 2 | 1 | 1 | 2 | 3 |
Profit | 40 | 100 | 20 | 60 | 20 |
The given jobs are sorted as per their profit in descending order to solve this problem. Hence, the jobs are ordered after sorting, as shown in the following table.
Job | J_{2} | J_{4} | J_{1} | J_{5} | J_{3} |
Deadline | 1 | 2 | 2 | 3 | 1 |
Profit | 100 | 60 | 40 | 20 | 20 |
From the given set of jobs, first, we select J_{2}, as it should be completed within its deadline and contributes maximum profit.
- Next, J_{4} is selected as it gives more profit than J_{1}.
- J_{1} cannot be selected in the next clock as its deadline is over. Hence J_{5} is selected as it executes within its deadline.
- Job J_{3} is discarded as it should not be executed within its deadline.
Therefore, the sequence of jobs (J_{2}, J_{4}, J_{5}) is executed within their deadline and gives the maximum profit.
The total profit of the sequence is 100 + 60 + 20 = 180.
Important GATE Topics | |
Moment Of Force | Structural Hazard |
Moment Arm | Electric Circuit |
What Is Multivibrator | Stability Of Structures |
Pn Junction Solar Cell | Dijkstra Algorithm |
BJT Amplifier | Support Reaction |
Comments
write a comment