direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2003

Scheduling AND/OR-Networks on Identical Parallel Machines
Zitatschlüssel Report-047-2003
Autor Thomas Erlebach and Vanessa K\ä\äb, and Rolf H. M\öhring
Jahr 2003
Nummer 047
Notiz Appears in the Proceedings of the Workshop on Approximation and Online Algorithms, Budapest, 2003, LNCS
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag