QoS support to ensure timeliness of results is a key requirement for applications that rely on Grid services for computationally demanding tasks. In this paper we present a generic Grid infrastructure based on standard Web Services which provides flexible application-level QoS support, addressing the special requirements of time-critical Grid applications. We describe the provision of parallel applications as QoS-aware Grid services, which are capable of dynamically negotiating with clients QoS guarantees for response time and price in the form of Web Service Level Agreements. The presented techniques have been implemented within the Vienna Grid Environment and utilized in the context of the EU project GEMSS for the development of Grid-enabled medical simulation services.