Scheduling tasks with AND/OR precedence constraints

In traditional precedence-constrained scheduling a task is ready to execute when all its predecessors are complete. Such a task is called an AND task. The authors allow certain tasks, known as OR tasks, to be ready when just one of their predecessors is complete. They analyze the complexity of two types of real-time AND/OR task scheduling problems. In the first type of problem, all predecessors of every OR task must eventually be completed, but in the second type of problem, some OR predecessors may be left unscheduled. The authors present two priority-driven heuristic algorithms that may be used to schedule AND/OR task systems on m processors to minimize completion time, and analyze the worst-case performance of these algorithms