On minimizing total tardiness in a serial batching problem

Authors
Baptiste, P Jouglet, A
Citation
P. Baptiste et A. Jouglet, On minimizing total tardiness in a serial batching problem, RAIRO RE OP, 35(1), 2001, pp. 107-115
Citations number
13
Categorie Soggetti
Engineering Mathematics
Journal title
RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH
ISSN journal
03990559 → ACNP
Volume
35
Issue
1
Year of publication
2001
Pages
107 - 115
Database
ISI
SICI code
0399-0559(200101/03)35:1<107:OMTTIA>2.0.ZU;2-L
Abstract
We study the problem of scheduling jobs on a serial batching machine to min imize total tardiness. Jobs of the same batch start and are completed simul taneously 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\SigmaT(i) is known to be NP-Hard in the ordinary sense. I n this paper we show that it is solvable in pseudopolynomial time by dynami c programming.