Minimization of Number of Tool Switching Instants in Automated Manufacturing Systems

Abstract

This study addresses the problem of minimizing tool switching instants in automated manufacturing systems. There exist a single machine and a group of jobs to be processed on it. Each job requires a set of tools, and due to limited tool magazine capacity, and because it is not possible to load all available tools on the machine, tools must be switched. The ultimate goal, in this framework, is to minimize the total number of tool switching instants. We provide a mathematical programming model and two constraint programming models for the problem. Because the problem is proven to be NP-hard, we develop two heuristic approaches, and compare their performance with methods described in the literature. Our analysis indicates that our constraint programming models perform relatively well in solution quality and execution time in small-sized problem instances. The performance of our greedy approach shows potential, reaching the optimal solution in 82.5% of instances. We also statistically demonstrate that the search algorithm enhances the quality of the solution obtained by the greedy heuristic, particularly in large sets. Hence, the solution approach, i.e., the greedy heuristic and the search algorithm proposed in this study is able to quickly reach near-optimal solutions, showing that the method is appropriate for manufacturing settings requiring sudden adjustments.

Keywords

• Tool switching instants
• Job grouping problem
• Mathematical model
• Heuristic algorithm
• Constraint programming

References

1. [1] Shirazi, R., Frizelle, G.D.M., “Minimizing the number of tool switches on a flexible machine: An empirical study”, International Journal of Production Research, 39(15): 3547–3560, (2001).
2. [2] Calmels, D., “The job sequencing and tool switching problem: state-of-the-art literature review, classification, and trends”, International Journal of Production Research, 57(15-16): 5005–5025, (2019).
3. [3] Crama, Y., “Combinatorial optimization models for production scheduling in automated manufacturing systems”, European Journal of Operational Research, 99: 136–153, (1997).
4. [4] Tang, C.S., Denardo, E.V., “Models arising from a flexible manufacturing machine, Part II: minimization of the number of switching instants”, Operations Research, 36(5): 778–784, (1988).
5. [5] Song, C.Y., Hwang, H., “Optimal tooling policy for a tool switching problem of a flexible machine with an automatic tool transporter”, International Journal of Production Research, 40: 873–883, (2002).
6. [6] Denizel, M., “Minimization of the number of tool magazine setups on automated machines: a lagrangean decomposition approach”, Operations Research, 51(2): 309–320, (2003).
7. [7] Konak, A., Kulturel-Konak, S., Azizo˘glu, M., “Minimizing the number of tool switching instants in flexible manufacturing systems”, International Journal of Production Economics, 116: 298–307, (2008).
8. [8] Konak, A., Kulturel-Konak, S., “An ant colony optimization approach to the minimum tool switching instant problem in flexible manufacturing system”, Proceedings of IEEE Symposium on Computational Intelligence in Scheduling, 43–48, (2007).

9. [9] Adjiashvili, D., Bosio, S., Zemmer, K., “Minimizing the number of switch instances on a flexible machine in polynomial time”, Operations Research Letters, 43(3): 317–322, (2015).
10. [10] Baykaso˘glu, A., Ozsoydan, F.B., “An improved approach for determination of index positions on CNC magazines with cutting tool duplications by integrating shortest path algorithm”, International Journal of Production Research, 54(3): 742–760, (2016).
11. [11] Baykaso˘glu, A., Ozsoydan, F.B., “Minimizing tool switching and indexing times with tool duplications in automatic machines”, The International Journal of Advanced Manufacturing Technology, 89: 1775–1789, (2017).
12. [12] Baykaso˘glu, A., Ozsoydan, F.B., “Minimisation of non-machining times in operating automatic tool changers of machine tools under dynamic operating conditions”, International Journal of Production Research, 56(4): 1548–1564, (2018).
13. [13] Chaves, A.A., Lorena, L.A.N., Senne, E.L.F., Resende, M.G.C., “Hybrid method with CS and BRKGA applied to the minimization of tool switches problem”, Computers & Operations Research, 67: 174–183, (2016).
14. [14] Furrer, M., Mütze, T.,“An algorithmic framework for tool switching problems with multiple objectives”, European Journal of Operational Research, 259(3): 1003–1016, (2017).
15. [15] Marvizadeh, S.Z., Choobineh, F.F., “Reducing the number of setups for CNC punch presses”, Omega, 41(2): 226–235, (2013).
16. [16] Paiva, G.S., Carvalho, M.A.M., “Improved heuristic algorithms for the job sequencing and tool switching problem”, Computers & Operations Research, 88: 208–219, (2017).
17. [17] Dang, Q.-V.., van Diessen, T., Martagan, T., Adan, I. “A matheuristic for parallel machine scheduling with tool replacements”, European Journal of Operational Research, https://doi.org/10.1016/j.ejor.2020.09.050.
18. [18] Atta, S., Sinha Mahapatra, P.R., Mukhopadhyay, A. “Solving tool indexing problem using harmony search algorithm with harmony refinement”, Soft Computing, 23: 7407-7423, (2019)
19. [19] da Silva, T.T., Chaves, A.A., Yanasse, H. Y. “A new multicommodity flow model for the job sequencing and tool switching problem”, International Journal of Production Research, https://doi.org/10.1080/00207543.2020.1748906.
20. [20] Smed, J., Johnsson, M., Puranen, M., Leipälä, T., Nevalainen, O., “Job grouping in surface mounted component printing”, Robotics and Computer-Integrated Manufacturing, 15: 39–49, (1999).
21. [21] Yuan, S., Skinner, B.T., Huang, S., Liu, D.K., Dissanayake, G., Lau, H., Pagac, D., “A job grouping approach for planning container transfers at automated seaport container terminals”, Advanced Engineering Informatics, 25: 413–426, (2011).
22. [22] Jans, R., Desrosiers, J., “Efficient symmetry breaking formulations for the job grouping problem”, Computers & Operations Research, 40(4): 1132–1142, (2013).
23. [23] Dadashi, H., Moslemi, S., Mirzazadeh, A., “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, (2016).
24. [24] Zeballos, L.J., “A constraint programming approach to tool allocation and production scheduling in flexible manufacturing systems”, Robotics and Computer-Integrated Manufacturing, 26(6): 725–743, (2010).
25. [25] Zeballos, L.J., Quiroga, O.D., Henning, G.P., “A constraint programming model for the scheduling of flexible manufacturing systems with machine and tool limitations”, Engineering Applications of Artificial Intelligence, 23(2): 229–248, (2010).
26. [26] Edis, E.B., Ozkarahan, I., “A combined integer/constraint programming approach to a resource-constrained parallel machine scheduling problem with machine eligibility restrictions”, Engineering Optimization, 43(2): 135–157, (2011).
27. [27] Novas, J.M., Henning, G.P., “Integrated scheduling of resource-constrained flexible manufacturing systems using constraint programming”, Expert Systems with Applications, 41(5): 2286–2299, (2014).
28. [28] Gökgür, B., Hnich, B., Özpeynirci, S., “Parallel machine scheduling with tool loading: a constraint programming approach”, International Journal of Production Research, 56(16): 5541-5557, (2018).
29. [29] Frisch, A.M., Hnich, B., Kiziltan, Z., Miguel, I., Walsh, T., “Propagation algorithms for lexicographic ordering constraints”, Artificial Intelligence, 170(10): 803–834, (2006).
30. [30] Flener, P., Frisch, A.M., Hnich, B., Kiziltan, Z., Miguel, I., Pearson, J., Walsh, T.,“Breaking row and column symmetries in matrix models”, International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, 2470: 462–476, (2002).