TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)2003

COGA 5-Wheel

Page Content

to Navigation

Preprints 2003

On the Complexity of Scheduling Unit-Time Jobs with OR-Precedence Constraints
Citation key Report-050-2003
Author Berit Johannes
Year 2003
Number 050
Institution Technische Universität Berlin, Institut für Mathematik
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.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe