Skip navigation
Please use this identifier to cite or link to this item:
Title: Cost-aware scheduling on uniform parallel machines
Authors: Kononov, A.
Lushchakova, I.
Keywords: публикации ученых;uniform parallel machines;total machine cost;polynomial-time algorithm
Issue Date: 2022
Publisher: Elsevier
Citation: Kononov, A. Cost-aware scheduling on uniform parallel machines / A. Kononov, I. Lushchakova // Computers & Industrial Engineering. – 2022. – Vol. 167. – 12 p. – DOI :
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.
Appears in Collections:Публикации в зарубежных изданиях

Files in This Item:
File Description SizeFormat 
Kononov_Cost_aware.pdf77.44 kBAdobe PDFView/Open
Show full item record

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.