• search hit 7 of 13
Back to Result List

Stochastic Online Scheduling with Precedence Constraints

Please always quote using this URN:urn:nbn:de:0296-matheon-5406
  • We consider the preemptive and non-preemptive problems of scheduling jobs with precedence constraints on parallel machines with the objective to minimize the sum of~(weighted) completion times. We investigate an online model in which the scheduler learns about a job when all its predecessors have completed. For scheduling on a single machine, we show matching lower and upper bounds of~$\Theta(n)$ and~$\Theta(\sqrt{n})$ for jobs with general and equal weights, respectively. We also derive corresponding results on parallel machines. Our result for arbitrary job weights holds even in the more general stochastic online scheduling model where, in addition to the limited information about the job set, processing times are uncertain. For a large class of processing time distributions, we derive also an improved performance guarantee if weights are equal.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Nicole Megow, Tjark Vredeveld
URN:urn:nbn:de:0296-matheon-5406
Referee:Rolf H. Möhring
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2009/05/01
Release Date:2009/05/01
Institute:Technische Universität Berlin
Preprint Number:534
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.