Improving prediction accuracy of open shop scheduling problems using hybrid artificial neural network and genetic algorithm
Abstract
Scheduling issues are typically classified as constrained optimization problems that examine the allocation of machines and the sequence in which tasks are processed. Regarding the existence of one machine, identification of works processing sequence forms a complete time schedule. Therefore, following a review of previous works, the goal of the present study is designing a mathematical model for open shop scheduling (OSS) problems using different machines aiming at minimizing the maximum time required to complete the works using an artificial neural network (ANN) and genetic algorithm (GA). The research data were driven from a Shoe company carried out between the years 2019 and 2020. The GA and ANN methodologies were employed to analyze and forecast the scheduling of activities within the shoe manufacturing sector. The findings indicated that the probability associated with the third population of the GA was 0.15. Furthermore, an examination of the average values of standard error revealed that the neural network model outperformed in terms of predictive accuracy. The estimated minimum time necessary for task completion, as determined by the neural network, was calculated to be 0.96699, facilitating an optimal condition for meeting the established objectives.
Keyword : open shop scheduling (OSS), different work stations, single machine problems, resource assignment, efficient production, artificial neural network (ANN), genetic algorithm (GA)
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
Ahmadian, M. M., Khatami, M., Salehipour, A., & Cheng, T. C. E. (2021). Four decades of research on the open shop scheduling problem to minimize makespan. European Journal of Operational Research, 295(2), 399–426. https://doi.org/10.1016/j.ejor.2021.03.026
Allen, F., & Karjalainen, R. (1999). Using genetic algorithms to find technical trading rules. Economics, 51(2), 245–271. https://doi.org/10.1016/S0304-405X(98)00052-X
Alwani, S. M., & Hosseinpour, D. (2016). Application of artificial neural networks in strategic decision-making. Management Studies Quarterly (Improvement and Transformation), 18(4), 1–28.
Anand, E., & Panneerselvam, R. (2015). Literature review of open shop scheduling problems. Intelligent Information Management, 7, 33–52. https://doi.org/10.4236/iim.2015.71004
Anderson, E. J., & Potts, C. N. (2002). On-line scheduling of a single machine to minimize total weighted completion time. Mathematics of Operations Research, 29(3), 548–557. https://doi.org/10.1287/moor.1040.0092
Anders, C. R., AlbarracΊn, J. M., & Tormo, G. (2005). Group technology in a hybrid flow shop environment: A case study. European Journal of Operational Research, 167, 272–281. https://doi.org/10.1016/j.ejor.2004.03.026
Arroyo, J. E. C., dos Santos Ottoni, R., & de Paiva Oliveira, A. (2011). Multi-objective variable neighborhood search algorithms for a single machine scheduling problem with distinct due windows. Electronic Notes in Theoretical Computer Science, 281, 5–19. https://doi.org/10.1016/j.entcs.2011.11.022
Azer, A., & Rajabzadeh, A. (2012). Evaluation of hybrid forecasting methods: With classical neural network approaches in the field of economics. Journal of Economic Research, 63, 87–14.
Baykasoğlu, A., Madenoglu, F. S., & Hamzadayi, A. (2020). Greedy randomized adaptive search for dynamic flexible job-shop scheduling. Journal of Manufacturing Systems, 56, 425–451. https://doi.org/10.1016/j.jmsy.2020.06.005
Baykasoğlu, A., & Ozsoydan, F. B. (2018). Dynamic scheduling of parallel heat treatment furnaces: A case study at a manufacturing system. Journal of Manufacturing Systems, 46, 152–162. https://doi.org/10.1016/j.jmsy.2017.12.005
Behnamian, J., Fatemi Ghomi, S. M. T., & Zandieh, M. (2010). Development of a hybrid metaheuristic to minimise earliness and tardiness in a hybrid flow shop with sequence dependent setup times. International Journal of Production Research, 48(5), 1415–1438. https://doi.org/10.1080/00207540802556817
Bello, I., Pham, H., Le, Q. V., Norouzi, M. & Bengio, S. (2016). Neural combinatorial optimization with reinforcement learning. arXiv. https://doi.org/10.48550/arXiv.1611.09940
Benavides, A. J. (2018). A new tiebreaker in the NEH heuristic for the permutation flow shop scheduling problem. (No 440). EasyChair preprint. https://doi.org/10.29007/ch1l
Blazewicz, J., Ecker, K. H., Pesch, E., Schmidt, G., & Weglarz, J. (2007). Handbook on scheduling: From theory to applications. Springer.
Caicedo-Rolón, A. J., & Parra Llanos, J. W. (2021). Production sequencing in a flow shop system using optimization and heuristic algorithms. Gestão & Produção, 28(1), Article e3886. https://doi.org/10.1590/1806-9649.2020v28e3886
Chen, B., & Strusevich, V. A. (1993). Approximation algorithms for three machine open shop scheduling. Informs Journal on Computing, 5(3), 321–326. https://doi.org/10.1287/ijoc.5.3.321
Coelho, J., & Vanhoucke, M. (2018). An exact composite lower bound strategy for the resource-constrained project scheduling problem. Computers & Operations Research, 93, 135–150. https://doi.org/10.1016/j.cor.2018.01.017
Colak, S., & Agarwal, A. (2005). Non-greedy heuristics and augmented neural networks for the open-shop scheduling problem. Naval Research Logistics, 52(7), 631–644. https://doi.org/10.1002/nav.20102
Daniels, R. L., Mazzola, J. B. & Shi, D. (2004). Flow shop scheduling with partial resource flexibility. Management Science, 50(5), 658–669. https://doi.org/10.1287/mnsc.1040.0209
Defersha, F. M., & Chen, M. (2010). A parallel genetic algorithm for a keller problem with sequence dependent setups. International Journal of Advanced Manufacturing Technology, 49, 263–279. https://doi.org/10.1016/j.ejor.2011.01.011
Doulabi, S. H. H. (2010). A mixed integer linear formulation for the open shop earliness-tardiness scheduling problem. Applied Mathematical Sciences, 4, 1703–1710.
Fekri, M., Heydari, M., & Mahdavi, M. (2024). Bi-objective optimization of flexible flow shop scheduling problem with multi-skilled human resources. Engineering Applications of Artificial Intelligence, 133(Part C), Article 108094. https://doi.org/10.1016/j.engappai.2024.108094
Fernandez-Viagas, V., Ruiz, R., & Framinan, J. M. (2017). A new vision of approximate methods for the permutation flow shop to minimize makespan: state-of-the-art and computational evaluation. European Journal of Operational Research, 257(3), 707–721. https://doi.org/10.1016/j.ejor.2016.09.055
Gautam, V. K., Pande, C. B., Moharir, K. N., Varade, A. M., Rane, N. L., Egbueri, J. C., & Alshehri, F. (2023). Prediction of sodium hazard of irrigation purpose using artificial neural network modelling. Sustainability, 15, Article 7593. https://doi.org/10.3390/su15097593
Gonzalez, T., & Sahni, S. (1976). Open shop scheduling to minimize finish time. Journal of the ACM, 23(4), 665–679. https://doi.org/10.1145/321978.321985
Gueret, C., & Prins, C. (1998). Classical and new heuristics for the open-shop problem: A computational evaluation. European Journal of Operational Research, 107(2), 306–314. https://doi.org/10.1016/S0377-2217(97)00332-9
Harmanani, H. M., & Ghosn, S. B. (2016). An efficient method for the open-shop scheduling problem using simulated annealing. In S. Latifi (Eds.), Advances in intelligent systems and computing: Vol. 448. Information technology: New generations. Springer, Cham. https://doi.org/10.1007/978-3-319-32467-8_102
Iba, H., & Sasaki, T. (1999). Using genetic programming to predict financial data. In Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406) (Vol. 1, pp. 244–251). IEEE. https://doi.org/10.1109/CEC.1999.781932
Iqbali, H., & Moghadspour, A. (2017). The use of artificial neural networks in business management decision-making [Conference presentation]. The second international conference on management and fuzzy systems.
Ji, M., Yao, D. L., Yang, Q. Y., & Cheng, T. C. E. (2015). Single-machine common flow allowance scheduling with aging effect, resource allocation, and a rate-modifying activity. International Transactions in Operational Research, 22(6), 997–1015. https://doi.org/10.1111/itor.12121
Lee, T. S., & Loong, Y. T. (2019). A review of scheduling problem and resolution methods in flexible flow shop. International Journal of Industrial Engineering Computations, 10(1), 67–88. https://doi.org/10.5267/j.ijiec.2018.4.001
Liaw, C. F. (1999). A tabu search algorithm for the open shop scheduling problem. Computers & Operations Research, 26(2), 109–126. https://doi.org/10.1016/S0305-0548(98)00056-2
Li, J., Dong, X. Y., Zhang, K., & Han, S. (2020). Solving open shop scheduling problem via graph attention neural network. In IEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI) (pp. 277–284). IEEE. https://doi.org/10.1109/ICTAI50040.2020.00052
Li, X. Y., Gao, L., Pan, Q. K., Wan, L., & Chao, K. M. (2018). An effective hybrid genetic algorithm and variable neighborhood search for integrated process planning and scheduling in a packaging machine workshop. IEEE Transactions on Systems Man Cybernetics Systems, 49(10), 1933–1945. https://doi.org/10.1109/TSMC.2018.2881686
Lin, H. T., Lee, H. T., & Pan W. J. (2008). Heuristics for scheduling in a no-wait open shop with movable dedicated machines. International Journal of Production Economics, 111(2), 368–377. https://doi.org/10.1016/j.ijpe.2007.01.005
Liu, C. L., & Xiong, C. H. (2021). Single machine resource allocation scheduling problems with deterioration effect and general positional effect. Mathematical Biosciences and Engineering, 18(3), 2562–2578. https://doi.org/10.3934/mbe.2021130
McCulloch, W. W., & Pitts, W. (1943). A logical calculus of ideas imminent in nervous activity. The Bulletin of Mathematical Biophysics, 5, 115−133. https://doi.org/10.1007/BF02478259
Ma, R., Guo, S. N., & Miao, C. X. (2021). A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection. Applied Mathematics and Computation, 392, Article 125670. https://doi.org/10.1016/j.amc.2020.125670
Minhaj, M. B. (2017). Neural networks. Islamic Azad University Publications.
Minsky, M., & Papert, S. (1969). Review of “Perceptrons: An Introduction to Computational Geometry” (Minsky, M., and Papert, S.; 1969). IEEE Transactions on Information Theory, 15(6), 738–739. https://doi.org/10.1109/TIT.1969.1054388
Mousighichi, K., & Avci, M. G. (2024). The distributed no-idle permutation flow shop scheduling problem with due windows. Computational & Applied Mathematics, 43, Article 179. https://doi.org/10.1007/s40314-024-02702-w
Naderi, B., Ghomi, S. M. T. F., Aminnayeri, M., & Zandieh, M. (2010). A contribution and new heuristics for open shop scheduling. Computers & Operations Research, 37(1), 213–221. https://doi.org/10.1016/j.cor.2009.04.010
Noori-Darvish, S., Mahdavi, I., & Mahdavi-Amiri, N. (2012). A bi-objective possibilistic programming model for open shop scheduling problems with sequence-dependent setup times, fuzzy processing times, and fuzzy due dates. Applied Sof Computing, 12, 1399–1416. https://doi.org/10.1016/j.asoc.2011.11.019
Nemati, K., Refahi, S., Kord Roostemi, S., & Amir, H. (2016). Optimization of parallel algorithms scheduling using genetic algorithms. Journal of Operational Research and its Applications, 13(2), 35–52.
Osorio Gómez, J. C., Castrillón Montenegro, O. E., Toro Cardona, J. A., & Orejuela Cabrera, J. P. (2008). Modelo de programación jerárquica de la producción en un Job shop flexible con interrupciones y tiempos de alistamiento dependientes de la secuencia. Revista Ingeniería e Investigación, 28(2), 72–79. https://doi.org/10.15446/ing.investig.v28n2.14896
Ouelhadj, D., & Petrovic, S. (2009). A survey of dynamic scheduling in manufacturing systems. Journal of Scheduling, 12(4), 417–431. https://doi.org/10.1007/s10951-008-0090-8
Panneerselvam, R. (1999). Heuristic for moderated job shop scheduling problem to minimize makespan. Industrial Engineering Journal, 28, 26–29.
Pinedo, M. L. (2022). Scheduling theory, algorithms, and systems. Springer. https://doi.org/10.1007/978-3-031-05921-6
Rimcharoen. S., Sutivong, D., & Chongstitvatana, P. (2005). Soft computing in the forecasting of the stock exchange of Thailand. In Proceedings of the fourth IEE international conference on management of innovation and technology. IEEE. https://doi.org/10.1109/ICMIT.2008.4654554
Sheykhalishahi, M., Eskandari, N., Mashayekhi, A., & Azadeh, A. (2019). Multi-objective open shop scheduling by considering human error and preventive maintenance. Applied Mathematical Modelling, 67, 573–587. https://doi.org/10.1016/j.apm.2018.11.015
Shioura, A., Shakhlevich, N. V., & Strusevich, V. A. (2018). Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: A review of solution approaches. European Journal of Operational Research, 266(3), 795–818. https://doi.org/10.1016/j.ejor.2017.08.034
Tavakkoli-Moghaddam, R., & Seraj, O. (2009). A tabu search method for a new bi-objective open shop scheduling problem by a fuzzy multi-objective decision making approach (research note). International Journal of Engineering, Transactions B: Applications, 22(3), 269–282.
Xue, H., Meng, L., Duan, P., Zhang, B., Zou,W., & Sang, H. (2024). Modeling and optimization of the hybrid flow shop scheduling problem with sequence-dependent setup times. International Journal of Industrial Engineering Computations, 15(2), 473–490. https://doi.org/10.5267/j.ijiec.2024.1.001
Wang, H. B., & Alidaee, B. (2019). Effective heuristic for large-scale unrelated parallel machines scheduling problems. Omega, 83, 261–274. https://doi.org/10.1016/j.omega.2018.07.005
Wang, X., Ren, T., Wang, X., Bai, D., Chu, F., Lu, X., Weng, Z., Li, J., & Li, J. (2024). Hybrid flow shop scheduling with learning effects and release dates to minimize the makespan. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 54(1), 365–378. https://doi.org/10.1109/TSMC.2023.3305089
Yao, J. T., & Tan, C. L. (2001, November 14–18). Guidelines for financial forecasting with neural networks. In Proceedings of International Conference on Neural Information Processing (pp. 757–761), Shanghai, China.
Zang, Z., Wang, W., Song, Y., Lu, L., Li, W., Wang, Y., & Zhao, Y. (2019). Hybrid deep neural network scheduler for job-shop problem based on convolution two-dimensional transformation. Computational Intelligence and Neuroscience, 2019, Article 172842. https://doi.org/10.1155/2019/7172842
Zhu, T., & Liu, G. (2023). A. Novel Hybrid methodology to study the risk management of prefabricated building supply chains: an outlook for sustainability. Sustainability, 15, Article 361. https://doi.org/10.3390/su15010361