Solving a New Multi-Objective Model for a Tool Switching Problem in Flexible Manufacturing Systems by a Genetic Algorithm

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Kharazmi University, Tehran, Iran

2 Department of Industrial Engineering, Kharazmi University

3 University of Kharazmi

Abstract

This paper deals with the Tool Switching Problem (ToSP), a famous problem in operations research. The simple ToSP includes finding a sequence of products and tool loading on a machine with the objective of minimizing the total number of tool switches. This paper presents a new multi-objective model for the ToSP, in which unlike the previous studies, the multi job tools have been considered (i.e., each tool can perform several tasks or jobs). This new model determines a product sequence and tool assigning for each stage that optimizes three objectives, namely 1) minimizing the total number of tool switches, 2) minimizing the overuse of tools per stage, and 3) balancing the tool usage. It is known that the ToSP is an NP-hard one, which is so difficult to be optimally solved in a reasonable computational time for large size problems. Therefore, a meta-heuristic, based on genetic algorithm (GA), is proposed in this study to solve such a hard problem. Moreover, a new tool loading algorithm is used to help the proposed GA related to the machine loading. Finally, the related results and conclusion are presented and discussed. The results of the numerical examples represented that the obtained results by GA are 3.5%. far from the optimum solutions found by the Branch-and-bound method.

Keywords

References

