Department of Industrial Engineering2024-11-0920061432-299410.1007/s00186-005-0014-82-s2.0-32044466907http://dx.doi.org/10.1007/s00186-005-0014-8https://hdl.handle.net/20.500.14288/11635In 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.Operations research and management scienceMathematicsApplied mathematicsJournal Article1432-5217235113900004Q35887