Titre : On preemptive and non-preemptive speed-scaling scheduling
Exposant : Giorgio Lucarelli, LIP 6
Résumé : We are given a set of jobs, each one specified by its release date, its deadline and its processing volume (work), and a single (or a set of) speed-scalable processor(s). We adopt the standard model in speed-scaling in which if a processor runs at speed s then the energy consumption is s^alpha per time unit, where alpha>1. Our goal is to find a schedule respecting the release dates and the deadlines of the jobs so that the total energy consumption is minimized. We present our results concerning the preemptive and non-preemptive cases. For the multiprocessor preemptive speed-scaling problem, we give a transformation to the convex cost flow problem and we obtain a polynomial-time algorithm, simplifying the previous known algorithms for the problem. For the single-processor non-preemptive speed-scaling problem, we present an approximation algorithm for unit-work jobs. Finally, for the multiprocessor non-preemptive case, we propose improved approximation algorithms, for agreeable instances.