SCALABLE ALGORITHM FOR THE SERVICE SELECTION PROBLEM

In this paper, we are interested in fast algorithms for the service selection problem. Given an abstract services' composition, the objective in this problem is to choose the best services for implementing the composition such as to minimize a given penalty function. Our work contributes to both the sequential and parallel resolution of this problem. For the sequential resolution, we show how to extend a prior algorithm for QoS prediction to obtain a fast sequential resolution of the service selection problem. Our proposal innovates in the optimization techniques (variable ordering, branch and bound, etc.) used for the runtime minimization. For the parallel resolution, we discuss on two possible formulations for the parallelism: task and data parallelism. We show that on our problem, the latter formulation is adequate because it leads to a more scalable resolution. Finally, we conduct various experiments that show that super-linear speedups can be reached with our new parallel algorithm.