A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Makespan criterion and arbitrary number of machines <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 and arbitrary number of machines <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> BIB002 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Makespan criterion and arbitrary number of machines <s> A basic problem of deterministic scheduling theory is that of scheduling n unit-length tasks on m identical processors subject to precedence constraints so as to meet a given overall deadline. T. C. Hu’s classic “level algorithm” can be used to solve this problem in linear time if the precedence constraints have the form of an in-forest or an out-forest. We show that a polynomial time algorithm for a wider class of precedence constraints is unlikely, by proving the problem to be NP-complete for precedence constraints that are the disjoint union of an in-forest and an out-forest (the “opposing forests” of our title). However, for any fixed value of m we show that this problem can be solved in polynomial time for such precedence constraints. For the special case of $m = 3$ we provide a linear time algorithm. <s> BIB003 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Makespan criterion and arbitrary number of machines <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> BIB004 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Makespan criterion and arbitrary number of machines <s> This paper addresses the problem of scheduling n unit length tasks on m identical machines under certain precedence constraints. The aim is to compute minimal length nonpreemptive schedules. We introduce a new order class which contains properly two rich families of precedence graphs: interval orders and a subclass of the class of series parallel orders. We present a linear time algorithm to find an optimal schedule for this new order class on 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 and arbitrary number of machines <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> Makespan criterion and arbitrary number of machines <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
Three seminal works on parallel machines with precedence constraints are the approaches of BIB001 , BIB002 and BIB004 in which the authors are respectively dealing with trees, interval order graphs and graphs of bounded width. In BIB001 , the author proves that problem P |tree, p j = p|Cmax is polynomially solvable by a list scheduling algorithm where the highest priority is given to the job with the highest level (this strategy is called HLF, for Highest Level First). It is unlikely to find a precedence graph that strictly includes trees for which the problem is solvable in polynomial time, since it was proven in BIB003 that scheduling opposing forest is N P-hard. The hardness of the latter problem is mainly due to the arbitrary number of machines, since it is solvable in polynomial time for any fixed number of machines. In BIB002 , the authors prove that problem P |io, p j = p|Cmax is polynomially solvable by a list scheduling algorithm where the highest priority is given to the job with the largest number of successors. This result has been improved twice; first BIB005 shows that the same algorithm gives an optimal solution if interval order graphs are replaced by quasi-interval order graphs, that properly contains the former. BIB007 show that the same result does not stand for over-interval order graphs, but the Coffman-Graham algorithm (see BIB006 ) can be applied to solve problem P |oio, p j = p|Cmax to optimality.