Scheduling AND/OR-Networks on Identical Parallel Machines

dc.contributor.authorKääb, Vanessa
dc.contributor.authorErlebach, Thomas
dc.contributor.authorMöhring, Rolf H.
dc.date.accessioned2021-12-17T10:05:23Z
dc.date.available2021-12-17T10:05:23Z
dc.date.issued2003
dc.description.abstractScheduling precedence constrained jobs on identical parallel machines is a well investigated problem with many applications. AND/OR-networks constitute a useful generalization of standard precedence constraints where certain jobs can be executed as soon as at least one of their direct predecessors is completed. For the problem of scheduling AND/OR-networks on parallel machines, we present a 2-approximation algorithm for the objective of minimizing the makespan. The main idea of the algorithm is to transform the AND/OR constraints into standard constraints. For the objective of minimizing the total weighted completion time on one machine, scheduling AND/OR-networks is as hard to approximate as Label Cover. We show that list scheduling with shortest processing time rule is an O(sqrt(n))-approximation for unit weights on one machine and an n-approximation for arbitrary weights.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15479
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14252
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherschedulingen
dc.subject.otherAND/OR networksen
dc.subject.otherapproximation algorithmsen
dc.subject.otherparallel machinesen
dc.titleScheduling AND/OR-Networks on Identical Parallel Machinesen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
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.issuenumber2003, 47en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
tub.subject.msc200090B35 Scheduling theory, deterministicen
tub.subject.msc200068W25 Approximation algorithmsen

Files

Original bundle
Now showing 1 - 2 of 2
Loading…
Thumbnail Image
Name:
Report-047-2003.pdf
Size:
212.84 KB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
Report-047-2003.ps.gz
Size:
134.18 KB
Format:
Unknown data format

Collections