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

Sr No. | Feasible Solution | Processing Time | Value |
---|---|---|---|

1. | (1,2) | 2,1 | 110 |

2. | (1,3) | 1,3 or 3,1 | 115 |

3. | (1,4) | 4,1 | 127 |

4. | (2,3) | 2,3 | 25 |

5. | (3,4) | 4,3 | 42 |

6. | (1) | 1 | 100 |

7. | (2) | 2 | 10 |

8. | (3) | 3 | 15 |

9. | (4) | 4 | 27 |

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

100 | 27 | 15 | 10 | 2 | 1 | 2 | 1 | |
---|---|---|---|---|---|---|---|---|

p1 | p4 | p3 | p2 | d1 | d4 | d3 | d2 |

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