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

Abstract

n this paper we study the single-machine problem 1 vertical bar chains(1), p(j) = p vertical bar Sigma 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.