On optimality conditions for job scheduling on uniform parallel machines
Authors:
- Volodymyr Popenko,
- Maiia Sperkach,
- Olena Zhdanova,
- Zbigniew Kokosiński
Abstract
We study three similar problems of scheduling of unrelated jobs on uniform parallel machines each having a distinct optimization criterion. In the first problem the criterion is the makespan minimization. In the second one the goal is to create a schedule, where the minimum of the completion times of the last jobs on the parallel machines is maximized (machine covering problem). In the third one the goal is to create a schedule with maximally uniform distribution of jobs among the machines. We propose the sufficient conditions of schedule optimality for these problems. First, optimality criteria for the analyzed problems were transformed into functions of makespan’s lower boundary deviation. This allows to define auxiliary optimization problems of the mixed-integer programming problems class. The objective of these auxiliary problems is to determine a perfect schedule - the one that gives the perfect value of the corresponding source criterion for the given volume of jobs. Perfect value allows us to determine the sufficient conditions of schedule optimality for all three problems.
- Record ID
- CUTa4559421192f4aa0a504386f394b5a60
- Publication categories
- ; ;
- Author
- Pages
- 103-112
- Other elements of collation
- rys.; tab.; Bibliografia (na s.) - 111-112; Bibliografia (liczba pozycji) - 18; Oznaczenie streszczenia - Abstr.
- Book
- Hu Zhengbing, Zhengbing Hu Petoukhov Sergey, Sergey Petoukhov Dychka Ivan Ivan Dychka [et al.] (eds.): Advances in Computer Science for Engineering and Education II, Advances in Intelligent Systems and Computing, no. 938, 2020, Cham, Springer, Springer, ISBN 978-3-030-16621-2 (eBook)
- Keywords in English
- schedule, uniform parallel machines, makespan, machine covering problem, auxiliary optimization problem, sufficient conditions of optimality
- DOI
- DOI:10.1007/978-3-030-16621-2_10 Opening in a new tab
- URL
- https://link.springer.com/chapter/10.1007%2F978-3-030-16621-2_10 Opening in a new tab
- Language
- eng (en) English
- Score (nominal)
- 20
- Publication indicators
- = 0
- Additional fields
- Indeksowana w: Scopus
- Uniform Resource Identifier
- https://cris.pk.edu.pl/info/article/CUTa4559421192f4aa0a504386f394b5a60/
- URN
urn:pkr-prod:CUTa4559421192f4aa0a504386f394b5a60
* presented citation count is obtained through Internet information analysis, and it is close to the number calculated by the Publish or PerishOpening in a new tab system.