TY - JOUR
T1 - Clustering-assisted gradient-based optimizer for scheduling parallel cloud workflows with budget constraints
AU - Li, Huifang
AU - Chen, Boyuan
AU - Huang, Jingwei
AU - Song, Zhuoyue
AU - Xia, Yuanqing
N1 - Publisher Copyright:
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2024.
PY - 2024/8
Y1 - 2024/8
N2 - Cloud computing has gradually become one of the most popular platforms for executing scientific applications due to its elastic and on-demand resource provisional capabilities. But, how to effectively schedule a set of parallel workflows to minimize the makespan under their individual budget constraints remains a critical problem. This work proposes a Clustering-assisted Gradient-Based Optimizer (C-GBO) to improve the performance for scheduling workflows in cloud environments. First, it designs a novel individual encoding mechanism including task-VM mapping and task-priority sub-strings to further optimize the makespan by updating both sub-strings simultaneously, especially each element representing task execution order in a task-priority sub-string can take any values within the pre-specified range but not subject to control dependencies among tasks. Second, to address the original GBO’s easiness of falling into local optima brought by its only one best guiding solution, it divides individuals into different groups as their position information by the K-means algorithm and selects the best guiding solution for each group with 50% probability from their own clusters locally, such that the search diversity is improved and the cross evolution is reduced. Third, a Gaussian disturbance-based elite enhancement strategy is developed by introducing a Gaussian disturbance operation to a certain number of each elite individual so as to fully exploit these individuals and increase the quality of the global best solution. Our proposed C-GBO algorithm is testified and compared with six peers on datasets with different scales through WorkflowSim. The results demonstrate that our proposed C-GBO achieves the best results in all the involved algorithms, i.e., obtaining the success rate of 100% on all datasets, and performs better in the average makespan that is at most 88.47% shorter than its peers in most cases.
AB - Cloud computing has gradually become one of the most popular platforms for executing scientific applications due to its elastic and on-demand resource provisional capabilities. But, how to effectively schedule a set of parallel workflows to minimize the makespan under their individual budget constraints remains a critical problem. This work proposes a Clustering-assisted Gradient-Based Optimizer (C-GBO) to improve the performance for scheduling workflows in cloud environments. First, it designs a novel individual encoding mechanism including task-VM mapping and task-priority sub-strings to further optimize the makespan by updating both sub-strings simultaneously, especially each element representing task execution order in a task-priority sub-string can take any values within the pre-specified range but not subject to control dependencies among tasks. Second, to address the original GBO’s easiness of falling into local optima brought by its only one best guiding solution, it divides individuals into different groups as their position information by the K-means algorithm and selects the best guiding solution for each group with 50% probability from their own clusters locally, such that the search diversity is improved and the cross evolution is reduced. Third, a Gaussian disturbance-based elite enhancement strategy is developed by introducing a Gaussian disturbance operation to a certain number of each elite individual so as to fully exploit these individuals and increase the quality of the global best solution. Our proposed C-GBO algorithm is testified and compared with six peers on datasets with different scales through WorkflowSim. The results demonstrate that our proposed C-GBO achieves the best results in all the involved algorithms, i.e., obtaining the success rate of 100% on all datasets, and performs better in the average makespan that is at most 88.47% shorter than its peers in most cases.
KW - Cloud computing
KW - Gradient-based optimizer
KW - Meta-heuristics
KW - Scheduling
KW - Workflow
UR - http://www.scopus.com/inward/record.url?scp=85191060986&partnerID=8YFLogxK
U2 - 10.1007/s11227-024-06114-9
DO - 10.1007/s11227-024-06114-9
M3 - Article
AN - SCOPUS:85191060986
SN - 0920-8542
VL - 80
SP - 17097
EP - 17134
JO - Journal of Supercomputing
JF - Journal of Supercomputing
IS - 12
ER -