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 d_i >= 0 and a profit p_i >= 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 p_i 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 p_i. 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:

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.

Total 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(n²)

Topic : Job sequencing with deadlines | Greedy method