In any organization, business processes are designed to adhere to specified business goals. On many occasions, however, in order to accommodate differing usage contexts, multiple variants of the same business process may need to be designed, all of which should adhere to the same goal. For business processes modeled as compositions of services, automated generation of such goal preserving process variants is a challenge. To that end, we present our approach for generating all goal preserving variants of a service-based business process. Our approach leverages our earlier works on semantic annotations of business processes and service variability modeling. Throughout our paper, we illustrate our ideas with a realistic running example, and also present a proof-of-concept prototype.