Optimal schedules with infinitely large stability radius∗
- 1 January 1995
- journal article
- research article
- Published by Taylor & Francis in Optimization
- Vol. 33 (3) , 271-280
- https://doi.org/10.1080/02331939508844080
Abstract
Recently necessary and sufficient conditions have been developed for a given optimal makespan schedule to have an infinite stability radius. In other words, there is identified a problem class whose optimal solutions are implied only by the given precedence constraints and the distribution of operations per machines, but independent from the job processing times. However, because of the generality of the considered problems it is difficult to check these conditions. This paper only deals with classical shop scheduling problems. We present necessary and sufficient conditions for a given problem to have at least one optimal schedule with an infinite stability radius for minimizing the makespan or maximum lateness. The obtained conditions can be verified in polynomial time. We also show that there does not exist such a schedule for other regular criteria which are considered in scheduling theoryKeywords
This publication has 5 references indexed in Scilit:
- Stability of an optimal scheduleEuropean Journal of Operational Research, 1991
- The stability of high-speed optimal schedulesUSSR Computational Mathematics and Mathematical Physics, 1989
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a SurveyPublished by Elsevier ,1979
- Stability of the travelling salesman problemUSSR Computational Mathematics and Mathematical Physics, 1975
- A note on two problems in connexion with graphsNumerische Mathematik, 1959