Реферат: We consider scheduling problems with uniform parallel machines to minimize the sum of the total (weighted) completion time and the total cost for usage of machines. A cost density function is given for each machine in advance. Integrating the cost density function for the time period(s) when the machine is busy, one obtains the cost of using this machine in a schedule. We suggest the classification of the problems under consideration according to the type of the cost density functions. The notions of a simple cost density function and an almost concave cost density function are introduced. For these types of cost density functions, we investigate the properties of optimal schedules. Based on these properties, we develop two families of exact pseudo-polynomial DP algorithms. For the case of two uniform machines, we present an FPTAS. Besides, a polynomial-solvable case of the problem is considered.

Библиографическая ссылка: Kononov A. , Lushchakova I.
Cost-aware scheduling on uniform parallel machines
Computers and Industrial Engineering. 2022. V.167. 107845 . DOI: 10.1016/j.cie.2021.107845 WOS Scopus РИНЦ OpenAlex

Даты:

Поступила в редакцию:	24 окт. 2020 г.
Принята к публикации:	24 нояб. 2021 г.
Опубликована online:	5 дек. 2021 г.
Опубликована в печати:	13 мая 2022 г.

Идентификаторы БД:

Web of science:	WOS:000772079700003
Scopus:	2-s2.0-85125258302
РИНЦ:	48185068
OpenAlex:	W4200119124

Цитирование в БД: Пока нет цитирований

Альметрики: