Stability of a schedule minimising the makespan for processing jobs on identical machines

ABSTRACT

A set of jobs has to be processed on identical machines. Every job may be processed on any available machine without preemptions. The criterion is to minimise the makespan (i.e. the completion time of the last job in a schedule). During the realisation of a schedule, durations of some jobs may deviate from the initial values estimated before scheduling. Other jobs have fixed durations that are known before scheduling. We conduct a stability analysis of the optimal semi-active schedule. First, we derive necessary and sufficient conditions for an optimal schedule to be unstable with respect to infinitely small variations of the non-fixed durations (the stability radius of an unstable schedule is equal to zero). Second, we show that the stability radius of an optimal schedule could be infinitely large. Furthermore, several lower and upper bounds on the stability radius have been established. Third, we derive a formula and develop an algorithm for calculating stability radii.

KEYWORDS:

• Scheduling
• identical machines
• makespan
• stability analysis
• stability radius

Disclosure statement

No potential conflict of interest was reported by the author.

Data availability statement

The author confirms that the data supporting the findings of this study are available within the article.

Additional information

Funding

This research was funded in part by Belorussian Republican Foundation for Fundamental Research [grant number Φ21-010 and grant number Φ23PHΦ-017].

Notes on contributors

Yuri N. Sotskov

Yuri N. Sotskov is a Principal Researcher and Professor at the United Institute of Informatics Problems (UIIP) of the National Academy of Sciences of Belarus. He received his PhD degree in the Institute of Mathematics of the National Academy of Sciences of Belarus, 1980, and his DSc degree in the Institute of Cybernetics of the National Academy of Sciences of Ukraine, 1991. He obtained the title of a Professor in the Application of Mathematical Models and Methods of Scientific Research in the Russian Academy of Sciences, 1994. He has more than 300 research publications on applied mathematics, operations research and scheduling. He coauthored four monographs and two textbooks. He was a supervisor of eight PhD scholars. In 1998, Yuri N. Sotskov received the National Price of Belarus in Science and Engineering.