{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T17:53:50Z","timestamp":1774720430269,"version":"3.50.1"},"posted":{"date-parts":[[2026]]},"group-title":"SSRN","reference-count":48,"publisher":"Elsevier BV","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Efficient management of tool switches is a critical issue in parallel machine environments where setup operations arise from tool loading, diameter adjustments and material changes. While tool loading constraints have been widely studied, the joint consideration of diameter adjustments and material changes has received comparatively limited attention in the scheduling literature. This paper studies an integrated parallel machine tooling problem that incorporates these setup dependencies, reflecting operational conditions observed in manufacturing systems.Two mixed-integer linear programming (MILP) formulations are developed. Model~1 extends formulations from the literature, while Model~2, inspired by the multiple travelling salesman problem, is designed to capture the problem&amp;apos;s combinatorial structure better. Both models solve a relaxed formulation that does not explicitly incorporate unloading decisions, and a final schedule is obtained by applying a KTNS-based policy.Computational experiments show that Model~1 is limited to small instances, whereas Model~2 presents better scalability. However, for some medium- and large-sized instances that meet the imposed time limit, the relaxed solution does not always yield a feasible schedule after the KTNS procedure.In addition, three evolutionary metaheuristic approaches are analysed: a permutation-based genetic algorithm (GA), its memetic extension with bounded local search (GA+LS), and a hybrid biased random-key genetic algorithm (BRKGA). Results on synthetic benchmarks show that BRKGA performs best overall, particularly on larger instances.An industrial case study reveals a different pattern: for medium-sized real instances, GA and GA+LS produce solutions comparable to those of the exact model within substantially shorter runtimes.<\/jats:p>","DOI":"10.2139\/ssrn.6485690","type":"posted-content","created":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T17:38:12Z","timestamp":1774719492000},"source":"Crossref","is-referenced-by-count":0,"title":["Exact and Evolutionary Approaches for an Integrated Parallel Machine Tooling Problem with Diameter and Material Setups"],"prefix":"10.2139","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3871-4215","authenticated-orcid":true,"given":"Alzira","family":"Mota","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7459-0109","authenticated-orcid":true,"given":"Pierpaolo","family":"Caricato","sequence":"additional","affiliation":[]},{"given":"Antonio","family":"Grieco","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9082-3291","authenticated-orcid":true,"given":"Jo\u00e3o","family":"Bastos","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8420-0875","authenticated-orcid":true,"given":"Paulo","family":"\u00c1vila","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"ref1","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/S0951-5240(96)00023-7","article-title":"Joint job\/tool scheduling in a flexible manufacturing cell with no on-board tool magazine","volume":"10","author":"A Agnetis","year":"1997","journal-title":"Computer Integrated Manufacturing Systems"},{"key":"ref2","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/j.asoc.2017.12.045","article-title":"A hybrid method of 2-TSP and novel learning-based GA for job sequencing and tool switching problem","volume":"65","author":"E Ahmadi","year":"2018","journal-title":"Applied Soft Computing"},{"key":"ref3","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/S0360-8352(02)00183-3","article-title":"A tabu search based algorithm for minimizing the number of tool switches on a flexible machine","volume":"44","author":"M A Al-Fawzan","year":"2003","journal-title":"Computers & Industrial Engineering"},{"key":"ref4","article-title":"Revisiting the parallel tempering algorithm: High-performance computing and applications in operations research","volume":"178","author":"A L B Almeida","year":"2025","journal-title":"Computers & Operations Research"},{"key":"ref5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s12293-019-00294-1","article-title":"Deep memetic models for combinatorial optimization problems: application to the tool switching problem","volume":"12","author":"J E Amaya","year":"2020","journal-title":"Memetic Computing"},{"key":"ref6","doi-asserted-by":"crossref","first-page":"1548","DOI":"10.1080\/00207543.2017.1357861","article-title":"Minimisation of non-machining times in operating automatic tool changers of machine tools under dynamic operating conditions","volume":"56","author":"A Baykaso?lu","year":"2018","journal-title":"International Journal of Production Research"},{"key":"ref7","doi-asserted-by":"crossref","first-page":"834","DOI":"10.1016\/j.ejor.2016.08.008","article-title":"Scheduling identical parallel machines with tooling constraints","volume":"257","author":"A C Beez\ufffdo","year":"2017","journal-title":"European Journal of Operational Research"},{"key":"ref8","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.omega.2004.10.004","article-title":"The multiple traveling salesman problem: an overview of formulations and solution procedures","volume":"34","author":"T Bektas","year":"2006","journal-title":"Omega"},{"key":"ref9","first-page":"1316","volume":"32","author":"M Berrada","year":"1986","journal-title":"A Branch and Bound Approach for Machine Load Balancing in Flexible Manufacturing Systems"},{"key":"ref10","doi-asserted-by":"crossref","first-page":"5005","DOI":"10.1080\/00207543.2018.1505057","article-title":"The job sequencing and tool switching problem: state-of-the-art literature review, classification, and trends","volume":"57","author":"D Calmels","year":"2019","journal-title":"International Journal of Production Research"},{"key":"ref11","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/j.ejor.2021.05.005","article-title":"An iterated local search procedure for the job sequencing and tool switching problem with non-identical parallel machines","volume":"297","author":"D Calmels","year":"2022","journal-title":"European Journal of Operational Research"},{"key":"ref12","doi-asserted-by":"crossref","first-page":"766","DOI":"10.1016\/j.ejor.2015.02.018","article-title":"Improved integer linear programming formulations for the job Sequencing and tool Switching Problem","volume":"244","author":"D Catanzaro","year":"2015","journal-title":"European Journal of Operational Research"},{"key":"ref13","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1016\/j.cor.2015.10.009","article-title":"Hybrid method with CS and BRKGA applied to the minimization of tool switches problem","volume":"67","author":"A A Chaves","year":"2016","journal-title":"Computers & Operations Research"},{"key":"ref14","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/j.cor.2019.01.005","article-title":"Minimizing the makespan on two identical parallel machines with mold constraints","volume":"105","author":"T Chung","year":"2019","journal-title":"Computers & Operations Research"},{"key":"ref15","first-page":"165","article-title":"Minimizing the number of tool switches on a flexible machine","author":"Y Crama","year":"1994","journal-title":"International Journal of Flexible Manufacturing Systems"},{"key":"ref16","doi-asserted-by":"crossref","DOI":"10.1016\/j.eswa.2023.119908","article-title":"Hybridizing local searching with genetic algorithms for the job sequencing and tool switching problem with non-identical parallel machines","volume":"223","author":"T Cura","year":"2023","journal-title":"Expert Systems with Applications"},{"key":"ref17","first-page":"52","article-title":"Optimization of a New Tool Switching Problem in Flexible Manufacturing Systems with a Tool Life by a Genetic Algorithm","volume":"1","author":"H Dadashi","year":"2016","journal-title":"International Journal of Industrial and Manufacturing Systems Engineering"},{"key":"ref18","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1016\/j.ejor.2020.09.050","article-title":"A matheuristic for parallel machine scheduling with tool replacements","volume":"291","author":"Q V Dang","year":"2021","journal-title":"European Journal of Operational Research"},{"key":"ref19","article-title":"Unsupervised parallel machines scheduling with tool switches","volume":"160","author":"Q V Dang","year":"2023","journal-title":"Computers & Operations Research"},{"key":"ref20","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1080\/00207540110076115","article-title":"Heuristic procedures for the parallel machine problem with tool switches","volume":"40","author":"Y Fathi","year":"2002","journal-title":"International Journal of Production Research"},{"key":"ref21","author":"M R Garey","year":"1979","journal-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness"},{"key":"ref22","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1016\/j.rcim.2007.02.011","article-title":"An exact solution to the TLP problem in an NC machine","volume":"23","author":"G Ghiani","year":"2007","journal-title":"Robotics and Computer-Integrated Manufacturing"},{"key":"ref23","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/net.20341","article-title":"Solving the job sequencing and tool switching problem as a nonlinear least cost hamiltonian cycle problem","volume":"55","author":"G Ghiani","year":"2010","journal-title":"Networks"},{"key":"ref24","doi-asserted-by":"crossref","first-page":"5541","DOI":"10.1080\/00207543.2017.1421781","article-title":"Parallel machine scheduling with tool loading: a constraint programming approach","volume":"56","author":"B G\ufffdkg\ufffdr","year":"2018","journal-title":"International Journal of Production Research"},{"key":"ref25","first-page":"69","article-title":"A comparative analysis of selection schemes used in genetic algorithms","volume":"1","author":"D E Goldberg","year":"1989","journal-title":"Optimization and Machine Learning"},{"key":"ref26","article-title":"A Genetic-Algorithm-Based Approach for Optimizing Tool Utilization and Makespan in FMS Scheduling","volume":"7","author":"A Grassi","year":"2023","journal-title":"Journal of Manufacturing and Materials Processing 2023"},{"key":"ref27","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1080\/07408179808966514","article-title":"Heuristics for minimizing tool switches when scheduling part types on a flexible machine","volume":"30","author":"A Hertz","year":"1998","journal-title":"IIE TRANSACTIONS"},{"key":"ref28","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0166-218X(95)00040-X","article-title":"An improved tabu search approach for solving the job shop scheduling problem with tooling constraints","volume":"65","author":"A Hertz","year":"1996","journal-title":"Discrete Applied Mathematics"},{"key":"ref29","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1016\/S0377-2217(03)00376-X","article-title":"The scheduling problem of pcbs for multiple non-identical parallel machines","volume":"158","author":"N V Hop","year":"2004","journal-title":"European Journal of Operational Research"},{"key":"ref30","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/s10696-006-9000-6","article-title":"Minimizing total flow time on a single flexible machine","volume":"18","author":"I Karakayali","year":"2006","journal-title":"International Journal of Flexible Manufacturing Systems"},{"key":"ref31","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1080\/095372800232496","article-title":"A generalized procedure for minimizing tool changeovers of two parallel and identical CNC machining centres","volume":"11","author":"B K Khan","year":"2000","journal-title":"Production Planning & Control"},{"key":"ref32","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1080\/00207549108930080","article-title":"Total tool requirements in multi-level machining systems","volume":"29","author":"C P Koulamas","year":"1991","journal-title":"The International Journal of Production Research"},{"key":"ref33","doi-asserted-by":"crossref","first-page":"3747","DOI":"10.1080\/00207540110064938","article-title":"Heuristic scheduling of parallel machines with sequence-dependent set-up times","volume":"39","author":"M E Kurz","year":"2001","journal-title":"International Journal of Production Research"},{"key":"ref34","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1080\/07408170490257871","article-title":"Exact algorithms for the job sequencing and tool switching problem","volume":"36","author":"G Laporte","year":"2004","journal-title":"IIE Transactions"},{"key":"ref35","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/j.orp.2016.09.002","article-title":"The irace package: Iterated racing for automatic algorithm configuration","volume":"3","author":"M L\ufffdpez-Ib\ufffd\ufffdez","year":"2016","journal-title":"Operations Research Perspectives"},{"key":"ref36","doi-asserted-by":"crossref","DOI":"10.1016\/j.cor.2020.105153","article-title":"A simple and effective hybrid genetic search for the job sequencing and tool switching problem","volume":"127","author":"J Mecler","year":"2021","journal-title":"Computers & Operations Research"},{"key":"ref37","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1016\/j.cor.2017.07.013","article-title":"Improved heuristic algorithms for the Job Sequencing and Tool Switching Problem","volume":"88","author":"G S Paiva","year":"2017","journal-title":"Computers and Operations Research"},{"key":"ref38","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-05921-6","author":"M L Pinedo","year":"2022","journal-title":"Scheduling: Theory, Algorithms, and Systems"},{"key":"ref39","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF00123680","article-title":"Modelling a tool switching problem on a single NC-machine","volume":"6","author":"C Privault","year":"1995","journal-title":"Journal of Intelligent Manufacturing"},{"key":"ref40","article-title":"A two-stage heuristic for the sequence-dependent job sequencing and tool switching problem","volume":"163","author":"A P Rifai","year":"2021","journal-title":"Computers & Industrial Engineering"},{"key":"ref41","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1016\/j.cie.2004.11.002","article-title":"A note on the tool switching problem of a flexible machine","volume":"50","author":"K Salonen","year":"2006","journal-title":"Computers & Industrial Engineering"},{"key":"ref42","doi-asserted-by":"crossref","first-page":"3547","DOI":"10.1080\/00207540110060888","article-title":"Minimizing the number of tool switches on a flexible machine: An empirical study","volume":"39","author":"R Shirazi","year":"2001","journal-title":"International Journal of Production Research"},{"key":"ref43","doi-asserted-by":"crossref","first-page":"3617","DOI":"10.1080\/00207543.2020.1748906","article-title":"A new multicommodity flow model for the job sequencing and tool switching problem","volume":"59","author":"T T Da Silva","year":"2021","journal-title":"International Journal of Production Research"},{"key":"ref44","doi-asserted-by":"crossref","DOI":"10.1016\/j.cor.2023.106509","article-title":"Biased random-key genetic algorithm for the job sequencing and tool switching problem with non-identical parallel machines","volume":"163","author":"L C Soares","year":"2024","journal-title":"Computers & Operations Research"},{"key":"ref45","doi-asserted-by":"crossref","first-page":"955","DOI":"10.1016\/j.ejor.2020.02.047","article-title":"Biased random-key genetic algorithm for scheduling identical parallel machines with tooling constraints","volume":"285","author":"L C R Soares","year":"2020","journal-title":"European Journal of Operational Research"},{"key":"ref46","first-page":"273","volume":"29","author":"K E Stecke","year":"1983","journal-title":"Formulation and solution of nonlinear integer production planning problems for flexible manufacturing systems"},{"key":"ref47","first-page":"767","volume":"36","author":"C S Tang","year":"1988","journal-title":"Models arising from a flexible manufacturing machine, part i: Minimization of the number of tool switches"},{"key":"ref48","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1109\/TSMCA.2004.832824","article-title":"The tool-switching problem with magazine capacity and tool size constraints","volume":"35","author":"N Van Hop","year":"2005","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans"}],"container-title":[],"original-title":[],"deposited":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T17:41:05Z","timestamp":1774719665000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ssrn.com\/abstract=6485690"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"references-count":48,"URL":"https:\/\/doi.org\/10.2139\/ssrn.6485690","relation":{},"subject":[],"published":{"date-parts":[[2026]]},"subtype":"preprint"}}