Titanium and its alloys are classified into difficult to cut materials. To machine such materials economically, the optimized process parameters plays significant role. Therefore the experiments have been planned and conducted using Design of Experiments. The experiments are conducted under different machining environments such as dry, flooded and Minimum Quantity Lubrication (MQL) machining with different tool materials such as uncoated, Chemical Vapour Deposition (CVD) and Physical Vapour Deposition (PVD) coated tools. In this study, Taguchi's L orthogonal array is 27 used to perform the experiments. The results obtained from these experiments are used to develop second order multiple regression model in terms of input process parameter. The same model is used as a fitness function for Simulated Annealing (SA) to optimize the process parameters for minimum surface roughness. The optimum results from SA is compared with Taguchi methodology and validated with Regression Analysis. The optimum parameters obtained both in Taguchi's methodology and Simulated Annealing are flooded machining, high cutting speed, low feed rate, low depth of cut and CVD coated tool.