JOB SEQUENCING PROBLEM

 

What is Job Sequencing Problem

Job scheduling algorithm is applied to schedule the jobs on a single processor to maximize the profits.

The greedy approach of the job scheduling algorithm states that, “Given ‘n’ number of jobs with a starting time and ending time, they need to be scheduled in such a way that maximum profit is received within the maximum deadline”.

Job Sequencing Algorithm

Set of jobs with deadlines and profits are taken as an input with the job scheduling algorithm and scheduled subset of jobs with maximum profit are obtained as the final output.

Algorithm

 

Step1 −  Find the maximum deadline value from the input set of jobs.

Step2 −  Once, the deadline is decided, arrange the jobs in descending order of their profits.

Step3 −  Selects the jobs with highest profits, their time periods not exceeding the maximum deadline.

Step4 −  The selected set of jobs are the output.

EXAMPLE

 

Consider the following tasks with their deadlines and profits. Schedule the tasks in such a way that they produce maximum profit after being executed –

SR. NO	1	2	3	4	5
JOB	J1	J2	J3	J4	J5
DEADLINE	2	2	1	3	4
PROFIT	20	60	40	100	80

 

STEP 1

Find the maximum deadline value, dm, from the deadlines given.

dm=4

STEP 2

Arrange the jobs in descending order of their profits.

SR. NO	1	2	3	4	5
JOB	J4	J5	J2	J3	J1
DEADLINE	3	4	2	1	2
PROFIT	100	80	60	40	20

The maximum deadline, d_m, is 4. Therefore, all the tasks must end before 4.

Choose the job with highest profit, J4. It takes up 3 parts of the maximum deadline.

Therefore, the next job must have the time period 1.

STEP 3

The next job with highest profit is J5. But the time taken by J5 is 4, which exceeds the deadline by 3. Therefore, it cannot be added to the output set.

STEP 4

The next job with highest profit is J2. The time taken by J5 is 2, which also exceeds the deadline by 1. Therefore, it cannot be added to the output set.

STEP 5

The next job with higher profit is J3. The time taken by J3 is 1, which does not exceed the given deadline. Therefore, J3 is added to the output set.

TOTAL PROFIT- 100+400=140

STEP 6

Since, the maximum deadline is met, the algorithm comes to an end. 

The output set of jobs scheduled within the deadline are {J4, J3} with the maximum profit of 140. 

 Submitted BY:  Name : Pranav Kale (Se Ai) 

 Roll No-49