Mathematical programming and heuristic approaches to the turret-index optimisation problem with tool duplications
针对CNC刀塔索引问题，提出整数线性规划和约束规划两种精确方法，以及迭代贪婪搜索元启发式算法，实验表明约束规划在小中型问题上最优，迭代贪婪搜索在大型问题上表现更佳。
This paper addresses the Tool Indexing Problem (TIP) with tool duplications, a critical optimisation problem in CNC turret operations where indexing time directly impacts production efficiency, particularly in high-volume manufacturing. The indexing problem has proven computationally challenging, and no highly effective exact formulations have been reported previously. We introduce two novel mathematical programming approaches: Integer Linear Programming (ILP) and, for the first time in the literature, a Constraint Programming (CP) formulation for the TIP with tool duplications. Additionally, we propose a new Iterated Greedy Search (IGS) metaheuristic designed to efficiently address large-scale problem instances resulting from the problem’s NP-hard nature. A comprehensive comparative analysis of benchmark instances shows that the CP formulation consistently outperforms the ILP model, especially for small- and medium-sized problems, making it the most effective exact approach reported to date. For larger problem sizes, the proposed IGS demonstrates slightly better performance than CP, surpassing all previously proposed heuristics in the literature. While CP remains an effective exact method across all problem scales, metaheuristics such as IGS continue to provide significant value by enabling the efficient solution of large-scale instances.