A Neighborhood Search Algorithm for the Tool Indexing Problem without Tool Duplication

In automated machining centers, a job is processed by having multiple cutting tools work on it in a pre-determined sequence. The total time to process such jobs is the sum of the machining time required by the cutting tools, and the non-machining time, required for other activities. The machining time on the job is fixed, and so such machining centers can be made more effective by reducing non-machining times. A significant portion of the non-machining time in machining centers is due to indexing, which is the operation by which tools kept in slots in tool changers are brought to the location from which the tool arm can pick them up and replace them after use. Tool changers can be visualized as disks with slots along their circumference in which tools are kept. Optimal positioning of tools in the slots can significantly speed up non-machining time. This optimization problem, called the tool indexing problem, is studied in this chapter. Specifically, a version of the problem in which only one copy of a tool can be present in the tool changer is studied here. The tool indexing problem is computationally difficult, and the chapter presents local search and tabu search algorithms to obtain good quality solutions to the problem. Two innovative bookkeeping techniques that were used to reduce the search time by two orders of magnitude have been proposed here. Computational results on benchmark tool indexing instances show that the algorithms proposed here are competitive when compared with the state-of-the-art heuristic algorithms for this problem. It is shown that some of the algorithms proposed here are both faster and generate better quality solutions for many of the benchmark instances.