97-19
On the Calculation of the Stability Radius of an Optimal or an Approximate Schedule
by Sotskov, Y.N.; Wagelmans, A.P.M.; Werner, F.
Preprint series: 97-19, Preprints
The paper is published: Annals of Operations Research 83, 1998, 213 - 252.
Abstract: bility analysis for scheduling problems. In spite of impressive theoretical results in sequencing and scheduling, up to now the implementation of scheduling al- gorithms with a rather deep mathematical background in production planning, scheduling and control, and in other real-life problems with sequencing aspects is limited. In classical scheduling theory, mainly deterministic systems are con- sidered and the processing times of all operations are supposed to be given in advance. 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, errors within the practical realization of a schedule, machine breakdowns, additional jobs 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 prac- tical use. Computational results on the calculation of the stability radius for randomly generated job shop scheduling problems are presented. The extreme values of the stability radius are considered in more detail. The new results are amply illustrated with examples.
Keywords: Stability, Scheduling, Disjunctive graph, Linear binary programming
Notes: Supported by Deutsche Forschungsgemeinschaft (Project ScheMA) and by INTAS(Project 93-257)
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.