Top

Published in:

2024 | OriginalPaper | Chapter

Analysis of Constructive Heuristics with Cuckoo Search Algorithm, Firefly Algorithm and Simulated Annealing in Scheduling Problems

Authors : Carlota Moreira, Catarina Costa, André S. Santos, Ana M. Madureira, Marta Barbosa

Published in: Flexible Automation and Intelligent Manufacturing: Establishing Bridges for More Sustainable Manufacturing Systems

Publisher: Springer Nature Switzerland

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This chapter delves into the analysis of constructive heuristics combined with nature-based metaheuristics, specifically the Cuckoo Search Algorithm, Firefly Algorithm, and Simulated Annealing, in the context of scheduling problems. It begins with an introduction to these metaheuristics and their adaptability to various optimization problems. The literature review highlights key constructive heuristics such as NEH, Palmer, and CDS, and discusses their effectiveness in minimizing makespan. The chapter then presents the problem context, parameterization of metaheuristics, and statistical analysis of the results. The statistical evaluation, using Kruskal-Wallis and Dunn's Post Hoc tests, reveals significant differences between the combinations of metaheuristics and heuristics. The results show that while the Firefly Algorithm with NEH (FA-NEH) generally provides the best solutions, it requires more runtime. Simulated Annealing with Palmer and CDS (SA-Palmer and SA-CDS) offers a better balance of effectiveness and efficiency. The chapter concludes with insights into the robustness of the algorithms and suggestions for future work, including the potential for hybrid metaheuristics.

AI Generated

This summary of the content was generated with the help of AI.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Study of Hysteresis Curves for Conformity Assessment in EGR Valves

next chapter Mapping of Newcomer Clients in Federated Learning Based on Activation Strength

Kalczynski, P.J., Kamburowski, J.: On the NEH heuristic for minimizing the makespan in permutation flow shops. Omega 35(1), 53–60 (2007)CrossRef

Sauvey, C., Sauer, N.: Two NEH heuristic improvements for Flowshop scheduling problem with Makespan criterion. Algorithms 13(112), 1–14 (2020)MathSciNet

Liu, W., Jin, Y., Price, M.: A new improved NEH heuristic for permutation flowshop scheduling problems. Int. J. Prod. Econ. 193(June), 21–30 (2017)CrossRef

Sharma, M., Sharma, M., Sharma, S.: An improved NEH heuristic to minimize makespan for flow shop scheduling problems. Decis. Sci. Lett. 10(3), 311–322 (2021)CrossRef

Chen, C., Vempati, V.S., Aljaber, N.: An application of genetic algorithms for flow shop problems. Eur. J. Oper. Res. 80(2), 389–396 (1995)CrossRef

Sharma, A., Moses, A.C., Borah, S.B., Adhikary, A.: Investigating the impact of workforce racial diversity on the organizational corporate social responsibility performance: an institutional logics perspective. J. Bus. Res. 107, 138–152 (2020)CrossRef

Taylor, P., Hundal, T.S., Rajgopal, J.: An extension of Palmer’s heuristic for the flow shop scheduling problem. Int. J. Prod. Res. 26(6), 1119–1124 (1988)CrossRef

Ho, J.C., Chang, Y.-L.: Theory and methodology a new heuristic for the n-job, M-machine flow-shop problem. Eur. J. Oper. Res. 52(2), 194–202 (1991)CrossRef

Mashuri, C., Mujianto, A.H., Sucipto, H., Arsam, R.Y., Permadi, G.S.: Production time optimization using Campbell Dudek Smith (CDS) algorithm for production scheduling. E3S Web Conf. 9(201 9), 5–9 (2019)

10.

Charpentier, P.: Design of job scheduling system and software for packaging process with SPT, EDD, LPT, CDS and NEH algorithm at PT. ACP Desi g n of job scheduling system and software for packaging process with SPT, EDD, LPT, CDS and NEH algorithm at PT. IOP Conf. Ser. Mater. Sci. Eng. 528(1), 012045 (2019)

11.

