A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> 15 <s> This paper deals with a new sequencing problem in which n jobs with ordering restrictions have to be done by men of equal ability. Assume every man can do any of the n jobs. The two questions considered in this paper are 1 How to arrange a schedule that requires the minimum number of men so that all jobs are completed within a prescribed time T, and 2 if m men are available, arrange a schedule that completes all jobs at the earliest time. <s> BIB001 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> 15 <s> Linear-time algorithms are presented for several problems of scheduling n equal-length tasks on m identical parallel processors subject to precedence constraints. This improves upon previous time bounds for the maximum lateness problem with treelike precedence constraints, the number-of-late-tasks problem without precedence constraints, and the one machine maximum lateness problem with general precedence constraints. <s> BIB002 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> 15 <s> Ordered sets have recently gained much importance in many applied and theoretical problems in computer science and operations research ranging from project planning via processor scheduling to sorting and retrieval problems. These problems involve partial orders as their basic structure, e.g. as precedence constraints in scheduling problems, or as comparability relation among the objects to be sorted or retrieved. <s> BIB003
In BIB003 , the author studies the problem with bounded width, equal processing times and the makespan criterion. He shows that the problem can be solved in polynomial time by using dynamic programming on the digraph of order ideals.  proposed their own approach to solve the problem P |w(G) ≤ k, r j , p j = 1|f for any regular function f . More precisely, their algorithm consists in searching a shortest path in the related transversal graph. When adding release dates, the problem is already N P-hard for intrees, yet it is solvable in polynomial time for outtrees (see , and BIB002 for a linear algorithm for the latter problem). Note that there is a strong relationship between scheduling with release dates and Cmax criterion and scheduling with Lmax, by simply looking at the schedule in the reverse way, and reversing the precedence constraints. Hence problems P |intree, p j = p|Lmax is polynomially solvable and P |outtree, p j = p|Lmax is N P-hard. Kubiak et al. [2009] recently opened new perspectives, since they show that P |DC −graph, p j = p|Cmax is solvable in polynomial time. They more precisely proved that the Highest Level First strategy (used in BIB001 ) solves the problem to optimality when the precedence graph is a divide-and-conquer graph (see Definition 3).