Assigning jobs to time frames on a single machine to minimizetotal tardiness

This paper deals with a sequencing problem arising in the management of paced flowlines, that is production lines where jobs are released at constant time intervals. The problem is to sequence jobs to minimize total tardiness. The problem can be formulated as an assignment problem with a number of knapsack constraints. We prove the strong NP-hardness of the problem and give a number of lower bounds which are used in a branch-and-bound algorithm. Computational results in realistic settings confirm the eff ectiveness of the procedure developed. The results are particularly interesting with reference to mixed-model assembly lines in which several jobs of few diff erent types are produced periodically.