In today?s businesses we can see the trend that serviceoriented architectures (SOA) represent the main paradigm for IT infrastructures. In this setting, a software offers its functionality as an electronic service to other software in a network. In order to realise more complex tasks or business processes that are comprised of individual services, compositions of these are formed.

For specific application cases such as the timedependent trading of goods or the IT-based management of natural disasters, service compositions are anticipated to provide soft real-time characteristics. Soft real-time characteristics for service compositions involve the QoS-based trading of services as well as a real-time conforming trading process that is capable of optimising the QoS in predictable and feasible amount of time. This paper will discuss the two aspects and introduce two heuristics for the QoS-aware trading that show feasible computational efforts. Based on a software simulation, the performance of these algorithms is discussed.