Modified Firefly Algorithm using Iterated Descent Method to Solve Machine Scheduling Problems
Keywords:
Single machine scheduling, Metaheuristics, Iterated descent method, Firefly algorithm, Genetic algorithmAbstract
One of the most efficient metaheuristic algorithms that is used to solve hard optimization problems is the firefly algorithm (FFA). In this paper we use this algorithm to solve a single machine scheduling problem, we aim to minimize the sum of the two cost functions: the maximum tardiness and the maximum earliness. This problem (P) is NP-hard so we solve this problem using FFA as a metaheuristic algorithm. To explore the search space and get a good solution to a problem (Q), we hybridize FFA by Iterated Descent Method (IDM) in three ways and the results are FFA1, FFA2, and FFA3. In the computational test, we evaluate these algorithms (FFA, FFA1, FFA2, FFA3) compared with the genetic algorithm (GA) through a simulation process with job sizes from 10 jobs to 100 jobs. The results indicate that these modifications improve the performance of the original FFA and one of them (FFA3) gives better performance than others.
References
Grefenstette, J.J.; “Genetic algorithms and machine learning”, EM Proceedings of the sixth annual conference on Computational learning theory, 1993, p. 3–4.
Poli, R.; Kennedy, J.; Blackwell, E.T.; “Particle swarm optimization”, Swarm Intelligence, 1(1): 33–57, 2007.
Husbands, P.; Harvey, I.; Cliff, D.; Miller, E.G.; “Artificial evolution: A new path for artificial intelligence”. Brain Cogn., 34(1): 130–159, 1997.
Yang, X.-S.; “Nature-inspired metaheuristic algorithms”. Luniver Press, 2010.
Yang, X.-S.; “Firefly algorithms for multimodal optimization”, Em. International symposium on stochastic algorithms, Springer, 2009, p. 169–178.
Sayadi, M.; Ramezanian, R.; Ghaffari-Nasab, E.N.; “A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems.”. Int. J. Indus. Eng. Comp., 1(1): 1–10, 2010.
Khadwilard, A.; Chansombat, S.; Thepphakorn, T.; Chainate, W.; Pongcharoen, E.P.; “Application of firefly algorithm and its parameter setting for job shop scheduling.”. The J. Indus. Technol., 8(1): 49–58, 2012.
Fister, I.; Yang, X.-S.; Fister, I.; Brest, E.J.; “Memetic firefly algorithm for combinatorial optimization”, arXiv preprint arXiv:1204.5165, 2012.
Nouri, B.V.; Fattahi, P.; Ramezanian, E.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.
Marichelvam, M.K.; Prabaharan, T.; Yang, E.X.S.; “A discrete firefly algorithm for the multi-objective hybrid flowshop scheduling problems”, IEEE Trans. Evol. Comp., 18(2): 301–305, 2013.
Huang, K.-W.; Girsang, A.S.; Wu, Z.-X.; Chuang, E.Y.-W.; “A hybrid crow search algorithm for solving permutation flow shop scheduling problems”, Appl. Sci., 9(7): 1353, 2019.
Jaradat, A.; Diabat, W.; “Solving traveling salesman problem using firefly algorithm and k-means clustering”, em 2019 IEEE Jordan International Joint Conference on Electrical Engineering and Information Technology (JEEIT), IEEE, 2019, p. 586–589.
Rajagopalan, A.; Modale, D.R.; Senthilkumar, E.R.; “Optimal scheduling of tasks in cloud computing using hybrid firefly-genetic algorithm”, em Advances in decision sciences, image processing, security and computer vision, Springer, 2020, p. 678–687.
Al-Behadili, H.N.K.; “Improved Firefly Algorithm with Variable Neighborhood Search for Data Clustering”, Baghdad Sci. J., 19(2), 2022.
Shandilya, S.K.; Choi, B.J.; Kumar, A.; Upadhyay, E.S.; “Modified Firefly Optimization Algorithm-Based IDS for Nature-Inspired Cybersecurity”, Processes, 11(3): 715-720, 2023.
Bacanin, N.; Brajevic, I.; Tuba, E.M.; “Firefly algorithm applied to integer programming problems”, Recent Adv. Math., 888: 999-1002, 2013.
Downloads
Published
Issue
Section
License
Copyright (c) 2023 Al-Nahrain Journal of Science
This work is licensed under a Creative Commons Attribution 4.0 International License.
.jpg)
