As Web Services proliferate, it becomes more difficult to find a service that can perform a given task, and a coordination of several services may be required. We present two algorithms to identify orderings of Web Service compositions. These algorithms follow different strategies to prune the space of possibilities while minimizing the evaluation cost. The first one, DP-BF, combines a best first strategy with a dynamic-programming technique and produces good Web Service compositions by exploring a small portion of the search space. The second one, PT-SAM, adapts a petri-net unfolding algorithm and tries to find a desired marking from an initial state. We conducted an experimental study to evaluate the behavior of DP-BFand PT-SAMcompared to SAM and to the exhaustive solution. Our experiments show that the quality of the compositions identified by our algorithms are 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. © 2008 IEEE.