TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)2003

COGA 5-Wheel

Page Content

to Navigation

Preprints 2003

Scheduling AND/OR-Networks on Identical Parallel Machines
Citation key Report-047-2003
Author Thomas Erlebach and Vanessa K\ä\äb, and Rolf H. M\öhring
Year 2003
Number 047
Note Appears in the Proceedings of the Workshop on Approximation and Online Algorithms, Budapest, 2003, LNCS
Institution Technische Universität Berlin, Institut für Mathematik
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.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe