**Job sequencing with deadlines-**

The sequencing of jobs on a single processor with deadline constraints is named as **job s****equencing with deadlines**.

**Problem-**

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?”

**Constraints-**

- 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.

**Solution-**

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.

**Step-01:**

Sort all the given jobs in the decreasing order of their profits.

**Step-02:**

Check the value of maximum deadline. Then, draw a Gantt chart where maximum time on Gantt chart is the value of maximum deadline.

**Step-03:**

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**

**Problem-**

Given the following jobs, their deadlines and associated profits as shown-

Jobs | J1 | J2 | J3 | J4 | J5 | J6 |

Deadlines | 5 | 3 | 3 | 2 | 4 | 2 |

Profits | 200 | 180 | 190 | 300 | 120 | 100 |

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?

**Solution-**

**Step-01:**

Sort all the given jobs in the decreasing order of their profits-

Jobs | J4 | J1 | J3 | J2 | J5 | J6 |

Deadlines | 2 | 5 | 3 | 3 | 4 | 2 |

Profits | 300 | 200 | 190 | 180 | 120 | 100 |

**Step-02:**

Value of maximum deadline = 5

So, draw a Gantt chart with maximum time on Gantt chart = 5 units as shown-

**Step-03:**

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-

Now,

- 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-

**Part-01:**

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.

**Part-02:**

- All the jobs are not completed in the optimal schedule.
- This is because job J6 could not be completed within its deadline.

**Part-03:**

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**.