A stochastic algorithm for scheduling bag-of-tasks applications on hybrid clouds under task duration variations

Hybrid cloud computing, which typically involves a hybrid architecture of public and private clouds, is an ideal platform for executing bag-of-tasks (BoT) applications. Most existing BoT scheduling algorithms ignore the uncertainty of task execution times in practical scenarios and schedule tasks by assuming that the task durations can be determined accurately in advance, often leading to the violation of the deadline constraint. In view of this fact, this paper devotes to maximizing the profit of the private cloud provider while guaranteeing the quality-of-service provided by the cloud platform, through designing an effective stochastic BoT scheduling algorithm based on the distribution of task duration variations. With the varying task execution times modeled as random variables, we formulate a stochastic scheduling framework that incorporates a probabilistic constraint upon the makespans of BoT applications. The resultant stochastic optimization model is capable of characterizing the complete distribution information of makespan variations and satisfying the deadline constraint in a probabilistic sense. We further design an immune algorithm-based metaheuristic to solve this stochastic optimization problem. Simulations results justify that our proposed algorithm outperforms several competing algorithms in maximizing the cloud provider's profit while satisfying the user-specified deadline constraint under the impact of uncertain task durations. (c) 2021 Elsevier Inc. All rights reserved.

Automated summary

This paper presents a stochastic BoT scheduling algorithm based on the distribution of task duration variations. The algorithm aims to maximize the profit of the cloud provider while guaranteeing quality of service. By modeling task execution times as random variables and using a stochastic optimization model and an immune algorithm-based metaheuristic, the proposed algorithm outperforms competing algorithms in terms of profit maximization and meeting the user-specified deadline constraint.