A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> 11 <s> Abstract We investigate the computational complexity of deterministic sequencing problems in which unit-time jobs have to be scheduled on a single machine subject to chain-like precedence constraints. NP-hardness is established for the cases in which the number of late jobs or the total weighted tardiness is to be minimized, and for several related problems involving the total weighted completion time criterion. <s> BIB001 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> 11 <s> The problem of minimizing the total tardiness for a set of unit-processing-time jobs on a single machine is considered. J. K. Lenstra and A. H. G. Rinnooy Kan have shown that the problem is NP-hard if the jobs have arbitrary precedence constraints. They asked whether the problem remains NP-hard for tree-structured precedence constraints. In this paper we show that the problem is NP-hard even for a set of chains. Our result gives a sharp boundary for the complexity of this problem, since there is a simple, polynomial-time algorithm for a set of independent jobs. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499. <s> BIB002
4 Single machine problems For single machine problems, most of the interesting results for this survey are related to the total weighted completion time w j C j . It is mainly due to the fact that 1|chains, p j = 1| U j (see BIB001 ) and 1|chains, p j = 1| T j (see BIB002 ) are already N P-hard, while 1|prec, r j |Cmax is solvable in polynomial time. Nevertheless, as we will see in Section 4.3, there are some interesting open problems for other criteria when considering preemption.