5.2. Consider P4 | prec Cmax with 12 jobs. jobs 1 2 3 45 6 7 8 9 10 11 12 P 10 1

Question

5.2. Consider P4 | prec Cmax with 12 jobs. jobs 1 2 3 45 6 7 8 9 10 11 12 P 10 10 10 12 11 10 12 12 10 10 10 10 The jobs are subject to the precedence constraints depicted in Figure 5.10. 10 5 12 Fig. 5.10 Precedence constraints graph (Exercise 5.2) Exercises 145 (a) Apply the generalized version of the CP rule: every time a machine is freed select the job at the head of the string with the largest total amount of processing (b) Apply the generalized version of the LNS rule: every time a machine is freed select the job that precedes the largest total amount of processing. (c) Is either one of these two schedules optimal?

Explanation / Answer

For the first machine we have 1,4 and 5 as independent jobs.

For the 2nd machine we have 7,8,9 as independent jobs.

a) For CP rule

So for first machine we start with 4(having highest time 12), then 5(having time 11) then we can choose either

1 or 6 (since 6 is dependent on 4,5) , then 6 (if 1 is choosen first) then 2 and then 3.

total time = (12+11+10+10+10+10)= 63

For the second machine we can start with 7 or 8(lets say 7) (having highest time 12) then choose 7(having highest time 12) ,

then we can choose 9 (having time 10) then choose each of 10,11,12 (each having time of 10)

so total time taken = (12+12+10+10+10+10)=64

b) LNS

For first machine we start with either of 1,4 or 5 (we will prefer 1 owing to its lowest time), then 2 (out of 2,4,5)

then 5 (out of 4,5) then 4 , followed by 3 and finally 6

For the second machine we have start with 9 (out of 7,8,9 we have 9 having lowest time 10) ,

then 8 (having time 12)

then 12 (out of 7,12 ; 12 prefered owing to lower time) then 7(having time 12) , then 10 (having time 10) and then

11 (having time 10).

c) The schedules optimality can only be compared when he process has a different start time and wait time can be associated.

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

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