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.

This publication has 37 references indexed in Scilit: