A central problem of tool management in Versatile Multi-tool machining centres is to decide how to batch the parts to be produced and what tools to allocate to the machine in order to maximize utilization of these expensive machines. Various authors have proposed heuristics and/or mathematical models to minimize the batches of parts to be manufactured in a production period. There is no comprehensive study reported to compare the number of actual batches (stoppages) formed with and without processing time considerations. In this paper, the sequential deterministic heuristics (SDHs) are appropriately adapted to include processing time of operations in the formation of groups. The modified heuristics are more realistic in reducing machine stoppages due to tools. Some stochastic search techniques have also been adapted to compute the number of groups. The results are compared with those obtained from SDHs and standard search techniques. The results indicate that the adapted search techniques are powerful approaches for forming optimum number of batches of parts and tools.