In this paper, we present the Vienna Grid Environment, a service-oriented Grid infrastructure based on standard Web Services technologies. VGE automates the provision of HPC applications as Grid services for on-demand supercomputing and simplifies the construction of client-side applications. As a key distinguishing feature, VGE supports a flexible QoS negotiation model which enables clients to negotiate dynamically, and on a case-by-case basis, QoS guarantees on execution time and price with potential service providers. The VGE service provision framework is currently utilized in the context of the EU Project GEMSS, which focuses on the provision of advanced medical simulation services by means of a Grid infrastructure.