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
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aarts E, Korst J (1989) Simulated Annealing and Boltzmann Machines – A Stochastic Approach to Combinatorial Optimization and Neural Computing. Wiley, Chichester
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
Aarts E, Ten Eikelder HMM (2002) Simulated Annealing. In: Pardalos PM, Resende MGC (eds) Handbook of Applied Optimization. Oxford University Press, pp 209–221
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
Aggoune R (2004) Minimizing the Makespan for the Flow Shop Scheduling Problem with Availability Constraints. Eur J Oper Res 153:534–543
Aggoune R, Portmann M-C (2006) Flow Shop Scheduling Problem with Limited Machine Availability: A Heuristic Approach. Int J Prod Econ 99:4–15
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
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
Arroyo JEC, Armentano VA (2005) Genetic Local Search for Multi-Objective Flowshop Scheduling Problems. Eur J Oper Res 167(3):717–738
Bagchi TP (1999) Multiobjective Scheduling by Genetic Algorithms. Kluwer, Boston
Bagchi TP, Gupta JND, Sriskandarajah C (2006) A Review of TSP Based Approaches for Flowshop Scheduling. Eur J Oper Res 169(3):816–854
Ben-Daya M, Al-Fawzan M (1998) A Tabu Search Approach for the Flow Shop Scheduling Problem. Eur J Oper Res 109:88–95
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
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
Campbell HG, Dudek RA, Smith ML (1970) A Heuristic Algorithm for the n-job, m-Machine Sequencing problem. Manag Sci 16:B630–B637
Carlier J, and Rebaï, I (1996) Two Branch and Bound Algorithms for the Permutation Flow Shop Problem. Eur J Oper Res 90:238–251
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
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
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
Conway RW, Maxwell WL, Miller LW (2003) Theory of Scheduling. Dover Publications INC., Mineola
Dannenbring DG (1977) An Evaluation of Flowshop Sequencing Heuristics. Manag Sci 23(11):1174–1182
De Castro LN, Von Zuben FJ (1999) Artificial Immune Systems, Part 1, Basic Theory and Applications. Technical Report, TR-DCA 01/99
De Castro LN, Von Zuben FJ (2001) Learning and Optimization Using the Clonal Selection Principle. Trans IEEE Evol Comput 6(3):239–251
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
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
Eren T, Guner E (2006) A Bicriteria Flowshop Scheduling Problem with Setup Times. Appl Math Comput 183(2):1292–1300
Fink A, Voßb S (2003) Solving the Continuous Flow-Shop Scheduling Problem by Metaheuristics. Eur J Oper Res 151:400–414
Finke G, Jiang H (1997) A Variant of the Permutation Flow Shop Model with Variable Processing Times. Discret Appl Math 76:123–140
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
Glover F (1989) Tabu Search I. ORSA J Comput 1(3):190–206
Glover F (1990) Tabu Search II. ORSA J Comput 2(1):4–32
Glover F, Laguna M, Taillard E, de Werra D (eds) (1993) Tabu Search. JC Baltzer AG, Science Publishers, Basel
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
Goldberg DE (1989) Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company INC, Massachussets
Gourgand M, Grangeon N, Norre S (2003) A Contribution to the Stochastic Flow Shop Scheduling Problem. Eur J Oper Res 151:415–433
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
Grabowski J, Pempera J (2005) Some Local Search Algorithms for No-Wait Flow-Shop Problem with Makespan Criterion. Comput Oper Res 32:2197–2212
Guinet A, Solomon M (1996) Scheduling Hybrid Flowshops to Minimize Maximum Tardiness or Maximum Completion Time. Int J Prod Res 34(6):1643–1654
Gupta JND, Stafford EF (2006) Flowshop Scheduling Research After Five Decades. Eur J Oper Res 169(3):699–711
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
Hansen P, Mladenovic N (2001) Variable Neighborhood Search: Principles and Applications. Eur J Oper Res 130:449–467
Holland JH (1975) Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor
Hunsucker JL, Shah JR (1992) Performance of priority rules in a due-date flowshop. OMEGA Int J Manag Sci 20(1):73–89
Jain AS, Meeran S (2002) A Multi-Level Hybrid Framework Applied to the General Flow-Shop Scheduling Problem. Comput Oper Res 29:1873–1901
Jia C (1998) Minimizing Variation in Stochastic Flow Shop. Oper Res Lett 23:109–111
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
Jin Z, Yang Z, Ito T (2006) Metaheuristic Algorithms for the Multistage Hybrid Flowshop Scheduling Problem. Int J Prod Econ 100(2):322–334
Karlor JK, Wang W (1996) Bilevel Programming Applied to the Flow Shop Scheduling Problem. Comput Oper Res 23(5):443–451
Kennedy J, Eberhart R (1995) Particle Swarm Optimization. In: Proceedings of 1995 IEEE International Conference on Neural Networks 4:1942–1948
Kirkpatrick S, Gelatt CD, Vecchi MP (1982) Optimization by Simulated Annealing. Science 220:671–680
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
Laha D, Chakraborty UK (2007) An Efficient Stochastic Hybrid Heuristic for Flowshop Scheduling. Eng Appl Artif Intell 20(6):851–856
Leu S-S, Hwang S-T (2002) GA-Based Resource‐Constrained Flow-Shop Scheduling Model for Mixed Precast Production. Automat Construct 11:439–452
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
Liao C-J, Sun C-L, You W-C (1995) Flow-Shop Scheduling with Flexible Processors. Comput Oper Res 22(3):297–301
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
Linn R, Zhang W (1999) Hybrid Flow Shop Scheduling: A Survey. Comput Indust Eng 37:57–61
Low C (2005) Simulated Annealing Heuristic for Flow Shop Scheduling Problems with Unrelated Parallel Machines. Comput Oper Res 32:2013–2025
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
Morton TE, Pentico DW (1993) Heuristic Scheduling Systems. With Applications to Production Systems and Project Management. Wiley, New York
Nawaz M, Enscore E, Ham I (1983) A Heuristic Algorithm for the m-Machine, n-Job Flowshop Sequencing Problem. Omega 11:91–95
Nearchou A (2004) A Novel Metaheuristic Approach for the Flow Shop Scheduling Problem. Eng Appl Artif Intell 17:289–300
Negenman EG (2001) Local Search Algorithms for the Multiprocessor Flow Shop Scheduling Problem. Eur J Oper Res 128:147–158
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
Nowicki E, Smutnicki C (2006) Some Aspects of Scatter Search in the Flow-Shop Problem. Eur J Oper Res 169:654–666
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
Sodererg B, Peterson C (1997) Artificial Neural Networks. In: Aarts E, Lenstra JK (eds) Local Search in Combinatorial Optimization. Wiley, Chichester, pp 173–214
Pinedo M (1995) Scheduling. Theory, Algorithms, and Systems. Prentice Hall, Englewood Cliffs
Proust C , Gupta JND, Deschamps V (1991) Flowshop Scheduling with Set-Up, Processing and Removal Times Separated. Int J Prod Res 29:479–493
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
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
Reeves CR (1995) Genetic Algorithms. In: Reeves CR (ed) Modern Heuristic Techniques for Combinatorial Problems. McGraw-Hill, London, pp 151–196
Reeves CR (2003) Genetic Algorithms. In: Glover F, Kochenberger GA (eds) Handbooks of Metaheuristics. Kluwer, Dordrecht, pp 55–82
Resende MGC, Ribeiro CC (2003) Greedy Randomized Adaptive Search Procedures. In: Glover F, Kochenberger GA (eds) Handbook of Metaheuristics. Kluwer, Boston, pp 219–249
Riezebos J, Gaalman GJC (1998) Time Lag Size in Multiple Operations Flow Shop Scheduling Heuristics. Eur J Oper Res 105:72–90
Rios-Mercado R, Bard J (1998) Heuristics for the Flow Line Problem with Setup Costs. Eur J Oper Res 110:76–98
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
Ruiz R, Maroto C (2005) A Comprehensive Review and Evaluation of Permutation Flowshop Heuristics. Eur J Oper Res 165(2):479–494
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
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
Ruiz R, Maroto C, Alcaraz J (2006) Two New Robust Genetic Algorithms for the Flowshop Scheduling Problem. Omega 34(5):461–476
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
Sayin S, Karabati S (1999) A Bicriteria Approach to the Two-Machine Flow Shop Scheduling Problem. Eur J Oper Res 113:435–449
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
Smutnicki C (1998) Some Results of the Worst-Case Analysis for Flow Shop Scheduling. Eur J Oper Res 109:66–87
Solimanpur M, Vrat P, Shankar R (2004) A Neuro-Tabu Search Heuristic for the Flow Shop Scheduling Problem. Comput Oper Res 31:2151–2164
Soukhal A, Oulamara A, Martineau P (2005) Complexity of Flow Shop Scheduling Problems with Transportation Constraints. Eur J Oper Res 161:32–41
Steinhöfel K, Albrecht A, Wong CK (2002) The Convergence of Stochastic Algorithms Solving Flow Shop Scheduling. Theoretic Comput Sci 285:101–117
Suliman SMA (2000) A Two-Phase Heuristic Approach to the Permutation Flow-Shop Scheduling Problem. Int J Prod Econ 64:143–152
Suresh V (1997) A Note on Scheduling of Two-Stage Flow Shop with Multiple Processors. Int J Prod Econ 49:77–82
Szwarc W (1983) Flowshop problems with time lags. Manag Sci 29:477–481
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
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
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
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
Townsend W (1977) Sequencing n-Jobs on m-Machines to Minimize Maximum Tardiness: A Branch-and-Bound Solution. Manag Sci 23:1016–1019
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
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
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
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
Wang J-B (2007) Flow Shop Scheduling Problems with Decreasing Linear Deterioration Under Dominant Machines. Comput Oper Res 34(7):2043–2058
Wang J-B, Xia Z-Q (2006) Flow Shop Scheduling with Deteriorating Jobs under Dominating Machines. Omega 34(4):327–336
Wang L, Zhang L (2006) Stochastic Optimization Using Simulated Annealing with Hypothesis Test. Appl Math Comput 174(2):1329–1342
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
Xuan H, Tang L (2007) Scheduling a Hybrid Flowshop with Batch Production at the Last Stage. Comput Oper Res 34(9):2718–2733
Yokoyama M (2001) Hybrid Flow-Shop Scheduling with Assembly Operations. Int J Prod Econ 73:103–116
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
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights 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
DOI: https://doi.org/10.1007/978-0-387-74759-0_185
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-74758-3
Online ISBN: 978-0-387-74759-0
eBook Packages: Mathematics and StatisticsReference Module Computer Science and Engineering