On Minimizing Total Tardiness in a Serial Batching Problem
Philippe Baptiste, Antoine Jouglet (2010)
RAIRO - Operations Research
Similarity:
We study the problem of scheduling jobs on a serial batching machine to minimize total tardiness. Jobs of the same batch start and are completed simultaneously and the length of a batch equals the sum of the processing times of its jobs. When a new batch starts, a constant setup time occurs. This problem | ∑ is known to be NP-Hard in the ordinary sense. In this paper we show that it is solvable in pseudopolynomial time by dynamic programming.