by Sotskov, Y. N., Werner, F..

**Series:** 1995-23, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic

**Abstract:**

The main objective of this paper is to stimulate interest in stability analysis

for scheduling problems. Inspite of impressive theoretical results in sequencing

and scheduling, the implementation of scheduling algorithms with a rather

deep mathematical background in production planning, scheduling and in

other real-life sequencing problems is up to now limited. In scheduling theory,

deterministic systems are mainly considered and so the processing times of all

operations are supposed to be given in advance. Unfortunately, such problems

do not often arise in practice. Even if the processing times are known before

applying a scheduling procedure, OR workers are forced to take into account

the precision of equipment, which is used to calculate the processing times,

round-off errors in the calculation of a schedule on the computer, possible

errors within the practical realization of a schedule, machine breakdowns,

additionally arriving jobs with high priorities and so on. This paper is devoted

to the calculation of the stability radius of an optimal or an approximate

schedule. We survey some recent results in this field and derive new results in

order to make this approach more suitable for a practical use. Moreover, first

computational results on the calculation of the stability radius for randomly

generated job shop scheduling problems are presented. Since the extreme

values of the stability radius are of particular importance for applications,

we consider these cases more in detail. At the end of the paper some open

questions and trends of stability analysis in scheduling theory are discussed.

**Keywords:**

**This paper was published in:**

Annals of Operations Research 83, 1998, 213 - 252.