Cloud computing provides services to potentially numerous remote users with diverse requirements. Al-
though predictable performance can be obtained through the provision of carefully delimited services,
it is straightforward to identify applications in which a cloud might usefully host services that support
the composition of more primitive analysis services or the evaluation of complex data analysis requests.
In such settings, a service provider must manage complex and unpredictable workloads. This paper
describes how utility functions can be used to make explicit the desirability of different workload evalu-
ation strategies, and how optimization can be used to select between such alternatives. The approach is
illustrated for workloads consisting of workflows or queries.