We introduce a model for 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
traditional stochastic scheduling models, we assume that jobs arrive
online, 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 nonpreemptive 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 NBUE distributions, we
improve upon previously best known performance bounds from
stochastic scheduling, even though we consider a more general
setting.
