Minimization of nonmachining time is a crucial issue for effective and profitable utilization of automatic machining centers. Most of the automatic machining centers contain an automatic tool changer (ATC) for holding multiple cutting tools. Effective operation of ATC in relation to the parts assigned for machining is critical in minimizing nonmachining times. There are actually two main operations on ATCs which can be reduced by making use of suitable optimization procedures. These operations are known as "ATC indexing problem" and "tool switching problem (ToSP)." These problems are separately addressed as NP-hard problems in the literature and mostly solved independently so far. In the present work, we made an attempt to solve these problems simultaneously by making use of a simulated annealing (SA) algorithm with novel solution coding/encoding strategies. The results are compared with the lower bounds obtained by a method proposed in the present work. Promising findings are expected to contribute to the possible future work of this research field.