# On Minimizing Total Tardiness in a Serial Batching Problem

Philippe Baptiste; Antoine Jouglet

RAIRO - Operations Research (2010)

- 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 35.1 (2010): 107-115. <http://eudml.org/doc/197830>.

@article{Baptiste2010,

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
| ∑Ti 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},

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

language = {eng},

month = {3},

number = {1},

pages = {107-115},

publisher = {EDP Sciences},

title = {On Minimizing Total Tardiness in a Serial Batching Problem},

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

volume = {35},

year = {2010},

}

TY - JOUR

AU - Baptiste, Philippe

AU - Jouglet, Antoine

TI - On Minimizing Total Tardiness in a Serial Batching Problem

JO - RAIRO - Operations Research

DA - 2010/3//

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
| ∑Ti 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; total tardiness

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

ER -

## References

top- S. Albers and P. Brucker, The Complexity of One-Machine Batching Problems. Discrete Appl. Math.47 (1993) 87-107. Zbl0792.90035
- Ph. Baptiste, Batching Identical Jobs, Technical Report, University of Technology of Compiègne (1999).
- P. Brucker, Scheduling Algorithms. Springer Lehrbuch (1995). Zbl0839.90059
- 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.90172
- P. Brucker and S. Knust, Complexity Results of Scheduling Problems.URL: www//mathematik.uni-osnabrueck.de/research/OR/class
- 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.90058
- 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.90035
- J. Du and J.Y.-T. Leung, Minimizing Total Tardiness on One Machine is NP-Hard. Math. Oper. Res.15 (1990) 483-495. Zbl0714.90052
- L. Dupont, Ordonnancements sur machines à traitement par batch (fournée). TSI10 (to appear).
- E.L. Lawler, A ``Pseudopolynomial'' Algorithm for Sequencing Jobs to Minimize Total Tardiness. Ann. Discrete Math.1 (1977) 331-342.
- C.L. Monma and C.N. Potts, On the Complexity of Scheduling with Batch Setup Times. Oper. Res.37 (1989) 798-804. Zbl0686.90025
- C.N. Potts and M.Y. Kovalyov. Scheduling with batching: A review. European J. Oper. Res.120 (2000) 228-249. Zbl0953.90028
- S. Webster and K.R. Baker, Scheduling Groups of Jobs on a Single Machine. Oper. Res.43 (1995) 692-703. Zbl0857.90062

## NotesEmbed ?

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