Job Sequencing with Deadlines

By Priyanshu Vaish|Updated : September 29th, 2022

Job Sequencing with Deadlines problem uses the greedy approach. So we have to find the best method/option in the greedy method out of many present ways. In this method/ approach, we focus on the first stage, decide the output, and don't think about the future.

Many optimization problems can be determined using the greedy algorithm. Some issues have no efficient solution, but the greedy algorithm may provide a solution close to optimal. Here, we will briefly see the Job sequencing with deadlines definition, algorithm, and example.

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 ForceStructural Hazard
Moment ArmElectric Circuit
What Is MultivibratorStability Of Structures
Pn Junction Solar CellDijkstra Algorithm
BJT AmplifierSupport Reaction

Comments

write a comment

FAQs on Job Sequencing with Deadlines

  • Job scheduling with deadlines is the problem of scheduling jobs out of a set of N jobs on a single processor, maximizing profit as much as possible. Consider N jobs, each taking unit time for execution. Each job has some profit and deadline associated with it.

  • A common job sequencing technique prioritizes jobs with the earliest need date. This can also be referred to as 'Due Date Assignment', and it places the high priority on processing jobs with early dues dates to complete all jobs on time.

  • No machine can process more than one operation at a time. Each operation, once started, must be performed till completion. A job is an entity, that is even though the job represents a lot of individual parts, no lot may be processed by more than one machine at a time.

  • Sequencing problems deal with selecting an optimum order for the number of jobs to perform with a finite number of facilities. The objective of sequencing is to determine the sequence of performing jobs to minimize the total cost/time.

  • The processing times on different machines are independent of the order of the job in which they are to be processed. Only one job can be processed on the given machine at a time. The time taken by the jobs moving from one machine to another is negligible and is taken as equal to zero.

Follow us for latest updates