Randomized approximation scheme for resource allocation in hybrid-cloud environment

Using the virtually unlimited resource capacity of public cloud, dynamic scaling out of large-scale applications is facilitated. A critical question arises practically here is how to run such applications effectively in terms of both cost and performance. In this paper, we explore how resources in the hybrid-cloud environment should be used to run Bag-of-Tasks applications. Having introduced a simple yet effective objective function, our algorithm helps the user to make a better decision for realization of his/her goal. Then, we cope with the problem in two different cases of “known” and “unknown” running time of available tasks. A solution to approximate the optimal value of user’s objective function will be provided for each case. Specifically, a fully polynomial-time randomized approximation scheme based on a Monte Carlo sampling method will be presented in case of unknown running time. The experimental results confirm that our algorithm approximates the optimal solution with a little scheduling overhead.