direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2003

On the Complexity of Scheduling Unit-Time Jobs with OR-Precedence Constraints
Zitatschlüssel Report-050-2003
Autor Berit Johannes
Jahr 2003
Nummer 050
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag