A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Conclusion <s> We survey and extend the results on the complexity of machine scheduling problems. After a brief review of the central concept of NP-completeness we give a classification of scheduling problems on single, different and identical machines and study the influence of various parameters on their complexity. The problems for which a polynomial-bounded algorithm is available are listed and NP-completeness is established for a large number of other machine scheduling problems. We finally discuss some questions that remain unanswered. <s> BIB001 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Conclusion <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> Conclusion <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> BIB003 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Conclusion <s> Abstract We investigate the computational complexity of deterministic sequencing problems in which unit-time jobs have to be scheduled on a single machine subject to chain-like precedence constraints. NP-hardness is established for the cases in which the number of late jobs or the total weighted tardiness is to be minimized, and for several related problems involving the total weighted completion time criterion. <s> BIB004 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Conclusion <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> BIB005 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Conclusion <s> We introduce an invariant of graphs called the tree-width, and use it to obtain a polynomially bounded algorithm to test if a graph has a subgraph contractible to H, where H is any fixed planar graph. We also nonconstructively prove the existence of a polynomial algorithm to test if a graph has tree-width ≤ w, for fixed w. Neither of these is a practical algorithm, as the exponents of the polynomials are large. Both algorithms are derived from a polynomial algorithm for the DISJOINT CONNECTING PATHS problem (with the number of paths fixed), for graphs of bounded tree-width. <s> BIB006 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Conclusion <s> We consider the problem of scheduling a set of chains onm > 1 identical processors with the objectives of minimizing the makespan and the mean flow time. We show that finding a nonpreemptive schedule with the minimum makespan is strongly NP-hard for each fixedm > 1, answering the open question of whether this problem is strongly NP-hard for trees. We also show that finding a nonpreemptive schedule with the minimum mean flow time is strongly NP-hard for each fixedm > 1, improving the known strong NP-hardness results for in-trees and out-trees. Finally, we generalize the result of McNaughton, showing that preemption cannot reduce the mean weighted flow time for a set of chains. The last two results together imply that finding a preemptive schedule with the minimum mean flow time is also strongly NP-hard for each fixedm > 1, answering another open question on the complexity of this problem for trees. <s> BIB007 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Conclusion <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> BIB008 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Conclusion <s> This paper considers single-machine scheduling problems with deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. In addition, the jobs are related by a series-parallel graph. It is shown that for the general linear problem to minimize the makespan, polynomial algorithms exist. It is also shown that for the proportional linear problem of minimization of the total weighted completion time, polynomial algorithms exist, too. <s> BIB009 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Conclusion <s> We consider various single machine scheduling problems in which the processing time of a job depends either on its position in a processing sequence or on its start time. We focus on problems of minimizing the makespan or the sum of (weighted) completion times of the jobs. In many situations we show that the objective function is priority-generating, and therefore the corresponding scheduling problem under series-parallel precedence constraints is polynomially solvable. In other situations we provide counter-examples that show that the objective function is not priority-generating. <s> BIB010 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Conclusion <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> BIB011 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Conclusion <s> Abstract In this paper we consider single-machine scheduling problems with position-dependent processing times, i.e., jobs whose processing times are an increasing or decreasing function of their positions in a processing sequence. In addition, the jobs are related by parallel chains and a series–parallel graph precedence constraints, respectively. It is shown that for the problems of minimization of the makespan polynomial algorithms exist. <s> BIB012 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Conclusion <s> Fixed-parameter tractability analysis and scheduling are two core domains of combinatorial optimization which led to deep understanding of many important algorithmic questions. However, even though fixed-parameter algorithms are appealing for many reasons, no such algorithms are known for many fundamental scheduling problems. <s> BIB013 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Conclusion <s> Abstract In contrast to undirected width measures such as tree-width, which have provided many important algorithmic applications, analogous measures for digraphs such as directed tree-width or DAG-width do not seem so successful. Several recent papers have given some evidence on the negative side. We confirm and consolidate this overall picture by thoroughly and exhaustively studying the complexity of a range of directed problems with respect to various parameters, and by showing that they often remain NP-hard even on graph classes that are restricted very beyond having small DAG-width. On the positive side, it turns out that clique-width (of digraphs) performs much better on virtually all considered problems, from the parameterized complexity point of view. <s> BIB014
In this paper, we surveyed the complexity results for scheduling problems with precedence constraints, and we have seen that single machine scheduling problems have been much more studied than others. This looks quite normal since the single machine problem is the scheduling problem that is the closest to order theory. Nevertheless, we show that there still are a few open problems for the single machine case. We believe that the most interesting problems for which the complexity is open lie in the parallel machine case; more precisely, we do conjecture that P m|sp − graph, p j = p|Cmax is solvable in polynomial time; this result will be a large breakthrough since series-parallel graphs are most of the time studied for single machine problems. Another approach to understand the complexity of scheduling problems is to deal with the parameterized complexity (see Downey and Fellows [2012] ). There are only very few results on parameterized complexity of scheduling problems. One can cite  who show that, if the precedence graph is of bounded width w (it is equal to the size of a maximum antichain), then problem 1|prec| T j ≤ k is FPT when parameterized by (w, k). The most recent result on the subject is that P ||Cmax is FPT for parameter pmax = max p j (see BIB013 ). A good graph measure is a powerful tool for parameterized complexity. For general (undirected) graphs, the creation of the treewidth (see BIB006 ) helped to discover many results in graph theory, including the Courcelle's theorem  ). For directed graphs, and more specifically DAGs, none of the existing measures (see BIB014 ) is satisfactory. In our opinion, a major breakthrough will be achieved when one will be able to find a good measure on directed acyclic graphs. BIB002 1|dim ≤ 2| w j C j P Ambühl and Mastrolilli [2009] 1|sp − graph, p BIB009 1|sp − graph, p j (t) = p j + α j t|Cmax P Wang et al. [2008] 1|sp − graph, p BIB012 1|sp − graph, p BIB012 1|sp − graph, p BIB010 1|sp − graph, p BIB010 1|sp − graph, p BIB010 1|sp − graph, p BIB010 1|sp − graph, p BIB010 1|pmtn, r j , p j = p| T j P Tian et al. [2006] 1|pmtn, r j , p j = p| w j U j P Baptiste [1999] 1|2 < f dim < 3| w j C j Open 1|io| C j Open 1|pmtn, chains, r j , p j = p| T j Open 1|pmtn, prec, r j , p j = p| w j T j Open 1|pmtn, chains, r j , p j = p| U j Open 1|pmtn, prec, r j , p j = p| w j U j Open 1|prec, p j = p| w j C j N P-hard BIB002 1|prec| C j N P-hard BIB002 1|indegree ≤ 2| C j N P-hard BIB003 1|h(G) ≤ k| w j C j N P-hard BIB002 1|io| w j C j N P-hard BIB011 1|f dim ≥ 3| w j C j N P-hard BIB011 1|chains, p j = 1| U j N P-hard BIB004 1|chains, p j = 1| T j N P-hard Leung and Young [1990] P |outtree, p j = p| C j P Hu [1961] P m|opp.f orest, p j = p|Cmax P Garey et al. [1983] P m|lo, p j = p|Cmax P Dolev and Warmuth [1985] P |io, p j = p|Cmax P Papadimitriou and Yannakakis [1979] P |io, p j = p| C j P Möhring [1989] P |qio, p j = p|Cmax P Moukrim [1999] P |oio, p j = p|Cmax P Chardon and Moukrim [2005] P |oio, p j = p| C j P Wang [2015] P |outtree, r j , p j = p|Cmax P Brucker et al. [1977] P |DC − graph, p j = p|Cmax P Kubiak et al. [2009] P m|h(G) ≤ k, p j = p|Cmax P Dolev and Warmuth [1984] P |w(G) ≤ k, r j , p j = 1|f P Middendorf and Timkovsky [1999] P 2|prec, p j = p|Cmax P Coffman Jr and BIB008 P 2|prec, p j = p| C j P Coffman Jr and BIB008 P 2|prec, r j , p j = 1| C j P Baptiste and Timkovsky [2004] Q2|chains, p j = p|Cmax P Brucker et al. [1999] P m|intree, p j = p| C j P Baptiste et al. [2004a] P |outtree, r j , p j = 1| C j P Brucker et al. [2002] Qm|r j , p j = p| C j P Dessouky et al. [1990] P m|sp − graph, p j = p|Cmax Open P m|prec, p j = p|Cmax Open P |intree, p j = p| C j Open P |outtree, r j , p j = p| C j Open Qm|prec, r j , p j = p|Lmax Open Qm|prec, r j , p j = p| C j Open P 2||Cmax N P-hard BIB001 P 2|chains| C j N P-hard BIB007 P |opp.f orest, p j = p|Cmax N P-hard BIB005 P |h(G) ≤ k, p j = p|Cmax N P-hard BIB003 P |intree, r j , p j = p|Cmax N P-hard P |h(G) ≤ k, p j = p| C j N P-hard Lenstra and Rinnooy Kan [1978] P |intree, r j , p j = 1| C j N P-hard Lenstra P 2|pmtn, outtree, r j , p j = 1| C j P Baptiste and Timkovsky [2001] P 2|pmtn, outtree, r j , p j = p| C j P Lushchakova [2006] P |pmtn, outtree, r j , p j = 1| C j P Brucker et al. [2002] P 2|pmtn, prec, p j = 1| C j P Coffman et al. [2003] P m|pmtn, qio, p j = p|Cmax Open P m|pmtn, oio, p j = p|Cmax Open P m|pmtn, lo, p j = p|Cmax Open P m|pmtn, sp − graph, p j = p|Cmax Open P m|pmtn, prec, p j = p|Cmax Open Qm|pmtn, prec, r j |Lmax Open P 2|pmtn, intree, r j , p j = 1| C j Open P 2|pmtn, prec, r j , p j = 1| C j Open P |pmtn, prec, p j = p|Cmax N P-hard Ullman [1976] P 2|pmtn, chains| C j N P-hard BIB007 P |pmtn, h(G) ≤ k, p j = p| C j N P-hard [this paper] P 2|pmtn, chains, p j = 1| w j C j N P-hard BIB007 P 2|pmtn, chains, p j = 1| U j N P-hard  