Service compositions define how serveral Web services (loosely coupled platform independent software components exposed on the Web with interfaces, operations and associated data types) can be put together to achieve a more complex processing task, which can be both long and cross-organizational.

Quality of Service (QoS) properties of a service composition, such as running time, are an important part of service usability for the end user. We discuss how to turn a formal service description based on discrete state transitions (in particular, a strand of Petri Nets) into a continuous time model that can be used to approximate running time of the composition, as well as time-varying utilization of the composition components. Such a model can be used for modeling different policies that the service provider may use.