Abstract: We are given a set of parallel jobs that have to be executed on a set of speed-scalable processors varying their speeds dynamically. Running a job at a slower speed is more energy-efficient, however, it takes a longer time and affects the performance. Every job is characterized by the processing volume and the number or the set of the required processors. Our objective is to minimize the maximum completion time so that the energy consumption is not greater than a given energy budget. For various particular cases, we propose polynomial-time approximation algorithms, consisting of two stages. At the first stage, we give an auxiliary convex program. By solving this problem, we get processing times of jobs and a lower bound on the makespan. Then, at the second stage, we transform our problem into the corresponding scheduling problem with the constant speed of processors and construct a feasible schedule. We also obtain an “almost exact” solution for the preemptive settings based on a configuration linear program.

Cite: Kononov A. , Zakharova Y.
Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion
Journal of Global Optimization. 2022. V.83. N3. P.539-564. DOI: 10.1007/s10898-021-01115-x WOS Scopus РИНЦ OpenAlex

Dates:

Submitted:	Apr 19, 2019
Accepted:	Nov 14, 2020
Published online:	Nov 26, 2020
Published print:	Jul 15, 2022

Identifiers:

Web of science:	WOS:000722491000001
Scopus:	2-s2.0-85119848695
Elibrary:	47532187
OpenAlex:	W3216574890

Citing:

DB	Citing
Scopus	7
Web of science	4
OpenAlex	4
Elibrary	3

Altmetrics: