Speed Scaling Scheduling of Multiprocessor Jobs with Energy Constraint and Total Completion Time Criterion Full article
| Journal |
International Journal of Artificial Intelligence
ISSN: 0974-0635 |
||||||
|---|---|---|---|---|---|---|---|
| Output data | Year: 2023, Volume: 21, Number: 2, Pages: 109 - 129 Pages count : 21 | ||||||
| Tags | approximation algorithm, multiprocessor job, NP-hardness, scheduling, speed scaling | ||||||
| Authors |
|
||||||
| Affiliations |
|
Funding (1)
| 1 | Russian Science Foundation | 21-41-09017 |
Abstract:
We consider the problem of speed scaling scheduling multiprocessor jobs under the given energy budget. A multiprocessor job must be performed by more than one processor at a time. The speed of a processor may be different for different jobs. Running a job at a lower speed is more energy efficient. However, this takes a longer time and affects the performance. Our goal is to minimize the total completion time of jobs. We analyze the complexity of both parallel and dedicated statements of the problem. Approximation and exact algorithms are proposed for various cases. In our algorithms, a sequence of jobs and their processing time are calculated at the first stage, and then a feasible solution is constructed using a greedy rule of list type
Cite:
Kononov A.
, Zakharova Y.
Speed Scaling Scheduling of Multiprocessor Jobs with Energy Constraint and Total Completion Time Criterion
International Journal of Artificial Intelligence. 2023. V.21. N2. P.109 - 129. Scopus
Speed Scaling Scheduling of Multiprocessor Jobs with Energy Constraint and Total Completion Time Criterion
International Journal of Artificial Intelligence. 2023. V.21. N2. P.109 - 129. Scopus
Dates:
| Published print: | Nov 9, 2023 |
| Published online: | Nov 9, 2023 |
Identifiers:
| Scopus: | 2-s2.0-85153263409 |
Citing:
| DB | Citing |
|---|---|
| Scopus | 5 |