Scheduling precedence-constrained jobs with stochastic processing times on parallel machines

dc.contributor.authorSkutella, Martin
dc.contributor.authorUetz, Marc
dc.date.accessioned2022-05-11T12:11:43Z
dc.date.available2022-05-11T12:11:43Z
dc.date.issued2000
dc.description.abstractWe consider parallel machine scheduling problems where the jobs are subject to precedence constraints, and the processing times of jobs are governed by independent probability distributions. The objective is to minimize the weighted sum of job completion times &;j wjC_j in expectation, where wj&; 0. Building upon an LP-relaxation by Möhring, Schulz, and Uetz (J.ACM 46 (1999), pp.924-942) and an idle time charging scheme by Chekuri, Motwani, Natarajan, and Stein (SIAM J. Comp., to appear) we derive the first approximation algorithms for this model.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/16900
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-15678
dc.language.isoen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subject.ddc510 Mathematiken
dc.subject.otherscheduling problemsen
dc.subject.otherapproximation algorithmen
dc.titleScheduling precedence-constrained jobs with stochastic processing times on parallel machinesen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfree
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2000, 691en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
tub.subject.msc200090B35 Deterministic scheduling theory in operations researchen
tub.subject.msc200090C59 Approximation methods and heuristics in mathematical programmingen

Files

Original bundle
Now showing 1 - 2 of 2
Loading…
Thumbnail Image
Name:
Report-691-2000.pdf
Size:
5.22 MB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
Report-691-2000.ps
Size:
248.91 KB
Format:
Postscript Files

Collections