Effectiveness of definite schedule optimization under processing time variability: Experimental analysis of job shop scheduling

The scheduling problem is often treated as a combinatorial optimization problem based on the definite processing time. In real production systems, however, the processing time is not always definite. In this paper, assuming that a shop is operated on a schedule sequence predetermined based on estimated processing times, the actual required-time performance of a schedule which is optimal with respect to the estimated processing times, is analyzed under the condition that the actual processing times fluctuate randomly around the estimated values. Extensive experimental results show that (1) finding and following the optimal or near-optimal schedule with respect to estimated times is meaningful enough to justify the schedule optimization, (2) even though the variability of processing times increases, the relative precision performance of schedules can deteriorate only a little linearly, whereas the associated precision worsens very quickly.