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},
     zbl = {0991.90062},
     mrnumber = {1841817},
     language = {en},
     url = {http://www.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
DA  - 2001///
SP  - 107
EP  - 115
VL  - 35
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/RO_2001__35_1_107_0/
UR  - https://zbmath.org/?q=an%3A0991.90062
UR  - https://www.ams.org/mathscinet-getitem?mr=1841817
LA  - en
ID  - RO_2001__35_1_107_0
ER  - 
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://www.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 1256738 | Zbl 0792.90035

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

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

[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 1642261 | Zbl 0909.90172

[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 1384656 | Zbl 0842.90058

[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 1087820 | Zbl 0712.90035

[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 1064213 | Zbl 0714.90052

[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 0353.68071

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

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

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