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

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

How to cite

top

Baptiste, 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. [1] S. Albers and P. Brucker, The Complexity of One-Machine Batching Problems. Discrete Appl. Math. 47 (1993) 87-107. Zbl0792.90035MR1256738
  2. [2] Ph. Baptiste, Batching Identical Jobs, Technical Report, University of Technology of Compiègne (1999). MR1989823
  3. [3] P. Brucker, Scheduling Algorithms. Springer Lehrbuch (1995). Zbl0839.90059
  4. [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. [5] P. Brucker and S. Knust, Complexity Results of Scheduling Problems. URL: www//mathematik.uni-osnabrueck.de/research/OR/class 
  6. [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. [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. [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. [9] L. Dupont, Ordonnancements sur machines à traitement par batch (fournée). TSI 10 (to appear). 
  10. [10] E.L. Lawler, A “Pseudopolynomial” Algorithm for Sequencing Jobs to Minimize Total Tardiness. Ann. Discrete Math. 1 (1977) 331-342. Zbl0353.68071
  11. [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. [12] C.N. Potts and M.Y. Kovalyov. Scheduling with batching: A review. European J. Oper. Res. 120 (2000) 228-249. Zbl0953.90028MR1785709
  13. [13] S. Webster and K.R. Baker, Scheduling Groups of Jobs on a Single Machine. Oper. Res. 43 (1995) 692-703. Zbl0857.90062MR1356417

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.