Job sequencing with deadlines | Greedy method

Greedy method Application Job sequencing with deadlines

Job sequencing with deadlines

Sequencing jobs on a single processor with deadline constraints is called Job sequencing with deadlines.
We give you a set of jobs.

  • Each job has a defined deadline and a certain benefit/profit is associated with it.
  • We get Profit For a job only when the particular job is completed within the deadline
  • A single processor is available to handle all jobs.
  • The processor takes a unit of time to complete a job.

The Problem is stated as follows:
There are n jobs let us say S={1, 2, …, n} and each job i has a deadline di >= 0 and a profit pi >= 0. We need one unit of time to process each job and we can do at most one job each time. We can earn the profit pi if job i is completed by its deadline but only one machine is available for processing. A feasible solution is a subset of jobs J, such that each job in the subset is completed by its deadline gaining a profit pi. An optimal solution is a feasible solution that maximizes total profit

Example: n=4, (p1, p2, p3, p4)=(100,10,15,27), (d1, d2, d3, d4)=(2,1,2,1)

Different feasible solution with the sequencing of jobs and total profit are given below:

   Feasible Solution     processing sequence value
1. (1, 2)        2, 1 110
2. (1, 3)        1, 3 or 3, 1 115
3. (1, 4)        4, 1 127 (optimal solution)
4. (2, 3)        2, 3 25
5. (3, 4)        4, 3 42

This is a trial and error method

Greedy approach is to sort pi into non-increasing order. After sorting p1 >= p2 >=…>= pi. Add the next job i to the solution set J if i can be completed by its deadline and that maximizes the total profit.


Job sequencing with deadlinesTotal Profit = 100 + 27 = 127. So this is an optimal solution.


An algorithm for solving Job sequencing with deadlines problem is given below:

Algorithm JS(d, n)
      // The jobs are ordered such that p[1]>=p[2]>= ... >=p[n].
     // J[i] is the ith job in the optimal solution, 1<=i<=k.
     d[0] := J[0] := 0; // Initialize. J[1] := 1; // Include job 1.
     k := 1;
    for (i:=2 to n) do
       // r is the position for i and check feasibility of insertion. 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
          // Insert i into J[].
          for ( q:=k to (r+1) step -1) do
            J[q+1] := J[q];
          J[r+1] := i; k:=K+1;
   return (k);



Example 2

JobID    Deadline           Profit/benifit
a1              4                              20
b1              1                              10
c1              1                              40
d1              1                             30

Output: Below sequence of jobs have maximum  profit
c1, a1


Example 3

JobID                 Deadline              Profit/benifit
a1                            2                                100
b1                             1                                 19
c1                             2                                 27
d1                             1                                 25
e1                             3                                15
Output: Below sequence of jobs have maximum  profit
c1, a1, e1


Time complexity of Job Sequencing algorithm is O(n2)


Topic : Job sequencing with deadlines | Greedy method


This Post Has 2 Comments

  1. M.Aruna


    1. ghgh

      M for what

Leave a Reply