Exact and Evolutionary Approaches for an Integrated Parallel Machine Tooling Problem with Diameter and Material Setups
Authors:
- Alzira MotaAlzira Mota
- Pierpaolo CaricatoPCPierpaolo Caricato
- Antonio GriecoAGAntonio Grieco
- João BastosJBJoão Bastos
- Paulo ÁvilaPÁPaulo Ávila
Preprint
- 28 March 2026
- preprint
- Published by Elsevier in SSRN Electronic Journal
Abstract
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'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.Keywords
This publication has 37 references indexed in Scilit:
- Scheduling2022
- Deep memetic models for combinatorial optimization problems: application to the tool switching problemMemetic Computing, 2019
- A hybrid method of 2-TSP and novel learning-based GA for job sequencing and tool switching problemApplied Soft Computing, 2018
- Improved heuristic algorithms for the Job Sequencing and Tool Switching ProblemComputers & Operations Research, 2017
- Hybrid method with CS and BRKGA applied to the minimization of tool switches problemComputers & Operations Research, 2016
- Solving the Job Sequencing and Tool Switching Problem as a nonlinear least cost Hamiltonian cycle problemNetworks, 2010
- Minimizing total flow time on a single flexible machineInternational Journal of Flexible Manufacturing Systems, 2006
- A note on the tool switching problem of a flexible machineComputers & Industrial Engineering, 2006
- An improved tabu search approach for solving the job shop scheduling problem with tooling constraintsDiscrete Applied Mathematics, 1996
- Modelling a tool switching problem on a single NC-machineJournal of Intelligent Manufacturing, 1995