Scheduling chains with identical jobs and constant delays on a single machine

In this paper we study the single-machine problem 1|chains(l), p j =p|∑ C j in which jobs with constant processing times and generalized precedence constraints in form of chains with constant delays are given. One has to schedule the jobs on a single machine such that all delays between consecutive jobs in a chain are satisfied and the sum of all completion times of the jobs is minimized. We show that this problem is polynomially solvable. Copyright Springer-Verlag 2006