Workflows often operate in volatile environments in which the component services? QoS changes frequently. Optimally adapting to these changes becomes an important problem that must be addressed by the Web service composition and execution (WSCE) system being utilized. We adopt the A-WSCE framework that utilizes a three-stage approach for composing and executing Web workflows. The A-WSCE framework offers a way to adapt by defining multiple workflows and switching among them in case of component failure or changes in the QoS parameters. However, the A-WSCE framework suffers from the limitations imposed by a simple strategy of periodically checking the QoS offerings of randomly picked providers in order to decide whether the current workflow is optimal. To address these limitations, we associate the value of changed information (VOC) with each workflow and utilize the VOC to update which workflow to execute. We empirically demonstrate the improved performance of the workflows selected using the new approach in comparison to the original framework.