A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Makespan criterion and fixed number of machines <s> A basic problem of deterministic scheduling theory is that of scheduling n unit-length tasks on m identical processors subject to precedence constraints so as to meet a given overall deadline. T. C. Hu’s classic “level algorithm” can be used to solve this problem in linear time if the precedence constraints have the form of an in-forest or an out-forest. We show that a polynomial time algorithm for a wider class of precedence constraints is unlikely, by proving the problem to be NP-complete for precedence constraints that are the disjoint union of an in-forest and an out-forest (the “opposing forests” of our title). However, for any fixed value of m we show that this problem can be solved in polynomial time for such precedence constraints. For the special case of $m = 3$ we provide a linear time algorithm. <s> BIB001 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Makespan criterion and fixed number of machines <s> The existence of a schedule for a partially ordered set of unit length tasks on m identical processors is known to be NP-complete (J. D. Ullman, NP-complete scheduling problems, J. Comput. System Sci., 10 (1975), 384–393). The problem remains NP-complete even if we restrict the precedence graph to be of height bounded by a constant. (J. K. Lenkstra and A. H. G. Rinnooy Kan, Complexity of scheduling under precedence constraints, Operations Res., 26 (1978), 22–35; D. Dolev and M. K. Warmuth, “Scheduling Flat Graphs,” IBM Research Report RJ 3398, 1982). In these NP-completeness proofs the upper bound on the number of available processors varies with the problem instance. We present a polynomial algorithm for the case where the upper bound on the number of available processors and the height of the precedence graph are both constants. <s> BIB002 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Makespan criterion and fixed number of machines <s> The question of existence of a schedule of a given length for n unit length tasks on n identical processors subject to precedence constraints is known to be NP-complete [Ullman, J. Comput. System Sci., 10 (1976), pp. 384–393]. For a fixed value of m we present polynomial algorithms to find an optimal schedule for two families of precedence graphs: level orders and opposing forests. In the case of opposing forest our algorithm is a considerable improvement over the algorithm presented in [Garey et al., SIAM J. Alg. Disc. Meth., 4 (1983), pp. 72–93]. <s> BIB003 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Makespan criterion and fixed number of machines <s> Despite the recognized potential of multiprocessing little is known concerning the general problem of finding efficient algorithms which compute minimallength schedules for given computations and m?2 processors. In this paper we formulate a general model of computation structures and exhibit an efficient algorithm for finding optimal nonpreemptive schedules for these structures on two-processor systems. We prove that the algorithm gives optimal solutions and discuss its application to preemptive scheduling disciplines. <s> BIB004 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Makespan criterion and fixed number of machines <s> We characterize a nontrivial special case with a polynomial-time algorithm for a well-known parallel machine scheduling problem with precedence constraints, with a fixed number of machines, and with tasks of unit length. The special case is related to instances with given maximum path length and maximum degree of the task precedence graph. The method is based on the observation that the number of tasks is either small and bounded by a constant depending on the maximum path length and maximum degree, or alternatively, the number of tasks is large, giving a "dense" schedule. <s> BIB005
Let us now focus on the case where the number of machines is fixed. Recall that the problem P m|prec, p j = p|Cmax is still open (this problem is known as [OPEN8] in the book by  ) for m ≥ 3, and it was solved for m = 2 in Coffman Jr and BIB004 . For opposing forests, BIB001 propose an optimal polynomial algorithm (of complexity O(n m 2 +2m−5 log n)) that consists in a divide and conquer approach, that uses the HLF algorithm as a subroutine. A new algorithm with complexity O(n 2m−2 log n) has been proposed by BIB003 , who also show that the problem is polynomially solvable for level order graphs (that are strictly included in series-parallel graphs). BIB002 solve the case where the precedence graph is of bounded height by proposing an algorithm of time complexity O(n h(m−1)+1 ). Recently, BIB005 show that P m|prec, p j = p|Cmax is solvable in polynomial time when the precedence graph is of bounded height and the maximum degree is bounded. This result is in fact a special case of the one proposed in BIB002 .