Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14622
For citation please use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorMunier, Alix
dc.contributor.authorQueyranne, Maurice
dc.contributor.authorSchulz, Andreas S.
dc.date.accessioned2021-12-17T10:13:33Z-
dc.date.available2021-12-17T10:13:33Z-
dc.date.issued1998
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15849-
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14622-
dc.description.abstractA well studied and difficult class of scheduling problems concerns parallel machines and precedence constraints. In order to model more realistic situations, we consider precedence delays, asso ciating with each precedence constraint a certain amount of time which must elapse between the completion and start times of the corresponding jobs. Release dates, among others, may be modeled in this fashion. We provide the first constant-factor approximation algorithms for the makespan and the total weighted completion time objectives in this general class of problems. These algorithms are rather simple and practical forms of list scheduling. Our analysis also unifies and simplifies that of a number of special cases heretofore separately studies, while actually improving some of the former approximation results.en
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherapproximation boundsen
dc.subject.otherschedulingen
dc.subject.otherscheduling problemsen
dc.subject.otherparallel machinesen
dc.subject.otherprecedence constraintsen
dc.titleApproximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problemsen
dc.typeResearch Paperen
tub.accessrights.dnbfreeen
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber1998, 584en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
dc.type.versionsubmittedVersionen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften » Inst. Mathematikde
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-584-1998.pdf
Format: Adobe PDF | Size: 17.34 MB
DownloadShow Preview
Thumbnail
Report-584-1998.ps
Format: Postscript | Size: 537.39 kB
Download

Item Export Bar

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