A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Makespan criterion <s> This paper deals with a new sequencing problem in which n jobs with ordering restrictions have to be done by men of equal ability. Assume every man can do any of the n jobs. The two questions considered in this paper are 1 How to arrange a schedule that requires the minimum number of men so that all jobs are completed within a prescribed time T, and 2 if m men are available, arrange a schedule that completes all jobs at the earliest time. <s> BIB001 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Makespan criterion <s> In 1979, Papadimitriou and Yannakakis gave a polynomial time algorithm for the scheduling of jobs requiring unit completion times when the precedence constraints form an interval order. The authors solve here the corresponding problem, for preemptive scheduling (a job can be interrupted to work on more important tasks, and completed at a later time, subject to the usual scheduling constraints.) The m-machine preemptive scheduling problem is shown to have a polynomial algorithm, for both unit time and variable execution times as well, when the precedence constraints are given by an interval order. <s> BIB002 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Makespan criterion <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> BIB003 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Makespan criterion <s> Abstract In parallel machine scheduling problems with general precedence constraints, it is advantageous to interrupt jobs and complete them at a later time in order to minimize Makespan. For general precedence constraints, we know that this problem is in the class of NP-hard combinatorial problems for which the development of efficient algorithms is unlikely. In this paper we propose two new heuristics SUPIO and INFIO which, respectively, give an upper bound and a lower bound to Makespan. We show numerically that the ratio between these two bounds is very close to one. SUPIO heuristic provides an optimal solution in the following cases: P2 | ,pmnt| C max , P| forest,pmnt| C max and P| interval order,pmnt| C max . Its absolute performance ratio is upper bounded by (2 − 2/ m ). We illustrate the efficiency of our heuristics by computational results associated with randomly generated problems.We show in the conclusion that this new approach could solve some non-preemptive parallel machine scheduling problems. <s> BIB004 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Makespan criterion <s> McNaughton’s theorem (1959) states that preemptions in scheduling arbitrary processing time jobs on identical parallel machines to minimize the total weighted completion time are redundant. Du, Leung and Young (1991) proved that this remains true even though the jobs have precedence constraints in the form of chains. There are known simple counterexamples showing that other extensions of McNaughton’s theorem to other criteria or more general precedence constraints such as intrees or outtrees, or different release dates of jobs, or different speeds of machines, are not true even for equal weights of jobs. In this paper we show that in the case of two machines and unit processing times, preemptions are still advantageous for intrees or machines with different speeds even for equal weights, or outtrees for different weights, but become redundant for outtrees and equal weights even for different release dates. We also conjecture that the latter statement is actually true for any number of machines. <s> BIB005 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Makespan criterion <s> In this paper, we consider the preemptive scheduling problem on a fixed number of identical parallel machines. We present a polynomial-time algorithm for finding a minimal length schedule for an order class which contains properly interval orders. <s> BIB006 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Makespan criterion <s> Scheduling of unit execution time (UET) task systems on parallel machines with minimal schedule length is known to be NP-complete. The problem is polynomially solvable for some special cases. For a fixed number of parallel machines m > 2, the complexity of the problem is still open, but the problem becomes NP-hard if m is arbitrary. In this paper we characterize a new order class that properly contains quasi-interval orders and we prove that the Coffman--Graham algorithm yields optimal schedules for this new class on any number of machines. Finally, some extensions are discussed for a larger order class and for scheduling in the presence of unit communication delays. <s> BIB007 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Makespan criterion <s> Brucker et al. (Math Methods Oper Res 56: 407–412, 2003) have given an O(n 2 )-time algorithm for the problems $$P \mid p_{j}=1, r_{j}$$ , outtree $$\mid \sum C_{j}$$ and $$P \mid pmtn, p_{j}=1, r_{j}$$ , outtree $$\mid \sum C_{j}$$ . In this note, we show that their algorithm admits an O(n log n)-time implementation. Copyright Springer-Verlag 2005 <s> BIB008 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Makespan criterion <s> Abstract We consider a scheduling problem with two identical parallel machines and n jobs. For each job we are given its release date when job becomes available for processing. All jobs have equal processing times. Preemptions are allowed. There are precedence constraints between jobs which are given by a (di)graph consisting of a set of outtrees and a number of isolated vertices. The objective is to find a schedule minimizing mean flow time. We suggest an O( n 2 ) algorithm to solve this problem. The suggested algorithm also can be used to solve the related two-machine open shop problem with integer release dates, unit processing times and analogous precedence constraints. <s> BIB009
Since P |tree, p j = p|Cmax is polynomially solvable (see BIB001 ), by Timkovsky's result, so is P |pmtn, tree|Cmax. The first polynomial algorithm for this problem is proposed in  with a running time of O(n 2 ). An algorithm in O(n log m) was then proposed in Gonzalez and Johnson [1980] . Note that the latter algorithm produces at most O(n) preemptions whereas the former may obtain a schedule with O(nm) preemptions. Lawler [1982] studies the case with release dates and outtree, and shows that it can be solved in O(n 2 ) with a dynamic priority list algorithm (i.e., priorities may change according to what has already been scheduled). Timkovsky's result can not be applied to precedence graphs such as interval order graphs. Yet, it was proven that the problem is also solvable in polynomial time for this precedence structure; first, BIB002 show it for a fixed number of machines P m|pmtn, io|Cmax by using a linear programming approach based on the set of jobs scheduled at each instant. Later BIB004 proposes another linear program that solves the problem for an arbitrary number of machines, i.e., P |pmtn, io|Cmax. For a fixed number m of machines, BIB006 extend the result of BIB002 , by proposing an linear programming approach for Am−order graphs (which properly contain interval order graphs). Other criteria and/or machine environment BIB003 explain that P 2|pmtn, chains| C j is strongly N P-hard by showing that preemption is useless for this problem, that is why we will only focus on the UET case for the total completion time 20 criterion. BIB007 prove that P 2|pmtn, prec, p j = p| C j is solvable in polynomial time by adapting the Coffman-Graham algorithm. Their algorithm finds an ideal schedule. By proving that preemption is redundant, BIB005 prove that P 2|pmtn, outtree, r j , p j = 1| C j is solvable in polynomial time. When the precedence graph is an intree, Coffman Jr et al. [2012] prove that the problem is not ideal, and  provide a deep analysis of the structure of preemption. Using the same methodology than BIB005 ,  show that the problem is solvable in polynomial time with an outtree and an arbitrary number of machines. Moreover, they provide a O(n 2 ) algorithm, that admits a O(n log n) implementation according to BIB008 . BIB009 slightly improves the result of BIB005 and proposes an algorithm of complexity O(n 2 ) for the problem P 2|pmtn, outtree, r j , p j = p| C j .