Geodesic
Minimizing makespan for parallelizable jobs with energy constraint
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 586-600.

Voir la notice de l'article provenant de la source Math-Net.Ru

We investigate the problem of scheduling parallelizable jobs to minimize the makespan under the given energy budget. A parallelizable job can be run on an arbitrary number of processors with a job execution time that depends on the number of processors assigned to it. We consider malleable and moldable jobs. Processors can vary their speed to conserve energy using dynamic speed scaling. Polynomial time algorithms with approximation guarantees are proposed. In our algorithms, a lower bound on the makespan and processing times of jobs are calculated. Then numbers of utilized processors are assigned for jobs and a feasible solution is constructed using a list-type scheduling rule.
Keywords: parallelizable job, speed scaling, scheduling, approximation algorithm. 
@article{SEMR_2022_19_2_a29,
     author = {A. Kononov and Yu. Zakharova},
     title = {Minimizing makespan for parallelizable jobs with energy constraint},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {586--600},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a29/}
}
TY  - JOUR
AU  - A. Kononov
AU  - Yu. Zakharova
TI  - Minimizing makespan for parallelizable jobs with energy constraint
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2022
SP  - 586
EP  - 600
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a29/
LA  - en
ID  - SEMR_2022_19_2_a29
ER  - 
%0 Journal Article
%A A. Kononov
%A Yu. Zakharova
%T Minimizing makespan for parallelizable jobs with energy constraint
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2022
%P 586-600
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a29/
%G en
%F SEMR_2022_19_2_a29
A. Kononov; Yu. Zakharova. Minimizing makespan for parallelizable jobs with energy constraint. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 586-600. http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a29/

[1] K. Belkhale, P. Banerjee, “An approximate algorithm for the partitionable independent task scheduling problem”, Proceedings of International Conference on Parallel Processing, ICPP-90, v. 1, 1990, 72–75 | MR

[2] M. Drozdowski, Scheduling for parallel processing, Springer-Verlag, London, 2009 | MR | Zbl

[3] M. Drozdowski, W. Kubiak, “Scheduling parallel tasks with sequential heads and tails”, Ann. Oper. Res., 90 (1999), 221–246 | DOI | MR | Zbl

[4] J. Du, J.Y-T. Leung, “Complexity of scheduling parallel task systems”, SIAM J. Discrete Math., 2:4 (1989), 473–487 | DOI | MR | Zbl

[5] J. Glasgow, H. Shachnai, “Channel based scheduling of parallelizable tasks”, Proceedings Fifth International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (Los Alamitos, CA, USA, 1997), 11–16

[6] K. Jansen, L. Porkolab, “Linear-time approximation schemes for scheduling malleable parallel tasks”, Algorithmica, 32:3 (2002), 507–520 | DOI | MR | Zbl

[7] A. Kononov, Y. Kovalenko, “Approximation algorithms for energy-efficient scheduling of parallel jobs”, J. Sched., 23:6 (2020), 693–709 | DOI | MR | Zbl

[8] A.V. Kononov, Yu.V. Zakharova, “Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion”, J. Glob. Optim., 83:3 (2022), 539–564 | DOI | MR | Zbl

[9] R. Krishnamurti, B. Narahari, “An approximation algorithm for preemptive scheduling on parallel-task systems”, SIAM J. Discrete Math., 8:4 (1995), 661–669 | DOI | MR | Zbl

[10] H. Kuhn, A. Tucker, “Nonlinear programming”, Proc. Berkeley Sympos. math. Statist. Probability (California July 31 - August 12, 1950), 1951, 481–492 | MR | Zbl

[11] R. Lepère, D. Trystram, G. Woeginger, “Approximation algorithms for scheduling malleable tasks under precedence constraints”, Int. J. Found. Comput. Sci., 13:4 (2002), 613–627 | DOI | MR | Zbl

[12] R. McNaughton, “Scheduling with deadlines and loss functions”, Manage. Sci., 6:1 (1959), 1–12 | DOI | MR | Zbl

[13] Y. Nesterov, Lectures on convex optimization, Springer, Cham, 2018 | MR | Zbl

[14] Q. Wang, K.H. Cheng, “List scheduling of parallel tasks”, Inf. Process. Lett., 37:5 (1991), 291–297 | DOI | MR | Zbl

[15] Q. Wang, K.H. Cheng, “A heuristic of scheduling parallel tasks and its analysis”, SIAM J. Comput., 21:2 (1992), 281–294 | DOI | MR | Zbl