Assigning jobs to time frames on a single machine to minimize total 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 effectiveness of the procedure developed. The results are particularly interesting with reference to mixed-model assembly lines in which several jobs of few different types are produced periodically.