One-machine generalized precedence constrained scheduling problems

The authors investigate one-machine scheduling problems subject to generalized precedence constraints which specify that when job precedes job denoted by , the time between the end of job J j and the beginning of job must be at least , but no more than , where . The objective is to minimize makespan. For some very simple precedence relations, the authors present polynomial algorithms. For more complex precedence structures, they establish that the problems are NP-hard. For one of these hard problems, the authors provide heuristics and worst-case bounds.