One-machine generalized precedence constrained scheduling problems

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