A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Minimum NP-hard cases <s> Precedence constraints between jobs that have to be respected in every feasible schedule generally increase the computational complexity of a scheduling problem. Occasionally, their introduction may turn a problem that is solvable within polynomial time into an NP-complete one, for which a good algorithm is highly unlikely to exist. We illustrate the use of these concepts by extending some typical NP-completeness results and simplifying their correctness proofs for scheduling problems involving precedence constraints. <s> BIB001 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Minimum NP-hard cases <s> Suppose n jobs are to be sequenced for processing by a single machine, with the object of minimizing total weighted completion time. It is shown that the problem is NP-complete if there are arbitrary precedence constraints. However, if precedence constraints are “series parallel”, the problem can be solved in O( n log n ) time. This result generalizes previous results for the more special case of rooted trees. It is also shown how a decomposition procedure suggested by Sidney can be implemented in polynomial-bounded time. Equivalence of the sequencing problem with the optimal linear ordering problem for directed graphs is discussed. <s> BIB002 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Minimum NP-hard cases <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> BIB003 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Minimum NP-hard cases <s> We consider the single-machine scheduling problem to minimize the weighted sum of completion times under precedence constraints. In a series of recent papers, it was established that this scheduling problem is a special case of minimum weighted vertex cover. ::: ::: In this paper, we show that the vertex cover graph associated with the scheduling problem is exactly the graph of incomparable pairs defined in the dimension theory of partial orders. Exploiting this relationship allows us to present a framework for obtaining (2-2/f)-approximation algorithms, provided that the set of precedence constraints has fractional dimension of at most f. Our approach yields the best-known approximation ratios for all previously considered special classes of precedence constraints, and it provides the first results for bounded degree and orders of interval dimension 2. ::: ::: On the negative side, we show that the addressed problem remains NP-hard even when restricted to the special case of interval orders. Furthermore, we prove that the general problem, if a fixed cost present in all feasible schedules is ignored, becomes as hard to approximate as vertex cover. We conclude by giving the first inapproximability result for this problem, showing under a widely believed assumption that it does not admit a polynomial-time approximation scheme. <s> BIB004
The problem 1|prec| w j C j is known to be N P-hard (see BIB001 ). In order to identify for which precedence graph the problem may be polynomially solvable, we present here the minimal (with respect to precedence constraints) N P-hard cases: the problem is still N P−hard even if the precedence graph is: -of indegree at most 2 (see BIB001 ). Note that this result also stands with equal weights (i.e., w j = 1) -of bounded height (proof is straightforward by using the transformation proposed in BIB002 ). -an interval order graph (see BIB004 ). This is a strong difference with parallel machine results for which interval order graphs provide often polynomial algorithms, as we will see in the dedicated section. -of fractional dimension (see Definition 10) greater or equal to 3 (see BIB004 ).  The interesting results for this survey are the N P-hardness of P |prec, p j = p|Cmax and P |prec, p j = p| C j (see BIB001 ). Note that the proof for the two problems also holds when the precedence graph is of bounded height, and that the problem P |opp.f orest, p j = p|Cmax is also N P-hard (see BIB003 ). When adding release dates, the corresponding problem is already N P-hard for intrees, for both the makespan and the total completion time (see ). Finally, what may not be obvious is that even if P ||Cmax is strongly N P-hard, the problem P |w(G) ≤ k|Cmax is solvable in pseudo-polynomial time  ). This results is due to the fact that the class of empty graphs is not included in bounded-width graphs class. For the makespan criterion, Ullman [1976] shows that P |pmtn, prec, p j = p|Cmax is N P-hard. For the total completion time criterion, if we carefully look at the N P-hardness proof of P |prec, p j = p| C j in Lenstra and Rinnooy BIB001 , we can see that preemption is useless for the instance constructed in the reduction and hence the preemptive version is still N P-hard for precedence graphs of bounded height: Theorem 1 P |pmtn, prec, p j = p| C j is N P-hard even if the precedence graph is of bounded height. Proof. We just need to modify slightly the proof in the reduction from Clique of BIB001 . Clique : G = (V, E) is an undirected graph and k an integer. Does G have a clique on k vertices? Let us recall this reduction; we denote by v (resp. e) the number of vertices (resp. edges) of G. We also define following parameters: l = we use the notations of the original article). We construct an instance of P |pmtn, prec, p j = p| C j with m = max{k, l + k ′ , l ′ } + 1 machines and n = 3m jobs: