Please use this identifier to cite or link to this item:
For citation please use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorMegow, Nicole
dc.contributor.authorVredeveld, Tjark
dc.description.abstractWe consider the classical non-preemptive scheduling problem of processing jobs with precedence constraints on parallel machines with the objective to minimize the sum of (weighted) completion times. We discuss a reasonable online model and give lower and upper bounds on the competitive ratio for scheduling without job preemptions. These are the first investigation on online scheduling with precedence constraints for the considered objective function. We show matching bounds for scheduling on a single machine and corresponding bounds for scheduling on parallel machines. Our results hold also in a the more general stochastic online scheduling model where, in addition to the limited information about the jobset, processing times are uncertain. In particular, we derive an n-approximation for the stochastic online scheduling problem P|prec|E(sum w_jC_j). This bound is not constant but it is a first performance guarantee for non-preemptive stochastic scheduling that is independent of processing time distributions.en
dc.subject.ddc510 Mathematiken
dc.subject.otherstochastic schedulingen
dc.subject.otheronline optimizationen
dc.subject.otherprecedence constraintsen
dc.titleStochastic Online Scheduling with Precedence Constraintsen
dc.typeResearch Paperen
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2007, 29en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften » Inst. Mathematikde
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 198.71 kB
DownloadShow Preview

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.