The problem of selecting services from a set of functionally appropriate ones under Quality of Service constraints - the Service Selection Problem - is well-recognized in the literature based on deterministic parameters. However, Quality of Service may rather follow a stochastic distribution and, thus, may change at runtime. In order to cope with differing Quality of Service, we present a heuristic approach for efficiently addressing the Service Selection Problem in conjunction with stochastic Quality of Service attributes. Accounting for penalty cost which accrue due to Quality of Service violations, our approach reduces the impact of stochastic Quality of Service behavior on total cost significantly.
