Job sequencing with deadlines-
The sequencing of jobs on a single processor with deadline constraints is named as job sequencing with deadlines.
You are given a set of jobs where each job has a defined deadline and some profit associated with it. The profit of that job is given only when that job is completed within its deadline.
The problem is-
“How can the total profit be maximized if only one job can be completed at a time?”
- Only one processor is available for processing all jobs.
- Processor takes one unit of time to complete a job.
- All the jobs have to be completed within their respective deadlines to obtain the profits associated with them.
For the given problem,
- A feasible solution would be a subset of jobs where each job of the subset gets completed within its deadline.
- Value of the feasible solution would be the sum of profits of all the jobs contained in the subset.
- An optimal solution of the problem would be a feasible solution which gives the maximum profit.
Job Sequencing with deadlines Greedy Algorithm-
We adopt a greedy algorithm to determine how the next job is selected for an optimal solution. The greedy algorithm described below always gives an optimal solution to the job sequencing problem.
Sort all the given jobs in the decreasing order of their profits.
Check the value of maximum deadline. Then, draw a Gantt chart where maximum time on Gantt chart is the value of maximum deadline.
Pick up the jobs one by one and then put them on the Gantt chart as far as possible from 0 (starting point) such that the job gets completed before its deadline.
The following practice problem illustrates these steps in detail.
PRACTICE PROBLEM BASED ON JOB SEQUENCING WITH DEADLINES
Given the following jobs, their deadlines and associated profits as shown-
Answer the following questions-
- Write the optimal schedule that gives maximum profit.
- Are all the jobs completed in the optimal schedule?
- What is the maximum earned profit?
Sort all the given jobs in the decreasing order of their profits-
Value of maximum deadline = 5
So, draw a Gantt chart with maximum time on Gantt chart = 5 units as shown-
Now, we will take each job one by one in the order they appear in step-01 and place them on Gantt chart as far as possible from 0 (starting point)
- First, we take job J4.
- Since, its deadline is 2, so we place it in the first empty cell before deadline 2 as-
- Now, we take job J1.
- Since, its deadline is 5, so we place it in the first empty cell before deadline 5 as-
- Now, we take job J3.
- Since, its deadline is 3, so we place it in the first empty cell before deadline 3 as-
- Now, we take job J2.
- Since, its deadline is 3, so we place it in the first empty cell before deadline 3.
- Since, the second and third cells are already filled, so we place job J2 in the first cell as-
- Now, we take job J5.
- Since, its deadline is 4, so we place it in the first empty cell before deadline 4 as-
- The only job left is job J6 whose deadline is 2.
- All the slots before deadline 2 are already occupied.
- Thus, job J6 can not be completed.
Now, the given questions may be answered as-
The optimal schedule is-
J2 , J4 , J3 , J5 , J1
This is the required order in which the jobs must be completed in order to obtain the maximum profit.
- All the jobs are not completed in the optimal schedule.
- This is because job J6 could not be completed within its deadline.
Maximum earned profit
= Sum of profits of all jobs in optimal schedule
= Profit of job J2 + Profit of job J4 + Profit of job J3 + Profit of job J5 + Profit of job J1
= 180 + 300 + 190 + 120 + 200
= 990 units
Get more notes and other study material of Design and Analysis of Algorithms (DAA).
Watch video lectures by visiting our YouTube channel LearnVidFun.