Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14249
For citation please use:
Main Title: On the Complexity of Scheduling Unit-Time Jobs with OR-Precedence Constraints
Author(s): Johannes, Berit
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15476
http://dx.doi.org/10.14279/depositonce-14249
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: AND/OR-networks are an important generalization of ordinary precedence constraints in various scheduling contexts. AND/OR-networks consist of traditional AND-precedence constraints, where a job can only be started after all its predecessors are completed, and OR-precedence constraints, where a job is ready as soon as any of its predecessors is completed. Hence, scheduling problems with AND/OR-constraints inherit the computational hardness of the corresponding problems with AND-precedence constraints. On the other hand, the complexity status of various scheduling problems with OR-constraints has remained open. In this paper, we present several complexity results for scheduling unit-time jobs subject to OR-precedence constraints. In particular, we give a polynomial-time algorithm for minimizing the makespan and the total completion time on identical parallel machines. This algorithm can also be applied if the number of available machines does not decrease over time. In the general case of profile scheduling, scheduling jobs with OR-precedence constraints to minimize the makespan or the total completion time is strongly NP-hard. Furthermore, it is not possible to approximate the makespan with a constant ratio, unless P=NP. In contrast to the makespan and the total completion time, minimizing the total weighted completion time is strongly NP-hard, even on a single machine.
Subject(s): scheduling
or-precedence constraints
algorithms
list-scheduling
complexity
makespan
sum of completion times
wieghted sum of completion times
profile scheduling
Issue Date: 2003
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 90B35 Scheduling theory, deterministic
68Q25 Analysis of algorithms and problem complexity
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2003, 50
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:
Report-050-2003.pdf
Format: Adobe PDF | Size: 98.68 kB
DownloadShow Preview
Thumbnail
Report-050-2003.ps
Format: Postscript | Size: 306.05 kB
Download

Item Export Bar

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