Job Sequencing with Deadline

Problem Statement

The job sequencing problem aims to find a sequence of jobs completed within their deadlines and gives maximum profit.

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

n = 5

Suppose we have a machine which requires 1 unit of time. We have to do jobs within the deadline so that the profits can be maximized. So, it is a maximization or optimization problem. We can/have to use the greedy method.

• The maximum deadline is 3 hours/unit. So, customers can wait max 3 hours for their job.
• J3 is not selected as the customer can wait 1 hour, but J2 already occupies the slot
• J5 is rejected as no available slots are there
• Maximum profit will be 40, and the selected job J1, J2, J4

Do it yourself