SEMINAIRES DU  GOTHA
			____________________

	vendredi 24 novembre à l'Université de Technologie de Troyes  à 10h00.

	Exposé de Yuri Sotskov

TITRE : 

Stability of Optimal Schedule

RESUME :

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
survey 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 already 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 denotes 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.