[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Memetic algorithm based on marriage in honey bees optimization for flexible job shop scheduling problem

  • Regular Research Paper
  • Published:
Memetic Computing Aims and scope Submit manuscript

Abstract

This paper proposes a new memetic algorithm based on marriage in honey bees optimization (MBO) algorithm for solving the flexible job shop scheduling problem. The proposed algorithm introduces four new features to the standard MBO algorithm, mainly to get the search to move away from the local optimum: (1) the use of a harmony memory to improve the quality of initial population; (2) the introduction of a new crossover operator called triparental crossover to help increase the genetic diversity in the offspring; (3) the addition of adaptive crossover probability (\(\hbox {P}_{\mathrm{c}})\) and mutation probability (\(\hbox {P}_{\mathrm{m}})\) to remove the need for users to specify these probabilities; and (4) the incorporation of simulated annealing algorithm embedded with a set of heuristics to enhance the local search capability. The proposed algorithm was evaluated and compared to several state-of-the-art algorithms in the literature. The experimental results on five sets of standard benchmarks show that the proposed algorithm is very effective in solving the flexible job shop scheduling problems.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Yuan Y, Xu H (2013) A memetic algorithm for the multi-objective flexible job shop scheduling problem. In: Proceeding of the 15th annual conference on genetic and evolutionary computation, pp 559–566. doi:10.1145/2463372.2463431

  2. González MA, Vela CR, Varela R (2015) Scatter search with path relinking for the flexible job shop scheduling problem. Eur J Oper Res 245:35–45. doi:10.1016/j.ejor.2015.02.052

    Article  MATH  MathSciNet  Google Scholar 

  3. Mekni S, Fayech BC (2014) A modified invasive weed optimization algorithm for multiobjective flexible job shop scheduling problems. Comput Sci Inf Technol 4:51–60. doi:10.5121/csit.2014.41106

    Google Scholar 

  4. Ma W, Zuo Y, Zeng J, Liang S, Jiao L (2014) A memetic algorithm for solving flexible job-shop scheduling problems. In: Proceedings of the 2014 IEEE congress on evolutionary computation, pp 66–73. doi:10.1109/CEC.2014.6900332

  5. Xu Y, Wang L, Wang S (2013) An effective shuffled frog-leaping algorithm for the flexible job-shop scheduling problem. In: Proceedings of the 2013 IEEE symposium on computational intelligence in control and automation, pp 128–134. doi:10.1109/CICA.2013.6611673

  6. Yuan Y, Xu H, Yang J (2013) A hybrid harmony search algorithm for the flexible job shop scheduling problem. Appl Soft Comput 13:3259–3272. doi:10.1016/j.asoc.2013.02.013

    Article  Google Scholar 

  7. Yuan Y, Xu H (2013) Flexible job shop scheduling using hybrid differential evolution algorithms. Comput Ind Eng 65:246–260. doi:10.1016/j.cie.2013.02.022

    Article  Google Scholar 

  8. Karimi H, Rahmati SA, Zandieh M (2012) An efficient knowledge-based algorithm for the flexible job shop scheduling problem. Knowl Based Syst 36:236–244. doi:10.1016/j.knosys.2012.04.001

  9. Wang L, Zhou G, Xu Y, Wang S, Liu M (2012) An effective artificial bee colony algorithm for the flexible job-shop scheduling problem. Int J Adv Manuf Technol 60:303–315. doi:10.1007/s00170-011-3610-1

  10. Rahmati SA, Zandieh M (2012) A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem. Int J Adv Manuf Technol 58:1115–1129. doi:10.1007/s00170-011-3437-9

    Article  Google Scholar 

  11. Hasan SMK, Sarker R, Essam D, Cornforth D (2009) Memetic algorithms for solving job-shop scheduling problems. Memet Comput 1:69–83. doi:10.1007/s12293-008-0004-5

    Article  Google Scholar 

  12. Raeesi NMR, Kobti Z (2012) A memetic algorithm for job shop scheduling using a critical-path-based local search heuristic. Memet Comput 4:231–245. doi:10.1007/s12293-012-0084-0

    Article  Google Scholar 

  13. Abbass HA (2001) MBO: marriage in honey bees optimization—a haplometrosis polygynous swarming approach. In: Proceedings of the 2001 congress on evolutionary computation, pp 207–214. doi:10.1109/CEC.2001.934391

  14. Perry M, Reny PJ, Robson AJ (2011) Understanding biparental sex through the absence of triparental sex. http://www.ma.huji.ac.il/~motty/documents/perry-reny-robson-06-04-11clean.pdf. Accessed Feb 2015

  15. Fischer-Fantuzzi L, Girolamo MD (1961) Triparental matings in escherichia coli. Genetics 46:1305–1315

    Google Scholar 

  16. Harbo JR, Rinderer TE (1980) Breeding and genetics of honey bees. In: Beekeeping in the United States. Agriculture handbook, No. 335. U.S. Department of Agriculture, Science and Education Administration, pp 49–57

  17. Glenn T (2007) Genetic aspects of queen production. Glenn Apiaries. http://www.glenn-apiaries.com/genetic_aspects_queen_production_1.html. Accessed Feb 2015

  18. Laidlaw HH, Page RE (1986) Mating designs. In: Rinderer TE (ed) Bee Genetics and Breeding. Academic Press, Florida, pp 323–344

  19. Gao J, Sun L, Gen M (2008) A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Comput Oper Res 35:2892–2907

    Article  MATH  MathSciNet  Google Scholar 

  20. Geem ZW, Kim JH, Loganathan GV (2001) A new heuristic optimization algorithm: harmony search. Simulation 76:60–68. doi:10.1177/003754970107600201

    Article  Google Scholar 

  21. Syswerda G (1989) Uniform crossover in genetic algorithms. In: Proceedings of the third international conference on genetic algorithms, pp 2–9

  22. De Jong KA (1975) Analysis of the behavior of a class of genetic adaptive systems. Ph.D. dissertation, University of Michigan

  23. Fogel DB (1988) An evolutionary approach to the traveling salesman problem. Biol Cybern 60:139–144. doi:10.1007/BF00202901

    Article  MathSciNet  Google Scholar 

  24. Mastrolilli M (2016) Flexible job shop problem. http://people.idsia.ch/~monaldo/fjsp.html

  25. Fattahi P, Mehrabad MS, Jolai F (2007) Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. J Intell Manuf 18:331–342. doi:10.1007/s10845-007-0026-8

    Article  Google Scholar 

  26. Yuan Y, Xu H (2013) An integrated search heuristic for large-scale flexible job shop scheduling problems. Comput Oper Res 40:2864–2877

    Article  MATH  MathSciNet  Google Scholar 

  27. Mastrolilli M, Gambardella LM (2000) Effective neighborhood functions for the flexible job shop problem. J Sched 3:3–20

    Article  MATH  MathSciNet  Google Scholar 

  28. Hmida AB, Haouari M, Huguet MJ, Lopez P (2010) Discrepancy search for the flexible job shop scheduling problem. Comput Oper Res 37:2192–2201

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgements

This work was supported by SHELL Centennial Education Fund, Shell Companies in Thailand.

Author information

Authors and Affiliations

  1. The Faculty of Information Technology, King Mongkut’s Institute of Technology Ladkrabang, Bangkok, 10520, Thailand

    Ajchara Phu-ang & Arit Thammano

Authors
  1. Ajchara Phu-ang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Arit Thammano
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Arit Thammano.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Phu-ang, A., Thammano, A. Memetic algorithm based on marriage in honey bees optimization for flexible job shop scheduling problem. Memetic Comp. 9, 295–309 (2017). https://doi.org/10.1007/s12293-017-0230-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12293-017-0230-9

Keywords

Search

Navigation