Question: Write short notes on Job Sequencing with deadlines.
0

Subject: Analysis Of Algorithm

Topic: Greedy Method

Difficulty: High

aoa(14) • 8.9k views
 modified 21 months ago by awari.swati831 • 250 written 3.3 years ago by
1
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.

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