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 iff job is completed by deadline. To complete a job one has to process a job for one unit of time. Our aim is to find 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}

Final solution is J={1,4} with total profit 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 outer for loop is O(k). Thus time complexity is O(n^2) .