Abstract: Developing modern computer technologies makes it possible not only to solve complex computing problems, but also gives rise to new problems of optimal usage of computing resources. Modern computers can use multiple processors simultaneously and dynamically change the speed of calculations due to additional energy consumption for performing intensive calculations. We consider the speed scaling scheduling problem with energy constraint and parallel jobs. The total sum of completion times is minimized. The NP-hardness of the problem is proved and a mixed integer convex program with continuous time representation is proposed. For searching near-optimal solutions in quick time we develop a genetic algorithm with the generational replacement scheme. The genetic algorithm is experimentally tested and compared with the known greedy algorithm and local improvements technique on meaningful instances. The numerical results highlight the effectiveness and the efficiency of the proposed algorithm. The lower bounds on the objective function and convex program are also experimentally evaluated.

Cite: Zakharova Y. , Sakhno M.
Complexity and heuristic algorithms for speed scaling scheduling of parallel jobs with energy constraint
Journal of Computational and Applied Mathematics. 2025. V.457. 116254 :1-13. DOI: 10.1016/j.cam.2024.116254 WOS Scopus РИНЦ OpenAlex

Dates:

Submitted:	Dec 13, 2023
Accepted:	Sep 4, 2024
Published online:	Sep 6, 2024
Published print:	Mar 15, 2025

Identifiers:

Web of science:	WOS:001315638000001
Scopus:	2-s2.0-85203550067
Elibrary:	80691506
OpenAlex:	W4402294511

Citing:

DB	Citing
Scopus	3
OpenAlex	2
Web of science	2

Altmetrics: