Zurück zu den Preprints des Jahres 1996


1996-22

Stability Radius of an Optimal Schedule: a Survey and Recent Developments

by Sotskov, Y.N., Tanaev, V.S., Werner, F..


Series: 1996-22, Preprints

MSC:
90B35 Scheduling theory, deterministic

Abstract:
The usual assumption that the processing times of the operations
are known in advance is the strictest one in deterministic scheduling
theory and it essentially restricts its practical aspects. Indeed, this
assumption is not valid for the most real-world processes. This sur-
vey is devoted to a stability analysis of an optimal schedule which
may help to extend the significance of scheduling theory for some
production scheduling problems. The terms 'stability', 'sensitivity' or
'postoptimal analysis' are generally used for the phase of an algorithm
at which a solution (or solutions) of an optimization problem has al-
ready been found, and additional calculations are performed in order
to investigate how this solution depends on the problem data. We
survey some recent results in the calculation of the stability radius of
an optimal schedule for a general shop scheduling problem which de-
notes the largest quantity of independent variations of the processing
times of the operations such that this schedule remains optimal. We
present formulas for the calculation of the stability radius, when the
objective is to minimize mean or maximum flow time. The extreme
values of the stability radius are of particular importance, and these
cases are considered more in detail. Moreover, computational results
on the calculation of the stability radius for randomly generated job
shop scheduling problems are briefly discussed. We also show that the
well-known test problem with 6 jobs and 6 machines has both stable
and unstable optimal makespan schedules.

Keywords:
shop scheduling, optimal schedule, stability analysis, sensitivity

This paper was published in:
Industrial Applications of Combinatorial