A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Open problems <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> Open problems <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> BIB002 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Open problems <s> textabstractWe address the problem of scheduling n identical jobs on m uniform parallel machines to optimize scheduling criteria that are nondecreasing in the job completion times. It is well known that this can be formulated as a linear assignment problem, and subsequently solved in O(n3) time. We give a more concise formulation for minsum criteria, and show that general minmax criteria can be minimized in O(n2) time. We present faster algorithms, requiring only O(n+mlog m) time for minimizing makespan and total completion time, O(nlogn) time for minimizing total weighted completion time, maximum lateness, total tardiness and the weighted number of tardy jobs, and O(nlog2n) time for maximum weighted tardiness. In the case of release dates, we propose an O(nlogn) algorithm for minimizing makespan, and an O(mn2m+1) time dynamic programming algorithm for minimizing total completion time. <s> BIB003 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Open problems <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> BIB004 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Open problems <s> We study the problem of minimizing the weighted number of late jobs to be scheduled on a single machine when processing times are equal. In this paper, we show that this problem, as well as its preemptive variant, are strongly polynomial. When preemption is not allowed (1∣pj=p, rj∣ΣwjUj), the problem can be solved in O(n7). In the preemptive case, (1∣pj=p, pmtn, rj ∣ΣwjUj), the problem can be solved in O(n10). Both algorithms are based upon dynamic programming. Copyright © 1999 John Wiley & Sons, Ltd. <s> BIB005 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Open problems <s> The problem of scheduling identical jobs with chain precedence constraints on two uniform machines is considered. It is shown that the corresponding makespan problem can be solved in linear time. <s> BIB006 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Open problems <s> We study the problem of computing a preemptive schedule of equal-length jobs with given release times, deadlines and weights. Our goal is to maximize the weighted throughput. In Graham's notation this problem is described as (1|r"j;p"j=p;pmtn|@?w"jU"j). We provide an O(n^4)-time algorithm, improving the previous bound of O(n^1^0). <s> BIB007 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Open problems <s> In this paper, we study the problem of scheduling n equal-length preemptive jobs on a single machine to minimize total tardiness, subject to release dates. The complexity status of this problem has remained open to date. We provide an O(n2) time algorithm to solve the problem. <s> BIB008
The problem 1|prec| w i C i has been widely studied, and the boundary between polynomial and N P-hard cases is globally well-defined. However, there are still boundaries to defined, as illustrated by the following examples. First, if the fractional dimension f dim of the precedence graph lies in interval ]2, 3[, the problem is open (it is polynomially solvable if f dim ≤ 2 since the fractional dimension of a DAG is less than or equal to the dimension of this DAG and the problem is solvable in polynomial time if the precedence graph is of dimension 2). This is an interesting question but the gap is rather limited. A wider open question is when we consider the problem with equal weights, i.e., 1|prec| C i . The problem is still N P-hard, even if the precedence graph is of indegree at most 2 (see BIB002 ). Nevertheless, we may hope that the problem becomes polynomial for precedence graphs with dimension larger than two. It is also possible that the problem is solvable in polynomial time if the precedence graph is an interval order graph, and even for larger classes like quasi-interval order graphs and over-interval order graphs. For the criteria related to tardiness T j and unit penalty U j , it is surprising to see that preemptive problems with precedence constraints have not been studied yet. More precisely, BIB008 have shown that 1|pmtn, r j , p j = p| T j is solvable in polynomial time, but it is still open whether adding precedence constraints leads this problem to be N P-hard or not; the problem remains also open when considering the more general criterion w j T j . The same outline appears when considering unit penalty: 1|r j ; pmtn; p j = p| w j U j is solvable in polynomial time (with an algorithm in O(n 10 ) by BIB005 , and in O(n 4 ) by BIB007 ); nevertheless, nothing has been shown when adding precedence constraints to the problem. The first research avenue is to study this problem including Chains as a first step and determine whether the problem is polynomial or not. 14 5 Parallel machines without preemption When considering non-preemptive scheduling problems, whatever the structure of precedence graphs, we will mainly focus on problems with equal processing times, since problems P 2||Cmax and P 2|chains| C j are already NP-hard (see BIB001 and BIB004 ). For an arbitrary number of machines and the makespan criterion, the boundary between polynomially solvable and N P-hard problems seems very sharp, we believe that the efforts should not be focused on these problems. When the number of machines is fixed, this boundary is much larger. Surprisingly, to the best of our knowledge, no other structures of precedence graphs than the ones introduced in previous section have been studied for problem Pm|prec, p j = p|Cmax. In our opinion, it could be a good opportunity to work on more general precedence graphs on this problem, to be able to arbitrate if Pm|prec, p j = p|Cmax is solvable in polynomial time or N P-hard. The most natural extension in our opinion is to consider seriesparallel graphs, since it is a generalization of opposing forests, level order graphs and DC-graphs, for which the problem is polynomially solvable. For the total completion time criterion, the two most intriguing problems are P |intree, p j = p| C j and P |outtree, r j , p j = p| C j . For the former problem, the interest lies in the fact that there exists an ideal schedule for outtree precedences, but not for intree precedences. Nevertheless, we do believe that this problem admits an optimal polynomial algorithm. For the latter problem, an algorithm exists for p j = 1 (i.e., release dates are multiple of the processing time, see  ), and hence the gap to p j = p seems small. For a fixed number of uniform parallel machines and the makespan criterion, the set of open problems is wide, since the only polynomial algorithm is for Q2|chains, p j = p|Cmax BIB006 ), and the problem Qm|prec, r j , p j = p|Lmax is still open. The same behavior occurs for the total completion time: BIB003 proved that Qm|r j , p j = p| C j is solvable in polynomial time, and problem Qm|prec, r j , p j = p| C j is still open. We hence believe that this set of problems deserves a deeper study. A first approach may consist in trying to adapt the algorithms available for identical parallel machines.