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
topHow 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.
- Ph. Baptiste, Batching Identical Jobs, Technical Report, University of Technology of Compiègne (1999).
- P. Brucker, Scheduling Algorithms. Springer Lehrbuch (1995).
- 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.
- 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.
- 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.
- J. Du and J.Y.-T. Leung, Minimizing Total Tardiness on One Machine is NP-Hard. Math. Oper. Res.15 (1990) 483-495.
- 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.
- C.N. Potts and M.Y. Kovalyov. Scheduling with batching: A review. European J. Oper. Res.120 (2000) 228-249.
- S. Webster and K.R. Baker, Scheduling Groups of Jobs on a Single Machine. Oper. Res.43 (1995) 692-703.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.