Models and Algorithms for Stochastic Online Scheduling
- 1 August 2006
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 31 (3), 513-525
- https://doi.org/10.1287/moor.1060.0201
Abstract
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 nonpreemptive 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 new better than used in expectation (NBUE) distributions, we improve upon previously best-known performance bounds from stochastic scheduling, even though we consider a more general setting.Keywords
This publication has 30 references indexed in Scilit:
- Stochastic Machine Scheduling with Precedence ConstraintsSIAM Journal on Computing, 2005
- On-line scheduling to minimize average completion time revisitedOperations Research Letters, 2004
- Beyond Competitive AnalysisSIAM Journal on Computing, 2000
- Approximation in stochastic schedulingJournal of the ACM, 1999
- Competitive snoopy cachingAlgorithmica, 1988
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985
- Stochastic scheduling problems I — General strategiesMathematical Methods of Operations Research, 1984
- Sequencing Tasks with Exponential Service Times to Minimize the Expected Flow Time or MakespanJournal of the ACM, 1981
- Scheduling tasks with exponential service times on non-identical processors to minimize various cost functionsJournal of Applied Probability, 1980
- Various optimizers for single‐stage productionNaval Research Logistics Quarterly, 1956