Supervision : Evripidis BAMPIS

Co-supervision : MILIS Ioannis

Algorithmic problems in power management of computing systems

This thesis is focused on energy-efficient algorithms for job scheduling problems on speed-scalable processors, as well as on processors operating under a thermal and cooling mechanism, where, for a given budget of energy or a thermal threshold, the goal is to optimize a Quality of Service criterion. A part of our research concerns scheduling problems arising in large-data processing environments. In this context, we focus on the MapReduce paradigm and we consider problems of energy-efficient scheduling on multiple speed-scalable processors as well as classical scheduling on a set of unrelated processors.
First, we propose complexity results, optimal and constant competitive algorithms for different energy-aware variants of the problem of minimizing the maximum lateness of a set of jobs on a single speed-scalable processor. Then, we consider energy-aware MapReduce scheduling as well as classical MapReduce scheduling (where energy is not our concern) on unrelated processors, where the goal is to minimize the total weighted completion time of a set of MapReduce jobs. We study special cases and generalizations of both problems and propose constant approximation algorithms. Finally, we study temperature-aware scheduling on a single processor that operates under a strict thermal threshold, where each job has its own heat contribution and the goal is to maximize the schedule's throughput. We consider the case of unit-length jobs with a common deadline and we study the approximability of the problem.

2012-2016 Publications

• 2016
  • E. Bampis, D. Letsios, I. Milis, G. Zois : “Speed Scaling for Maximum Lateness”, Theory of Computing Systems, vol. 58 (2), pp. 304-321, (Springer Verlag) (2016)
• 2015
  • D. Fotakis, I. Milis, E. Zampetakis, G. Zois : “Scheduling MapReduce Jobs and Data Shuffle on Unrelated Processors”, SEA 2015 - 14^th International Symposium on Experimental Algorithms, Paris, France, pp. 137-150, (Springer) (2015)
• 2014
  • G. Zois : “Problèmes algorithmiques dans les systèmes informatiques sous contraintes d’énergie”, thesis, defence 12/12/2014, supervision Bampis, Evripidis, rapporteurs : MILIS Ioannis (2014)
  • E. Bampis, V. Chau, D. Letsios, G. Lucarelli, I. Milis, G. Zois : “Energy Efficient Scheduling of MapReduce Jobs”, 20^th International Conference on Parallel Processing (Euro-Par 2014), vol. 8632, Lecture Notes in Computer Science, Porto, Portugal, pp. 198-209, (Springer) (2014)
• 2012
  • Ch. Dürr, I. Milis, J. Robert, G. Zois : “Approximating the Throughput by Coolest First Scheduling”, Approximation and Online Algorithms, Ljubljana, Slovenia, pp. 187-200, (Springer) (2012)
  • E. Bampis, D. Letsios, Ioannis Z. Milis, G. Zois : “Speed scaling for maximum lateness”, 18^th Annual International Computing and Combinatorics Conference (COCOON 2012), vol. 7434, Lecture Notes in Computer Science, Sydney, NSW, Australia, pp. 25-36 (2012)