Speed Scaling Scheduling of Multiprocessor Jobs with Energy Constraint and Total Completion Time Criterion | Sciact - Система учета научной деятельности ИМ СО РАН

Speed Scaling Scheduling of Multiprocessor Jobs with Energy Constraint and Total Completion Time Criterion Научная публикация

Журнал

International Journal of Artificial Intelligence
ISSN: 0974-0635

Вых. Данные

Год: 2023, Том: 21, Номер: 2, Страницы: 109 - 129 Страниц : 21

Ключевые слова

approximation algorithm, multiprocessor job, NP-hardness, scheduling, speed scaling

Авторы

Kononov A. ¹ , Zakharova Y. ^2,3

Организации

1	Sobolev Institute of Mathematics
2	Sobolev Institute of Mathematics
3	Dostoevsky Omsk State University

Информация о финансировании (1)

Российский научный фонд

21-41-09017

We consider the problem of speed scaling scheduling multiprocessor jobs under the given energy budget. A multiprocessor job must be performed by more than one processor at a time. The speed of a processor may be different for different jobs. Running a job at a lower speed is more energy efficient. However, this takes a longer time and affects the performance. Our goal is to minimize the total completion time of jobs. We analyze the complexity of both parallel and dedicated statements of the problem. Approximation and exact algorithms are proposed for various cases. In our algorithms, a sequence of jobs and their processing time are calculated at the first stage, and then a feasible solution is constructed using a greedy rule of list type

Kononov A. , Zakharova Y.
Speed Scaling Scheduling of Multiprocessor Jobs with Energy Constraint and Total Completion Time Criterion
International Journal of Artificial Intelligence. 2023. V.21. N2. P.109 - 129. Scopus

Опубликована в печати:	9 нояб. 2023 г.
Опубликована online:	9 нояб. 2023 г.

Scopus:

2-s2.0-85153263409

БД	Цитирований
Scopus	4