Stability of an optimal schedule in a job shop

This paper is devoted to the calculation of the stability radius of an optimal schedule for a job shop problem, when the objective is to minimize mean or maximum dow times. The approach used may be regarded as an a posteriori analysis, in which an optimal schedule has already been constructed and the question is to determine such changes in the processing times of operations as do not destroy the optimality of the schedule at hand. More precisely, the stability radius denotes the largest quantity of independent variations of the processing times of the operations such that an optimal schedule of the problem remains optimal. Although in scheduling theory mainly deterministic problems are considered and the processing times are supposed to be given in advance, such scheduling problems do not often arise in practice. Even if tbe processing times are known before applying a scheduling procedure, OR workers are forced to take into account possible changes and errors within the practical realization of a schedule, e.g. additionally arriving jobs, machine breakdowns, the precision of equipment which is used to calculate the processing times, and so on. In other words, usually in practice a schedule has to be realized under conditions of uncertainty. This paper investigates the influence of errors and possible changes of the processing times on the optimality of a schedule. To this end, extensive numerical experiments with randomly generated job shop scheduling problems are performed and discussed. The developed software provides the possibility of comparing the values of the stability radii, the numbers of optimal schedules and some other ''numbers'' for two often used criteria. The main question we try to answer is how Large the stability radius is, on average, for randomly generated job shop problems. (C) 1997 Elsevier Science Ltd.