As Grids become larger, more open and dynamic in nature, it will inevitably become necessary to deal with service failures and mitigate uncertainty in the execution of large service workflows. To this end, we propose a decision-theoretic approach to the provisioning problem (i.e., selecting service instances for the tasks of an abstract workflow). Our approach introduces redundancy into workflows to reduce the probability of failures, it dynamically re-provisions failed services and it negotiates advance agreements with providers when this is beneficial.