On minimizing total tardiness in a serial batching problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 35 (2001) no. 1, pp. 107-115.

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|∑T i 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.

Classification : 90B35, 90C39, 90C27
Mots-clés : scheduling, batching, dynamic programming, total tardiness 
@article{RO_2001__35_1_107_0,
     author = {Baptiste, Philippe and Jouglet, Antoine},
     title = {On minimizing total tardiness in a serial batching problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {107--115},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {1},
     year = {2001},
     mrnumber = {1841817},
     zbl = {0991.90062},
     language = {en},
     url = {http://archive.numdam.org/item/RO_2001__35_1_107_0/}
}
TY  - JOUR
AU  - Baptiste, Philippe
AU  - Jouglet, Antoine
TI  - On minimizing total tardiness in a serial batching problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2001
SP  - 107
EP  - 115
VL  - 35
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/RO_2001__35_1_107_0/
LA  - en
ID  - RO_2001__35_1_107_0
ER  - 
%0 Journal Article
%A Baptiste, Philippe
%A Jouglet, Antoine
%T On minimizing total tardiness in a serial batching problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2001
%P 107-115
%V 35
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/item/RO_2001__35_1_107_0/
%G en
%F RO_2001__35_1_107_0
Baptiste, Philippe; Jouglet, Antoine. On minimizing total tardiness in a serial batching problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 35 (2001) no. 1, pp. 107-115. http://archive.numdam.org/item/RO_2001__35_1_107_0/

[1] S. Albers and P. Brucker, The Complexity of One-Machine Batching Problems. Discrete Appl. Math. 47 (1993) 87-107. | MR | Zbl

[2] Ph. Baptiste, Batching Identical Jobs, Technical Report, University of Technology of Compiègne (1999). | MR

[3] P. Brucker, Scheduling Algorithms. Springer Lehrbuch (1995). | Zbl

[4] P. Brucker, A. Gladky, H. Hoogeveen, M. Kovalyov, C. Potts, T. Tautenhahn and S. Van De Velde, Scheduling a Batching Machine. J. Sched. 1 (1998) 31-54. | MR | Zbl

[5] P. Brucker and S. Knust, Complexity Results of Scheduling Problems. URL: www//mathematik.uni-osnabrueck.de/research/OR/class

[6] P. Brucker and M.Y. Kovalyov, Single machine batch scheduling to minimize the weighted number of late jobs. Math. Methods Oper. Res. 43 (1996) 1-8. | MR | Zbl

[7] E.G. Coffman, M. Yannakakis, M.J. Magazine and C. Santos, Batch sizing and sequencing on a single machine. Ann. Oper. Res. 26 (1990) 135-147. | MR | Zbl

[8] J. Du and J.Y.-T. Leung, Minimizing Total Tardiness on One Machine is NP-Hard. Math. Oper. Res. 15 (1990) 483-495. | MR | Zbl

[9] L. Dupont, Ordonnancements sur machines à traitement par batch (fournée). TSI 10 (to appear).

[10] E.L. Lawler, A “Pseudopolynomial” Algorithm for Sequencing Jobs to Minimize Total Tardiness. Ann. Discrete Math. 1 (1977) 331-342. | Zbl

[11] C.L. Monma and C.N. Potts, On the Complexity of Scheduling with Batch Setup Times. Oper. Res. 37 (1989) 798-804. | MR | Zbl

[12] C.N. Potts and M.Y. Kovalyov. Scheduling with batching: A review. European J. Oper. Res. 120 (2000) 228-249. | MR | Zbl

[13] S. Webster and K.R. Baker, Scheduling Groups of Jobs on a Single Machine. Oper. Res. 43 (1995) 692-703. | MR | Zbl