Geodesic
Approximate schedules for non-migratory parallel jobs in speed-scaled multiprocessor systems
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 249-257.

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

We consider a problem of scheduling rigid parallel jobs on variable speed processors so as to minimize the total energy consumption. Each job is specified by its processing volume and the required number of processors. We propose new constant factor approximation algorithms for the non-migratory cases when all jobs have a common release time and/or a common deadline.
Keywords: approximation algorithm, speed scaling, schedule, parallel job
Mots-clés : migration. 
@article{SEMR_2019_16_a113,
     author = {A. Kononov and Yu. Kovalenko},
     title = {Approximate schedules for non-migratory parallel jobs in speed-scaled multiprocessor systems},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {249--257},
     publisher = {mathdoc},
     volume = {16},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2019_16_a113/}
}
TY  - JOUR
AU  - A. Kononov
AU  - Yu. Kovalenko
TI  - Approximate schedules for non-migratory parallel jobs in speed-scaled multiprocessor systems
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2019
SP  - 249
EP  - 257
VL  - 16
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2019_16_a113/
LA  - en
ID  - SEMR_2019_16_a113
ER  - 
%0 Journal Article
%A A. Kononov
%A Yu. Kovalenko
%T Approximate schedules for non-migratory parallel jobs in speed-scaled multiprocessor systems
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2019
%P 249-257
%V 16
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2019_16_a113/
%G en
%F SEMR_2019_16_a113
A. Kononov; Yu. Kovalenko. Approximate schedules for non-migratory parallel jobs in speed-scaled multiprocessor systems. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 249-257. http://geodesic.mathdoc.fr/item/SEMR_2019_16_a113/

[1] S. Albers, “Energy-efficient algorithms”, Communications of the ACM, 53:5 (2010), 86–96 | DOI | MR

[2] S. Albers, A. Antoniadis, G. Greiner, “On multi-processor speed scaling with migration”, Journal of Computer and System Sciences, 81 (2015), 1194–1209 | DOI | MR | Zbl

[3] S. Albers, F. Müller, S. Schmelzer, “Speed scaling on parallel processors”, Algorithmica, 68:2 (2007), 404–425 | DOI | MR

[4] E. Angel, E. Bampis, F. Kacem, D. Letsios, “Speed scaling on parallel processors with migration”, 18th International European Conference on Parallel and Distributed Computing, Lecture Notes in Computer Science, 7484, 2012, 128–140 | DOI | Zbl

[5] A. Antoniadis, C.C. Huang, “Non-preemptive speed scaling”, J. Sched., 16:4 (2013), 385–394 | DOI | MR | Zbl

[6] E. Bampis, A. Kononov, D. Letsios, G. Lucarelli, I. Nemparis, “From preemptive to non-preemptive speed-scaling scheduling”, Discrete Applied Mathematics, 181 (2015), 11–20 | DOI | MR | Zbl

[7] E. Bampis, A. Kononov, D. Letsios, G. Lucarelli, M. Sviridenko, “Energy efficient scheduling and routing via randomized rounding”, J. Sched., 21:1 (2018), 35–51 | DOI | MR | Zbl

[8] B.D. Bingham, M.R. Greenstreet, “Energy optimal scheduling on multiprocessors with migration”, International Symposium on Parallel and Distributed Processing with Applications (ISPA'08), IEEE, 2018, 153–161 | DOI

[9] J. Chen, H. Hsu, K. Chuang, C. Yang, A. Pang, T. Kuo, “Multiprocessor energy-efficient scheduling with task migration considerations”, 16th Euromicro Conference on Real-Time Systems (ECRTS 2004), IEEE, 101–108 | DOI

[10] V. Cohen-Addad, Z. Li, C. Mathieu, I. Milis, “Energy-efficient algorithms for non-preemptive speed-scaling”, International Workshop on Approximation and Online Algorithms (WAOA 2014), Lecture Notes in Computer Science, 8952, 2015, 107–118 | DOI | MR | Zbl

[11] M. Drozdowski, Scheduling for Parallel Processing, Springer-Verlag, London, 2009 | MR | Zbl

[12] M.E.T Gerards, J.L. Hurink, P.K.F. Hölzenspies, “A survey of offline algorithms for energy minimization under deadline constraints”, J. Sched., 19 (2016), 3–19 | DOI | MR | Zbl

[13] G. Greiner, T. Nonner, A. Souza, “The bell is ringing in speed-scaled multiprocessor scheduling”, Theory of Computing Systems, 54:1 (2014), 24–44 | DOI | MR | Zbl

[14] B. Johannes, “Scheduling parallel jobs to minimize the makespan”, J. Sched., 9 (2006), 433–452 | DOI | MR | Zbl

[15] A. Kononov, Y. Kovalenko, “On speed scaling scheduling of parallel jobs with preemption”, International Conference on Discrete Optimization and Operations Research (DOOR-2016), Lecture Notes in Computer Science, 9869, 2016, 309–321 | DOI | MR | Zbl

[16] A. Kononov, Y. Kovalenko, “An approximation algorithm for preemptive speed scaling scheduling of parallel jobs with migration”, International Conference on Learning and Intelligent Optimization (LION-11), Lecture Notes in Computer Science, 10556, 2017, 351–357 | DOI | MR

[17] C-Y. Lee, X. Cai, “Scheduling one and two-processor tasks on two parallel processors”, IIE Transactions, 31:5 (1999), 445–455 | DOI

[18] M. Li, F. Yao, H. Yuan, “An $O(n^2)$ algorithm for computing optimal continuous voltage schedules”, International Conference on Theory and Applications of Models of Computation (TAMC 2017), Lecture Notes in Computer Science, 10185, 2017, 389–400 | DOI | MR | Zbl

[19] E. Naroska, U. Schwiegelshohn, “On an on-line scheduling problem for parallel jobs”, Information Processing Letters, 81:6 (2002), 297–304 | DOI | MR | Zbl

[20] A. Shioura, N. Shakhlevich, V. Strusevich, “Energy saving computational models with speed scaling via submodular optimization”, Third International Conference on Green Computing, Technology and Innovation (ICGCTI 2015) (Serdang, 2015), 7–18 | Zbl

[21] F. Yao, A. Demers, S. Shenker, “A scheduling model for reduced CPU energy”, 36th Annual Symposium on Foundation of Computer Science (FOCS 1995), IEEE, 1995, 374–382 | DOI | Zbl