96-22
Stability Radius of an Optimal Schedule: a Survey and Recent Developments
by Sotskov, Y.N.; Tanaev, V.S.; Werner, F.
Preprint series: 96-22, Preprints
The paper is published: Industrial Applications of Combinatorial Optimization (edited by G. Yu), \rKluwer Academic Publishers, 16, 1998, 72 - 108.
Abstract: The usual assumption that the processing times of the operationsare known in advance is the strictest one in deterministic schedulingtheory and it essentially restricts its practical aspects. Indeed, thisassumption is not valid for the most real-world processes. This sur-vey is devoted to a stability analysis of an optimal schedule whichmay help to extend the significance of scheduling theory for someproduction scheduling problems. The terms \'stability\', \'sensitivity\' or\'postoptimal analysis\' are generally used for the phase of an algorithmat which a solution (or solutions) of an optimization problem has al-ready been found, and additional calculations are performed in orderto investigate how this solution depends on the problem data. Wesurvey some recent results in the calculation of the stability radius ofan optimal schedule for a general shop scheduling problem which de-notes the largest quantity of independent variations of the processingtimes of the operations such that this schedule remains optimal. Wepresent formulas for the calculation of the stability radius, when theobjective is to minimize mean or maximum flow time. The extremevalues of the stability radius are of particular importance, and thesecases are considered more in detail. Moreover, computational resultson the calculation of the stability radius for randomly generated jobshop scheduling problems are briefly discussed. We also show that thewell-known test problem with 6 jobs and 6 machines has both stableand unstable optimal makespan schedules.
Keywords: shop scheduling, optimal schedule, stability analysis, sensitivity
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.