On the calculation of the stability radius of an optimal or an approximate schedule

On the calculation of the stability radius of an optimal or an approximate schedule

0.00 Avg rating0 Votes
Article ID: iaor19991178
Country: Netherlands
Volume: 83
Issue: 1
Start Page Number: 213
End Page Number: 252
Publication Date: Oct 1998
Journal: Annals of Operations Research
Authors: , ,
Keywords: programming: linear
Abstract:

The main objective of this paper is to stimulate interest in stability analysis for scheduling problems. In spite of impressive theoretical results in sequencing and scheduling, up to now the implementation of scheduling algorithms 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 considered 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 practical 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.

Reviews

Required fields are marked *. Your email address will not be published.