Seminario Interdipartimentale di Algoritmica  

Monday, May 2, 2005, 12:00 noon
Models and algorithms for stochastic online scheduling
Tjark Vredeveld, Maastricht University

DIS - Department of Computer and System Sciences
C3 Room, second floor

Abstract:

We introduce a model for non-preemptive scheduling under uncertainty. In this model, we combine the main characteristics of online and stochastic scheduling in a simple and natural way. Job processing times are assumed to be stochastic, but in contrast to the traditional stochastic scheduling models, we assume that jobs arrive online over time, and there is no knowledge about the jobs that will arrive in the future. The model incorporates both, stochastic scheduling and online scheduling as a special case. The particular setting we analyze is parallel machine scheduling, with the objective to minimize the total weighted completion times of jobs. We propose simple, combinatorial online scheduling policies for that model, and derive performance guarantees that match the currently best known performance guarantees for stochastic and online parallel machine scheduling. For processing times that follow distributions, we improve upon previously best known performance bounds from stochastic scheduling, even though we consider a more general setting.

This is joint work with Nicole Megow (TU Berlin) and Marc Uetz (Maastricht University)