What is meant by job sequencing?

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 Ji is di and the profit received from job Ji is pi. 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 di & 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 p1⩾p2⩾p3⩾...⩾pn.

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

J1

J2

J3

J4

J5

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

J2

J4

J1

J5

J3

Deadline

1

2

2

3

1

Profit

100

60

40

20

20

From the given set of jobs, first, we select J2, as it should be completed within its deadline and contributes maximum profit.

  • Next, J4 is selected as it gives more profit than J1.
  • J1 cannot be selected in the next clock as its deadline is over. Hence J5 is selected as it executes within its deadline.
  • Job J3 is discarded as it should not be executed within its deadline.

Therefore, the sequence of jobs (J2, J4, J5) 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

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-

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-

Step-01:

  • Sort all the given jobs in decreasing order of their profit.

Step-02:

  • Check the value of maximum deadline.
  • 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.
  • Put the job on Gantt chart as far as possible from 0 ensuring that the job gets completed before its deadline.

PRACTICE PROBLEM BASED ON JOB SEQUENCING WITH DEADLINES-

Problem-

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

  1. Write the optimal schedule that gives maximum profit.
  2. Are all the jobs completed in the optimal schedule?
  3. What is the maximum earned profit?

Solution-

Step-01:

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

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-

What is meant by job sequencing?

Now,

  • We take each job one by one in the order they appear in Step-01.
  • We place the job on Gantt chart as far as possible from 0.

Step-03:

  • We take job J4.
  • Since its deadline is 2, so we place it in the first empty cell before deadline 2 as-

What is meant by job sequencing?

Step-04:

  • We take job J1.
  • Since its deadline is 5, so we place it in the first empty cell before deadline 5 as-

What is meant by job sequencing?

Step-05:

  • We take job J3.
  • Since its deadline is 3, so we place it in the first empty cell before deadline 3 as-

What is meant by job sequencing?

Step-06:

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

What is meant by job sequencing?

Step-07:

  • Now, we take job J5.
  • Since its deadline is 4, so we place it in the first empty cell before deadline 4 as-

What is meant by job sequencing?

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 optimal schedule.
  • This is because job J6 could not be completed within its deadline.

Part-03:

Maximum earned profit

= Sum of profit of all the 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

To gain better understanding about Job Sequencing With Deadlines,

Watch this Video Lecture

Next Article- Huffman Coding

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary

What is meant by job sequencing?

Article Name

Job Sequencing With Deadlines | Algorithm | Example

Description

Job Sequencing with Deadlines- The sequencing of jobs on a single processor with deadline constraints is called as Job Sequencing with Deadlines. Greedy Algorithm is adopted to solve this problem. Job Sequencing with Deadlines Example.

Author

Akshay Singhal

Publisher Name

Gate Vidyalay

Publisher Logo

What is meant by job sequencing?

What is job sequencing with example?

The sequencing of jobs on a single processor with deadline constraints is called as Job Sequencing with Deadlines. 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.

What is job sequencing in operating system?

Job scheduling is the process of allocating system resources to many different tasks by an operating system (OS). The system handles prioritized job queues that are awaiting CPU time and it should determine which job to be taken from which queue and the amount of time to be allocated for the job.

What is job scheduling and job sequencing?

Sequencing is the order of tasks to be done in chain. Hence the next task is started once the previous one is completed. Scheduling, on the other hand is the process in which people are assigned to time to accomplish different tasks. It improves the delivery performance and reduces the manufacturing time and cost.

What is job sequencing in optimization techniques?

The job sequencing technique is used to determine an optimal sequence. It performs a series of jobs by a number of specific orders so that it calculates the optimal cost. In this paper, we propose a novel approach to find an optimal path from source to destination by taking advantage of job sequencing technique.