Article contents
On Minimizing Total Tardiness in a Serial Batching Problem
Published online by Cambridge University Press: 15 August 2002
Abstract
We study the problem of scheduling jobs on a serial batching machineto minimize total tardiness. Jobs of the same batch start and arecompleted simultaneously and the length of a batch equals the sum ofthe processing times of its jobs. When a new batch starts, a constantsetup time s occurs. This problem 1| s-batch| ∑Ti isknown to be NP-Hard in the ordinary sense. In this paper we show thatit is solvable in pseudopolynomial time by dynamic programming.
- Type
- Research Article
- Information
- Copyright
- © EDP Sciences, 2001
References
- 7
- Cited by