68M20 Performance evaluation; queueing; scheduling [See also 60K25, 90Bxx]
Refine
Year of publication
- 2005 (1)
Language
- English (1)
Keywords
- approximation (1)
- online (1)
- scheduling (1)
- stochastic (1)
- total weighted completion time (1)
Project
- C5 (1)
Application Area
- C (1)
We consider 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 consider is non-preemptive parallel machine scheduling, with the objective to
minimize the total weighted completion times of jobs. We analyze
simple, combinatorial online scheduling policies for that model, and
derive performance guarantees that match performance guarantees previously
known for stochastic and online parallel machine scheduling, respectively.
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.