Scheduling for multi-stage applications with scalable virtual resources in cloud computing

Nowadays multi-stage computing applications are widespread and they are suitable for being executed in cloud platforms, where virtual resources are provisioned on-demand. By specific rules, virtual resources are automatically scaled out/in according to workloads. In this paper, we model processes of multi-stage computing applications on scalable resources as hybrid flowshop scheduling with deadline constraints. The objective is to minimize the number of scaled-out virtual machines. For the NP-hard problem under study, which has not been explored yet, we propose two greedy methods SNG and SENG. Based on benchmark instances, the performance of the two methods are evaluated and compared. For small-size, medium-size and large-size instances, SENG can averagely save up to 38.99, 33.04 and 29.98 % of VMs, respectively. While SNG can averagely save up to 24.5, 25.38 and 28.87 %, respectively. The CPU time consumed by SENG is averagely one time more than that of SNG.