Skip to main content
SpringerLink
Log in

Heuristics for permutation flow shop scheduling with batch setup times

  • Theoretical Papers
  • Published:
Operations-Research-Spektrum Aims and scope Submit manuscript

Abstract

In this paper we consider permutation flow shop scheduling problems with batch setup times. Each job has to be processed on each machine once and the technological routes are identical for all jobs. The set of jobs is divided into groups. There are given processing timest ij of jobi on machinej and setup timess rj on machinej when a job of ther-th group is processed after a job of another group. It is assumed that the same job order has to be chosen on each machine. We consider both the problems of minimizing the makespan and of minimizing the sum of completion times, where batch or item availability of the jobs is assumed. For these problems we give various constructive and iterative algorithms. The constructive algorithms are based on insertion techniques combined with beam search. We introduce suitable neighbourhood structures for such problems with batch setup times and describe iterative algorithms that are based on local search and reinsertion techniques. The developed algorithms have been tested on a large collection of problems with up to 80 jobs.

Zusammenfassung

In dieser Arbeit werden Permutationsflußprobleme mit Batch Setup Zeiten betrachtet. Jeder Job hat die gleiche technologische Reihenfolge. Die Jobs sind in Gruppen eingeteilt. Gegeben sind Bearbeitungszeient ij für Jobi auf Maschinej sowie Setup Zeitens rj auf Maschinej, wenn ein Job derr-ten Gruppe nach einem Job einer anderen Gruppe bearbeitet wird. Es wird vorausgesetzt, daß auf allen Maschinen die gleiche Reihenfolge der Jobs gewählt wird. In der Arbeit werden sowohl das Problem der Minimierung der Gesamtbearbeitungszeit als auch das Problem der Minimierung der Summe der Bearbeitungsendtermine mit Item oder Batch Verfügbarkeit betrachtet. Für diese Probleme werden konstruktive und iterative Algorithmen entwickelt. Die konstruktiven Algorithmen basieren auf Einfügungstechniken mit Beamsuche. Es werden geeignete Nachbarschaftsstrukturen eingeführt und auf lokaler Suche und Wiedereinfügungstechniken basierende iterative Algorithmen entwickelt. Die Algorithmen wurden an Beispielen mit bis zu 80 Jobs getestet.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Albers S, Brucker P (1993) The Complexity of One-Machine Batching Problems. Discr Appl Math 47:87–107

    Google Scholar 

  2. Allison JD (1990) Combining Petrov's Heuristic and the CDS Heuristic in Group Scheduling Problems. Comput Ind. Eng 19:457–461

    Google Scholar 

  3. Baker KR (1988) Scheduling the Production of Components at a Common Facility. IEE Transact 20:32–35

    Google Scholar 

  4. Bräsel H, Tautenhahn T, Werner F (1993) Constructive Heuristic Algorithms for the Open Shop Problem. Computing 51:95–110

    Google Scholar 

  5. Campbell HG, Dudek RA, Smith ML (1970) A Heuristic Algorithm for then-Job,m-Machine Sequencing Problem. Manag Sci 16:630–637

    Google Scholar 

  6. Chen WH, Sristava B (1994) Simulated Annealing Procedures for Forming Machine Cells in Group Technology. Eur J Oper Res 75:100–111

    Google Scholar 

  7. Cleveland GA, Smith SF (1989) Using Genetic Algorithms to Schedule Flow Shop Releases, In: Schaeffer JD (ed) Proceedings of the third international conference on genetic algorithms. Morgan Kaufmann, San Mateo, pp 160–169

    Google Scholar 

  8. Dannenbring DG (1977) An Evaluation of Flow Shop Sequencing Heuristics. Manag Sci 23:1273–1283

    Google Scholar 

  9. Dobson G, Kamarkar US, Rummel JL (1987) Batching to Minimize Flow Times on One Machine. Manag Sci 33:784–799

    Google Scholar 

  10. Domschke W, Forst P, Voss S (1992) Tabu Search Techniques for the Quadratic Semi-Assignment Problem. In: Fandel G, Gulledge T, Jones A (eds) New Directions for Operations Research in Manufacturing. Springer, Berlin, pp 389–405

    Google Scholar 

  11. Dudek RA, Panwalkar SS, Smith ML (1992) The Lessons of Flowshop Scheduling Research. Oper Res 40:7–13

    Google Scholar 

  12. Garey MR, Johnson DS, Sethi R (1976) The Complexity of Flowshop and Jobshop Scheduling. Math Oper Res 1:117–129

    Google Scholar 

  13. Glass CA, Potts CN (1994) A Comparison of Local Search Methods for Flow Shop Scheduling. Working Paper, University of Southampton

  14. Glover F (1989) Tabu Search — Part I. ORSA J Comput 1:190–206

    Google Scholar 

  15. Glover F (1990) Tabu Search — Part II. ORSA J Comput 2:4–32

    Google Scholar 

  16. Grabowski J (1982) A New Algorithm of Solving the Flow Shop Problem, In: Feichtinger G, Kall P (eds) Operations Research in Progress. Reidel, Dordrecht, pp 57–75

    Google Scholar 

  17. Gupta JND (1988) Single Facility Scheduling with Multiple Job Classes. Eur J Oper Res 33:42–45

    Google Scholar 

  18. Hitomi K, Ham I (1976) Operations Scheduling for Group Technology. CIRP Annals 25:419–422

    Google Scholar 

  19. Ho JC, Chang YL (1991) A New Heuristic for then-Job,m-Machine Flow-Shop Problem. Eur J Oper Res 52:194–202

    Google Scholar 

  20. Ignall E, Schrage L (1965) Application of the Branch and Bound Technique to Some Flow-Shop Scheduling Problems. Oper Res 13:400–412

    Google Scholar 

  21. Johnson SM (1954) Optimal Two- and Three-Stage Production Scheduling with Setup Times Included. Naval Res Logist Quart 1:61–68

    Google Scholar 

  22. Kleinau U (1993) Two-Machine Shop Scheduling Problems with Batch Processing. Math Comput Modelling 17:55–63

    Google Scholar 

  23. Kuik R, Salomon M, van Wassenhove L (1994) Batching Decisions: Structure and Models. Eur J Oper Res 75:243–263

    Google Scholar 

  24. Kusiak A, Chow WS (1988) Decomposition of Manufacturing Systems. IEEE J Robotics and Automation 4/5:457–471

    Google Scholar 

  25. van Laarhoven PJM, Aarts EHL (1987) Simulated Annealing: Theory and Applications. Reidel, Dordrecht

    Google Scholar 

  26. Lenstra JK, Rinnooy Kan AHG, Brucker P (1977) Complexity of Machine Scheduling Problems. Ann Discr Math 1:343–362

    Google Scholar 

  27. MacCarthy BL, Liu J (1993) Addressing the Gap in Scheduling Research: A Review of Optimization and Heuristic Methods in Production Research. Int J Prod Res 31:59–79

    Google Scholar 

  28. Monma CL, Potts CN (1989) On the Complexity of Scheduling with Batch Setup Times. Oper Res 37:788–803

    Google Scholar 

  29. Naddef D, Santos C (1988) One-Pass Batching Algorithms for the One-Machine Problem. Discr Appl Math 21:133–145

    Google Scholar 

  30. Nawaz M, Enscore EE, Ham I (1983) A Heuristic Algorithm for them-Machine,n-Job Flow Shop Sequencing Problem. OMEGA 11:91–95

    Google Scholar 

  31. Osman IH, Potts CN (1989) Simulated Annealing for Permutation Flow-Shop Scheduling. OMEGA 17:551–557

    Google Scholar 

  32. Ow PS, Morton TE (1989) The Single Machine Early/Tardy Problem. Manag Sci 35:177–191

    Google Scholar 

  33. Pinto PA, Rao BM (1992) Joint Lot-Sizing and Scheduling for Multi-Stage Multi-Product Flow Shops. Int J Prod Res 30:1137–1152

    Google Scholar 

  34. Reeves CR (1993) Improving the Efficiency of Tabu Search for Machine Sequencing Problems. J Oper Res Soc 44:375–382

    Google Scholar 

  35. Santos C, Magazine M (1985) Batching in Single Operation Manufacturing Systems. Oper Res Lett 4:99–103

    Google Scholar 

  36. Shanthikumar JG, Wu YB (1985) Decomposition Approaches in Permutation Scheduling Problems with Applications to them-Machine Flow Shop Scheduling Problem. Eur J Oper Res 19:125–141

    Google Scholar 

  37. Simons JV (1992) Heuristics in Flow Shop Scheduling with Sequence Dependent Setup Times. Omega 20:215–225

    Google Scholar 

  38. Stöppler S, Bierwirth C (1992) The Application of a Parallel Genetic Algorithm to then/m/P/C max Flowshop Problem. In: Fandel G, Gulledge T, Jones A (eds) New directions for Operations Research in Manufacturing. Springer, Berlin, pp 149–160

    Google Scholar 

  39. Taillard E (1990) Some Efficient Heuristic Methods for the Flow Shop Sequencing Problem. Eur J Oper Res 47:65–74

    Google Scholar 

  40. Taillard E (1993) Benchmarks for Basic Scheduling Problems. Eur J Oper Res 64:278–285

    Google Scholar 

  41. Vakharia AJ, Chang Y-L (1990) A Simulated Annealing Approach to Scheduling a Manufacturing Cell. Naval Res Log Quart 37:559–577

    Google Scholar 

  42. van de Velde SL (1990) Minimizing the Sum of the Job Completion Times in the Two-Machine Flow Shop by Lagrangean Relaxation. Ann Oper Res 26:257–268

    Google Scholar 

  43. van Wassenhove L, Potts CN (1992) Integrating Scheduling with Batching and Lot Sizing: A Review of Algorithms and Complexity. J Oper Res Soc 43:395–406

    Google Scholar 

  44. Werner F (1988) Ein adaptives stochastisches Suchverfahren für spezielle Reihenfolgeprobleme. Ekonomicko-Matematicky Obzor 24:50–67

    Google Scholar 

  45. Werner F (1993) On the Heuristic Solution of the Permutation Flow Shop Problem by Path Algorithms. Comput Oper Res 20:707–722

    Google Scholar 

  46. Werner F, Winkler A (1995) Insertion Techniques for the Heuristic Solution of the Job Shop Problem. Discr Appl Math 58:191–211

    Google Scholar 

  47. Widmer M, Hertz A (1989) A New Heuristic Method for the Flow Shop Sequencing Problem. Eur J Oper Res 41:186–193

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Engineering Cybernetics of the Byelorussian Academy of Sciences, Surganov St. 6, 220012, Minsk, Belarus

    Yuri N. Sotskov

  2. Otto-von-Guericke-Universität Magdeburg, Postfach 4120, D-39016, Magdeburg, Germany

    Thomas Tautenhahn & Frank Werner

Authors
  1. Yuri N. Sotskov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Thomas Tautenhahn
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Frank Werner
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Supported by Deutsche Forschungsgemeinschaft (Project ScheMA) and by the International Association for the Promotion of Cooperation with Scientists from the Independent States of the Former Soviet Union (Project INTAS-93-257)

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sotskov, Y.N., Tautenhahn, T. & Werner, F. Heuristics for permutation flow shop scheduling with batch setup times. OR Spektrum 18, 67–80 (1996). https://doi.org/10.1007/BF01539731

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01539731

Key words

Schlüsselwörter

Search

Navigation