Combining stochastic and online scheduling

scheduling model with the goal to minimize the weighted completion
times of jobs. In contrast to the classical stochastic model where
jobs with their processing time distributions are known
beforehand, we assume that jobs appear one by one, and every job
must be assigned to a machine online. We propose a simple online
scheduling policy for that model, and prove a performance
guarantee that matches the currently best known performance
guarantee for stochastic parallel machine scheduling. For the more
general model with job release dates we derive an analogous
result, and for NBUE distributed processing times we even improve
upon the previously best known performance guarantee for
stochastic parallel machine scheduling. Moreover, we derive some
lower bounds on approximation.

Joint work with:
* Nicole Megow (TU Berlin)
* Marc Uetz (Maastricht University)