Many workflow applications have time constraints. The serving time of the servers and the arrival intervals of users' service requests in a workflow are often stochastic. From the statistic angle, we can fmd a tiny proportion of service requests will be executed beyond the deadline in any case. Thus people can only require an acceptable proportion of service requests to be finished within the deadline normally. We try to determine its probability density function at a workflow network so that we will know the accurate proportion of requests that can be executed without delay. We also present a method to improve the proportion of the undelayed with the lowest additional cost. An experiment illustrates our method can be effectively utilized in practice.