 |
|
|||
| Authors: | Thomas Erlebach, Vanessa Kääb, Rolf Möhring |
| Group: | Theory of Communication Networks |
| Type: | Inproceedings |
| Title: | Scheduling AND/OR-Networks on Identical Parallel Machines |
| Year: | 2004 |
| Pub-Key: | EKM03 |
| Book Titel: | Lecture Notes in Computer Science. Proceedings of the First Workshop on Approximation and Online Algorithms (WAOA 2003) |
| Volume: | 2909 |
| Pages: | 123-136 |
| Publisher: | Springer-Verlag |
| 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. |
| Location: | Budapest, Hungary |
| Resources: | [BibTeX] |
