Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm

摘要

Purpose: The objective of this study is to optimize task scheduling and resource allocation using an improved differential evolution algorithm (IDEA) based on the proposed cost and time models on cloud computing environment. Methods: The proposed IDEA combines the Taguchi method and a differential evolution algorithm (DEA). The DEA has a powerful global exploration capability on macro-space and uses fewer control parameters. The systematic reasoning ability of the Taguchi method is used to exploit the better individuals on microspace to be potential offspring. Therefore, the proposed IDEA is well enhanced and balanced on exploration and exploitation. The proposed cost model includes the processing and receiving cost. In addition, the time model incorporates receiving, processing, and waiting time. The multi-objective optimization approach, which is the non-dominated sorting technique, not with normalized single-objective method, is applied to find the Pareto front of total cost and makespan. Results: In the five-task five-resource problem, the mean coverage ratios C(IDEA, DEA) of 0.368 and C (IDEA, NSGA-Ⅱ) of 0.3 are superior to the ratios C(DEA, IDEA) of 0.249 and C(NSGA-Ⅱ, IDEA) of 0.288, respectively. In the ten-task ten-resource problem, the mean coverage ratios C(IDEA, DEA) of 0.506 and C (IDEA, NSGA-Ⅱ) of 0.701 are superior to the ratios C(DEA, IDEA) of 0.286 and C(NSGA-Ⅱ, IDEA) of 0.052, respectively. Wilcoxon matched-pairs signed-rank test confirms there is a significant difference between IDEA and the other methods. In summary, the above experimental results confirm that the IDEA outperforms both the DEA and NSGA-Ⅱ in finding the better Pareto-optimal solutions. Conclusions: In the study, the IDEA shows its effectiveness to optimize task scheduling and resource allocation compared with both the DEA and the NSGA-Ⅱ. Moreover, for decision makers, the Gantt charts of task scheduling in terms of having smaller makespan, cost, and both can be selected to make their decision when conflicting objectives are present.