## 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 proﬁt. For any job i proﬁt 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 ﬁnd feasible subset of jobs such that proﬁt 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) .

## 0 Comments

Subscribe Us and Thanks for visiting blog.