Sciact
  • EN
  • RU

Heuristics with Local Improvements for Two-processor Scheduling Problem with Energy Constraint and Parallelization Full article

Conference The 4th international Сonference and Summer School “Numerical Computations: Theory and Algorithms”
14-20 Jun 2023 , CALABRIA
Source Numerical Computations: Theory and Algorithms : 4th International Conference, NUMTA 2023, Pizzo Calabro, Italy, June 14–20, 2023, Revised Selected Papers
Compilation, Springer Cham. 2024. 412 c. ISBN 978-3-031-81241-5.
Journal Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349
Output data Year: 2024, Volume: 14476, Pages: 241–256 Pages count : 16 DOI: 10.1007/978-3-031-81241-5_17
Tags Approximation algorithm, Computational complexity, Energy, Parallelizable job, Scheduling, Speed scaling
Authors Zakharova Yu.V. 1 , Sakhno M.Yu. 1
Affiliations
1 Sobolev Institute of Mathematics SB RAS

Funding (1)

1 Russian Science Foundation 22-71-10015

Abstract: Modern computer systems offer some type of parallelism and use restricted resources. Parallel jobs require more than one processor at the same moment of time. Processors may operate at variable speeds. Running a job at a slower speed is more energy-efficient. However, it takes a longer time and affects the performance. We propose and experimentally evaluate heuristic methods based on greedy rules and list scheduling for the speed scaling scheduling problem with the total completion time criterion. Series of instances with various structure are constructed and tested. NP-hard and polynomially solvable cases are identified.
Cite: Zakharova Y.V. , Sakhno M.Y.
Heuristics with Local Improvements for Two-processor Scheduling Problem with Energy Constraint and Parallelization
In compilation Numerical Computations: Theory and Algorithms : 4th International Conference, NUMTA 2023, Pizzo Calabro, Italy, June 14–20, 2023, Revised Selected Papers. – Springer Cham., 2024. – Т.Part I. – C.241–256. – ISBN 978-3-031-81241-5. DOI: 10.1007/978-3-031-81241-5_17 Scopus OpenAlex
Dates:
Accepted: Nov 29, 2023
Published print: Dec 31, 2024
Published online: Jan 1, 2025
Identifiers:
Scopus: 2-s2.0-85215658599
OpenAlex: W4405921859
Citing: Пока нет цитирований
Altmetrics: