A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Polynomial cases <s> A one-machine deterministic job-shop sequencing problem is considered. Associated with each job is its processing time and linear deferral cost. In addition, the jobs are related by a general precedence relation. The objective is to order the jobs so as to minimize the sum of the deferral costs, subject to the constraint that the ordering must be consistent with the precedence relation. A decomposition algorithm is presented, and it is proved that a permutation is optimal if and only if it can be generated by this algorithm. Four special network structures are then considered, and specializations of the general algorithm are presented. <s> BIB001 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Polynomial cases <s> Suppose n jobs are to be sequenced for processing by a single machine, with the object of minimizing total weighted completion time. It is shown that the problem is NP-complete if there are arbitrary precedence constraints. However, if precedence constraints are “series parallel”, the problem can be solved in O( n log n ) time. This result generalizes previous results for the more special case of rooted trees. It is also shown how a decomposition procedure suggested by Sidney can be implemented in polynomial-bounded time. Equivalence of the sequencing problem with the optimal linear ordering problem for directed graphs is discussed. <s> BIB002 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Polynomial cases <s> This paper considers single-machine scheduling problems with deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. In addition, the jobs are related by a series-parallel graph. It is shown that for the general linear problem to minimize the makespan, polynomial algorithms exist. It is also shown that for the proportional linear problem of minimization of the total weighted completion time, polynomial algorithms exist, too. <s> BIB003 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Polynomial cases <s> We consider various single machine scheduling problems in which the processing time of a job depends either on its position in a processing sequence or on its start time. We focus on problems of minimizing the makespan or the sum of (weighted) completion times of the jobs. In many situations we show that the objective function is priority-generating, and therefore the corresponding scheduling problem under series-parallel precedence constraints is polynomially solvable. In other situations we provide counter-examples that show that the objective function is not priority-generating. <s> BIB004 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> Polynomial cases <s> Abstract In this paper we consider single-machine scheduling problems with position-dependent processing times, i.e., jobs whose processing times are an increasing or decreasing function of their positions in a processing sequence. In addition, the jobs are related by parallel chains and a series–parallel graph precedence constraints, respectively. It is shown that for the problems of minimization of the makespan polynomial algorithms exist. <s> BIB005
Lawler [1978] uses Sidney's theory BIB001 ) to derive a polynomial-time algorithm to solve problem 1|sp − graph| w i C i . The most important results are based on the concept of a module in a precedence graph G = (N, A): A non-empty subset M ⊂ N is a module if, for each job j ∈ N − M , exactly one of the three conditions holds: 1. j must precede every job in M , 2. j must follow every job in M , 3. j is not constrained to any job in M . Using this concept leads to a very powerful theorem stating that there exists an optimal sequence consistent with any optimal sequence of any module. A large improvement on this problem has been done recently, by using order theory and by proving that the problem is a special case of the vertex cover problem. More precisely, in Correa and Schulz [2005] the authors conjecture that 1|prec| w j C j is a special case of vertex cover and prove that, under this conjecture, the problem 1|prec| w j C j is polynomial if the precedence graph is of dimension 2. In Ambühl and Mastrolilli [2009] , the authors prove the conjecture and hence the result provided in BIB002 is considerably extended (since series-parallel graphs are strictly included in DAGs of dimension 2). Using the same methodology as in BIB002 , BIB003 extend these results to the case where jobs are deteriorating, i.e., processing times are an increasing function of their starting time, and they show that 1|sp − graph, p solved in a polynomial time, where p j , a, and α j are positive constants and t is the starting time of the job. The same framework is used in BIB005 for position-dependent processing times, and the authors show that 1|sp − graph, p where r is the position of the job, a j and b j positive constants, are polynomially solvable. BIB004 propose a more general framework than the one introduced in BIB003 , that was first presented in Monma and Sidney [1979] . They extend it to different models with deterioration and learning, that were aimed at minimizing either the total weighted completion time or the makespan, with series-parallel precedence constraints.  