This paper presents an optimization model for service orchestration in multi-cloud environments. The objective is to minimize the total cost of deploying a set of services over multiple clouds while ensuring that the Quality of Service (QoS) requirements are met. The proposed model considers the heterogeneity of cloud resources and the interdependence among the services. A case study is presented to demonstrate the effectiveness of the proposed approach. The results show that the proposed model can achieve significant cost savings while satisfying QoS requirements. The execution time of the algorithm is also analyzed, and it is found that it increases with the number of network elements. This study provides a framework for efficient service orchestration in multi-cloud environments, which can be extended to include additional constraints and objectives. The findings of this study are promising for practical applications for cloud service providers and users, who can benefit from the proposed optimization algorithm to achieve cost-effective service orchestration while meeting QoS requirements.