Minimizing makespan for parallelizable jobs with energy constraint | Sciact - Система учета научной деятельности ИМ СО РАН

Minimizing makespan for parallelizable jobs with energy constraint Научная публикация

Журнал

Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304

Вых. Данные

Год: 2022, Том: 19, Номер: 2, Страницы: 586-600 Страниц : 15 DOI: 10.33048/semi.2022.19.049

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

Approximation algorithm; Parallelizable job; Scheduling; Speed scaling

Авторы

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

Организации

1	Sobolev Institute of Mathematics, 4,Koptyuga ave., Novosibirsk, 630090, Russian Federation
2	Dostoevsky Omsk State University, 55a,Mira ave., Omsk, 644077, Russian Federation
3	Sobolev Institute of Mathematics, 4,Koptyuga ave., Novosibirsk, 630090, Russian Federation

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

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

21-41-09017

We investigate the problem of scheduling parallelizable jobs to minimize the makespan under the given energy budget. A parallelizable job can be run on an arbitrary number of processors with a job execution time that depends on the number of processors assigned to it.We consider malleable and moldable jobs. Processors can vary their speed to conserve energy using dynamic speed scaling. Polynomial time algorithms with approximation guarantees are proposed. In our algorithms, a lower bound on the makespan and processing times of jobs are calculated. Then numbers of utilized processors are assigned for jobs and a feasible solution is constructed using a list-type scheduling rule.

Kononov A. , Zakharova Y.
Minimizing makespan for parallelizable jobs with energy constraint
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2022. V.19. N2. P.586-600. DOI: 10.33048/semi.2022.19.049 WOS Scopus РИНЦ

Принята к публикации:	13 мая 2022 г.
Опубликована online:	30 авг. 2022 г.

Web of science:	WOS:000886649600015
Scopus:	2-s2.0-85137647648
РИНЦ:	50336835

БД	Цитирований
РИНЦ	1