Performance evaluation and execution managementof service-oriented workflows became quite important inorder to avoid performance degradation. Performance measurement is crucial to ensure that workflow execution remains feasible and that SLA violations due to overload are avoided.Network calculus as a well-known system theory for deterministic queuing systems can be used to describe the worst-case performance behavior of a workflow in order to plan workflow control in advance.Concerning business processes with high repetition rates theworkflow controller has to be able to serve all incoming requests with an optimal composition of Web services. Thus, this paper presents a formal worst-case calculation model using the concepts of network calculus. Furthermore, optimization problems based on the worst-case scenario are introduced in order to minimize the worst-case delay and to maximize the throughput of the Web services invoked with minimal costs.