Service Composition (SC) is an important problem in the Cloud Manufacturing (CM) paradigm in which, after receiving customers’ requests, a composition of cloud services is determined for accomplishment of their needs. Actually, a customer’ s need is decomposed to some distinct tasks such that a manufacturing resource or a group of them can perform each task. The ultimate goal of SC is optimal assignment of tasks to resources while specific objective function(s) and constraint(s) are considered. In this paper, as the main contribution, an Integer Programming (IP) model of service composition problem is presented which includes transportation between manufacturing resources scattered over the globe. Then, two different scenarios of SC problem are generated such that each center of Iran's provinces includes a resource which can perform some pre-determined tasks. In addition, distance of center of Iran's provinces as well as transportation time between them are estimated based on real data. In order to solve the mentioned scenarios, Branch and Bound (B&B) exact algorithm is used. Furthermore, before developing a metaheuristic algorithm for implementation in service composition problem, landscape analysis of the problem is completed. Based on the results of this analysis, the problem has a random uniform nature and its local optima are scattered over the search space. As a result, simple singlesolution based algorithms such as Local Search (LS) heuristic can be efficient in SC problem solving. Results of comparison between B&B and LS algorithms indicate superiority of LS in finding optimum or near-optimum solution with lower computational cost.