Artificial neural network for solving flow shop optimization problem with sequence independent setup time

• Autorzy: Sadki, Hajar , Allali, Karam
• Języki publikacji: EN

Abstrakty

EN

In this paper, we will study the permutation flow shop scheduling problem (PFSSP) with sequence independent setup time (SIST). This constraint is the most common encountered in industrial production. In this case, the SIST constraint depends on the technology nature of the machine, as well as the means used to prepare it for the execution of a new job. The purpose of this paper is to develop an artificial intelligence system and to train a neural network model for solving the flow shop scheduling problem. The objective function is to minimize the total completion time, which is known as makespan. The latter is an important task in manufacturing systems. The paper begins by suggesting an exact and four approximate methods: a mixed integer linear programming (MILP), an artificial neural network (ANN), and three e cient heuristics. The first heuristic is based on Johnson’s rule algorithm (ABJR), the second on the Nawaz-Enscore and Ham algorithm (NEH), and the last on the greedy randomized adaptive search procedure algorithm (GRASP). We aim to verify the e ectiveness of our resolution algorithms by considering randomly generated instances with n jobs and m machines in the flow shop factory. Our goal is to determine the optimal sequence of n jobs to be scheduled on m machines. The paper moves to the comparison between the studied heuristics. The numerical results demonstrate that the NEH algorithm outperforms the other approximate methods for our considered problem. Indeed, the NEH heuristic performs a success rate of 82.81% and achieves a minimum relative percentage deviation value of 0.0139%. It was observed that ANN method outperforms GRASP and gives sometimes best results than ABJR. The numerical simulations align with our theoretical postulations given by RPD values.

Słowa kluczowe

EN

flow shop scheduling; sequence independent setup time; artificial neural network; makespan; heuristic

• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2024
• Tom: Vol. 49, No. 4
• Strony: 355--383
• Opis fizyczny: Bibliogr. 38 poz., rys., tab.

Twórcy

autor

Sadki, Hajar

• Laboratory of Mathematics, Computer Science and Applications, FST Mohammedia, University Hassan II of Casablanca, Morocco,

autor

Allali, Karam

• Laboratory of Mathematics, Computer Science and Applications, FST Mohammedia, University Hassan II of Casablanca, Morocco

Bibliografia

