Technical Report 047-2003

Title

Scheduling AND/OR-Networks on Identical Parallel Machines

Authors

Thomas Erlebach and Vanessa Kääb and Rolf H. Möhring

Publication

Appears in the Proceedings of the Workshop on Approximation and Online Algorithms, Budapest, 2003, LNCS

Source

Download as [PDF] [ps.gz]

Classification

MSC:
primary:	90B35	Scheduling theory, deterministic
secondary:	68W25	Approximation algorithms

Keywords

Scheduling, AND/OR networks, approximation algorithms, parallel machines

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.