Abstract: 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.

Cite: 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

Dates:

Submitted:	Oct 24, 2020
Accepted:	Nov 24, 2021
Published online:	Dec 5, 2021
Published print:	May 13, 2022

Identifiers:

Web of science:	WOS:000772079700003
Scopus:	2-s2.0-85125258302
Elibrary:	48185068
OpenAlex:	W4200119124

Citing: Пока нет цитирований

Altmetrics: