Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Scheduling AND/OR-Networks on Identical Parallel Machines
Author(s): Kääb, Vanessa
Erlebach, Thomas
Möhring, Rolf H.
Type: Research Paper
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.
Subject(s): scheduling
AND/OR networks
approximation algorithms
parallel machines
Issue Date: 2003
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 90B35 Scheduling theory, deterministic
68W25 Approximation algorithms
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2003, 47
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 212.84 kB
DownloadShow Preview
Format: Unknown | Size: 134.18 kB

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.