Skip to main content

Flow Shop Scheduling Problem

  • Reference work entry
Encyclopedia of Optimization
  • 784 Accesses

Article Outline

Introduction

Variations

Exact Algorithms for the Flow Shop Scheduling Problem

Heuristic Algorithms for the Flow Shop Scheduling Problem

Metaheuristic Algorithms for the Flow Shop Scheduling Problem

References

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

Access this chapter

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 2,500.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 2,499.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Aarts E, Korst J (1989) Simulated Annealing and Boltzmann Machines – A Stochastic Approach to Combinatorial Optimization and Neural Computing. Wiley, Chichester

    MATH  Google Scholar 

  2. Aarts E, Korst J, Van Laarhoven P (1997) Simulated Annealing. In: Aarts E, Lenstra JK (eds) Local Search in Combinatorial Optimization. Wiley, Chichester, pp 91–120

    Google Scholar 

  3. Aarts E, Ten Eikelder HMM (2002) Simulated Annealing. In: Pardalos PM, Resende MGC (eds) Handbook of Applied Optimization. Oxford University Press, pp 209–221

    Google Scholar 

  4. Agarwal A, Colak S, Eryarsoy E (2006) Improvement Heuristic for the Flow-Shop Scheduling Problem: An Adaptive-Learning Approach. Eur J Oper Res 169:801–815

    Article  MathSciNet  MATH  Google Scholar 

  5. Aggoune R (2004) Minimizing the Makespan for the Flow Shop Scheduling Problem with Availability Constraints. Eur J Oper Res 153:534–543

    Article  MathSciNet  MATH  Google Scholar 

  6. Aggoune R, Portmann M-C (2006) Flow Shop Scheduling Problem with Limited Machine Availability: A Heuristic Approach. Int J Prod Econ 99:4–15

    Article  Google Scholar 

  7. Al-Anzi FS, Allahverdi A (2007) A Self-Adaptive Differential Evolution Heuristic for Two-Stage Assembly Scheduling Problem to Minimize Maximum Lateness With Setup Times. Eur J Oper Res 182(1):80–94

    Article  MathSciNet  MATH  Google Scholar 

  8. Allahverdi A, Al-Anzi FS (2006) A PSO and a Tabu Search Heuristics for the Assembly Scheduling Problem of the Two-Stage Distributed Database Application. Comput Oper Res 33(4):1056–1080

    Article  MATH  Google Scholar 

  9. Arroyo JEC, Armentano VA (2005) Genetic Local Search for Multi-Objective Flowshop Scheduling Problems. Eur J Oper Res 167(3):717–738

    Article  MathSciNet  MATH  Google Scholar 

  10. Bagchi TP (1999) Multiobjective Scheduling by Genetic Algorithms. Kluwer, Boston

    MATH  Google Scholar 

  11. Bagchi TP, Gupta JND, Sriskandarajah C (2006) A Review of TSP Based Approaches for Flowshop Scheduling. Eur J Oper Res 169(3):816–854

    Article  MathSciNet  MATH  Google Scholar 

  12. Ben-Daya M, Al-Fawzan M (1998) A Tabu Search Approach for the Flow Shop Scheduling Problem. Eur J Oper Res 109:88–95

    Article  MATH  Google Scholar 

  13. Botta-Genoulaz V (2000) Hybrid Flow Shop Scheduling with Precedence Constraints and Time Lags to Minimize Maximum Lateness. Int J Prod Econ 64:101–111

    Article  Google Scholar 

  14. Botta V, Guinet A (1996) Scheduling flowshops with precedence constraints and time lags. Proceedings of the Workshop on Production Planning and Control, Mons, Belgium, 16–19

    Google Scholar 

  15. Campbell HG, Dudek RA, Smith ML (1970) A Heuristic Algorithm for the n-job, m-Machine Sequencing problem. Manag Sci 16:B630–B637

    Google Scholar 

  16. Carlier J, and Rebaï, I (1996) Two Branch and Bound Algorithms for the Permutation Flow Shop Problem. Eur J Oper Res 90:238–251

    Google Scholar 

  17. Chang PC, Chen SH, Liu CH (2007) Sub-Population Genetic Algorithm with Mining Gene Structures for Multiobjective Flowshop Scheduling Problems. Exp Syst Appl 33(3):762–771

    Article  Google Scholar 

  18. Cheng BW, Chang CL (2007) A Study on Flowshop Scheduling Problem Combining Taguchi Experimental Design and Genetic Algorithm. Exp Syst Appl 32(2):415–421

    Article  MathSciNet  Google Scholar 

  19. Chung CS, Flynn J, Kirca O (2006) A Branch and Bound Algorithm to Minimize the Total Tardiness for M‑Machine Permutation Flowshop Problems. Eur J Oper Res 174(1):1–10

    Article  MathSciNet  MATH  Google Scholar 

  20. Conway RW, Maxwell WL, Miller LW (2003) Theory of Scheduling. Dover Publications INC., Mineola

    MATH  Google Scholar 

  21. Dannenbring DG (1977) An Evaluation of Flowshop Sequencing Heuristics. Manag Sci 23(11):1174–1182

    Article  MATH  Google Scholar 

  22. De Castro LN, Von Zuben FJ (1999) Artificial Immune Systems, Part 1, Basic Theory and Applications. Technical Report, TR-DCA 01/99

    Google Scholar 

  23. De Castro LN, Von Zuben FJ (2001) Learning and Optimization Using the Clonal Selection Principle. Trans IEEE Evol Comput 6(3):239–251

    Article  Google Scholar 

  24. Dorigo M, Maniezzo V, Colorni A (1996) Ant System: Optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern B 26(1):29–41

    Article  Google Scholar 

  25. Engin O, Döyen A (2004) A New Approach to Solve Hybrid Flow Shop Scheduling Problems by Artificial Immune System. Future Generat Comput Syst 20:1083–1095

    Article  Google Scholar 

  26. Eren T, Guner E (2006) A Bicriteria Flowshop Scheduling Problem with Setup Times. Appl Math Comput 183(2):1292–1300

    Article  MathSciNet  MATH  Google Scholar 

  27. Fink A, Voßb S (2003) Solving the Continuous Flow-Shop Scheduling Problem by Metaheuristics. Eur J Oper Res 151:400–414

    Article  MATH  Google Scholar 

  28. Finke G, Jiang H (1997) A Variant of the Permutation Flow Shop Model with Variable Processing Times. Discret Appl Math 76:123–140

    Article  MathSciNet  MATH  Google Scholar 

  29. Gajpal Y, Rajendran C (2006) An Ant-Colony Optimization Algorithm for Minimizing the Completion-Time Variance of Jobs in Flowshops. Int J Prod Econ 101(2):259–272

    Article  Google Scholar 

  30. Glover F (1989) Tabu Search I. ORSA J Comput 1(3):190–206

    MATH  Google Scholar 

  31. Glover F (1990) Tabu Search II. ORSA J Comput 2(1):4–32

    MATH  Google Scholar 

  32. Glover F, Laguna M, Taillard E, de Werra D (eds) (1993) Tabu Search. JC Baltzer AG, Science Publishers, Basel

    Google Scholar 

  33. Glover F, Laguna M, Marti R (2003) Scatter Search and Path Relinking. In: Glover F, Kochenberger GA (eds) Advances and Applications Handbook of Metaheuristics. Kluwer, Boston, pp 1–36

    Chapter  Google Scholar 

  34. Goldberg DE (1989) Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company INC, Massachussets

    MATH  Google Scholar 

  35. Gourgand M, Grangeon N, Norre S (2003) A Contribution to the Stochastic Flow Shop Scheduling Problem. Eur J Oper Res 151:415–433

    Article  MathSciNet  MATH  Google Scholar 

  36. Gowrishankar K, Rajendran C, Srinivasan G (2001) Flow Shop Scheduling Algorithms for Minimizing the Completion Time Variance and the Sum of Squares of Completion Time Deviations from a Common Due Date. Eur J Oper Res 132:643–665

    Article  MATH  Google Scholar 

  37. Grabowski J, Pempera J (2005) Some Local Search Algorithms for No-Wait Flow-Shop Problem with Makespan Criterion. Comput Oper Res 32:2197–2212

    Article  MathSciNet  MATH  Google Scholar 

  38. Guinet A, Solomon M (1996) Scheduling Hybrid Flowshops to Minimize Maximum Tardiness or Maximum Completion Time. Int J Prod Res 34(6):1643–1654

    Article  MATH  Google Scholar 

  39. Gupta JND, Stafford EF (2006) Flowshop Scheduling Research After Five Decades. Eur J Oper Res 169(3):699–711

    Article  MATH  Google Scholar 

  40. Gupta JND, Henning K, Werner F (2002) Local Search Heuristics for Two-Stage Flow Shop Problems with Secondary Criterion. Comput Oper Res 29:123–149

    Article  MATH  Google Scholar 

  41. Hansen P, Mladenovic N (2001) Variable Neighborhood Search: Principles and Applications. Eur J Oper Res 130:449–467

    Article  MathSciNet  MATH  Google Scholar 

  42. Holland JH (1975) Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor

    Google Scholar 

  43. Hunsucker JL, Shah JR (1992) Performance of priority rules in a due-date flowshop. OMEGA Int J Manag Sci 20(1):73–89

    Article  Google Scholar 

  44. Jain AS, Meeran S (2002) A Multi-Level Hybrid Framework Applied to the General Flow-Shop Scheduling Problem. Comput Oper Res 29:1873–1901

    Article  Google Scholar 

  45. Jia C (1998) Minimizing Variation in Stochastic Flow Shop. Oper Res Lett 23:109–111

    Article  MathSciNet  MATH  Google Scholar 

  46. Janiak A, Kozan E, Lichtenstein M, Oğuz C (2005) Metaheuristic Approaches to the Hybrid Flow Shop Scheduling Problem with a Cost-Related Criterion. Int J Prod Econ 31(3):504–514

    Google Scholar 

  47. Jin Z, Yang Z, Ito T (2006) Metaheuristic Algorithms for the Multistage Hybrid Flowshop Scheduling Problem. Int J Prod Econ 100(2):322–334

    Article  Google Scholar 

  48. Karlor JK, Wang W (1996) Bilevel Programming Applied to the Flow Shop Scheduling Problem. Comput Oper Res 23(5):443–451

    Article  Google Scholar 

  49. Kennedy J, Eberhart R (1995) Particle Swarm Optimization. In: Proceedings of 1995 IEEE International Conference on Neural Networks 4:1942–1948

    Google Scholar 

  50. Kirkpatrick S, Gelatt CD, Vecchi MP (1982) Optimization by Simulated Annealing. Science 220:671–680

    Article  MathSciNet  Google Scholar 

  51. Kumar A, Prakash A, Shankar R, Tiwari MK (2005) Psycho-Clonal Algorithm Based Approach to Solve Continuous Flow Shop Scheduling Problem. Exp Syst Appl, in press

    Google Scholar 

  52. Laha D, Chakraborty UK (2007) An Efficient Stochastic Hybrid Heuristic for Flowshop Scheduling. Eng Appl Artif Intell 20(6):851–856

    Article  Google Scholar 

  53. Leu S-S, Hwang S-T (2002) GA-Based Resource‐Constrained Flow-Shop Scheduling Model for Mixed Precast Production. Automat Construct 11:439–452

    Article  Google Scholar 

  54. Lian Z, Gu X, Jiao B (2006) A Similar Particle Swarm Optimization Algorithm for Permutation Flowshop Scheduling to Minimize Makespan. Appl Math Comput 175(1):773–785

    Article  MathSciNet  MATH  Google Scholar 

  55. Liao C-J, Sun C-L, You W-C (1995) Flow-Shop Scheduling with Flexible Processors. Comput Oper Res 22(3):297–301

    Article  MATH  Google Scholar 

  56. Liao CJ, Tseng CT, Luarn P (2007) A Discrete Version of Particle Swarm Optimization for Flowshop Scheduling Problems. Comput Oper Res 34(10):3099–3111

    Article  MATH  Google Scholar 

  57. Linn R, Zhang W (1999) Hybrid Flow Shop Scheduling: A Survey. Comput Indust Eng 37:57–61

    Article  Google Scholar 

  58. Low C (2005) Simulated Annealing Heuristic for Flow Shop Scheduling Problems with Unrelated Parallel Machines. Comput Oper Res 32:2013–2025

    Article  MATH  Google Scholar 

  59. Martin CH (2006) A Hybrid Genetic Algorithm/Mathematical Programming Approach to the Multi‐Family Flowshop Scheduling Problem with Lot Streaming. Omega, In Press, Available online 26 December 2006. doi: 10.1016/j.omega.2006.11.002

    Google Scholar 

  60. Morton TE, Pentico DW (1993) Heuristic Scheduling Systems. With Applications to Production Systems and Project Management. Wiley, New York

    Google Scholar 

  61. Nawaz M, Enscore E, Ham I (1983) A Heuristic Algorithm for the m-Machine, n-Job Flowshop Sequencing Problem. Omega 11:91–95

    Article  Google Scholar 

  62. Nearchou A (2004) A Novel Metaheuristic Approach for the Flow Shop Scheduling Problem. Eng Appl Artif Intell 17:289–300

    Article  Google Scholar 

  63. Negenman EG (2001) Local Search Algorithms for the Multiprocessor Flow Shop Scheduling Problem. Eur J Oper Res 128:147–158

    Article  MathSciNet  MATH  Google Scholar 

  64. Neppali VR, Chen C-L, Gupta JND (1996) Genetic Algorithms for the Two-Stage Bicriteria Flow Shop Problem. Eur J Oper Res 95:356–373

    Article  Google Scholar 

  65. Nowicki E, Smutnicki C (2006) Some Aspects of Scatter Search in the Flow-Shop Problem. Eur J Oper Res 169:654–666

    Article  MathSciNet  MATH  Google Scholar 

  66. Oğuz C, Zinder Y, Do VH, Janiak A, Lichtenstein M (2004) Hybrid Flow-Shop Scheduling Problems with Multiprocessor Task Systems. Eur J Oper Res 152:115–131

    Article  MATH  Google Scholar 

  67. Sodererg B, Peterson C (1997) Artificial Neural Networks. In: Aarts E, Lenstra JK (eds) Local Search in Combinatorial Optimization. Wiley, Chichester, pp 173–214

    Google Scholar 

  68. Pinedo M (1995) Scheduling. Theory, Algorithms, and Systems. Prentice Hall, Englewood Cliffs

    MATH  Google Scholar 

  69. Proust C , Gupta JND, Deschamps V (1991) Flowshop Scheduling with Set-Up, Processing and Removal Times Separated. Int J Prod Res 29:479–493

    Article  Google Scholar 

  70. Rajendran C, Ziegler H (2004) Ant-Colony Algorithms for Permutation Flowshop Scheduling to Minimize Makespan/Total Flowtime of Jobs. Eur J Oper Res 155(2):426–438

    Google Scholar 

  71. Rajendran C, Ziegler H (2005) Two Ant-Colony Algorithms for Minimizing Total Flowtime in Permutation Flowshops Computers and Industrial Engineering. Comput Indust Eng 48(4):789–797

    Article  Google Scholar 

  72. Reeves CR (1995) Genetic Algorithms. In: Reeves CR (ed) Modern Heuristic Techniques for Combinatorial Problems. McGraw-Hill, London, pp 151–196

    Google Scholar 

  73. Reeves CR (2003) Genetic Algorithms. In: Glover F, Kochenberger GA (eds) Handbooks of Metaheuristics. Kluwer, Dordrecht, pp 55–82

    Chapter  Google Scholar 

  74. Resende MGC, Ribeiro CC (2003) Greedy Randomized Adaptive Search Procedures. In: Glover F, Kochenberger GA (eds) Handbook of Metaheuristics. Kluwer, Boston, pp 219–249

    Chapter  Google Scholar 

  75. Riezebos J, Gaalman GJC (1998) Time Lag Size in Multiple Operations Flow Shop Scheduling Heuristics. Eur J Oper Res 105:72–90

    Article  MATH  Google Scholar 

  76. Rios-Mercado R, Bard J (1998) Heuristics for the Flow Line Problem with Setup Costs. Eur J Oper Res 110:76–98

    Article  MATH  Google Scholar 

  77. Rios-Mercado R, Bard J (1999) An Enhanced TSP-based Heuristic for Makespan Minimization in a Flow Shop with Setup Costs. J Heuristic 5:57–74

    Google Scholar 

  78. Ruiz R, Maroto C (2005) A Comprehensive Review and Evaluation of Permutation Flowshop Heuristics. Eur J Oper Res 165(2):479–494

    Article  MathSciNet  MATH  Google Scholar 

  79. Ruiz R, Maroto C (2006) A Genetic Algorithm for Hybrid Flowshops with Sequence Dependent Setup Times and Machine Eligibility. Eur J Oper Res 169(3):781–800

    Article  MathSciNet  MATH  Google Scholar 

  80. Ruiz R, Maroto C, Alcaraz J (2006) Solving the Flowshop Scheduling Problem with Sequence Dependent Setup Times Using Advanced Metaheuristics. Eur J Oper Res 165(1):34–54

    Article  MathSciNet  Google Scholar 

  81. Ruiz R, Maroto C, Alcaraz J (2006) Two New Robust Genetic Algorithms for the Flowshop Scheduling Problem. Omega 34(5):461–476

    Article  Google Scholar 

  82. Sadegheih A (2006) Scheduling Problem Using Genetic Algorithm, Simulated Annealing and the Effects of Parameter Values on GA Performance. Appl Math Modell 30(2):147–154

    Article  MATH  Google Scholar 

  83. Sayin S, Karabati S (1999) A Bicriteria Approach to the Two-Machine Flow Shop Scheduling Problem. Eur J Oper Res 113:435–449

    Article  MATH  Google Scholar 

  84. Shyu SJ, Lin BMT, Yin PY (2004) Application Of Ant Colony Optimization For No-Wait Flowshop Scheduling Problem To Minimize The Total Completion Time. Comput Indust Eng 47(2–3):181–193

    Article  Google Scholar 

  85. Smutnicki C (1998) Some Results of the Worst-Case Analysis for Flow Shop Scheduling. Eur J Oper Res 109:66–87

    Article  MATH  Google Scholar 

  86. Solimanpur M, Vrat P, Shankar R (2004) A Neuro-Tabu Search Heuristic for the Flow Shop Scheduling Problem. Comput Oper Res 31:2151–2164

    Article  MATH  Google Scholar 

  87. Soukhal A, Oulamara A, Martineau P (2005) Complexity of Flow Shop Scheduling Problems with Transportation Constraints. Eur J Oper Res 161:32–41

    Article  MathSciNet  MATH  Google Scholar 

  88. Steinhöfel K, Albrecht A, Wong CK (2002) The Convergence of Stochastic Algorithms Solving Flow Shop Scheduling. Theoretic Comput Sci 285:101–117

    Article  MATH  Google Scholar 

  89. Suliman SMA (2000) A Two-Phase Heuristic Approach to the Permutation Flow-Shop Scheduling Problem. Int J Prod Econ 64:143–152

    Article  Google Scholar 

  90. Suresh V (1997) A Note on Scheduling of Two-Stage Flow Shop with Multiple Processors. Int J Prod Econ 49:77–82

    Article  Google Scholar 

  91. Szwarc W (1983) Flowshop problems with time lags. Manag Sci 29:477–481

    Article  MATH  Google Scholar 

  92. Tang L, Xuan H, Liu J (2006) A New Lagrangian Relaxation Algorithm for Hybrid Flowshop Scheduling to Minimize Total Weighted Completion Time. Comput Oper Res 33(11):3344–3359

    Article  MATH  Google Scholar 

  93. Tasgetiren MF, Liang YC, Sevkli M, Gencyilmaz G (2007) A Particle Swarm Optimization Algorithm for Makespan and Total Flowtime Minimization in the Permutation Flowshop Sequencing Problem. Eur J Oper Res 177(3):1930–1947

    Article  MATH  Google Scholar 

  94. Tian P, Ma J, Zhang D-M (1999) Application of the Simulated Annealing Algorithm to the Combinatorial Optimisation Problem with Permutation Property: An Investigation of Generation Mechanism. Eur J Oper Res 118:81–94

    Article  MATH  Google Scholar 

  95. Toktaç B, Azizoğlu M, Köoksalan SK (2004) Two-Machine Flow Shop Scheduling with Two Criteria: Maximum Earliness and Makespan. Eur J Oper Res 157:286–295

    Article  Google Scholar 

  96. Townsend W (1977) Sequencing n-Jobs on m-Machines to Minimize Maximum Tardiness: A Branch-and-Bound Solution. Manag Sci 23:1016–1019

    MATH  Google Scholar 

  97. Vallada E, Ruiz R, Minella G (2008) Minimising Total Tardiness in the M-Machine Flowshop Problem: A Review and Evaluation of Heuristics and Metaheuristics. Comput Oper Res 35(4):1350–1373

    Article  MATH  Google Scholar 

  98. Varadharajan TK, Rajendran C (2005) A Multi-Objective Simulated-Annealing Algorithm for Scheduling in Flowshops to Minimize the Makespan and Total Flowtime of Jobs. Eur J Oper Res 167(3):772–795

    Article  MathSciNet  MATH  Google Scholar 

  99. Wang C, Chu C, Proth J-M (1996) Efficient Heuristic and Optimal Approaches for n/2/F/∑C i Scheduling Problems. Int J Prod Econ 44:225–237

    Article  Google Scholar 

  100. Wang C, Chu C, Proth J-M (1997) Heuristic Approaches for n/m/F/\( { \sum C_i } \) Scheduling Problems. Eur J Oper Res 96:636–644

    Article  MATH  Google Scholar 

  101. Wang J-B (2007) Flow Shop Scheduling Problems with Decreasing Linear Deterioration Under Dominant Machines. Comput Oper Res 34(7):2043–2058

    Article  MATH  Google Scholar 

  102. Wang J-B, Xia Z-Q (2006) Flow Shop Scheduling with Deteriorating Jobs under Dominating Machines. Omega 34(4):327–336

    Article  Google Scholar 

  103. Wang L, Zhang L (2006) Stochastic Optimization Using Simulated Annealing with Hypothesis Test. Appl Math Comput 174(2):1329–1342

    Article  MathSciNet  MATH  Google Scholar 

  104. Wardono B, Fathi Y (2004) A Tabu Search Algorithm for the Multi-Stage Parallel Machine Problem with Limited Buffer Capacities. Eur J Oper Res 155(2):380–401

    Article  MathSciNet  MATH  Google Scholar 

  105. Xuan H, Tang L (2007) Scheduling a Hybrid Flowshop with Batch Production at the Last Stage. Comput Oper Res 34(9):2718–2733

    Article  MATH  Google Scholar 

  106. Yokoyama M (2001) Hybrid Flow-Shop Scheduling with Assembly Operations. Int J Prod Econ 73:103–116

    Article  Google Scholar 

  107. Yokoyama M, Santos DL (2005) Three-Stage Flow-Shop Scheduling with Assembly Operations to Minimize the Weighted Sum of Product Completion Times. Eur J Oper Res 161:754–770

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag

About this entry

Cite this entry

Marinaki, M. (2008). Flow Shop Scheduling Problem . In: Floudas, C., Pardalos, P. (eds) Encyclopedia of Optimization. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-74759-0_185

Download citation

Publish with us

Policies and ethics