Finding optimal solutions to Web Service Location Allocation Problem (WSLAP) using exhaustive algorithms and exact approaches is not practical. Computational time required to solve WSLAP using exact approaches increases exponentially with the problem size. The disclosure herein generally relates to service deployment, and, more particularly, to a method and system for web service location allocation and virtual machine deployment. The system identifies a plurality of web-services that are associated with the WSLAP and then decomposes the WSLAP to a plurality of sub-problems. For each sub-problem, the system determines at least one non-dominating solution, which are then merged to generate the solution for the WSLAP. The generated solution to the WSLAP can be used for perform Virtual Machine (VM) deployment under uncertainties, using a stochastic approach, wherein the uncertainties refer to dynamic change in requirements in terms of parameters such as but not limited to configuration, and cost.