Semantic Web services allow applications to automatically discover and provision distributed services at runtime. However, when such services are offered by autonomous providers, as is common in large distributed systems, their behaviour is inherently non-deterministic and unreliable. To address this problem, we describe an OWL-S extension that allows services to be annotated with quantitative performance measures, and outline a flexible, decision-theoretic algorithm that uses this knowledge to provision services as part of complex workflows.