TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen2005

COGA 5-Wheel


zur Navigation

Preprints 2005

Stochastic Online Scheduling on Parallel Machines
Zitatschlüssel Report-018-2004
Autor Nicole Megow and Marc Uetz and Tjark Vredeveld
Jahr 2004
Nummer 018
Notiz 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
Zusammenfassung 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.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe