Models and Algorithms for Stochastic Online Scheduling?

Algorithms for Optimization with Incomplete Information

计算机科学;物理学;物理学

Nicole Megow1 ; Marc Uetz2 ; Tjark Vredeveld2 ; 2 Maastricht University, Department of Quantitative Economics P.O. Box 616, 6200 MD Maastricht, The Netherlands

Others  :  http://drops.dagstuhl.de/opus/volltexte/2005/110/pdf/05031.MegowNicole.ExtAbstract.110.pdf
PID  :  6813

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

We introduce a model for non-preemptive scheduling underuncertainty. 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 stochas- tic scheduling models, we assume that jobs arrive online, and there is no knowledge about the jobs that will arrive in the future. The particular setting we analyze is parallel machine scheduling, with the objective to minimize the total weighted completion times of jobs. We propose sim- ple, combinatorial online scheduling policies for that model, and derive performance guarantees that match the currently best known perfor- mance 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.