|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Approximation algorithms for energy-efficient scheduling of parallel jobsстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 8 октября 2025 г.
- Авторы: Kononov A., Kovalenko Y.
- Журнал: Journal of Scheduling
- Том: 23
- Номер: 6
- Год издания: 2020
- Издательство: Springer Nature
- Местоположение издательства: Switzerland
- Первая страница: 693
- Последняя страница: 709
- DOI: 10.1007/s10951-020-00653-8
- Аннотация: In this paper, we consider the homogeneous scheduling on speed-scalable processors, where the energy consumption is minimized. While most previous works have studied single-processor jobs, we focus on rigid parallel jobs, using more than one processor at the same time. Each job is specified by release date, deadline, processing volume and the number of required processors. Firstly, we develop constant-factor approximation algorithms for such interesting cases as agreeable jobs without migration and preemptive instances. Next, we propose a configuration linear program, which allows us to obtain an “almost exact” solution for the preemptive setting. Finally, in the case of non-preemptive agreeable jobs with unit-work operations, we present a three-approximation algorithm by generalization of the known exact algorithm for single-processor jobs.
- Добавил в систему: Кононов Александр Вениаминович