ZOIS Georgios

PhD graduated
Team : RO
Departure date : 12/31/2014

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.

Defence : 12/12/2014 - 14h30 - Site Jussieu 24-25/405
Jury members :
Stavros Kolliopoulos, University of Athens [Rapporteur]
Monaldo Mastrolilli, Rapporteur, IDSIA, Lugano [Rapporteur]
Evripidis Bampis, Université Pierre et Marie Curie
Christoph Dürr, CNRS, Université Pierre et Marie Curie
Evangelos Markakis, Athens University of Economics and Business
Ioannis Milis, Athens University of Economics and Business
Denis Trystram, Grenoble INP

2012-2016 Publications

All Journal articles Conference papers These

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
- 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)
- G. Zois : “Problèmes algorithmiques dans les systèmes informatiques sous contraintes d’énergie”, these, defence 12/12/2014, supervision Bampis, Evripidis, co-supervision MILIS Ioannis (2014)
2012
- Ch. Dürr, I. Milis, J. Robert, G. Zois : “Approximating the Throughput by Coolest First Scheduling”, WAOA 2012 - 10^th International Workshop on Approximation and Online Algorithms, Ljubljana, Slovenia, pp. 187-200, (Springer) (2012)
- E. Bampis, D. Letsios, I. 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, (Springer) (2012)