The sequence-dependent job sequencing and tool switching problem with non-identical parallel machines
Submitted: 2024-12-18
|Accepted: 2026-03-05
|Published: 2026-06-03
Copyright (c) 2026 Achmad Pratama Rifai, Wangi Pandan Sari
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Downloads
Additional Files
Keywords:
Job sequencing and tool switching, non-identical parallel machines, sequence-dependent setup time, adaptive large neighborhood search, simulated annealing
Supporting agencies:
Abstract:
This study explores the job sequencing and tool switching problem with sequence-dependent setup times on non-identical parallel machines (SDSSP-NPM). The problem involves diverse parallel machines with varying tool magazine capacities, processing times, and sequence-dependent setup times. This extension is particularly relevant in manufacturing, where production lines consist of machines capable of handling different job requirements. The model addresses three objectives: minimizing total setup time, total flow time, and makespan. To tackle the SDSSP-NPM, a two-stage metaheuristic approach is introduced, combining adaptive large neighborhood search (ALNS) and simulated annealing (SA). ALNS is employed to solve the job sequencing subproblem (SP), while SA, coupled with the keep tool needed soonest (KTNS) algorithm, handles the tool switching subproblem (TP). The proposed method is rigorously tested across 640 instances with varying complexities. Additionally, sensitivity analysis is conducted to assess the impact of two key parameters: the number of required tools for each job and the duration of switching time on the method's performance. The experimental results demonstrate the effectiveness of the proposed method, outperforming other recent approaches by generating solutions with superior objectives.
References:
Adjiashvili, D., Bosio, S., & Zemmer, K. (2015). Minimizing the number of switch instances on a flexible machine in polynomial time. Operations Research Letters, 43(3), 317–322. https://doi.org/10.1016/j.orl.2015.04.001
Atta, S., Sinha Mahapatra, P. R., & Mukhopadhyay, A. (2019). Solving tool indexing problem using harmony search algorithm with harmony refinement. Soft Computing, 23, 7407–7423. https://doi.org/10.1007/s00500-018-3385-5
Beezão, A. C., Cordeau, J.-F., Laporte, G., & Yanasse, H. H. (2017). Scheduling identical parallel machines with tooling constraints. European Journal of Operational Research, 257(3), 834–844. https://doi.org/10.1016/j.ejor.2016.08.008
Burger, A. P., Jacobs, C. G., van Vuuren, J. H., & Visagie, S. E. (2015). Scheduling multi-colour print jobs with sequencedependent setup times. Journal of Scheduling, 18, 131–145. https://doi.org/10.1007/s10951-014-0400-2
Calmels, D. (2019). 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. https://doi.org/10.1080/00207543.2018.1505057
Calmels, D. (2022). An iterated local search procedure for the job sequencing and tool switching problem with nonidentical parallel machines. European Journal of Operational Research, 297(1), 66–85. https://doi.org/10.1016/j.ejor.2021.05.005
Catanzaro, D., Gouveia, L., & Labbé, M. (2015). Improved integer linear programming formulations for the job sequencing and tool switching problem. European Journal of Operational Research, 244(3), 766–777. https://doi.org/10.1016/j.ejor.2015.02.018
Chaves, A. A., Lorena, L. A. N., Senne, E. L. F., & Resende, M. G. C. (2016). Hybrid method with CS and BRKGA applied to the minimization of tool switches problem. Computers & Operations Research, 67, 174–183. https://doi.org/10.1016/j.cor.2015.10.009
Cura, T. (2023). Hybridizing local searching with genetic algorithms for the job sequencing and tool switching problem with non-identical parallel machines. Expert Systems with Applications, 223, Article 119908. https://doi.org/10.1016/j.eswa.2023.119908
Dang, Q.-V., van Diessen, T., Martagan, T., & Adan, I. (2021). A matheuristic for parallel machine scheduling with tool replacements. European Journal of Operational Research, 291(2), 640–660. https://doi.org/10.1016/j.ejor.2020.09.050
Dang, Q.-V., Herps, K., Martagan, T., Adan, I., & Heinrich, J. (2023). Unsupervised parallel machines scheduling with tool switches. Computers & Operations Research, 160, Article 106361. https://doi.org/10.1016/j.cor.2023.106361
Furrer, M., & Mütze, T. (2017). An algorithmic framework for tool switching problems with multiple objectives. European Journal of Operational Research, 259(3), 1003–1016. https://doi.org/10.1016/j.ejor.2016.11.034
Ghrayeb, O. A., Phojanamongkolkij, N., & Finch, P. R. (2003). A mathematical model and heuristic procedure to schedule printed circuit packs on sequencers. International Journal of Production Research, 41(16), 3849–3860.https://doi.org/10.1080/0020754031000118071
Gökgür, B., Hnich, B., & Özpeynirci, S. (2018). Parallel machine scheduling with tool loading: A constraint programming approach. International Journal of Production Research, 56(16), 5541–5557. https://doi.org/10.1080/00207543.2017.1421781
Grassi, A., Guizzi, G., Popolo, V., & Vespoli, S. (2023). A genetic-algorithm-based approach for optimizing tool utilization and makespan in FMS scheduling. Journal of Manufacturing and Materials Processing, 7(2), Article 75. https://doi.org/10.3390/jmmp7020075
Iori, M., Locatelli, A., Locatelli, M., & Salazar-González, J. J. (2022). Tool switching problems in the context of overlay printing with multiple colours. In Combinatorial Optimization (pp. 260–271). https://doi.org/10.1007/978-3-031-18530-4_19
Javaid, M., Haleem, A., Singh, R. P., & Suman, R. (2022). Enabling flexible manufacturing system (FMS) through the applications of industry 4.0 technologies. Internet of Things and Cyber-Physical Systems, 2, 49–62.https://doi.org/10.1016/j.iotcps.2022.05.005
Khan, B. K., Gupta, B. D., Sen Gupta, D. K., & Kumar, K. D. (2000). A generalized procedure for minimizing tool changeovers of two parallel and identical CNC machining centres. Production Planning & Control, 11(1), 62–72.https://doi.org/10.1080/095372800232496
Laporte, G., Salazar-Gonzalez, J. J., & Semet, F. (2004). Exact algorithms for the job sequencing and tool switching problem. IIE Transactions, 36(1), 37–45. https://doi.org/10.1080/07408170490257871
Mara, S. T. W., Sutoyo, E., Norcahyo, R., & Rifai, A. P. (2023). The job sequencing and tool switching problem with sequencedependent setup time. Journal of King Saud University - Engineering Sciences, 35(1), 53–61. https://doi.org/10.1016/j.jksues.2021.02.015
Mütze, T. (2014). Scheduling with few changes. European Journal of Operational Research, 236(1), 37–50.https://doi.org/10.1016/j.ejor.2013.11.011
Özpeynirci, S., Gökgür, B., & Hnich, B. (2016). Parallel machine scheduling with tool loading. Applied Mathematical Modelling, 40(9–10), 5660–5671. https://doi.org/10.1016/j.apm.2016.01.006
Paiva, G. S., & Carvalho, M. A. M. (2017). Improved heuristic algorithms for the job sequencing and tool switching problem. Computers & Operations Research, 88, 208–219. https://doi.org/10.1016/j.cor.2017.07.013
Pisinger, D., & Ropke, S. (2010). Large neighborhood search. In M. Gendreau & J.-Y. Potvin (Eds.), Handbook of Metaheuristics (pp. 399–419). Springer. https://doi.org/10.1007/978-1-4419-1665-5_13
Privault, C., & Finke, G. (1995). Modelling a tool switching problem on a single NC-machine. Journal of Intelligent Manufacturing, 6, 87–94. https://doi.org/10.1007/BF00123680
Privault, C., & Finke, G. (2000). k-server problems with bulk requests: An application to tool switching in manufacturing. Annals of Operations Research, 96(1–4), 255–269. https://doi.org/10.1023/A:1018939132489
Raduly-Baka, C., & Nevalainen, O. S. (2015). The modular tool switching problem. European Journal of Operational Research, 242(1), 100–106. https://doi.org/10.1016/j.ejor.2014.09.052
Rifai, A. P., Nguyen, H.-T., & Dawal, S. Z. M. (2016). Multi-objective adaptive large neighborhood search for distributed reentrant permutation flow shop scheduling. Applied Soft Computing, 40, 42–57. https://doi.org/10.1016/j.asoc.2015.11.034
Rifai, A. P., Mara, S. T. W., & Norcahyo, R. (2022a). A two-stage heuristic for the sequence-dependent job sequencing and tool switching problem. Computers & Industrial Engineering, 163, Article 107813. https://doi.org/10.1016/j.cie.2021.107813
Rifai, A. P., Sutoyo, E., Mara, S. T. W., & Dawal, S. Z. M. (2022b). Multiobjective sequence-dependent job sequencing and tool switching problem. IEEE Systems Journal, 17(1), 1395–1406. https://doi.org/10.1109/JSYST.2022.3213767
Ropke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4), 455–472. https://doi.org/10.1287/trsc.1050.0135
Schwerdfeger, S., & Boysen, N. (2017). Order picking along a crane-supplied pick face: The SKU switching problem. European Journal of Operational Research, 260(2), 534–545. https://doi.org/10.1016/j.ejor.2016.12.037
Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. In M. Maher & J.-F. Puget (Eds.), Principles and Practice of Constraint Programming—CP98 (pp. 417–431). Springer.https://doi.org/10.1007/3-540-49481-2_30
Shirazi, R., & Frizelle, G. D. M. (2001). Minimizing the number of tool switches on a flexible machine: An experimental study. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 215(2),253–261. https://doi.org/10.1243/0954405011515190
Tang, C. S., & Denardo, E. V. (1988). Models arising from a flexible manufacturing machine, Part I: Minimization of the number of tool switches. Operations Research, 36(5), 767–777. https://doi.org/10.1287/opre.36.5.767
Van Hop, N., & Nagarur, N. N. (2004). The scheduling problem of PCBs for multiple non-identical parallel machines. European Journal of Operational Research, 158(3), 577–594. https://doi.org/10.1016/S0377-2217(03)00376-X
