Given a Web Services Composition, we deal with the prediction of the mean service response time that can be expected from a user request that is serviced. This challenge is a key issue in the design of middleware, managing Web Services Composition. We focus on complex services composition that can be described as BPMN choreographies of services. Our main contribution is a mathematical programming based approach for the prediction of the response time of Web Services Compositions. This new approach occurs through the automatic generation of a linear program whose number of variables and constraints is polynomial in the number of elements used to represent the Service Composition. The equations of the linear program are based on well known aggregation rules for service composition and a new modeling that we introduced for handling communication within Web Services.