# On minimizing total tardiness in a serial batching problem

Philippe Baptiste; Antoine Jouglet

RAIRO - Operations Research - Recherche Opérationnelle (2001)

- Volume: 35, Issue: 1, page 107-115
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topBaptiste, Philippe, and Jouglet, Antoine. "On minimizing total tardiness in a serial batching problem." RAIRO - Operations Research - Recherche Opérationnelle 35.1 (2001): 107-115. <http://eudml.org/doc/105232>.

@article{Baptiste2001,

abstract = {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$|\sum 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.},

author = {Baptiste, Philippe, Jouglet, Antoine},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {scheduling; batching; dynamic programming; total tardiness; pseudopolynomial algorithm; scheduling of jobs},

language = {eng},

number = {1},

pages = {107-115},

publisher = {EDP-Sciences},

title = {On minimizing total tardiness in a serial batching problem},

url = {http://eudml.org/doc/105232},

volume = {35},

year = {2001},

}

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

PB - EDP-Sciences

VL - 35

IS - 1

SP - 107

EP - 115

AB - 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$|\sum 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.

LA - eng

KW - scheduling; batching; dynamic programming; total tardiness; pseudopolynomial algorithm; scheduling of jobs

UR - http://eudml.org/doc/105232

ER -

## References

top- [1] S. Albers and P. Brucker, The Complexity of One-Machine Batching Problems. Discrete Appl. Math. 47 (1993) 87-107. Zbl0792.90035MR1256738
- [2] Ph. Baptiste, Batching Identical Jobs, Technical Report, University of Technology of Compiègne (1999). MR1989823
- [3] P. Brucker, Scheduling Algorithms. Springer Lehrbuch (1995). Zbl0839.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. Zbl0909.90172MR1642261
- [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. Zbl0842.90058MR1384656
- [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. Zbl0712.90035MR1087820
- [8] J. Du and J.Y.-T. Leung, Minimizing Total Tardiness on One Machine is NP-Hard. Math. Oper. Res. 15 (1990) 483-495. Zbl0714.90052MR1064213
- [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. Zbl0353.68071
- [11] C.L. Monma and C.N. Potts, On the Complexity of Scheduling with Batch Setup Times. Oper. Res. 37 (1989) 798-804. Zbl0686.90025MR1021421
- [12] C.N. Potts and M.Y. Kovalyov. Scheduling with batching: A review. European J. Oper. Res. 120 (2000) 228-249. Zbl0953.90028MR1785709
- [13] S. Webster and K.R. Baker, Scheduling Groups of Jobs on a Single Machine. Oper. Res. 43 (1995) 692-703. Zbl0857.90062MR1356417

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.