|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Cost-aware scheduling on uniform parallel machinesстатья
Статья опубликована в высокорейтинговом журнале
Статья опубликована в журнале из списка Web of Science и/или Scopus- Авторы: Kononov A., Lushchakova I.
- Журнал: Computers and Industrial Engineering
- Том: 167
- Год издания: 2022
- Издательство: Pergamon Press Ltd.
- Местоположение издательства: United Kingdom
- Номер статьи: 107845
- Аннотация: 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.
- Добавил в систему: Кононов Александр Вениаминович