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

Abstract

top
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.

How to cite

top

Baptiste, 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
  1. S. Albers and P. Brucker, The Complexity of One-Machine Batching Problems. Discrete Appl. Math.47 (1993) 87-107.  Zbl0792.90035
  2. Ph. Baptiste, Batching Identical Jobs, Technical Report, University of Technology of Compiègne (1999).  
  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.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.  Zbl0842.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.  Zbl0712.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.  Zbl0714.90052
  9. L. Dupont, Ordonnancements sur machines à traitement par batch (fournée). TSI10 (to appear).  
  10. E.L. Lawler, A ``Pseudopolynomial'' Algorithm for Sequencing Jobs to Minimize Total Tardiness. Ann. Discrete Math.1 (1977) 331-342.  
  11. C.L. Monma and C.N. Potts, On the Complexity of Scheduling with Batch Setup Times. Oper. Res.37 (1989) 798-804.  Zbl0686.90025
  12. C.N. Potts and M.Y. Kovalyov. Scheduling with batching: A review. European J. Oper. Res.120 (2000) 228-249.  Zbl0953.90028
  13. S. Webster and K.R. Baker, Scheduling Groups of Jobs on a Single Machine. Oper. Res.43 (1995) 692-703.  Zbl0857.90062

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.