1. he Job sequencing problem states as follows:

   • There are ‘n’ jobs to be processed on a machine

   • Each job ‘i’ has a deadline di ≥ 0 and profit pi ≥ 0.

   • Profit is earned if & only if the job is completed by its deadline.

• The job is completed if it is processed on a machine for unit time.

• Only one machine is available for processing jobs.

• Only one job is processed at a time on the machine.

• A feasible solution is a subset of jobs J such that each job is completed by its deadline.

• An optimal solution is a feasible solution with maximum profit value.

Example:

Let n = 4, (p1,p2,p3,p4) = (100,10,15,27), (d1,d2,d3,d4) = (2,1,2,1) The feasible solution and their values are given below.

Consider the jobs in the non-increasing order of profits subject to the constraint that the resulting job sequence J is a feasible solution.

In the example considered before, the non-increasing profit vector is

i. Now we start adding the job with J = 0 and Σ i ej Pi= 0.

ii. Job 1 is added to J as it has the largest profit and thusJ = {1} is a feasible one.

iii. Now job 4 is considered. The solution J = {1, 4} is a feasible one with processing sequence (4, 1).

iv. The next job, Job 3 is considered & it is discarded as J = {1, 3, 4} is not feasible.

v. Finally, job 2 is added into J and it is discarded as J = {1, 2, 4} is not feasible.

vi. Thus we have J = {1, 4} is optimal solution with value 127.’

[Note: If this question is asked for 10 marks then write algorithm also.]

Algorithm:-

Algorithm Job_seq (d, 1, n)

{

d [0] = 0;

JS [1] = 1;

i = 1;

for j= 2 to n do;

{

k = i;

while ((d[JS[k] > d[j]]) and (d[JS[k]] != k)) do

k = k -1;

if ((d[JS[k] < d[j]]) and (d[j] > k)) then

{

For m= i to (k+1) step-1 do

JS [m+1] = JS [m];

JS [K+1] = j;

i = i+1;

}

} Return i;

It is established that the computing time of job sequencing can be reduced from O(n2)O(n2) to O (n).