Today, workflows are widely used to model business processes. A recent trend is to use them to model applications in heterogeneous, large-scale distributed systems. In such systems, many, possibly mobile, providers offer independent and interchangeable services that can be used to satisfy the different activities of a workflow. Due to varying server loads, failures, and changing network characteristics, the response time of these services is highly volatile. Thus, it is hard to ensure the timely and reliable execution of workflows depending on such services. A common approach is to invoke several services in parallel to increase the probability of success. This, however, can easily lead to overprovisioning and high cost when needlessly invoked services have to be compensated. In this paper, we investigate the search space between parallel and sequential invocation of services. We propose to invoke independent services staggered over time to ensure timely workflow execution at minimal cost. Evaluations show that our approach reduces the execution cost by up to 85 % while it guarantees to fulfill activity deadlines with 99.9 % probability.