Clustering-assisted gradient-based optimizer for scheduling parallel cloud workflows with budget constraints

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.