This paper presents a new approach, based on the principles of fuzzy logic and Genetic Algorithm (GA) for selection of optimal process parameters in Abrasive Water Jet (AWJ) cutting of granite to any predetermined depth, using multi-criteria optimization technique. The proposed approach suggests the best combination of process parameters such as water jet pressure, jet traverse rate and abrasive flow rate for cutting granite material to any predetermined depth. GA, in combination with the model built based on fuzzy approach, generates several sets of process parameters satisfying the objective of achieving the desired depth of cut. These sets of parameters are subjected to multi-criteria optimization procedure which suggests a set of process parameters that can minimize the cost of production by increasing the rate of production and reducing the consumption of abrasives, maintaining the desired depth of cut within the specified limits. The proposed approach is validated with suitable experiments conducted on Paradiso granite.