A method of assigning web service requests to service providers includes searching for an optimal assignment from all possible assignments using a genetic algorithm (GA) that represents possible assignments as chromosomes, and converging towards an assignment of web service request to service providers that maximizes overall business value for all workflows to the service providers. An adaptive mutation scheme is used to introduce mutation into populations of chromosomes. The mutation scheme includes a mutation rate that increases when chromosomes under evaluation fail to improve its workload against the metric over a certain number of generations.