Optimal schedules with infinitely large stability radius∗

What is it about?

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 theory.

Featured Image