A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Scheduling notation <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> BIB001 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Scheduling notation <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> BIB002
In this paper, we will use the standard α|β|γ notation introduced in BIB001 , and updated in BIB002 . We define below the different notations used all along the paper. The α-field is used for the machine environment. α = 1 corresponds to a single machine problem; if α = P m, there is a fixed number m of identical parallel machines. If this number is arbitrary, it is noted α = P . Similarly, if α = Qm (resp. α = Q), it corresponds to a fixed (resp. arbitrary) number of uniform parallel machines, i.e., each machine i has a speed s i and the processing time of a job j on machine i is equal to p j /s i . The field β ⊂ {β 1 , β 2 , β 3 , β 4 } describes the jobs characteristics, the possible entries that we will deal with are the following ones: -β 1 ∈ {pmtn, •} : pmtn means that preemption is allowed, i.e., a job may be interrupted and finished later. If β 1 = •, preemption is forbidden. -β 2 describes the precedence constraints. If β 2 = •, there is no precedence constraint, whereas β 2 = prec means that the precedence graph is a general directed acyclic graph. This field can take many values according to the structure of the directed acyclic graph, as presented in the previous section. For sake of completeness, all the acronyms are recalled hereinafter: chains, intree, outtree, opp.f orest (opposing forest), io (interval order graph), qio (quasi-interval order graph), oio (over-interval order graph), sp − graph (series-parallel graph), DC − graph (divide-and-conquer graph), lo (level order graph), h(G) ≤ k (directed acyclic graph with height bounded by k), dim ≤ k (directed acyclic graph with dimension bounded by k), f dim ≤ k (directed acyclic graph with fractional dimension bounded by k), w(G) ≤ k (directed acyclic graph with width bounded by k). It appears there that classical literature often abuses of terms intree and outtree to handle in fact inf orest and outf orest, that can be mixed in opp.f orest for some problems. -β 3 ∈ {r j , •} : if β 3 = r j , each job j has a given release date. If β 3 = •, the release date is 0 for each job. -β 4 represents the processing time of a job j. If β 4 = •, there is one processing time p j for each job j. If p j = p, all the jobs have the same processing time p. When p j = 1, we use the acronym UET which stands for Unit Execution Time. In some cases, the processing time may increase or decrease with either the position of the job or the starting time of the job. If the job is in position r on a machine, the processing time will be noted p j . If the processing time is depending of the starting time t of the job, it will be written p The γ−field is related to the objective function of the problem. Let C j be the completion time of job j. The makespan is defined by Cmax = max j C j and the total completion time by j C j . It is clear that, in general, makespan and total completion time are not equivalent. Nevertheless, for some problems, we can show that there exists an ideal schedule, which both minimizes makespan Cmax and total completion time C j . Due-date related objectives are also studied; if d j is the due date of job j, then the lateness of job and the unit penalty U j is equal to one if C j > d j and to zero otherwise. We then can define the maximum lateness Lmax = max L j , the total tardiness T j , the total number of late jobs U j . A weight w j may also exist for each job j, leading to the corresponding objective functions: the total weighted completion time w j C j , the total weighted tardiness w j T j and the total weighted number of late jobs w j U j . All the functions presented so far are regular functions, i.e., they are non-decreasing with C j .