Dagstuhl - Monday morning

I'm attending a Dagstuhl workshop on scheduling etc. This morning we had three talks. The main theme seemed to be defining new scheduling problems.

Kirk Pruhs talked about green computing. To conserve energy, current architectures have heterogeneous processors, so scheduling with related machines are problems of current interest. Speed-scaling is also of interest. The problems sucessfully studied in that realm seem to have mostly straighforward algorithmic solutions, and the theoretically interesting part is in the analysis rather than in the design. The main open question currently is to define "good" problems.

Samir Khuller talked about busy times minimization. Busy times are times when at least one processor is active. Thus one tries to schedule jobs simultaneously as much as possible, given various traditional scheduling constraints.

Tami Tamir talked about bullying. Replace the usual notion of precedence constraint (job j can only start once job i has finished) by "bullying" precedence constraints (job j can only start once job i has started), and study various traditional scheduling problems when one adds this new type of constraints.

Maybe I'm blase, but so far I have not seen a problem that I'd like to work on or a result whose proof I' am curious to understand in depth. It would be nice if the speakers could formally define a nice, compelling open problem, even if that problem is beyond our reach at present. What is driving the field? Is there an open problem whose answer would be a breakthrough, and why? That'll be my question for our session on the future of scheduling.