As Grids become larger and more interconnected in nature, scientists can benefit from a growing number of distributed services that may be invoked on demand to complete complex computational workflows. However, it also means that these scientists become dependent on the cooperation of third-party service providers, whose behaviour may be uncertain, failure-prone and highly heterogeneous. To address this, we have developed a novel decision-theoretic algorithm that automatically selects appropriate services for the tasks of an abstract workflow and deals with failures through redundancy and dynamic re-invocation of functionally equivalent services. In this article, we summarise our approach, describe in detail how it can be applied to a real-world bioinformatics workflow and show that it offers a significant improvement over current service selection techniques.