Al-Fawzan, M. A., & Al-Sultan, K. S. (2003). A tabu search based algorithm for minimizing the number of tool switches on a flexible machine. Computers and Industrial Engineering, 44(1), 35–47. https://doi.org/10.1016/S0360-8352(02)00183-3
Amaya, J. E., Cotta, C., & Fernández, A. J. (2008). A memetic algorithm for the tool switching problem. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5296 LNCS, 190–202. https://doi.org/10.1007/978-3-540-88439-2_14
Amaya, J. E., Cotta, C., & Fernández-Leiva, A. J. (2012). Solving the tool switching problem with memetic algorithms. Artificial Intelligence for Engineering Design, Analysis and Manufacturing: AIEDAM, 26(2), 221–235. https://doi.org/10.1017/S089006041100014X
Amouzgar, K., Nourmohammadi, A., & Ng, A. H. C. (2021). Multi-objective optimisation of tool indexing problem: a mathematical model and a modified genetic algorithm. International Journal of Production Research, 59(12), 3572–3590. https://doi.org/10.1080/00207543.2021.1897174
Bard, J. F. (1988). A heuristic for minimizing the number of tool switches on a flexible machine. IIE Transactions (Institute of Industrial Engineers), 20(4), 382–391. https://doi.org/10.1080/07408178808966195
Belady, L. A. (1966). A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal, 5(2), 78–101. https://doi.org/10.1147/sj.52.0078
Błazewicz, J., & Finke, G. (1994). Scheduling with resource management in manufacturing systems. European Journal of Operational Research, 76(1), 1–14. https://doi.org/10.1016/0377-2217(94)90002-7
Crama, Y., Oerlemans, A. G., & Spieksma, F. C. R. (1994). Minimizing the number of tool switches on a flexible machine. The International Journal of Flexible Manufacturing Systems, 6, 165–195. https://doi.org/10.1007/978-3-662-00459-3_8
Dadashi, H., Moslemi, S., & Mirzazadeh, A. (2016). Optimization of a New Tool Switching Problem in Flexible Manufacturing Systems with a Tool Life by a Genetic Algorithm. International Journal of Industrial and Manufacturing Systems Engineering, 1(3), 52–58. https://doi.org/10.11648/j.ijimse.20160103.12
Darányi, A., Czvetkó, T., Kummer, A., Ruppert, T., & Abonyi, J. (2023). Multi-objective hierarchical clustering for tool assignment. CIRP Journal of Manufacturing Science and Technology, 42, 47–54. https://doi.org/10.1016/j.cirpj.2023.02.002
Djellab, H., Djellab, K., & Gourgand, M. (2000). New heuristic based on a hypergraph representation for the tool switching problem. International Journal of Production Economics, 64(1), 165–176. https://doi.org/10.1016/S0925-5273(99)00055-9
ElMaraghy, H. A. (1985). Automated tool management in flexible manufacturing. Journal of Manufacturing Systems, 4(1), 1–13. https://doi.org/10.1016/0278-6125(85)90003-2
Hertz, A., Laporte, G., Mittaz, M., & Stecke, K. E. (1998). Heuristics for minimizing tool switches when scheduling part types on a flexible machine. IIE Transactions (Institute of Industrial Engineers), 30(8), 689–694. https://doi.org/10.1080/07408179808966514
Hertz, A., & Widmer, M. (1996). An improved tabu search approach for solving the job shop scheduling problem with tooling constraints. Discrete Applied Mathematics, 65(1–3), 319–345. https://doi.org/10.1016/0166-218X(95)00040-X
Iori, M., Locatelli, A., Locatelli, M., & Salazar-González, J. J. (2024). Tool switching problems with tool order constraints. Discrete Applied Mathematics, 347(April), 249–262. https://doi.org/10.1016/j.dam.2023.12.031
Jun, H. B., Kim, Y. D., & Suh, H. W. (1999). Heuristics for a tool provisioning problem in a flexible manufacturing system with an automatic tool transporter. IEEE Transactions on Robotics and Automation, 15(3), 488–496. https://doi.org/10.1109/70.768181
Kashyap, A. S., & Khator, S. K. (1990). Modeling of a Tool Shared Flexible Manufa Cturing System. Proceedings of the 1994 Winter Simulation Conference, 1249(Oct), 395–403.
Kiran, A., & Krason, R. (1988). Automated tooling in a flexible manufacturing system. Industrial Engineering.
Konak, A., Kulturel-Konak, S., & Azizoǧlu, M. (2008). Minimizing the number of tool switching instants in Flexible Manufacturing Systems. International Journal of Production Economics, 116(2), 298–307. https://doi.org/10.1016/j.ijpe.2008.09.001
Laporte, G., Salazar-González, J. J., & Semet, F. (2004). Exact algorithms for the job sequencing and tool switching problem. IIE Transactions (Institute of Industrial Engineers), 36(1), 37–45. https://doi.org/10.1080/07408170490257871
Larranaga, P., Kuijpers, C. M. H., Murga, R. H., Inza, I., & Dizdarevic, S. (1999). Costs of secondary parasitism in the facultative hyperparasitoid Pachycrepoideus dubius: Does host size matter? Artificial Intelligence Review, 13, 129–170. https://doi.org/10.1023/A
Oerlemans, A. (1992). Production planning for flexible manufacturing systems. University of Limburg, Maastricht, Limburg, Netherlands.
Paiva, G. S., & Carvalho, M. A. M. (2017). Improved heuristic algorithms for the Job Sequencing and Tool Switching Problem. Computers and Operations Research, 88, 208–219. https://doi.org/10.1016/j.cor.2017.07.013
Pasha, N., Amoozad Mahdiraji, H., Razavi Hajiagha, S. H., Garza-Reyes, J. A., & Joshi, R. (2024). A multi-objective flexible manufacturing system design optimization using a hybrid response surface methodology. Operations Management Research, 17(1), 135–151. https://doi.org/10.1007/s12063-023-00412-w
Privault, C., & Finke, G. (1995). Modelling a tool switching problem on a single NC-machine. Journal of Intelligent Manufacturing, 6(2), 87–94. https://doi.org/10.1007/BF00123680
Rifai, A. P., Mara, S. T. W., & Norcahyo, R. (2022). A two-stage heuristic for the sequence-dependent job sequencing and tool switching problem. Computers & Industrial Engineering, 163, 107813. https://doi.org/10.1016/j.cie.2021.107813
Salonen, K., Raduly-Baka, C., & Nevalainen, O. S. (2006). A note on the tool switching problem of a flexible machine. Computers and Industrial Engineering, 50(4), 458–465. https://doi.org/10.1016/j.cie.2004.11.002
Shirazi, R., & Frizelle, G. D. M. (2001). Minimizing the number of tool switches on a flexible machine: An empirical study. International Journal of Production Research, 39(15), 3547–3560. https://doi.org/10.1080/00207540110060888
Solimanpur, M., & Rastgordani, R. (2012). Minimising tool switching and indexing times by ant colony optimisation in automatic machining centres. International Journal of Operational Research, 13(4), 465–479. https://doi.org/10.1504/IJOR.2012.046228
Tang, C. S., & Denardo, E. V. (1988). Models arising from a flexible manufacturing machine, part II: minimization of the number of switching instants. Operations Research, 36(5), 778–784. https://doi.org/10.1287/opre.36.5.778
Tri Windras Mara, S., Sutoyo, E., Norcahyo, R., & Pratama Rifai, A. (2023). The job sequencing and tool switching problem with sequence-dependent set-up time. Journal of King Saud University - Engineering Sciences, 35(1), 53–61. https://doi.org/10.1016/j.jksues.2021.02.015
Tzur, M., & Altman, A. (2004). Minimization of tool switches for a flexible manufacturing machine with slot assignment of different tool sizes. IIE Transactions (Institute of Industrial Engineers), 36(2), 95–110. https://doi.org/10.1080/07408170490245351
Wang, S., Zou, H., & Wang, S. (2022). A Tabu-GA-based parallel machine scheduling with restrained tool resources. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 236(1–2), 39–50. https://doi.org/10.1177/0954405420928691
Wierzbicki, A. P. (1982). A mathematical basis for satisficing decision making. Mathematical Modelling, 3(5), 391–405. https://doi.org/10.1016/0270-0255(82)90038-0
Wierzbicki, A. P. (1986). On the Completeness and Constructiveness of Parametric Characterizations to Vector Optimization Problems. OR Spectrum, 8, 73–87.
Wierzbicki, A. P. (1999). Reference point approaches. In Multicriteria Decision Making: Advances in MCDM Models, Algorithms, Theory, and Applications by T. Gal, T.J. Stewart, T. Hanne (Eds.) (p. Chapter 9).
Zhou, B. H., Xi, L. F., & Cao, Y. S. (2005). A beam-search-based algorithm for the tool switching problem on a flexible machine. International Journal of Advanced Manufacturing Technology, 25(9–10), 876–882. https://doi.org/10.1007/s00170-003-1925-2
Management Science and Information Technology
Volume 1, Issue 1
September 2024
Pages 42-56

Files

Share

How to cite

Statistics