Supervision : Christoph DÜRR

Job scheduling in order to aggregate energy consumption and quality of service: optimization and game theory

This thesis focuses on a job scheduling problem with the goal of minimizing the sum of energy consumption and the weighted flow time from two different approaches: centralized and decentralized. In the decentralized setting, we defined two games which differ in the strategies players can choose from and design cost sharing mechanisms, charging the consumed energy to the users in order to incentive a socially desirable behavior. More precisely we were interested in the existence of pure Nash equilibria, in the convergence time, and the ratio between the consumed energy and the total charged amount. On the other side, for the centralized approach, we reduced the minimization problem to a classical scheduling problem with a polynomial concave penalty function, for which little results were known. We established a state of the art for a family of scheduling problems of this form with different penalty functions and showed that a classical NP-completeness proof technique fails here. Finally we addressed the exact resolution of the problem using the algorithm A*. In this context, we showed new order dominance rules. More precisely, we characterized the conditions under which any optimal solution must schedule a job pair in a certain order. In addition we carried out a computational experience to evaluate the practical impact of these new rules compared to the existing ones.

2012-2017 Publications

• 2017
  • N. Bansal, Ch. Dürr, N. Thang, O. Vasquez Perez : “The local–global conjecture for scheduling with non-linear cost”, Journal of Scheduling, vol. 20 (3), pp. 239-254, (Springer Verlag) (2017)
  • Ch. Dürr, Z. Hanzalek, Ch. Konrad, Y. Seddik, R. Sitters, O. Vasquez Perez, Gerhard J. Woeginger : “The triangle scheduling problem”, Journal of Scheduling, (Springer Verlag) (2017)
• 2015
  • Ch. Dürr, Ł. Jeż, O. Vasquez Perez : “Scheduling under dynamic speed-scaling for minimizing weighted completion time and energy consumption”, Discrete Applied Mathematics, vol. 196, pp. 20-27, (Elsevier) (2015)
• 2014
  • Ó. Vásquez Pérez : “Job scheduling in order to aggregate energy consumption and quality of service: optimization and game theory”, thesis, phd defence 01/23/2014, supervision Dürr, Christoph (2014)
  • Ch. Dürr, O. Vasquez Perez : “Order constraints for single machine scheduling with non-linear cost”, 16^th Workshop on Algorithm Engineering and Experiments (ALENEX 2014), Portland, United States, pp. 98-111, (SIAM) (2014)
• 2013
  • Ch. Dürr, Ł. Jeż, O. Vasquez Perez : “Mechanism design for aggregating energy consumption and quality of service in speed scaling scheduling”, WINE 2013: The 9^th Conference on Web and Internet Economics, vol. 8289, Lecture Notes in Computer Science, Cambridge, MA, United States, pp. 134-145, (Springer) (2013)
  • O. Vasquez Perez, J. M. Sepúlveda, Miguel D. Alfaro, L. Osorio‑Valenzuela : “Disaster Response Project Scheduling Problem: A Resolution Method based on a Game-Theoretical Model”, International Journal of Computers, Communications and Control, vol. 8 (2), pp. 334-345, (Agora University of Oradea) (2013)
• 2012
  • O. Vasquez Perez : “Energy in computing systems with speed scaling: optimization and mechanisms design”, (2012)