Job Sequencing with Deadline | DAA

Job Sequencing with Deadline

We are given a set of n jobs. Associated with each job I, di>=0 is an integer deadline and pi>=O is profit. For any job i profit is earned if the job is completed by the deadline. To complete a job one has to process a job for one unit of time. Our aim is to find a feasible subset of jobs such that profit is maximum.

Example

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

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

We have to try all the possibilities, complexity is O(n!). Greedy strategy using total profit as optimization function to above example. Begin with J=

• Job 1 considered, and added to J ->J={1}
• Job 4 considered, and added to J -> J={1,4}
• Job 3 considered, but discarded because not feasible  ->J={1,4}
• Job 2 considered, but discarded because not feasible  -> J={1,4}

The final solution is J={1,4} with a total profit of 127 and it is optimal

Algorithm:

Assume the jobs are ordered such that p[1]>=p[2] >=…>=p[n]  d[i]>=1, 1<=i<=n are the deadlines, n>=1. The jobs n are ordered such that p[1]>=p[2]>=... >=p[n]. J[i] is the ith job in the optimal solution, 1<=i<=k. Also, at termination  d[J[i]]<=d[J[i+1]], 1<=i

JobSequencing(int d[], int j[], int n)
{
    d[0] = J[0] = 0; // Initialize.
    J[1] = 1; // Include job 1.
    int k = 1;
    for (int i = 2; i <= n; i++)
    { // Consider jobs in nonincreasing order of p[i]. Find position for i and 
         check feasibility of insertion.
        int r = k;
        while ((d[J[r]] > d[i]) && (d[J[r]] != r))
            r--;
        if ((d[J[r]] <= d[i]) && (d[i] > r))
        { // Insert i into J[].
            for (int q = k; q >= (r + 1); q--)
                J[q + 1] = J[q];
            J[r + 1] = i;
            k++;
        }
    }
    return (k);
}

Analysis

For loop executes O(n) line. While loop inside the for loop executes at most times and if the condition given inside if statement is true inner for loop executes O(k-r) times.  Hence total time for each iteration of the outer for loop is O(k). Thus time complexity is O(n^2).