Production Scheduling Portal
Your Gateway to Production Scheduling
 
Home arrow Scheduling Anomaly Thursday, 20 November 2008
Translate this page!
Main Menu
Scheduling Anomaly PDF Print E-mail
Written by Administrator   
Thursday, 07 December 2006

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. 

jobs12345678910
pj87723228815

  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."

 

Image

 

Figure 1

 

Image

 

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)

 

 

 

     
 
Production Scheduling Portal. © 2006 All rights reserved.