Beneficial Management Practices (BMPs) are important measures for reducing agricultural non-point source (NPS) pollution. However, selection of BMPs for placement in a watershed requires optimizing available resources to maximize possible water quality benefits. Due to its iterative nature, the optimization typically takes a long time to achieve the BMP trade-off results which is not desirable in practice. In this study, an optimization model, consisting of a multi-objective genetic algorithm, ε-NSGA-II, in combination with the Soil Water and Assessment Tool (SWAT) and the parallel computation technique, is developed and tested in the Fairchild Creek watershed in southern Ontario of Canada. The two objectives are to minimize BMPs costs and maximize total phosphorous load reduction. The parallel computation allows the run of multiple SWAT models simultaneously and can reduce the ε-NSGA-II optimization time significantly to achieve the objective. The Pareto-optimal fronts generated between the two objective functions can be used to achieve desired water quality goals with minimum BMP implementation cost to support spatial watershed management and policy making.