This paper reports a tabu-search approach to minimize the total processing cost for hole-making operations. Four issues, namely, tool travel scheduling, tool switch scheduling, tool selection, and machining speed specification have been simultaneously addressed in this study. The total processing cost consists of tooling cost, machining cost, non-productive tool travelling cost, and tool switching cost. This problem has a structure similar to the Travelling Salesman Problem (TSP) and hence is NP-complete. In addition, the problem under consideration is more complex since the cost associated with each operation is both sequence-dependent and position-dependent. To provide an efficient solution procedure, a tabu search approach is used. To improve the search performance two new neighbourhood generation and move selection policies have been proposed and tested. The decisions on the above issues can be made simultaneously based on the output of the proposed algorithm. The results obtained from computational experiments show that the total processing cost can be significantly reduced within a reasonable search time. The effects of some search parameters and diversification strategies on the search performance have also been investigated.