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