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

2022 
Abstract 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.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    59
    References
    0
    Citations
    NaN
    KQI
    []