Scheduling AND/OR-Networks on Identical Parallel Machines
dc.contributor.author | Kääb, Vanessa | |
dc.contributor.author | Erlebach, Thomas | |
dc.contributor.author | Möhring, Rolf H. | |
dc.date.accessioned | 2021-12-17T10:05:23Z | |
dc.date.available | 2021-12-17T10:05:23Z | |
dc.date.issued | 2003 | |
dc.description.abstract | Scheduling 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.issn | 2197-8085 | |
dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15479 | |
dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14252 | |
dc.language.iso | en | en |
dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
dc.subject.ddc | 510 Mathematik | en |
dc.subject.other | scheduling | en |
dc.subject.other | AND/OR networks | en |
dc.subject.other | approximation algorithms | en |
dc.subject.other | parallel machines | en |
dc.title | Scheduling AND/OR-Networks on Identical Parallel Machines | en |
dc.type | Research Paper | en |
dc.type.version | submittedVersion | en |
tub.accessrights.dnb | free | en |
tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
tub.affiliation.institute | Inst. Mathematik | de |
tub.publisher.universityorinstitution | Technische Universität Berlin | en |
tub.series.issuenumber | 2003, 47 | en |
tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
tub.subject.msc2000 | 90B35 Scheduling theory, deterministic | en |
tub.subject.msc2000 | 68W25 Approximation algorithms | en |