The arrangement of tools in tool holding pockets of a tool magazine in a CNC machining center plays an important role in reducing processing times of complex job processes in automated machining environments. This problem is called the ATC indexing problem (ATCIP). Computing the cost of a solution for an ATCIP instance of size $n$ requires $\\mathcal{O}(n^2)$ time, so that neighborhood search iteration for the ATCIP on an $\\mathcal{O}(n^2)$ neighborhood requires $\\mathcal{O}(n^4)$ time. We describe techniques to reduce this effort for two common neighborhood structures from $\\mathcal{O}(n^4)$ time to $\\mathcal{O}(n^2)$ time.