Composition of Internet-based services exported by different organizations has quickly become a key software paradigm for engineering and scientific communities. Although the scheduling of composite service invocations in such a multi-organization, multi-tiered and geographically dispersed environment may have strong impact on performance, this issue has not been explored very much so far. In this work we study the performance of the composite service and we take the perspective of the organizations involved in its implementation. We focus on the trade-off between the performance of the composite service and the global cost incurred at the participating organizations. We seek techniques for executing a given workload by minimizing such cost, while maintaining the performance delivered to clients to an acceptable level.