Smith, C.D., Pour, H.: Makespan minimization in batik Murni SMEs with palmer, Campbell Dukdek Smith, and heuristic pour algorithm. Spektrum Ind. 18(1), 95–102 (2020)CrossRef

12.

Melouk, S., Damodaran, P., Chang, P.Y.: Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing. Int. J. Prod. Econ. 87(2), 141–147 (2004)CrossRef

13.

D’Amico, S.J., Wang, S.J., Batta, R., Rump, C.M.: A simulated annealing approach to police district design. Comput. Oper. Res. 29(6), 667–684 (2002)CrossRef

14.

Marichelvam, M.K., Prabaharan, T., Yang, X.S.: Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan. Appl. Soft Comput. J. 19, 93–101 (2014)CrossRef

15.

de Alencar, M.R.B., de Souza, B.A., Neves, W.L.A., Ferraz, R.S.F.: Aplicação de Algoritmo de Busca Cuco no Dimensionamento Ótimo de Gerador Fotovoltaico para Redução de Custos, pp. 731–736 (2019)

16.

Moreira, C., Costa, C., Santos, A.S., Bastos, J.A., Varela, L.R., Brito, M.F.: Firefly and cuckoo search algorithm for scheduling problems: a performance analysis. In: Machado, J., et al. (eds.) ICIENG 2022. LNME, pp. 75–88. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-09360-9_7

17.

Yang, X.S., Karamanoglu, M.: Swarm Intelligence and Bio-Inspired Computation: An Overview (2013)

18.

Udaiyakumar, K.C., Chandrasekaran, M.: Application of firefly algorithm in job shop scheduling problem for minimization of Makespan. Procedia Eng. 97, 1798–1807 (2014)CrossRef

19.

Jaradat, A., Matalkeh, B., Diabat, W.: Solving traveling salesman problem using firefly algorithm and k-means clustering. In: 2019 IEEE Jordan International Joint. Conference on Electronic Engineering Information Technology JEEIT 2019 - Proceedings, no. September, pp. 586–589 (2019)

20.

Kota and, L., Jármai, K.: Discretization of the Firefly Algorithm for the Travelling Salesman Problem (2013)

21.

Aarts, E., Korst, J.: Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing. Wiley, New York

22.

Kolisch, R., Hartmann, S.: Heuristic algorithms for the resource-constrained project scheduling problem: classification and computational analysis. In: Węglarz, J. (ed.) Project Scheduling. Springer, Boston (1999). https://doi.org/10.1007/978-1-4615-5533-9_7

23.

Khadwilard, A., Chansombat, S., Thepphakorn, T., Thapatsuwan, P., Chainate, W., Pongcharoen, P.: Application of firefly algorithm and its parameter setting for job shop scheduling. In: First Symposium Hands-On Research Development, vol. 1, no. 1 (2011)

24.

García, J., Crawford, B., Soto, R., Castro, C., Paredes, F.: A k-means binarization framework applied to multidimensional knapsack problem. Appl. Intell. 48(2), 357–380 (2017). https://doi.org/10.1007/s10489-017-0972-6CrossRef

25.

Belbachir, D., Boumediene, F., Hassam, A., Ghomri, L.: Adaptation and parameters studies of CS algorithm for flow shop scheduling problem. Int. J. Electr. Comput. Eng. 11(3), 2266–2274 (2021)

26.

Gleason, J.: Comparative Power of the Anova, Randomization Anova, and Kruskal-Wallis Test. Detroit, Michigan (2013)

Title: Analysis of Constructive Heuristics with Cuckoo Search Algorithm, Firefly Algorithm and Simulated Annealing in Scheduling Problems
Authors: Carlota Moreira
Catarina Costa
André S. Santos
Ana M. Madureira
Marta Barbosa
Publisher: Springer Nature Switzerland
Book: Flexible Automation and Intelligent Manufacturing: Establishing Bridges for More Sustainable Manufacturing Systems
Print ISBN: 978-3-031-38164-5

Electronic ISBN: 978-3-031-38165-2

Copyright Year: 2024
DOI: https://doi.org/10.1007/978-3-031-38165-2_129