95-23
On the Calculation of the Stability Radius of an Optimal or an Approximate Schedule
Preprint series: 95-23, Preprints
The paper is published: Annals of Operations Research 83, 1998, 213 - 252.
Abstract: The main objective of this paper is to stimulate interest in stability analysisfor scheduling problems. Inspite of impressive theoretical results in sequencingand scheduling, the implementation of scheduling algorithms with a ratherdeep mathematical background in production planning, scheduling and inother real-life sequencing problems is up to now limited. In scheduling theory,deterministic systems are mainly considered and so the processing times of alloperations are supposed to be given in advance. Unfortunately, such problemsdo not often arise in practice. Even if the processing times are known beforeapplying a scheduling procedure, OR workers are forced to take into accountthe precision of equipment, which is used to calculate the processing times,round-off errors in the calculation of a schedule on the computer, possibleerrors within the practical realization of a schedule, machine breakdowns,additionally arriving jobs with high priorities and so on. This paper is devotedto the calculation of the stability radius of an optimal or an approximateschedule. We survey some recent results in this field and derive new results inorder to make this approach more suitable for a practical use. Moreover, firstcomputational results on the calculation of the stability radius for randomlygenerated job shop scheduling problems are presented. Since the extremevalues of the stability radius are of particular importance for applications,we consider these cases more in detail. At the end of the paper some openquestions and trends of stability analysis in scheduling theory are discussed.
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.