On Minimizing Total Tardiness in a Serial Batching Problem
CNRS, UMR 6599 ,
Université de Technologie de Compiègne,
Centre de Recherches de Royallieu,
60205 Compiègne Cedex, France.
Accepted: November 2000
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 s occurs. This problem 1| s-batch | ∑Ti 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.
Mathematics Subject Classification: 90B35 / 90C39 / 90C27
Key words: Scheduling / batching / dynamic programming / total tardiness.
© EDP Sciences, 2001