Modified artificial fish swarm algorithm to solve unrelated parallel machine scheduling problem under fuzzy environment

Azhar Mahdi Ibadi; Rosshairy Abd Rahman; Azhar Mahdi Ibadi; Rosshairy Abd Rahman

doi:10.3934/math.20241679

AIMS Mathematics

2024, Volume 9, Issue 12: 35326-35354. doi: 10.3934/math.20241679

Previous Article Next Article

Research article Special Issues

Modified artificial fish swarm algorithm to solve unrelated parallel machine scheduling problem under fuzzy environment

Azhar Mahdi Ibadi ^{1,2
,
,},
Rosshairy Abd Rahman ¹

1.
School of Quantitative Sciences, Universiti Utara Malaysia, Sintok, Kedah 06010, Malaysia
2.
Department of Physics, College of Science, University of Sumer, Al Rifaee, Thi-Qar 64005, Iraq

Received: 07 July 2024 Revised: 29 November 2024 Accepted: 04 December 2024 Published: 18 December 2024
MSC : 90C27, 90C70

Unrelated parallel machine scheduling problem (UPMSP) in a fuzzy environment is an active research area due to the fuzzy nature of most real-world problems. UPMSP is an NP-hard problem; thus, finding optimal solutions is challenging, particularly when multiple objectives need to be considered. Hence, a metaheuristic algorithm based on a modified artificial fish swarm algorithm (AFSA) is presented in this study to minimize the multi-objective makespan and total tardiness. Three modifications were made to the proposed algorithm. First, aspiration behavior was added to AFSA behaviors to increase effectiveness. Second, improved parameters such as step and visual were used to balance global search capability and convergence rate. Finally, a transformation method was injected to make the algorithm suitable for discrete optimization problems such as UPMSP. The proposed algorithm was compared with AFSA and five modified versions of AFSA to verify and measure the algorithm's effectiveness by conducting three different sizes of problems. Afterward, the Wilcoxon signed-rank test was used to statistically evaluate the algorithm's performance. The results indicate that the proposed algorithm significantly outperformed the other algorithms, especially for medium and large-sized problems.
- unrelated parallel machine scheduling problem,
- fuzzy sets,
- multi-objective,
- artificial fish swarm algorithm,
- modified algorithm
Citation: Azhar Mahdi Ibadi, Rosshairy Abd Rahman. Modified artificial fish swarm algorithm to solve unrelated parallel machine scheduling problem under fuzzy environment[J]. AIMS Mathematics, 2024, 9(12): 35326-35354. doi: 10.3934/math.20241679

Related Papers:

Abstract

Unrelated parallel machine scheduling problem (UPMSP) in a fuzzy environment is an active research area due to the fuzzy nature of most real-world problems. UPMSP is an NP-hard problem; thus, finding optimal solutions is challenging, particularly when multiple objectives need to be considered. Hence, a metaheuristic algorithm based on a modified artificial fish swarm algorithm (AFSA) is presented in this study to minimize the multi-objective makespan and total tardiness. Three modifications were made to the proposed algorithm. First, aspiration behavior was added to AFSA behaviors to increase effectiveness. Second, improved parameters such as step and visual were used to balance global search capability and convergence rate. Finally, a transformation method was injected to make the algorithm suitable for discrete optimization problems such as UPMSP. The proposed algorithm was compared with AFSA and five modified versions of AFSA to verify and measure the algorithm's effectiveness by conducting three different sizes of problems. Afterward, the Wilcoxon signed-rank test was used to statistically evaluate the algorithm's performance. The results indicate that the proposed algorithm significantly outperformed the other algorithms, especially for medium and large-sized problems.

References

[1]	K. Salimifard, D. Mohammadi, R. Moghdani, A. Abbasizad, Green fuzzy parallel machine scheduling with sequence-dependent setup in the plastic moulding industry, Asian J. Manag. Sci. Appl., 4 (2019), 27–48. https://doi.org/10.1504/AJMSA.2019.101423 doi: 10.1504/AJMSA.2019.101423
[2]	M. R. Garey, D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, Freeman, San Francisco, (1979). https://doi.org/10.1137/1024022
[3]	A. E. Ezugwu, A. K. Shukla, R. Nath, A. A. Akinyelu, J. O. Agushaka, H. Chiroma, et al., Metaheuristics: A comprehensive overview and classification along with bibliometric analysis. Artif. Intell. Rev., 54 (2021), 4237–4316. https://doi.org/10.1007/s10462-020-0952-0 doi: 10.1007/s10462-020-0952-0
[4]	D. Y. Lin, T. Y. Huang, A hybrid metaheuristic for the unrelated parallel machine scheduling problem, Mathematics, 9 (2021). 1–20. https://doi.org/10.3390/math9070768
[5]	A. E. Ezugwu, F. Akutsah, An improved firefly algorithm for the unrelated parallel machines scheduling problem with sequence-dependent setup times, IEEE Access, 6 (2018), 54459–54478. https://doi.org/10.1109/access.2018.2872110 doi: 10.1109/access.2018.2872110
[6]	C. Chen, M. Fathi, M. Khakifirooz, K. Wu, Hybrid tabu search algorithm for unrelated parallel machine scheduling in semiconductor fabs with setup times, job release, and expired times, Comput. Ind. Eng., 165 (2022), 107915. https://doi.org/10.1016/j.cie.2021.107915 doi: 10.1016/j.cie.2021.107915
[7]	J. B. Abikarram, K. McConky, R. Proano, Energy cost minimization for unrelated parallel machine scheduling under real time and demand charge pricing, J. Clean. Prod., 208 (2019), 232–242. https://doi.org/10.1016/j.jclepro.2018.10.048 doi: 10.1016/j.jclepro.2018.10.048
[8]	N. Vakhania, On preemptive scheduling on unrelated machines using linear programming, AIMS Math., 8 (2023), 7061–7082. https://doi.org/10.3934/math.2023356 doi: 10.3934/math.2023356
[9]	Y. Fu, Y. Hou, Z. Wang, X. Wu, K. Gao, L. Wang, Distributed scheduling problems in intelligent manufacturing systems, Tsinghua Sci. Technol., 26 (2021), 625–645. https://doi.org/10.26599/tst.2021.9010009 doi: 10.26599/tst.2021.9010009
[10]	İ. Sarıçiçek, Multi-objective scheduling by maximizing machine preferences for unrelated parallel machines, Sigma J. Eng. Nat. Sci., 38 (2020), 405–419. https://doi.org/10.5829/idosi.ije.2017.30.02b.09 doi: 10.5829/idosi.ije.2017.30.02b.09
[11]	R. Meng, Y. Rao, Q. Luo, Modeling and solving for bi-objective cutting parallel machine scheduling problem, Ann. Oper. Res., 285 (2020), 223–245. https://doi.org/10.1007/s10479-019-03208-z doi: 10.1007/s10479-019-03208-z
[12]	M. Moser, N. Musliu, A. Schaerf, F. Winter, Exact and metaheuristic approaches for unrelated parallel machine scheduling, J. Scheduling, 25 (2022), 507–534. https://doi.org/10.1007/s10951-021-00714-6 doi: 10.1007/s10951-021-00714-6
[13]	M. Đurasević, D. Jakobović, Heuristic and metaheuristic methods for the unrelated machines scheduling problem: A Survey, IEEE T. Cybernetics, (2021). http://arXiv.org/abs/2107.13106
[14]	A. F. Guevara-Guevara, V. Gómez-Fuentes, L. J. Posos-Rodríguez, N. Remolina-Gómez, E. M. González-Neira, Earliness/tardiness minimization in a no-wait flow shop with sequence-dependent setup times, J. Proj. Manag., 7 (2022). 177–190. https://doi.org/10.5267/j.jpm.2021.12.001
[15]	A. Sadati, R. Tavakkoli-Moghaddam, B. Naderi, M. Mohammadi, A bi-objective model for a scheduling problem of unrelated parallel batch processing machines with fuzzy parameters by two fuzzy multi-objective meta-heuristics, Iran. J. Fuzzy Syst., 16 (2019), 21–40. https://doi.org/10.3233/ifs-151846 doi: 10.3233/ifs-151846
[16]	G. Rivera Zarate, Outranking-based multi-objective PSO for scheduling unrelated parallel machines with a freight industry-oriented application, Instituto de Ingeniería Tecnología. (2021). https://doi.org/10.1016/j.engappai.2021.104556
[17]	A. Fallahi, B. Shahidi-Zadeh, S. T. A. Niaki, Unrelated parallel batch processing machine scheduling for production systems under carbon reduction policies: NSGA-II and MOGWO metaheuristics, Soft Comput., 27 (2023), 17063–17091. https://doi.org/10.1007/s00500-023-08754-0 doi: 10.1007/s00500-023-08754-0
[18]	W. Zhou, F. Chen, X. Ji, H. Li, J. Zhou, A Pareto-based discrete particle swarm optimization for parallel casting workshop scheduling problem with fuzzy processing time, Knowl. Based Syst., (2022), 256, 109872. https://doi.org/10.1016/j.knosys.2022.109872
[19]	M. Z. Erişgin Barak, M. Koyuncu, Fuzzy order acceptance and scheduling on identical parallel machines, Symmetry, 13 (2021), 1236. https://doi.org/10.3390/sym13071236 doi: 10.3390/sym13071236
[20]	J. Rezaeian, S. Mohammad-Hosseini, S. Zabihzadeh, K. Shokoufi, Fuzzy scheduling problem on unrelated parallel machine in JIT production system, Artif. Intell. Evol., 1 (2020), 17–33. https://doi.org/10.37256/aie.112020202 doi: 10.37256/aie.112020202
[21]	K. Li, J. Chen, H. Fu, Z. Jia, W. Fu, Uniform parallel machine scheduling with fuzzy processing times under resource consumption constraint, Appl. Soft Comput., 82 (2019), 1–13. https://doi.org/10.1016/j.asoc.2019.105585 doi: 10.1016/j.asoc.2019.105585
[22]	H. A. Alsattar, A. A. Zaidan, B. B. Zaidan, Novel meta-heuristic bald eagle search optimisation algorithm, Artif. Intell. Rev., 53 (2020), 2237–2264. https://doi.org/10.1007/s10462-019-09732-5 doi: 10.1007/s10462-019-09732-5
[23]	F. Pourpanah, R. Wang, C. P. Lim, X. Z. Wang, D. Yazdani, A review of artificial fish swarm algorithms: Recent advances and applications, Artif. Intell. Rev., 56 (2020), 1867–1903. https://doi.org/10.1007/s10462-022-10214-4 doi: 10.1007/s10462-022-10214-4
[24]	L. Zhao, F. Wang, Y. Bai, Route planning for autonomous vessels based on improved artificial fish swarm algorithm, Ships Offshore Struc., 18 (2023), 897–906. https://doi.org/10.1080/17445302.2022.2081423 doi: 10.1080/17445302.2022.2081423
[25]	W. H. Tan, J. Mohamad-Saleh, Normative fish swarm algorithm (NFSA) for optimization, Soft Comput., 24 (2020), 2083–2099. https://doi.org/10.1007/s00500-019-04040-0 doi: 10.1007/s00500-019-04040-0
[26]	J. Huang, J. Zeng, Y. Bai, Z. Cheng, Z. Feng, L. Qi, et al., Layout optimization of fiber Bragg grating strain sensor network based on modified artificial fish swarm algorithm, Opt. Fiber Technol., 65 (2021), 102583. https://doi.org/10.1016/j.yofte.2021.102583 doi: 10.1016/j.yofte.2021.102583
[27]	F. Wang, L. Zhao, Y. Bai, Path planning for unmanned surface vehicles based on modified Artificial Fish Swarm Algorithm with local optimizer, Math. Probl. Eng., (2022). https://doi.org/10.1155/2022/1283374
[28]	J. Jin, Z. Zhang, L. Zhang, A modified artificial fish swarm algorithm for unit commitment optimization, in 2023 Eighth International Conference on Electromechanical Control Technology and Transportation (ICECTT), 760–767. https://doi.org/10.1117/12.2689449
[29]	Y. Gao, L. Xie, Z. Zhang, Q. Fan, Twin support vector machine based on improved artificial fish swarm algorithm with application to flame recognition, Appl. Intell., 50 (2020), 2312–2327. https://doi.org/10.1007/s10489-020-01676-6 doi: 10.1007/s10489-020-01676-6
[30]	T. Li, F. Yang, D. Zhang, L. Zhai, Computation scheduling of multi-access edge networks based on the artificial fish swarm algorithm, IEEE Access, 9 (2021), 74674–74683. https://doi.org/10.1109/ACCESS.2021.3078539 doi: 10.1109/ACCESS.2021.3078539
[31]	E. B. Tirkolaee, A. Goli, G. W. Weber, Fuzzy mathematical programming and self-adaptive artificial fish swarm algorithm for just-in-time energy-aware flow shop scheduling problem with outsourcing option, IEEE T. Fuzzy Syst., 28 (2020), 2772–2783. https://doi.org/10.1109/TFUZZ.2020.2998174 doi: 10.1109/TFUZZ.2020.2998174
[32]	P. Kongsri, J. Buddhakulsomsiri, A mixed integer programming model for unrelated parallel machine scheduling problem with sequence dependent setup time to minimize makespan and total tardiness, In 2020 IEEE 7th International Conference on Industrial Engineering and Applications (ICIEA), 605–609. https://doi.org/10.1109/iciea49774.2020.9102086
[33]	R. L. Graham, E. L. Lawler, J. K. Lenstra, A. R. Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals Discrete Math., 5 (1979), 287–326. https://doi.org/10.1016/s0167-5060(08)70356-x doi: 10.1016/s0167-5060(08)70356-x
[34]	Y. Li, J. F. Côté, L. Callegari-Coelho, P. Wu, Novel formulations and logic-based benders decomposition for the integrated parallel machine scheduling and location problem, INFORMS J. Comput., 34 (2022), 1048–1069. https://doi.org/10.1287/ijoc.2021.1113 doi: 10.1287/ijoc.2021.1113
[35]	Y. Li, J. F. Côté, L. C. Coelho, P. Wu, Novel efficient formulation and matheuristic for large-sized unrelated parallel machine scheduling with release dates, Int. J. Prod. Res., 60 (2022), 6104–6123. https://doi.org/10.1080/00207543.2021.1983224 doi: 10.1080/00207543.2021.1983224
[36]	S. Chakraverty, D. M. Sahoo, N. R. Mahato, Defuzzification, In Concepts of Soft Computing, Springer Singapore, 2019,117–127. https://doi.org/10.1007/978-981-13-7430-2_7
[37]	L. A. Zadeh, Fuzzy sets, Inf. Control, 8 (1965), 338–353. https://doi.org/10.1016/s0019-9958(65)90241-x doi: 10.1016/s0019-9958(65)90241-x
[38]	H. J. Zimmermann, Fuzzy set theory, WIRES Comput. Stat., 2 (2010), 317–332. https://doi.org/10.1002/wics.82 doi: 10.1002/wics.82
[39]	H. T. Lee, S. H. Chen, H. Y. Kang, Multicriteria scheduling using fuzzy theory and tabu search, Int. J. Prod. Res., 40 (2002), 1221–1234. https://doi.org/10.1080/00207540110098832 doi: 10.1080/00207540110098832
[40]	S. Banerjee, T. K. Roy, Arithmetic operations on generalized trapezoidal fuzzy number and its applications, Turkish J. Fuzzy Syst., 3 (2012), 16–44.
[41]	J. Shen, An uncertain parallel machine problem with deterioration and learning effect, Comput. Appl. Math., 38 (2019), 1–17. https://doi.org/10.1007/s40314-019-0789-5
[42]	T. W. Liao, P. Su, Parallel machine scheduling in fuzzy environment with hybrid ant colony optimization including a comparison of fuzzy number ranking methods in consideration of spread of fuzziness, Appl. Soft Comput. J., 56 (2017), 65–81. https://doi.org/10.1016/j.asoc.2017.03.004 doi: 10.1016/j.asoc.2017.03.004
[43]	T. S. Liou, M. J. Wang, Ranking fuzzy numbers with integral value, Fuzzy Sets Syst., 50 (1992), 247–255. https://doi.org/10.1016/0165-0114(92)90223-q doi: 10.1016/0165-0114(92)90223-q
[44]	X. L. Li, An optimizing method based on autonomous animats: fish-swarm algorithm, Syst. Eng. Theory Practice, 22 (2002), 32–38.
[45]	A. W. Abdulqader, S. M. Ali, Diversity operators-based Artificial Fish Swarm Algorithm to solve flexible job shop scheduling problem, Baghdad Sci. J., (2023). https://doi.org/10.21123/bsj.2023.6810
[46]	L. Zhang, M. Fu, T. Fei, X. Pan, Application of FWA-Artificial Fish Swarm Algorithm in the Location of Low-Carbon Cold Chain Logistics Distribution Center in Beijing-Tianjin-Hebei Metropolitan Area, Sci. Programming, (2021), 1–10. https://doi.org/10.1155/2021/9945583
[47]	Y. Liu, X. Feng, L. Zhang, W. Hua, K. Li, A pareto artificial fish swarm algorithm for solving a multi-objective electric transit network design problem, Transportmetrica A, 16 (2020), 1648–1670. https://doi.org/10.1080/23249935.2020.1773574 doi: 10.1080/23249935.2020.1773574
[48]	S. Gorgich, S. Tabatabaei, Proposing an energy-aware routing protocol by using fish swarm optimization algorithm in WSN (wireless sensor networks), Wireless Pers. Commun., 119 (2021), 1935–1955. https://doi.org/10.1007/s11277-021-08312-7 doi: 10.1007/s11277-021-08312-7
[49]	R. A. Hasan, R. A. I. Alhayali, M. A., Mohammed, T. Sutikno, An improved fish swarm algorithm to assign tasks and cut down on latency in cloud computing, TELKOMNIKA (Telecommunication Computing Electronics and Control), 20 (2022), 1103–1108. https://doi.org/10.12928/telkomnika.v20i5.22645 doi: 10.12928/telkomnika.v20i5.22645
[50]	N. M. Sureja, S. P. Patel, Solving a combinatorial optimization problem using artificial fish swarm algorithm, Int. J. Eng. Trends Technol, 68 (2020), 27–32. https://doi.org/10.14445/22315381/ijett-v68i5p206s doi: 10.14445/22315381/ijett-v68i5p206s
[51]	M. Yadollahi, S. S. Razavi, Using Artificial Fish Swarm Algorithm to solve university exam timetabling problem, J. Adv. Comput. Res., 10 (2019), 109–117.
[52]	C. Peraza, P. Ochoa, L. Amador, O. Castillo, Artificial Fish Swarm Algorithm for the Optimization of a Benchmark Set of Functions, In New Perspectives on Hybrid Intelligent System Design based on Fuzzy Logic, Neural Networks and Metaheuristics, Studies in Computational Intelligence, 1050 (2022), (77–92). https://doi.org/10.1007/978-3-031-08266-5_6
[53]	S. P. M. Villablanca, An artificial fish swarm algorithm to solve the set covering problem doctoral dissertation, pontificia universidad católica de valparaíso, (2016).
[54]	J. Derrac, S. García, D. Molina, F. Herrera, A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms, Swarm Evol Comput, 1 (2011), 3–18. https://doi.org/10.1016/j.swevo.2011.02.002 doi: 10.1016/j.swevo.2011.02.002
[55]	F. Wilcoxon, Individual comparisons by ranking methods, Biometrics Bulletin, 1 (1945), 80–83. https://doi.org/10.2307/3001968 doi: 10.2307/3001968

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)