Question 4:

(a) Job Sequencing with Deadlines using Greedy Method, find an optimal solution to the problem of job sequencing with Deadlines, where n = 4, (p₁, p₂, p₃, p₄) = (10, 1, 15, 7) and (d₁, d₂ d₃, d₄) = (1, 2, 1, 2). (10 marks)

Answer:

Solution 3 is optimal. In this solution only jobs 1 and 4 are processed and the value is 17. These jobs must be processed in the order job 4 followed by job 1. Thus the processing of job 4 begins at time zero and that of job 1 is completed at time 2.

To formulate a greedy algorithm to obtain an optimal solution. We must formulate an optimization measure to determine how the next job is choosen. As a fist attempt we can choose the objective function ? i € j Pi as our optimization measure. Using this measure, the next job to include is the one that increases ? i € j Pi the most, subject to the constraint that the resulting J is a feasible solution.

Read Full Post HERE

<< Previous Answer || Index Assignments ||