• [1] Ahmad, Q. S., and Khan, M. H., Application of Neural Networks to Scheduling Problem including Transportation Time, International Journal of Computer Applications, 54, (5), 2012.
• [2] Akyol, D. E., Application of neural networks to heuristic scheduling algorithms, Computers & Industrial Engineering. 46, (4), 2004, 679-696.
• [3] Al-Barazanchi, I., Hashim, W., Alkahtani, A. A., Abdulshaheed, H. R., Gheni, H. M., Murthy, A., and Jaaz, Z. A., Remote monitoring of COVID-19 patients using multisensor body area network innovative system. Computational Intelligence and Neuroscience, 2022.
• [4] Allali, K., Aqil, S., and Belabid, J., Distributed no-wait flow shop problem with sequence dependent setup time: Optimization of makespan and maximum tardiness. Simulation Modelling Practice and Theory, 116, 102455.
• [5] Anh, B. T., and Hiep, P. T., Developing the max-min power control algorithm for distributed wireless body area networks, AEU-International Journal of Electronics and Communications, 158, 154448, 2023.
• [6] Aqil, S., Effective Population-Based Meta-heuristics with NEH and GRASP Heuristics Minimizing Total Weighted flow Time in No-Wait Flow Shop Scheduling Problem Under Sequence-Dependent Setup Time Constraint. Arabian Journal for Science and Engineering, 2024, 1-24.
• [7] Baskar, A., Minimizing the makespan in permutation flow shop scheduling problems using simulation, Indian Journal of Science and Technology, 8, (22), 2015, p. 1.
• [8] Deepak, K. S., and Babu, A. V., Packet size optimization for energy efficient cooperative wireless body area networks. In 2012 Annual IEEE India Conference (INDICON), 736-741.
• [9] Elissaouy, O., and Allali, K., Minimizing the maximum tardiness for a permutation flow shop problem under the constraint of sequence independent setup time. RAIRO-Operations Research, 58, (1), 2024, 373-395.
• [10] de Garis, H., An artificial brain ATR’s CAM-Brain Project aims to build/evolve an artificial brain with a million neural net modules inside a trillion cell Cellular Automata Machine, New Generation Computing, 12, 1994, 215-221.
• [11] Garey MR., Johnson DS., Sethi R., The complexity of flowshop and jobshop scheduling, Mathematics of operations research. 1, (2), 1976, 117-129.
• [12] Goli, A., Integration of blockchain-enabled closed-loop supply chain and robust product portfolio design. Computers & Industrial Engineering, 179, 109211.
• [13] Goli, A., Ala, A., and Mirjalili, S., A robust possibilistic programming framework for designing an organ transplant supply chain under uncertainty. Annals of Operations Research, 328, (1), 493-530.
• [14] Goli, A., Ala, A., and Hajiaghaei-Keshteli, M., Efficient multi-objective meta-heuristic algorithms for energy-aware non-permutation flow-shop scheduling problem. Expert Systems with Applications, 213, 119077.
• [15] Goli, A., and Tirkolaee, E. B,. Designing a portfolio-based closed-loop supply chain network for dairy products with a financial approach: Accelerated Benders decomposition algorithm. Computers & Operations Research, 155, 106244.
• [16] Goli, A., Tirkolaee., E. B., and Weber, G. W., An integration of neural network and shuffled frog-leaping algorithm for CNC machining monitoring, Foundations of Computing and Decision Sciences, 46, (1), 2021, 27–42.
• [17] Hees, A., Schutte, C. S., and Reinhart, G., A production planning system to continuously integrate the characteristics of reconfigurable manufacturing systems. Production Engineering, 11, 2017, 511-521.
• [18] Johnson SM., Optimal two-and three-stage production schedules with setup times included. Naval research logistics quarterly, 1, (1), 1954, 61-68.
• [19] Kropat, E., Weber, G. W., and Akteke-Öztürk, B., Eco-finance networks under uncertainty. In Proceedings of the international conference on engineering optimization, 353-377.
• [20] Kumar, H., and Giri, S., Optimisation of makespan of a flow shop problem using multi layer neural network. International Journal of Computing Science and Mathematics, 11, (2), 2020, 107-122.
• [21] Kumar, S., Manjrekar, V., Singh, V., and Lad, B. K., Integrated yet distributed operations planning approach: A next generation manufacturing planning system. Journal of Manufacturing Systems, 54, 2020, 103-122.
• [22] Lee, I., and Shaw, M. J., A neural-net approach to real time flow-shop sequencing. Computers & Industrial Engineering, 38, (1), 2000, 125-147.
• [23] Nawaz, M., Enscore Jr, E. E., and Ham, I., A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega, 11, (1), 91-95.
• [24] Özmen, A., Kropat, E., and Weber, G. W., Robust optimization in spline regression models for multi-model regulatory networks under polyhedral uncertainty. Optimization, 66, (12), 2135-2155.
• [25] Prabhaharan, G., Khan, B. S. H., and Rakesh, L., Implementation of grasp in flow shop scheduling, The International Journal of Advanced Manufacturing Technology, 30, 2006, 1126-1131.
• [26] Rahman, Humyun Fuad and Sarker, Ruhul and Essam Daryl., Multiple-order permutation flow shop scheduling under process interruptions, The International Journal of Advanced Manufacturing Technology, 97, 2018, 2781-2808.
• [27] Ramanan, T. R., Sridharan, R., Shashikant, K. S., and Haq, A. N., An artificial neural network based heuristic for flow shop scheduling problems. Journal of Intelligent Manufacturing, 22, 2011, 279-288.
• [28] Rouhani, S., Fathian, M., Jafari, M., and Akhavan, P., Solving the problem of flow shop scheduling by neural network approach. In Networked Digital Technologies: Second International Conference, July 7-9, 2010, pp. 172-183.
• [29] Ruiz, R., and Maroto, C., A comprehensive review and evaluation of permutation flowshop heuristics, European journal of operational research, 165(2), 2005, 479-494.
• [30] Sadki, H., Aqil, S., Belabid, J., and Allali, K., Multi-Objective Optimization Flow Shop Scheduling Problem Solving the Makespan and Total Flow Time with Sequence Independent Setup Time, Journal of Advanced Manufacturing Systems, 2023, 1-22.
• [31] Sadki, H., Belabid, J., Aqil, S., and Allali, K., On Permutation Flow Shop Scheduling Problem with Sequence-Independent Setup Time and Total Flow Time, In International Conference on Advanced Technologies for Humanity, 2022, 507-518.
• [32] Savku, E., and Weber, G. W., Stochastic differential games for optimal investment problems in a Markov regime-switching jump-diffusion market. Annals of Operations Research, 312, (2), 1171-1196.
• [33] Sharma, S., and Mehra, R., Implications of pooling strategies in convolutional neural networks: A deep insight, Foundations of Computing and Decision Sciences, 44, (3), 2019, 303-330.
• [34] Singhal, E., and Hemrajani, N., An improved NEH algorithm applied to permutation flow shop scheduling, International Journal of Engineering Sciences & Research Technology, 2, (5), 2013, 1164-1170.
• [35] Sta ord, E. F., Tseng, F. T., and Gupta, J. N., Comparative evaluation of MILP flowshop models, Journal of the Operational Research Society, 56, 2005, 88-101.
• [36] Weber, G. W., Kropat, E., Tezel, A., and Belen, S., Optimization applied on regulatory and eco-finance networks-survey and new developments.
• [37] Xu, Z., Xu, D., He, J., Wang, Q., Liu, A., and Xiao, J., Mixed integer programming formulations for two-machine flow shop scheduling with an availability constraint. Arabian Journal for Science and Engineering, 43, (2), 2018, 777-788.
• [38] Yenisey, M. M., and Yagmahan, B., Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends. Omega, 45, 2014, 119-135.

Identyfikatory

DOI

10.2478/fcds-2024-0018