ICE-TCS Lectures Series - Hadas Shachnai - Real-time Scheduling to Minimize Machine Busy Times

The next ICE-TCS  talk for this semester will be delivered on Wednesday, 9 December, by Hadas Shachnai (Technion, Haifa, Israel). The talk, entitled Real-time Scheduling to Minimize Machine Busy Times, will be held in room K1 at Reykjavík University (Kringlan 1) from 14:00 till 15:00. 

Further information about forthcoming ICE- TCS events may be found at the ICE-TCS  news page

Abstract

Traditional research interest in cluster systems has been high performance, such as high throughput, low response time, load balancing, and so on.  However, recent research work has focused on {\em reducing power consumption} in cluster systems. We consider {\em power-aware scheduling} problems where the power consumption of a machine is assumed to be proportional to the time it is in {\em on} state, also called its {\em busy-time}.  In our model, the jobs have release times, deadlines, processing times, and demands and need to be scheduled {\em non-preemptively} in their release-time-deadline windows, so that the total demand of jobs scheduled on a single machine at any given time is at most its capacity.

We present a constant factor approximation for minimizing the total busy-time of a schedule. We extend this result to the case of {\em moldable} jobs where the algorithm also needs to choose, for each job, one of several processing-time vs. demand configurations.  Better bounds and exact algorithms are derived for several special cases,
including interval jobs with unit demands, proper interval graphs, intervals forming a clique and scheduling laminar family of intervals.

Based on joint works with Michele Flammini, Rohit Khandekar, Gianpiero Monaco, Luca Moscardelli, Baruch Schieber, Mordechai Shalom, Tami Tamir and Shmuel Zaks.