The on-demand provisioning of services, a cloud-based extension for traditional service-oriented architectures, improves the handling of services in usage scenarios where they are only used rarely and irregularly. However, the standard process of service provisioning and de-provisioning shows still some shortcomings when applying it in real world. In this paper, we introduce a middleware-centric optimization approach that can be integrated in the existing on-demand provisioning middleware in a loosely coupled manner, changing the standard provisioning and de-provisioning behavior in order to improve it with respect to cost and time. We define and implement a set of optimization strategies, evaluate them based on a real world use case from the eScience domain and provide qualitative as well as quantitative decision support for effectively selecting and parametrizing a suitable strategy. Altogether, our work improves the applicability of the existing on-demand provisioning approach and system in real world, including guidance for selecting the suitable optimization strategy for specific use cases.