Реферат: 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.

Библиографическая ссылка: 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

Даты:

Поступила в редакцию:	13 дек. 2023 г.
Принята к публикации:	4 сент. 2024 г.
Опубликована online:	6 сент. 2024 г.
Опубликована в печати:	15 мар. 2025 г.

Идентификаторы БД:

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

Цитирование в БД:

БД	Цитирований
Web of science	1

Альметрики: