Proble We shall consider a set J of jobs where each job j has a duration DG) and

Question

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

Explanation / Answer

1.

Strategy 1- Consider 3 jobs a, b and c, where-

P(a) = 10

D(a) = 8

P(b) = 3

D(b) = 2

P(c) = 1

D(c) = 1

Now according to strategy 1 (S1) we have the job scheduled in the order :

abc

which makes C(S1) = 10*8 + 3(8+2) + 1(8+2+1) = 121

Strategy 2- Consider 3 jobs a, b and c, where-

P(a) = 10

D(a) = 8

P(b) = 3

D(b) = 2

P(c) = 1

D(c) = 1

Now according to strategy 2 (S2) we have the job scheduled in the order :

cba

which makes C(S2) = 1*1 + 3(1+2) + 10(1+2+8) = 120

Strategy 3- Consider 3 jobs a, b and c, where-

P(a) = 10

D(a) = 8

P(b) = 3

D(b) = 2

P(c) = 1

D(c) = 1

Now according to strategy 3 (S3) we have the job scheduled in the order :

abc

which makes C(S3) = 10*8 + 3(8+2) + 1(8+2+1) = 121

Strategy 4- Consider 3 jobs a, b and c, where-

P(a) = 10

D(a) = 8

P(b) = 3

D(b) = 2

P(c) = 1

D(c) = 1

Now according to strategy 4 (S4) we have the job scheduled in the order :

bac

which makes C(S3) = 3(2) + 10(2+8) + 1(2+8+1) = 117

---

So, we can see that the strategy 1, strategy 2 and strategy 3 don't produce an optimal schedule but strategy 4 does.

----------------------------------------------------------

2. (a)

If R(i) > R(k), let us take both conditions, when i is executed before k and when k is executed defore i.

when i is executed before k:

C(S1) = P(i)*D(i) + P(k)*(D(i)+D(k))

= P(i)*D(i) + P(k)*D(i) + P(k)*D(k)

( dividing the equation by D(i)*D(k) )

=R(i)*D(i)/D(k) + R(k) + R(k)*D(k)/D(i)     --> eqn 1

when k is executed defore i:

C(S2) = P(k)*D(k) + P(i)*(D(k)+D(i))

= P(k)*D(k) + P(i)*D(k) + P(i)*D(i)

( dividing the equation by D(i)*D(k) )

=R(k)*D(k)/D(i) + R(i) + R(i)*D(i)/D(k)     --> eqn 2

Comparing the two equations we can see that they differ by only one term-

R(i) vs R(k)

since R(i) > R(k)

So, C(S1) < C(S2).

And if R(i) = R(k), then both C(S1) and C(S2) are optimal.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.