Linear formulations and a hybrid large neighborhood search algorithm for the tool indexing problem
研究了数控机床工具索引问题，提出三种混合整数线性规划公式，并设计混合大邻域搜索与局部搜索算法，在85个基准实例上验证其优于其他算法。
In this article, one of the most commonly encountered problems in manufacturing systems, known as the Tool Indexing Problem (TIP), is considered. TIP involves allocating cutting tools to different slots in a tool magazine of a Computer Numerically Controlled (CNC) machine to reduce the processing time of jobs on the machine. In this article, three mixed-integer linear programming formulations of single-objective TIP without tool duplication and lifespan are presented. A comparative study of these three linear formulations of TIP is also included in this article. During the study, it was found that the exact solver CPLEX with these linear formulations struggles to find optimal solutions in a reasonable time for larger instances. Therefore, a Hybrid Large Neighborhood Search with Local Search (HLNS-LS) algorithm, which is a metaheuristic approach, is proposed for solving TIP. The LNS phase iteratively destroys and repairs solutions to explore different regions of the solution space, while the LS phase intensifies the search by applying multiple neighborhood operators, such as swap, insert, shift, and customized 2-Opt and 3-Opt, to refine solutions further. This hybrid approach balances diversification and intensification, aiming to find high-quality solutions that minimize the total turret rotation cost associated with tool indexing. The performance of the proposed HLNS-LS algorithm is evaluated against an improved Harmony Search algorithm, a Weighted Superposition Attraction-based algorithm, and a Constraint Programming model across 85 small-, medium-, and large-sized benchmark instances from the existing TIP literature.