1. The 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 (n^2)$ to O (n).