A Hybrid Firefly - VNS Algorithm for the Permutation Flowshop Scheduling Problem | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Hybrid Firefly - VNS Algorithm for the Permutation Flowshop Scheduling Problem

  • Conference paper
  • First Online:
Variable Neighborhood Search (ICVNS 2018)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 11328))

Included in the following conference series:

Abstract

In this paper a Permutation Flowshop Scheduling Problem is solved using a hybridization of the Firefly algorithm with Variable Neighborhood Search algorithm. The Permutation Flowshop Scheduling Problem (PFSP) is one of the most computationally complex problems. It belongs to the class of combinatorial optimization problems characterized as NP-hard. In order to find high quality solutions in reasonable computational time, heuristic and metaheuristic algorithms have been used for solving the problem. The proposed method, Hybrid Firefly Variable Neighborhood Search algorithm, uses in the local search phase of the algorithm a number of local search algorithms, 1-0 relocate, 1-1 exchange and 2-opt. In order to test the effectiveness and efficiency of the proposed method we used a set of benchmark instances of different sizes from 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

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 7435
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 9294
Price includes VAT (Japan)
  • Compact, lightweight 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

Similar content being viewed by others

References

  1. Chen, S.-H., Chang, P.-C., Cheng, T.C.E., Zhang, Q.: A self-guided genetic algorithm for permutation flowshop scheduling problems. Comput. Oper. Res. 39, 1450–1457 (2012)

    Article  MathSciNet  Google Scholar 

  2. Gajpal, Y., Rajendran, C.: An ant-colony optimization algorithm for minimizing the completion-time variance of jobs in flowshops. Int. J. Prod. Econ. 101(2), 259–272 (2006)

    Article  Google Scholar 

  3. Garey, M.R., Johnson, D.S., Sethi, R.: The complexity of flowshop and jobshop scheduling. Math. Oper. Res. 1, 117–129 (1976)

    Article  MathSciNet  Google Scholar 

  4. Grabowski, J., Wodecki, M.: A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion. Comput. Oper. Res. 31, 1891–1909 (2004)

    Article  MathSciNet  Google Scholar 

  5. Hansen, P., Mladenovic, N.: Variable neighborhood search: principles and applications. Eur. J. Oper. Res. 130, 449–467 (2001)

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  8. Liu, B., Wang, L., Jin, Y.-H.: An effective PSO-based memetic algorithm for flow shop scheduling. IEEE Trans. Syst. Man Cybern.-Part B: Cybern. 37(1), 18–27 (2007)

    Article  Google Scholar 

  9. Liu, Y.-F., Liu, S.-Y.: A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem. Appl. Soft Comput. 13, 1459–1463 (2013)

    Article  Google Scholar 

  10. Ma, Y., Zhao, Y., Wu, L., He, Y., Yang, X.-S.: Navigability analysis of magnetic map with projecting pursuit-based selection method by using firefly algorithm. Neurocomputing 159, 288–297 (2015)

    Article  Google Scholar 

  11. Marinakis, Y., Marinaki, M.: Particle swarm optimization with expanding neighborhood topology for the permutation flowshop scheduling problem. Soft Comput. 17(7), 1159–1173 (2013)

    Article  Google Scholar 

  12. Nowicki, E., Smutnicki, C.: A fast tabu search algorithm for the permutation flow-shop problem. Eur. J. Oper. Res. 91, 160–175 (1996)

    Article  Google Scholar 

  13. Osaba, E., Yang, X.S., Diaz, F., Onieva, E., Masegosa, A.D., Perallos, A.: A discrete firefly algorithm to solve a rich vehicle routing problem modelling a newspaper distribution system with recycling policy. Soft Comput. 21(18), 5295–5308 (2017)

    Article  Google Scholar 

  14. Pan, Q.-K., Tasgetiren, M.F., Liang, Y.-C.: A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Comput. Ind. Eng. 55, 795–816 (2008)

    Article  Google Scholar 

  15. 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  Google Scholar 

  16. Rajendran, C., Ziegler, H.: Two ant-colony algorithms for minimizing total flowtime in permutation flowshops. Comput. Ind. Eng. 48(4), 789–797 (2005)

    Article  Google Scholar 

  17. Ruiz, R., Maroto, C.: A comprehensive review and evaluation of permutation flowshop heuristics. Eur. J. Oper. Res. 165, 479–494 (2005)

    Article  Google Scholar 

  18. Ruiz, R., Maroto, C., Alcaraz, J.: Two new robust genetic algorithms for the flowshop scheduling problem. Omega 34, 461–476 (2006)

    Article  Google Scholar 

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

    Article  Google Scholar 

  20. Srikakulapu, R., Vinatha, U.: Combined approach of firefly algorithm with travelling salesmen problem for optimal design of offshore wind farm. In: IEEE Power and Energy Society General Meeting 2017, pp. 1–5 (2017)

    Google Scholar 

  21. Taillard, E.: Benchmarks for basic scheduling problems. Eur. J. Oper. Res. 64, 278–285 (1993)

    Article  Google Scholar 

  22. Tseng, L.-Y., Lin, Y.-T.: A hybrid genetic local search algorithm for the permutation flowshop scheduling problem. Eur. J. Oper. Res. 198, 84–92 (2009)

    Article  Google Scholar 

  23. 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, 121–128 (2010)

    Article  Google Scholar 

  24. Yang, X.-S.: Nature-Inspired Metaheuristic Algorithms, 2nd edn. Luniver Press, London (2010)

    Google Scholar 

  25. Zhang, C., Sun, J., Zhu, X., Yang, Q.: An improved particle swarm optimization algorithm for flowshop scheduling problem. Inf. Process. Lett. 108, 204–209 (2008)

    Article  MathSciNet  Google Scholar 

  26. Zhang, C., Ning, J., Ouyang, D.: A hybrid alternate two phases particle swarm optimization algorithm for flow shop scheduling problem. Comput. Ind. Eng. 58, 1–11 (2010)

    Article  Google Scholar 

  27. Zobolas, G.I., Tarantilis, C.D., Ioannou, G.: Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm. Comput. Oper. Res. 36, 1249–1267 (2009)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Production Engineering and Management, Technical University of Crete, Chania, Greece

    Andromachi Taxidou, Ioannis Karafyllidis, Magdalene Marinaki & Yannis Marinakis

  2. Industrial Logistics, Luleå Technical University, 97187, Luleå, Sweden

    Athanasios Migdalas

Authors
  1. Andromachi Taxidou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ioannis Karafyllidis
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Magdalene Marinaki
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Yannis Marinakis
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Athanasios Migdalas
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yannis Marinakis .

Editor information

Editors and Affiliations

  1. University of Macedonia, Thessaloniki, Greece

    Angelo Sifaleras

  2. University of Kent, Canterbury, UK

    Said Salhi

  3. Royal Military College of Canada, Kingston, ON, Canada

    Jack Brimberg

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Taxidou, A., Karafyllidis, I., Marinaki, M., Marinakis, Y., Migdalas, A. (2019). A Hybrid Firefly - VNS Algorithm for the Permutation Flowshop Scheduling Problem. In: Sifaleras, A., Salhi, S., Brimberg, J. (eds) Variable Neighborhood Search. ICVNS 2018. Lecture Notes in Computer Science(), vol 11328. Springer, Cham. https://doi.org/10.1007/978-3-030-15843-9_21

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-15843-9_21

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-15842-2

  • Online ISBN: 978-3-030-15843-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation