Flexible Job Shop Scheduling Problem-Solving Using  Apiary Organizational-Based Optimization Algorithm

Mais A. Al-Sharqi; Ahmed T.   Sadiq; Safaa O. Al-mamory

doi:10.14500/aro.11609

Mais A. Al-Sharqi Informatics Institute for Postgraduate Studies, Iraqi Commission for Computers and Informatics, Baghdad, Iraq https://orcid.org/0000-0002-9059-9031
Ahmed T. Sadiq Department of Computer Science, University of Technology, Baghdad, Iraq https://orcid.org/0000-0002-4217-1321
Safaa O. Al-mamory 3Department of Cybersecurity, College of Information Technology, University of Babylon, Babylon, Iraq https://orcid.org/0000-0003-3144-8222

Keywords: Apiary Organizational-Based Optimization Algorithm, Flexible job shop scheduling, Makespan, Metaheuristic nature-inspired

Abstract

Flexible job shop scheduling problem (FJSSP) is a complex and challenging problem that plays a crucial role in industrial and manufacturing production. FJSSP is an expansion of the standard job shop scheduling problem (JSSP). One of FJSSP’s objectives that the manufacturing system competing for is minimizing the makespan. This paper uses a new nature-inspired metaheuristic optimization algorithm called the Apiary Organizational-Based Optimization algorithm (AOOA) to solve the FJSSP. This Algorithm simulates the organizational behavior of honeybees inside the apiary and translates their activities and vital processes during their lifecycle into phases that can solve such NP-hard problems. Two benchmark datasets, Brandimarte and Hurink, with 10 MK instances and 24 (edata, rdata, and vdata) instances respectively, were used to demonstrate the ability of AOOA to solve FJSSP. Moreover, the results of AOOA were compared with a set of state-of-the-art algorithms and statistically measured using the paired samples t-test and p-value, RPD, and group-based superiority statistical analysis to test its performance. AOOA outperformed Elitism GA, Enhanced GA, Improved GA, and MOGWO in solving all 10 MK instances and HICSA in solving 9 MK instances out of 10. Moreover, AOOA overcame CS, CS-BNG, CS-ILF, CHA, and MCA in solving 24, 12, 12, 23, and 24 instances of edata, rdata, and vdata, respectively. AOOA proved its robustness, showing promising outcomes.

Downloads

Download data is not yet available.

Author Biographies

Mais A. Al-Sharqi, Informatics Institute for Postgraduate Studies, Iraqi Commission for Computers and Informatics, Baghdad, Iraq

Mais A. Al-Sharqi is a Lecturer at the Department of Bioinformatics, College of Biomedical Informatics, University of Information Technology and Communications. She got the B.Sc. degree in Computer Science from theComputer Science Department, College of Science, University of Baghdad in 2002, the M.Sc. degree in Computer Science, Artificial Intelligence from the Informatics Institute for Postgraduate Studies in 2012. Her research interests
are in artificial intelligence, optimization and data mining.

Ahmed T. Sadiq, Department of Computer Science, University of Technology, Baghdad, Iraq

Ahmed T. Sadiq is a Professor at the Department of Computer Sciences, University of Technology. He got the B.Sc., M.Sc. and Ph.D. in Computer Science from University of Technology, Baghdad, Iraq, 1993, 1996 and 2000, respectively. His research interests are in artificial intelligence, data security, patterns recognition and data mining.

Safaa O. Al-mamory, 3Department of Cybersecurity, College of Information Technology, University of Babylon, Babylon, Iraq

Safaa O. Al-mamory is a Professor at the Department of Cybersecurity, College of Information Technology, University of Babylon. He got the B.Sc. degree in Information System, the M.Sc. degree in Computer Security from
University of Technology-Iraq at 1999 and 2002, respectively. He got Ph.D. degree in Computer Architecture from Harbin Institute of Technology-China in 2009. His research interests are in data mining, and network security.

References

Al-Obaidi, A.T.S., Abdullah, H.S., and Ahmed, Z.O., 2017. Camel herds algorithm: A new swarm intelligent algorithm to solve optimization problems. International Journal on Perceptive and Cognitive Computing, 3(1), pp.6–10. DOI: https://doi.org/10.31436/ijpcc.v3i1.44

Al-Obaidi, A.T.S., Abdullah, H.S., and Ahmed, Z.O., 2018. Meerkat clan algorithm: Anew swarm intelligence algorithm. Indonesian Journal of Electrical Engineering and Computer Science, 10(1), pp.354-360. DOI: https://doi.org/10.11591/ijeecs.v10.i1.pp354-360

Al-Obaidi, A.T.S., and Hussein, S.A., 2016. Two improved Cuckoo search algorithms for solving the flexible job-shop scheduling problem. International Journal on Perceptive and Cognitive Computing, 2(2), pp.25-31. DOI: https://doi.org/10.31436/ijpcc.v2i2.34

Al-Sharqi, M.A., Al-Obaidi, A.T.S., and Al-mamory, S.O., 2024. Apiary organizational-based optimization algorithm: A new nature-inspired metaheuristic algorithm. International Journal of Intelligent Engineering and Systems, 17(3), pp.783-801. DOI: https://doi.org/10.22266/ijies2024.0630.61

Alzaqebah, M., Jawarneh, S., Alwohaibi, M., Alsmadi, M.K., Almarashdeh, I., and Mohammad, R.M.A., 2022. Hybrid brain storm optimization algorithm and late acceptance hill climbing to solve the flexible job-shop scheduling problem. Journal of King Saud University -Computer and Information Sciences, 34(6), pp.2926-2937. DOI: https://doi.org/10.1016/j.jksuci.2020.09.004

Amirteimoori, A., Mahdavi, I., Solimanpur, M., Ali, S.S., and Tirkolaee, E.B., 2022. Aparallel hybrid PSO-GA algorithm for the flexible flow-shop scheduling with transportation. Computers and Industrial Engineering, 173, p.108672. DOI: https://doi.org/10.1016/j.cie.2022.108672

Bissoli, D.C., Altoe, W.A.S., Mauri, G.R., and Amaral, A.R.S., 2018. ASimulated Annealing Metaheuristic for the Bi-objective Flexible Job Shop Scheduling Problem. In: 2018 International Conference on Research in Intelligent and Computing in Engineering (RICE). pp.1-6. DOI: https://doi.org/10.1109/RICE.2018.8627907

Brandimarte, P., 1993. Routing and scheduling in a flexible job shop by Tabu search. Annals of Operations Research, 41(3), pp.157-183. DOI: https://doi.org/10.1007/BF02023073

Dai, M., Tang, D., Giret, A., and Salido, M.A., 2019. Multi-objective optimization for energy-efficient flexible job shop scheduling problem with transportation constraints. Robotics and Computer-Integrated Manufacturing, 59, pp.143-157. DOI: https://doi.org/10.1016/j.rcim.2019.04.006

Fattahi, P., Saidi Mehrabad, M., and Jolai, F., 2007. Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. Journal of Intelligent Manufacturing, 18(3), pp.331-342. DOI: https://doi.org/10.1007/s10845-007-0026-8

Hurink, J., Jurisch, B., and Thole, M., 1994. Tabu search for the job-shop scheduling problem with multi-purpose machines. OR Spektrum, 15(4), pp.205-215. DOI: https://doi.org/10.1007/BF01719451

Jiang, M., Yu, H., and Chen, J., 2023. Improved self-learning genetic algorithm for solving flexible job shop scheduling. Mathematics, 11(22), p.4700. DOI: https://doi.org/10.3390/math11224700

Kacem, I., Hammadi, S., and Borne, P., 2002. Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews, 32(1), pp.1-13. DOI: https://doi.org/10.1109/TSMCC.2002.1009117

Li, Y., Yang, Z., Wang, L., Tang, H., Sun, L., and Guo, S., 2022. A hybrid imperialist competitive algorithm for energy-efficient flexible job shop scheduling problem with variable-size sublots. Computers and Industrial Engineering, 172, p.108641. DOI: https://doi.org/10.1016/j.cie.2022.108641

Lu, C., Gao, L., Pan, Q., Li, X., and Zheng, J., 2019. A multi-objective cellular grey wolf optimizer for hybrid flowshop scheduling problem considering noise pollution. Applied Soft Computing Journal, 75, pp.728-749. DOI: https://doi.org/10.1016/j.asoc.2018.11.043

Luo, S., Zhang, L., and Fan, Y., 2019a. Energy-efficient scheduling for multi-objective flexible job shops with variable processing speeds by grey wolf optimization. Journal of Cleaner Production, 234, pp.1365-1384.

Luo, S., Zhang, L., and Fan, Y., 2019b. Energy-efficient scheduling for multi-objective flexible job shops with variable processing speeds by grey wolf optimization. Journal of Cleaner Production, 234, pp.1365-1384. DOI: https://doi.org/10.1016/j.jclepro.2019.06.151

Meng, L., Duan, P., Gao, K., Zhang, B., Zou, W., Han, Y., and Zhang, C., 2024. MIP modeling of energy-conscious FJSP and its extended problems: From simplicity to complexity. Expert Systems with Applications, 241, p.122594. DOI: https://doi.org/10.1016/j.eswa.2023.122594

Piotr Jedrzejowicza, I.W., 2022. Implementation of the Mushroom PickingFramework for Solving Flexible Job Shop Scheduling Problems in Parallel. In: 26th International Conference on Knowledge-Based and Intelligent Information and Engineering 26th International Conference on Knowledge-Based and Intelligent Information and Engineering Systems (KES 2022). pp.292-298.

Rajwar, K., Deep, K., and Das, S., 2023. An exhaustive review of the metaheuristic algorithms for search and optimization: Taxonomy, applications, and open challenges. Artificial Intelligence Review, 56(11), pp.13187-13257. DOI: https://doi.org/10.1007/s10462-023-10470-y

Sadiq Al-Obaidi, A.T., Abdullah, H.S., and Ahmed, Z.O., 2018. Solving flexible job shop scheduling problem using meerkat clan algorithm. Iraqi Journal of Science, 59(2A), pp.754-761. DOI: https://doi.org/10.24996/ijs.2018.59.2A.13

Şahman, M.A., 2021. A discrete spotted hyena optimizer for solving distributed job shop scheduling problems. Applied Soft Computing, 106, p.107349. DOI: https://doi.org/10.1016/j.asoc.2021.107349

Song, L., Liu, C., Shi, H., and Zhu, J., 2022. An improved immune genetic algorithm for solving the flexible job shop scheduling problem with batch processing. Wireless Communications and Mobile Computing, 2022, p.2856056. DOI: https://doi.org/10.1155/2022/2856056

Wang, Y., Xia, T., Xu, Y., Ding, Y., Zheng, M., Pan, E., and Xi, L., 2024. Joint optimization of flexible job shop scheduling and preventive maintenance under high-frequency production switching. International Journal of Production Economics, 269, p.109163. DOI: https://doi.org/10.1016/j.ijpe.2024.109163

Wu, L., and Cai, H., 2021. Energy-efficient adaptive sensing scheduling in wireless sensor networks using Fibonacci tree optimization algorithm. Sensors (Basel), 21(15), p.55002. DOI: https://doi.org/10.3390/s21155002

Xie, J., Gao, L., Peng, K., Li, X., and Li, H., 2019. Review on flexible job shop scheduling. IET Collaborative Intelligent Manufacturing, 1, p.67-77. DOI: https://doi.org/10.1049/iet-cim.2018.0009

Xie, N., and Chen, N., 2018. Flexible job shop scheduling problem with interval grey processing time. Applied Soft Computing Journal, 70, pp.513-524. DOI: https://doi.org/10.1016/j.asoc.2018.06.004

Zeidabadi, F.A., and Dehghani, M., 2022. POA: Puzzle optimization algorithm. International Journal of Intelligent Engineering and Systems, 15(1), pp.273-281. DOI: https://doi.org/10.22266/ijies2022.0228.25

Zhang, C., Tan, J., Peng, K., Gao, L., Shen, W., and Lian, K., 2021. A discrete whale swarm algorithm for hybrid flow-shop scheduling problem with limited buffers. Robotics and Computer-Integrated Manufacturing, 68, p.102081. DOI: https://doi.org/10.1016/j.rcim.2020.102081

Zhang, G., Hu, Y., Sun, J., and Zhang, W., 2020. An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints. Swarm and Evolutionary Computation, 54, p.100664. DOI: https://doi.org/10.1016/j.swevo.2020.100664

Zhu, N., Zhao, F., Wang, L., Ding, R., Xu, T., and Jonrinaldi, 2022. A discrete learning fruit fly algorithm based on knowledge for the distributed no-wait flow shop scheduling with due windows. Expert Systems with Applications, 198, p.116921. DOI: https://doi.org/10.1016/j.eswa.2022.116921