A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Other criteria and/or machine environment <s> We show that unit execution time jobs subject to a precedence constraint whose complement is chordal can be scheduled in linear time on m processors. Generalizations to arbitrary execution times are NP-complete. <s> BIB001 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Other criteria and/or machine environment <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> BIB002 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Other criteria and/or machine environment <s> An O(n3/(b+1)) time algorithm to obtain a minimum finish time schedule subject to tree-like precedence constraints for unit-time tasks on two uniform processors is obtained. It is assumed that the slower processor takesb time units for each one taken by the speedier one, for some integerb. It is also noted that a slight modification of this schedule yields a minimum mean flow time schedule. <s> BIB003 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Other criteria and/or machine environment <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> BIB004 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Other criteria and/or machine environment <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> Other criteria and/or machine environment <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> BIB006 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Other criteria and/or machine environment <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> BIB007 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Other criteria and/or machine environment <s> We consider the problem of scheduling a set of n unit-execution-time (UET) tasks, with precedence constraints, on m ≥ 1 parallel and identical processors so as to minimize the mean flow time. For two processors, the Coffman--Graham algorithm gives a schedule that simultaneously minimizes the mean flow time and the makespan. The problem becomes strongly NP-hard for an arbitrary number of processors, although the complexity is not known for each fixed m ≥ 3. For arbitrary precedence constraints, we show that the Coffman--Graham algorithm gives a schedule with a worst-case bound no more than 2, and we give examples showing that the bound is tight. For intrees, the problem can be solved in polynomial time for each fixed m ≥ 1, although the complexity is not known for an arbitrary number of processors. We show that Hu's algorithm (which is optimal for the makespan objective) yields a schedule with a worst-case bound no more than 1.5, and we give examples showing that the ratio can approach 1.308999. <s> BIB008
The other well-studied criterion for parallel machine environment is the total completion time C j . One of the reasons for that is that, for some problems, it is equivalent to solve the total completion time and the makespan since they admit an ideal schedule. For example, ideal schedules exist when considering two machines, arbitrary precedence constraints and equal processing times, hence problem P 2|prec, p j = p| C j is polynomially solvable with CG-algorithm (see BIB006 ). When adding release dates, BIB005 show that P 2|prec, r j , p j = 1| C j is solvable in polynomial time by reducing it to a shortest path problem. For an arbitrary number of machines, if the precedence graph forms an outtree and the processing times are UET, the same result holds and hence P |outtree, p j = p| C j is solvable in polynomial time. Note that problem P 3|intree, p j = p| C j is not ideal, see BIB008 for a counterexample. Nevertheless, for any fixed number of machines, problem P m|intree, p j = p| C j is solvable in polynomial time (see  ). Adding release dates maintains the same property: the algorithm proposed in  solves simultaneously problems P |outtree, r j , p j = 1|Cmax and P |outtree, r j , p j = 1| C j . An improvement of this algorithm has been proposed in BIB007 . For interval order graphs, BIB002 notices that P |io, p j = p| C j is solvable in polynomial time since the proof of the algorithm for P |io, p j = p|Cmax (in BIB001 ) only uses swaps between tasks, and this property is verified by the makespan and the total completion time. It has been noticed recently that the same result holds for overinterval orders (that properly contain interval orders), the problem admits also an ideal solution, so P |oio, p j = p| C j is solvable in polynomial time (see  ). When considering uniform parallel machines, only few results are available; problem Q2|chains, p j = p|Cmax is solvable in polynomial time (see BIB004 ). If one processor is going b times faster than the other (with b an integer), the problem Q2|tree, p j = p|Cmax is also polynomially solvable (see BIB003 ); the problem is also ideal, and hence Q2|tree, p j = p| C j is also solvable in polynomial time.