On the application of insertion techniques for job shop problems with setup times

Yuri N. Sotskov; Thomas Tautenhahn; Frank Werner

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

  • Volume: 33, Issue: 2, page 209-245
  • ISSN: 0399-0559

How to cite


Sotskov, Yuri N., Tautenhahn, Thomas, and Werner, Frank. "On the application of insertion techniques for job shop problems with setup times." RAIRO - Operations Research - Recherche Opérationnelle 33.2 (1999): 209-245. <http://eudml.org/doc/105190>.

author = {Sotskov, Yuri N., Tautenhahn, Thomas, Werner, Frank},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {job shop scheduling; setup times; constructive heuristics},
language = {eng},
number = {2},
pages = {209-245},
publisher = {EDP-Sciences},
title = {On the application of insertion techniques for job shop problems with setup times},
url = {http://eudml.org/doc/105190},
volume = {33},
year = {1999},

AU - Sotskov, Yuri N.
AU - Tautenhahn, Thomas
AU - Werner, Frank
TI - On the application of insertion techniques for job shop problems with setup times
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1999
PB - EDP-Sciences
VL - 33
IS - 2
SP - 209
EP - 245
LA - eng
KW - job shop scheduling; setup times; constructive heuristics
UR - http://eudml.org/doc/105190
ER -


  1. 1. J. ADAMS, E. BALAS and D. ZAWACK, The Shifting Bottleneck Procedure for Job Shop Scheduling, Management Sci., 1988, 34, p.391-401. Zbl0637.90051MR938771
  2. 2. S. ALBERS and P. BRUCKER, The Complexity of One-Machine Batching Problems, Discrete Appl. Math., 1993, 47, p. 87-107. Zbl0792.90035MR1256738
  3. 3. J. D. ALLISON, Combining Petrov's Heuristic and the CDS Heuristic in Group Scheduling problems, Computers Ind. Engng., 1990, 19, p. 457-461. 
  4. 4. D. APPLEGATE and W. COOK, A Computational Study of The Job-Shop Scheduling Problem, ORSA J. Computing, 1991, 3, p. 149-156. Zbl0755.90039
  5. 5. K. R. BAKER, Scheduling The Production of Components at a Common Facility, IEE Transactions, 1988, 20, p. 32-35. 
  6. 6. J. N. BLACKSTONE, D. T. PHILIPS and C. L. HOGG, A State-of-the-Art Survey of Manufacturing Job Shop Operations, International Journal of Production Research, 1982, 20, p. 27-45. 
  7. 7. H. BRASEL, T. TAUTENHAHN and F. WERNER, Constructive Heuristic Algorithms for the Open Shop Problem, Computing, 1993, 51, p. 95-110. Zbl0796.90031
  8. 8. P. BRUCKER B. JURISCH and B. SIEVERS, A Branch and Bound Algorithm for the Job-Shop Problem, Discrete Appl Math., 1994, 49, p. 107-127. Zbl0802.90057MR1272483
  9. 9. P. BRUCKER and O. THIELE, A Branch and Bound Method for the General-Shop Problem with Sequence-Dependent Setup-Times, OR Spektrum, 1996 (to appear). Zbl0852.90087MR1397929
  10. 10. J. CARLIER and E. PINSON, An Algorithm for Solving the Job-Shop Problem, Management Sci., 1989, 35, p. 164-176. Zbl0677.90036MR985230
  11. 11. G. DOBSON, U. S. KAMARKAR and J. L. RUMMEL, Batching to Minimize Flow Times on One Machine, Management Sci., 1987, 33, p. 784-799. Zbl0624.90047
  12. 12. M. R. GAREY R. TARJAN and G. WILFONG, One Machine Processor Scheduling with Symmetric Earliness and Tardiness Penalties, Mathematics of Operations Research, 1988, 13, p. 330-348. Zbl0671.90033MR942622
  13. 13. J. N. D. GUPTA, Single Facility Scheduling with Multiple Job Classes, European J. Oper. Res., 1988, 33, p. 42-45. Zbl0648.90040
  14. 14. W. S. GERE, Heuristics in Job Shop Scheduling, Management Sci., 1996, 13, p. 167-190. 
  15. 15. R. E. GRAHAM, E. L. LAWLER and J. K. LENSTRA, A. H. G. RINNOOY KAN, Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey, Annals Discr. Math., 1979, 5, p. 287-326. Zbl0411.90044MR558574
  16. 16. R. HAUPT, A Survey of Scheduling Rules, Operations Research, 1989, 25, p. 45-61. MR443969
  17. 17. N. ISHII and J. T. TALAVAGE, A Mixed Dispatching Rule Approach in FMS Scheduling, International J. Flexible Manufacturing Systems, 1994, p. 69-87. 
  18. 18. U. KLEINAU, Two-Machine Shop Scheduling Problems with Batch Processing, Math. Comput. Modelling, 1993, 17, p. 55-63. Zbl0776.90037MR1214314
  19. 19. R. KUIK, M. SALOMON and L. Van WASSENHOVE, Batching Decisions: Structure and Models, European J. Oper. Res., 1994, 75, p. 243-263. 
  20. 20. P. J. M. Van LAARHOVEN E. H. L. AARTS and J. K. LENSTRA, Job Shop Scheduling by Simulated Annealing, Operations Res., 1992, 40, p. 113-125. Zbl0751.90039MR1152731
  21. 21. J. K. LENSTRA, A. H. G. RINNOOY KAN and P. BRUCKER, Complexity of Machine Scheduling Problems, Annals of Discrete Mathematics, 1977, 1, p. 343-362 Zbl0353.68067MR456421
  22. 22. B. L. MACCARTHY and J. LIU, Adressing the Gap in Scheduling Research: A Review of Optimization and Heuristic Methods in Production Research, International J. Production Research, 1993, 31, p. 59-79. 
  23. 23. C. L. MONMA, C. N. POTTS, On the Complexity of Scheduling with Batch Setup Times, Operations Research, 1989, 37, p. 788-803. Zbl0686.90025MR1021421
  24. 24. J. F. MUTH and G. L. THOMPSON, Industrial Scheduling, Prentice Hall, Englewood Cliffs, NJ, 1963. 
  25. 25. N. NADDEF and C. SANTOS, One-Pass Batching Algorithms for the One-Machine Problem, Discrete Appl. Math., 1988, 21, p. 133-145. Zbl0661.90044MR959425
  26. 26. M. NAWAZ, E. E. ENSCORE and I. HAM, A Heuristic Algorithm for the m-Machine, n-Job Flow Shop Sequencing Problem, OMEGA, 1983, 11, p. 91-95. 
  27. 27. E. NOWICKI and C. SMUTNICKI, A Fast Taboo Search Algorithm for the Job Shop Problem, TU Wroclav, Preprint 8/93, 1993. Zbl0880.90079
  28. 28. P. S. Ow and T. E. MORTON, The Single Machine Early/Tardy Problem, Management Sci., 1989, 5, p. 177-191. Zbl0666.90043MR985231
  29. 29. E. PESCH, Machine Learning by Schedule Decomposition, University of Limburg, 1993. 
  30. 30. S. S. PANWALKAR and W. ISKANDER, A Survey of Scheduling Rules, Operations Res., 1977, 25, p. 25-61. Zbl0369.90054MR443969
  31. 31. C. SANTOS and M. MAGAZINE, Batching in Single Operation Manufacturing Systems, Operations Research Letters, 1985, 4, p. 99-103. Zbl0572.90051
  32. 32. Y. N. SOTSKOV, T. TAUTENHAHN and F. WERNER, Heuristics for Permutation Flow Shop Scheduling with Batch Setup Times, OR Spektrum, 1996, 18, p. 67-80. Zbl0858.90079
  33. 33. E. TAILLARD, Benchmarks for Basic Scheduling Problems, European J. Oper, Res., 1993, 64, p. 278-285. Zbl0769.90052
  34. 34. A. J. VAKHARIA and Y.-L. CHANG, A Simulated Annealing Approach to Scheduling a Manufacturing Cell, Naval Res. Log. Quart., 1990, 37, p. 559-577. Zbl0701.90049MR1066197
  35. 35. L. Van WASSENHOVE and C. N. POTTS, Integrating Scheduling with Batching and Lot Sizing: A Review of Algorithms and Complexity, Journal. Oper. Res. Soc., 1992, 43, p. 395-406. Zbl0756.90050MR1180033
  36. 36. S. WEBSTER and K. R. BAKER, Scheduling Groups of Jobs on a Single Machine, Operations Research, 1995, 4, p. 692-703. Zbl0857.90062MR1356417
  37. 37. F. WERNER and A. WINKLER, Insertion Techniques for the Heuristic Solution of the Job Shop Problem, Discrete Appl. Math., 1995, 58, p. 191-211. Zbl0833.90073MR1331171

NotesEmbed ?


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.