Abstract: The execution time of web services composition that is described by business process execution language for web service(BPEL2WS) is analyzed.An algorithm is presented to solve the probability density function(PDF) of web services composition by the PDF of each service and the structure of BPEL2WS model when the execution time of each service is stochastically distributed.The probability can be obtained under which the business process can be finished before any given deadline by the PDF,therefore the service composition can be optimized to minimize the execution cost based on the given probability condition.Finally an example shows that the proposed method can be applied to practice effectively.