On the Complexity of Scheduling Unit-Time Jobs with OR-Precedence Constraints

scheduling, or-precedence constraints, algorithms, list-scheduling, complexity, makespan, sum of completion times, wieghted sum of completion times, profile scheduling

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.

Download as [ps.gz]