In this paper we propose a solution for optimizing (web service) business workflow response times through dynamic resource allocation. On-the-fly monitoring is combined with a novel workflow modeling algorithm that discovers critical execution paths and builds "dynamic" stochastic models in the associated "critical graph." One novel contribution of this work is the ability to naturally handle parallel workflow execution paths. This is essential in applications where workflows include multiple concurrent service calls/paths that need to be "joined" at a later point in time. We discuss the automatic deployment of on-the-fly monitoring mechanisms within the resource management mechanisms. We implement, deploy and experiment with a proof of concept within a generalized web services business process (BPEL4WS/SOAP) framework. In the experimental setup we explore and show the natural adaptation to changing workflow conditions and appropriate automatic re-allocation of resources to reduce execution times.