This chapter presents an aggregated metric to estimate the quality of service compositions, and two algorithms to select the best compositions based on this metric. Both algorithms follow different strategies to prune the space of possibilities while minimizing the evaluation cost. The first algorithm, DP-BF, combines a best first strategy with a dynamic-programming technique. The second one, PT-SAM, adapts a Petri-net unfolding algorithm and tries to find a desired marking from an initial state. An experimental study was conducted in order to evaluate the behavior of DP-BF and PT-SAM compared to SAM and to the exhaustive solution. The experiments show that the quality of the compositions identified by the presented algorithms is close to the optimal solution produced by the exhaustive algorithm, while the optimization time is close to the time required by SAM to identify a solution.