A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s>  <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>  <s> The theory of deterministic sequencing and scheduling has expanded rapidly during the past years. In this paper we survey the state of the art with respect to optimization and approximation algorithms and interpret these in terms of computational complexity theory. Special cases considered are single machine scheduling, identical, uniform and unrelated parallel machine scheduling, and open shop, flow shop and job shop scheduling. We indicate some problems for future research and include a selective bibliography. <s> BIB002 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s>  <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 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s>  <s> Besides scheduling problems for single and parallel machines and shop scheduling problems, this book covers advanced models involving due-dates, sequence dependent changeover times and batching. Discussion also extends to multiprocessor task scheduling and problems with multi-purpose machines. Among the methods used to solve these problems are linear programming, dynamic programming, branch-and-bound algorithms, and local search heuristics. The text goes on to summarize complexity results for different classes of deterministic scheduling problems. <s> BIB004
only precedence constraints related to assembling steps, precedence constraints can be represented by a particular directed acyclic graph called intree. The fact that the precedence graph takes a particular form may transform the complexity of the problem. Most of the time, adding precedence constraints makes problem harder, since the empty graph is included in many graph classes. Yet, it may make the problem easier if it is not the case, for example for the class of graphs of bounded width. For this reason, the idea of this survey is to consider the complexity results in scheduling theory according to the structure of precedence constraints. We assume that the reader is conversant with the theory of N P-completeness, otherwise the book by  is a good entry point. We will discuss, in the conclusion of this paper, the parameterized complexity. The reader can refer to the book of Downey and Fellows [2012] if needed. BIB001 offer a large set of complexity results for scheduling problems with precedence constraints. BIB002 and  propose two surveys of complexity results for scheduling problems, but they are not necessarily focused on precedence constraints. For complexity results with the most classical precedence constraints (i.e., chains, trees, series-parallel and arbitrary precedence constraints), the reader can refer to the book by BIB004 , and/or to the websites  and  . Note that this website has been recently updated in order to include most of the results discussed in this article. BIB003 proposes a very interesting survey dedicated to specific partial ordered sets, and studies their structure. Some applications to scheduling are also presented. Since this survey was conducted, many results arised in scheduling theory for specific precedence graphs, we hence believe that a new survey would be beneficial for the scheduling community. We restrict our field on purpose to complexity results and do not talk about approximations results  ), despite the fact that many results arised in this field recently in scheduling theory, such as Svensson [2011] and  . We believe that it is important to limit the scope of the survey, in order to be as complete as possible in a given field.