Number 2

Proble We shall consider a set J of jobs where each job j has a duration DG) and a priority PG), both>0. Only one job can be executed at a time, and once a job j has started (at time t) it will be finished (at time t + D(j). Example: ifj1 is the first Job to run and J2 ?s the second. J1 will finish at time D0) and j will finish at time DD(2) For a given schedule S, let Fs) denote the time at which job j finishes according to S. Our goal is to find a schedule that minimizes C(S)-PG) FsG) jEJ We shall consider the following four strategies, all potentially non-deterministic 1. Schedule the jos in decreasing order of their priority, that is: for all i,k EJ, if P(i)>P(k) then job i must execute before job k 2. Schedule the jobs in increasing order of their duration, that is for al i,kEJ,if DO) R(k) then job i must execute before job k Your task is: 1. (15p) For each of the strategies (1-3) above, find an example where that strategy does not produce an optimal schedule, but strategy 4 does. 2. We shall now argue, in a sequence of steps, that strategy 4 is indeed optimal. (a) 10p) First assume there are only two jobs, i and k. Prove that if Ri) R(k) then it is best to execute i before k. and that if R(i) = R(k) it doesn't matter which job we execute first (b) (p) Now prove that a schedule that can not have been produced by strategy 4 is not optimal. Hint: consider such a schedule and show that it can be improved by swapping two jobs. (c) (5p) Finally, prove that al schedules produced by strategy 4 are optimal