A procedure for the one-machine sequencing problem with dependent jobs

The problem of minimizing the makespan on one machine with possible dependencies between jobs is considered. We enlarge the notion of precedence constraint by considering a minimal duration between the start times of each pair of dependent jobs. We propose an exact algorithm where this duration is taken into account. This algorithm is based on Carlier's algorithm, closely related to that of McMahon and Florian, for the One-Machine Sequencing problem with independent jobs. Computational results are reported showing the efficiency of our procedure.