Skip to main content
SpringerLink
Log in

Firefly Algorithm for Flow Shop Optimization

  • Chapter
  • First Online:
Recent Advances in Swarm Intelligence and Evolutionary Computation

Part of the book series: Studies in Computational Intelligence ((SCI,volume 585))

Abstract

In this chapter, a recently developed bio-inspired meta-heuristic algorithm namely firefly algorithm (FA) is addressed to solve the flow shop scheduling problems with sequence dependent setup times which have been proved to be strongly NP-hard type of combinatorial optimization problems. Four different performance measures namely minimization of makespan, mean flow time, mean tardiness and number of tardy jobs are considered. Extensive computational experiments were carried out to compare the performance of the proposed FA on different random problem instances. The results indicate that the proposed FA is more effective than many other algorithms reported earlier in the literature.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 109.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. Armentano, V.A., Ronconi, D.P.: Tabu search for total tardiness minimization in flowshop scheduling problems. Comp. Oper. Res. 26(3), 219–235 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  2. Arroyo, J.E.C., Armentano, V.A.: Genetic local search for multi-objective flowshop scheduling problems. Eur. J. Oper. Res. 167, 717–738 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  3. Baker, K.R.: Introduction to sequencing and scheduling. Wiley, New York (1974)

    Google Scholar 

  4. Banati, H., Bajaj, M.: Firefly based feature selection approach. Int. J. Comp. Sci. Issues 8(4), 473–480 (2011)

    Google Scholar 

  5. Bean, J.C.: Genetic algorithms and random keys for sequencing and optimization. ORSA J. comput. 6(2), 154–160 (1994)

    Article  MATH  Google Scholar 

  6. Boxma, O.J., Forst, F.G.: Minimizing the expected weighted number of tardy jobs in stochastic flow shops. Oper. Res. Lett. 5(3), 119–126 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  7. Chakraborty, U.K., Turvey, K.P.: Floating-point to integer mapping schemes in differential evolution for permutation flow shop scheduling. Int. J. Bio-Inspired Comput. 2(3), 183–204 (2010)

    Article  Google Scholar 

  8. Chandrasekaran, K., Simon, S.P.: Network and reliability constrained unit commitment problem using binary real coded firefly algorithm. Int. J. Electr. Power Energy Syst. 43(1), 921–932 (2012)

    Article  Google Scholar 

  9. Chowdhury, A., Ghosh, A., Sinha, S., Das, S., Ghosh, A.: A novel genetic algorithm to solve travelling salesman problem and blocking flow shop scheduling problem. Int. J. Bio-Inspired Comput. 5(5), 303–314 (2013)

    Article  Google Scholar 

  10. Coelho, L.D.S., Mariani, V.C.: Firefly algorithm approach based on chaotic Tinkerbell map applied to multivariable PID controller tuning. Comput. Math. Appl. 64(8), 2371–2382 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  11. Corwin, B.D., Esogbue, A.O.: Two machine flow shop scheduling problems with sequence dependent setup times: a dynamic programming approach. Naval Res. Logistics Q. 21(3), 515–524 (1974)

    Article  MATH  MathSciNet  Google Scholar 

  12. Czapiński, M.: Parallel simulated annealing with genetic enhancement for flowshop problem with Csum. Comput. Ind. Eng. 59(4), 778–785 (2010)

    Article  Google Scholar 

  13. Dekhici, L., Borne, P., Khaled, B.: Firefly algorithm for economic power dispatching with pollutants emission. Informatica Economică 16(2), 45–57 (2012)

    Google Scholar 

  14. Dong, X., Huang, H., Chen, P.: An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion. Comput. Oper. Res. 36(5), 1664–1669 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  15. Fister, I., Fister Jr, I., Yang, X.S., Brest, J.: A comprehensive review of firefly algorithms. Swarm Evol. Comput. 13, 34–46 (2013)

    Article  Google Scholar 

  16. França, P.M., Gupta, J.N., Mendes, A.S., Moscato, P., Veltink, K.J.: Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups. Comput. Ind. Eng. 48(3), 491–506 (2005)

    Article  Google Scholar 

  17. Gandomi, A.H., Yang, X.S., Alavi, A.H.: Mixed variable structural optimization using firefly algorithm. Comput. Struct. 89(23), 2325–2336 (2011)

    Article  Google Scholar 

  18. Gao, K.Z., Pan, Q.K., Li, J.Q.: Discrete harmony search algorithm for the no-wait flow shop scheduling problem with total flow time criterion. Int. J. Adv. Manuf. Technol. 56(5–8), 683–692 (2011)

    Article  Google Scholar 

  19. Gao, K., Pan, Q., Suganthan, P.N., Li, J.: Effective heuristics for the no-wait flow shop scheduling problem with total flow time minimization. Int. J. Adv. Manuf. Technol. 66(9–12), 1563–1572 (2013)

    Article  Google Scholar 

  20. Gupta, J.N., Darrow, W.P.: The two-machine sequence dependent flowshop scheduling problem. Eur. J. Oper. Res. 24(3), 439–446 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  21. Gupta, J.N.D., Chen, C.L., Yap, L.Y., Deshmukh, H.: Designing a tabu search algorithm to minimize total flow time in a flow shop. Arab. J. Sci. Eng. 25(1), 79–94 (2000)

    Google Scholar 

  22. Gupta, J.N., Neppalli, V.R., Werner, F.: Minimizing total flow time in a two-machine flowshop problem with minimum makespan. Int. J. Prod. Econ. 69(3), 323–338 (2001)

    Article  Google Scholar 

  23. Gupta, J.N., Stafford Jr, E.F.: Flowshop scheduling research after five decades. Eur. J. Oper. Res. 169(3), 699–711 (2006)

    Article  MATH  Google Scholar 

  24. Horng, M.H.: Vector quantization using the firefly algorithm for image compression. Expert Syst. Appl. 39(1), 1078–1091 (2012)

    Article  MathSciNet  Google Scholar 

  25. Ignall, E., Schrage, L.: Application of the branch and bound technique to some flow-shop scheduling problems. Oper. Res. 13(3), 400–412 (1965)

    Article  MathSciNet  Google Scholar 

  26. Jarboui, B., Eddaly, M., Siarry, P.: An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems. Comput. Oper. Res. 36(9), 2638–2646 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  27. Johnson, S.M.: Optimal two and three stage production schedules with setup times included. Naval Res. Logistics Q. 1(1), 61–68 (1954)

    Article  Google Scholar 

  28. Kazemzadeh, A.S., Kazemzadeh, A.S.: Optimum design of structures using an improved firefly algorithm. Int. J. Optim. Civ. Eng. 2, 327–340 (2011)

    Google Scholar 

  29. Khadwilard, A., Chansombat, S., Thepphakorn, T., Thapatsuwan, P., Chainat, W., Pongcharoen, P.: Application of firefly algorithm and its parameter setting for job shop scheduling. J. Ind. Technol. 8, 49–58 (2012)

    Google Scholar 

  30. Khalili, M., Tavakkoli-Moghaddam, R.: A multi-objective electromagnetism algorithm for a bi-objective flowshop scheduling problem. J. Manuf. Syst. 31(2), 232–239 (2012)

    Article  Google Scholar 

  31. Kim, Y.D.: Minimizing total tardiness in permutation flowshops. Eur. J. Oper. Res. 85(3), 541–555 (1995)

    Article  MATH  Google Scholar 

  32. Liao, C.J., Tseng, C.T., Luarn, P.: A discrete version of particle swarm optimization for flowshop scheduling problems. Comput. Oper. Res. 34(10), 3099–3111 (2007)

    Article  MATH  Google Scholar 

  33. Liu, C.P., Ye, C.M.: Solving Permutation Flow Shop Scheduling Problem by firefly Algorithm. Ind. Eng. Manage. 17(3), 56–59 (2012)

    Google Scholar 

  34. Marichelvam, M.K.: An improved hybrid Cuckoo Search (IHCS) metaheuristics algorithm for permutation flow shop scheduling problems. Int. J. Bio-Inspired Comput. 4(4), 200–205 (2012)

    Article  Google Scholar 

  35. Marichelvam, M.K., Prabaharan, T., Yang, X.S.: A discrete firefly algorithm for the multi-objective hybrid flowshop scheduling problems. IEEE Trans. Evol. Comput. 18(2), 301–305 (2014)

    Article  Google Scholar 

  36. Miguel, L.F.F., Lopez, R.H., Miguel, L.F.F.: Multimodal size, shape, and topology optimisation of truss structures using the firefly algorithm. Adv. Eng. Softw. 56, 23–37 (2013)

    Article  Google Scholar 

  37. Murata, T., Ishibuchi, H., Tanaka, H.: Multi-objective genetic algorithm and its applications to flowshop scheduling. Comput. Ind. Eng. 30(4), 957–968 (1996)

    Article  Google Scholar 

  38. Nagano, M.S., Moccellin, J.V.: Reducing mean flow time in permutation flow shop. J. Oper. Res. Soc. 59(7), 939–945 (2008)

    Article  MATH  Google Scholar 

  39. Naderi, B., Tavakkoli-Moghaddam, R., Khalili, M.: Electromagnetism-like mechanism and simulated annealing algorithms for flowshop scheduling problems minimizing the total weighted tardiness and makespan. Knowl.-Based Syst. 23(2), 77–85 (2010)

    Article  Google Scholar 

  40. Neppalli, V.R., Chen, C.L., Gupta, J.N.: Genetic algorithms for the two-stage bicriteria flowshop problem. Eur. J. Oper. Res. 95(2), 356–373 (1996)

    Article  MATH  Google Scholar 

  41. Osman, I.H., Potts, C.N.: Simulated annealing for permutation flow-shop scheduling. Omega 17(6), 551–557 (1989)

    Article  Google Scholar 

  42. Pan, Q.K., Fatih Tasgetiren, M., Suganthan, P.N., Chua, T.J.: A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Inf. Sci. 181(12), 2455–2468 (2011)

    Article  Google Scholar 

  43. Parthasarathy, S., Rajendran, C.: An experimental evaluation of heuristics for scheduling in a real-life flowshop with sequence-dependent setup times of jobs. Int. J. Prod. Econ. 49(3), 255–263 (1997)

    Article  Google Scholar 

  44. Pinedo, M.: Scheduling: theory, algorithms, and systems. Prentice-Hall, New Jersey (2002)

    Google Scholar 

  45. Rahimi-Vahed, A.R., Mirghorbani, S.M.: A multi-objective particle swarm for a flow shop scheduling problem. J. Comb. Optim. 13(1), 79–102 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  46. Rajendran, C.: Heuristic algorithm for scheduling in a flowshop to minimize total flowtime. Int. J. Prod. Econ. 29(1), 65–73 (1993)

    Article  Google Scholar 

  47. Rajendran, C., Ziegler, H.: An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs. Eur. J. Oper. Res. 103(1), 129–138 (1997)

    Article  MATH  Google Scholar 

  48. Rajendran, C., Ziegler, H.: Scheduling to minimize the sum of weighted flowtime and weighted tardiness of jobs in a flowshop with sequence-dependent setup times. Eur. J. Oper. Res. 149(3), 513–522 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  49. Rajendran, C., Ziegler, H.: Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. Eur. J. Oper. Res. 155(2), 426–438 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  50. Ravindran, D., Selvakumar, S.J., Sivaraman, R., Haq, A.N.: Flow shop scheduling with multiple objective of minimizing makespan and total flow time. Int. J. Adv. Manuf. Technol. 25(9–10), 1007–1012 (2005)

    Article  Google Scholar 

  51. Rios-Mercado, R.Z., Bard, J.F.: Heuristics for the flow line problem with setup costs. Eur. J. Oper. Res. 110(1), 76–98 (1998)

    Article  MATH  Google Scholar 

  52. Ruiz, R., Stützle, T.: A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur. J. Oper. Res. 177(3), 2033–2049 (2007)

    Article  MATH  Google Scholar 

  53. Ruiz, R., Maroto, C., Alcaraz, J.: Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics. Eur. J. Oper. Res. 165(1), 34–54 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  54. Salmasi, N., Logendran, R., Skandari, M.R.: Total flow time minimization in a flowshop sequence-dependent group scheduling problem. Comput. Oper. Res. 37(1), 199–212 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  55. Sayadi, M., Ramezanian, R., Ghaffari-Nasab, N.: A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems. Int. J. Ind. Eng. Comput. 1(1), 1–10 (2010)

    Google Scholar 

  56. Senthilnath, J., Omkar, S.N., Mani, V.: Clustering using firefly algorithm: performance study. Swarm Evol. Comput. 1(3), 164–171 (2011)

    Article  Google Scholar 

  57. Simons Jr, J.V.: Heuristics in flow shop scheduling with sequence dependent setup times. Omega 20(2), 215–225 (1992)

    Article  MathSciNet  Google Scholar 

  58. Srikar, B.N., Ghosh, S.: A MILP model for the n-job, m-stage flowshop with sequence dependent set-up times. Int. J. Prod. Res. 24(6), 1459–1474 (1986)

    Article  Google Scholar 

  59. Tang, L., Liu, J.: A modified genetic algorithm for the flow shop sequencing problem to minimize mean flow time. J. Intell. Manuf. 13(1), 61–67 (2002)

    Article  Google Scholar 

  60. TT’kindt, V., Monmarché, N., Tercinet, F., Laügt, D.: An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem. Eur. J. Oper. Res. 142(2), 250–257 (2002)

    Article  Google Scholar 

  61. Tasgetiren, M.F., Liang, Y.C., Sevkli, M., Gencyilmaz, G.: 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 (2007)

    Article  MATH  Google Scholar 

  62. Tasgetiren, M.F., Pan, Q.K., Suganthan, P.N., Chen, A.H.: A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops. Inf. Sci. 181(16), 3459–3475 (2011)

    Article  MathSciNet  Google Scholar 

  63. Tavakkoli-Moghaddam, R., Rahimi-Vahed, A., Mirzaei, A.H.: A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: weighted mean completion time and weighted mean tardiness. Inf. Sci. 177(22), 5072–5090 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  64. Tseng, L.Y., Lin, Y.T.: A genetic local search algorithm for minimizing total flowtime in the permutation flowshop scheduling problem. Int. J. Prod. Econ. 127(1), 121–128 (2010)

    Article  Google Scholar 

  65. Vahedi Nouri, B., Fattahi, P., Ramezanian, R.: Hybrid firefly-simulated annealing algorithm for the flow shop problem with learning effects and flexible maintenance activities. Int. J. Prod. Res. 51(12), 3501–3515 (2013)

    Article  Google Scholar 

  66. Varadharajan, T.K., Rajendran, C.: 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 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  67. Vempati, V.S., Chen, C.L., Bullington, S.F.: An effective heuristic for flow shop problems with total flow time as criterion. Comput. Ind. Eng. 25(1), 219–222 (1993)

    Article  Google Scholar 

  68. Yang, X.S.: Multiobjective firefly algorithm for continuous optimization. Eng. Comput. 29(2), 175–184 (2013)

    Article  Google Scholar 

  69. Yang, X.S., Sadat Hosseini, S.S., Gandomi, A.H.: Firefly algorithm for solving non-convex economic dispatch problems with valve loading effect. Appl. Softw. Comput. 12(3), 1180–1186 (2012)

    Article  Google Scholar 

  70. Yang, X.S.: Nature-Inspired metaheuristic algorithms. Luniver press, UK (2008)

    Google Scholar 

  71. Yagmahan, B., Yenisey, M.M.: Ant colony optimization for multi-objective flow shop scheduling problem. Comput. Ind. Eng. 54(3), 411–420 (2008)

    Article  Google Scholar 

  72. Zhang, Y., Li, X., Wang, Q.: Hybrid genetic algorithm for permutation flowshop scheduling problems with total flowtime minimization. Eur. J. Oper. Res. 196(3), 869–876 (2009)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mechanical Engineering, Mepco Schlenk Engineering College, Sivakasi, 626005, Tamilnadu, India

    M. K. Marichelvam & T. Prabaharan

  2. Department of Mathematics, Kamaraj College of Engineering and Technology, Virudhunagar, 626001, Tamilnadu, India

    M. Geetha

Authors
  1. M. K. Marichelvam
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. T. Prabaharan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. Geetha
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. K. Marichelvam .

Editor information

Editors and Affiliations

  1. School of Science and Technology, Middlesex University, London, United Kingdom

    Xin-She Yang

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this chapter

Cite this chapter

Marichelvam, M.K., Prabaharan, T., Geetha, M. (2015). Firefly Algorithm for Flow Shop Optimization. In: Yang, XS. (eds) Recent Advances in Swarm Intelligence and Evolutionary Computation. Studies in Computational Intelligence, vol 585. Springer, Cham. https://doi.org/10.1007/978-3-319-13826-8_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-13826-8_12

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-13825-1

  • Online ISBN: 978-3-319-13826-8

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation