Job Sequencing With Deadlines

The sequencing of jobs on a single processor with deadline constraints is called as Job Sequencing with Deadlines.

Here-

You are given a set of jobs.
Each job has a defined deadline and some profit associated with it.
The profit of a job is given only when that job is completed within its deadline.
Only one processor is available for processing all the jobs.
Processor takes one unit of time to complete a job.

The problem states-

“How can the total profit be maximized if only one job can be completed at a time?”

Approach to Solution-

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 profit of all the jobs contained in the subset.
An optimal solution of the problem would be a feasible solution which gives the maximum profit.

Greedy Algorithm is adopted 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-

Check the value of maximum deadline.
Draw a Gantt chart where maximum time on Gantt chart is the value of maximum deadline.

Pick up the jobs one by one.
Put the job on Gantt chart as far as possible from 0 ensuring that the job gets completed before its deadline.

Consider the following 5 jobs and their associated deadline and profit.

Note! If two or more jobs are having the same profit then sort them as per their entry in the job list.

Looking at the jobs we can say the max deadline value is 3.
So, dmax = 3

As dmax = 3 so we will have THREE slots to keep track of free time slots. Set the time slot status to EMPTY

Total number of jobs is 5.
So we can write n = 5

Note!

If we look at job j2, it has a deadline 1. This means we have to complete job j2 in time slot 1 if we want to earn its profit.

Similarly, if we look at job j1 it has a deadline 2. This means we have to complete job j1 on or before time slot 2 in order to earn its profit.

Similarly, if we look at job j3 it has a deadline 3. This means we have to complete job j3 on or before time slot 3 in order to earn its profit.

time slot	1	2	3
status	j2 (D =1 , P =100)	j1 ( D = 2 P = 60)	j3 (D = 3 P= 20)

Maximum earned profit

= Sum of profit of all the jobs in optimal schedule

= Profit of job J2 + Profit of job J1 + Profit of job J3

= 100 + 60+ 20

= 180units