Models and algorithms for stochastic online scheduling

Megow, N. and Uetz, M.J. and Vredeveld, T. (2006) Models and algorithms for stochastic online scheduling. Mathematics of Operations Research, 31 (3). pp. 513-525. ISSN 0364-765X

PDF
Restricted to UT campus only: Request a copy
271Kb

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.
Item Type:	Article
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/62394
Official URL:	http://dx.doi.org/10.1287/moor.1060.0201
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page