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.


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)

Job Sequencing with Deadline

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


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))
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;
return (k);


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) .

Post a Comment