Minimizing makespan for parallelizable jobs with energy constraint Full article
| Journal |
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304 |
||||||
|---|---|---|---|---|---|---|---|
| Output data | Year: 2022, Volume: 19, Number: 2, Pages: 586-600 Pages count : 15 DOI: 10.33048/semi.2022.19.049 | ||||||
| Tags | Approximation algorithm; Parallelizable job; Scheduling; Speed scaling | ||||||
| Authors |
|
||||||
| Affiliations |
|
Funding (1)
| 1 | Russian Science Foundation | 21-41-09017 |
Abstract:
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.
Cite:
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 РИНЦ
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 РИНЦ
Dates:
| Accepted: | May 13, 2022 |
| Published online: | Aug 30, 2022 |
Identifiers:
| Web of science: | WOS:000886649600015 |
| Scopus: | 2-s2.0-85137647648 |
| Elibrary: | 50336835 |
Citing:
| DB | Citing |
|---|---|
| Elibrary | 1 |