For improved flexibility and concurrent usage existing transaction management models for Web services relax the isolation property of Web service-based transactions. Correctness of the concurrent execution then has to be ensured by commit order-preserving transaction schedulers. However, local schedulers of service providers typically do take into account neither time constraints for committing the whole transaction, nor the individual services' constraints when scheduling decisions are made. This often leads to an unnecessary blocking of transactions by (possibly long-running) others. In this paper, we propose a novel nonblocking scheduling mechanism that is used prior to the actual service invocations. Its aim is to reach an agreement between the client and all participating providers on what transaction processing times have to be expected, accepted, and guaranteed. This enables service consumers to find a set of best suited providers fitting their deadlines. Service providers on the other hand can benefit from the proposed mechanism due to the now possible intelligent scheduling of service invocations for best throughput. In fact, our experiments show a significant improvement in terms of overall throughput, service chain completions and resources' utilization.