TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)2004

COGA 5-Wheel

Page Content

to Navigation

Preprints 2004

Stochastic Online Scheduling on Parallel Machines
Citation key Report-018-2004
Author Nicole Megow and Marc Uetz and Tjark Vredeveld
Year 2004
Number 018
Note Appeared in: Persiano and R. Solis-Oba (eds): Approximation and Online Algorithms, Lecture Notes in Computer Science 3351, pages 167-180, Springer-Verlag, 2005.
Institution Technische Universität Berlin, Institut für Mathematik
Abstract We consider a non-preemptive, stochastic parallel machine scheduling model with the goal to minimize the weighted completion times of jobs. In contrast to the classical stochastic model where jobs with their processing time distributions are known beforehand, we assume that jobs appear one by one, and every job must be assigned to a machine online. We propose a simple online scheduling policy for that model, and prove a performance guarantee that matches the currently best known performance guarantee for stochastic parallel machine scheduling. For the more general model with job release dates we derive an analogous result, and for NBUE distributed processing times we even improve upon the previously best known performance guarantee for stochastic parallel machine scheduling. Moreover, we derive some lower bounds on approximation.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe