|
When we arrange schedule we want it to be a nondelay schedule. It means that these is no forced idleness. But there are some classes of nonpreemptive, nondelay schedules which may lead to some interesting and unexpected anomalies. Following example from Pinedo[1]: "Consider an instance of P2 | prec | Cmax with 10 jobs and the following processing times. | jobs | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | pj | 8 | 7 | 7 | 2 | 3 | 2 | 2 | 8 | 8 | 15 |
The jobs are subject to the precedence constraints depicted in Figure 1. The makespan of the nondelay schedule depicted in Figure 1 is 31 and the schedule is clearly optimal. One would expect that, if each one of the 10 processing times is reduced by one time unit, the makespan would be less than 31. However, requiring the schedule to be nondelay results in the schedule depicted in Figure 2 , with a makespan of 32. Suppose that now an additional machine is made available and that there are three machines instead of two. One would again expect that the makespan with the original processing times is less than 31. Again, the nondelay requirement has an unexpected effect. The makespan is 36." 
Figure 1 
Figure 2 Gantt charts of nondelay schedules: (a) original schedules which total schedule is 31, (b) processing times one unit less for each job and total schedule is 32 (c) three machines and original processing times result is 36. REFERENCE [1] Pinedo., M., Scheduling: Theory, Algorithms, and Systems (2nd Edition)
|