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.
