Scheduling scientific workflows on virtual machines using a Pareto and hypervolume based black hole optimization algorithm

摘要

The problem of workflow scheduling on virtual machines in a cloud environment is to find the near optimal permutation of the assignment of independent computational jobs on a set of machines that satisfies conflicting objectives. This problem is known to be an NP-hard problem. Evolutionary multiobjective algorithms are optimization methods to solve such problems. hypervolume is one of the most important criteria that is used to both as solution evaluation and as a guidance for near-optimal selection of a set of solutions called the Pareto front. In this paper, a new hypervolume-based multiobjective algorithm is proposed for driving the Pareto front. To this end, we extend the single-objective Black hole heuristic algorithm based on the adopted theta dominance relation to improving the diversity and convergence to an optimal Pareto front. The conflicting objectives are resource utilization, resource cost, and the workflow makespan (completion time). Also to presenting the appropriate scheduling algorithm, we have proven the correctness of the proposed algorithm by providing the behavioral model of the suggested system using model checking tool. For this purpose, we first introduce the behavioral model of the proposed system using state machine and extract the properties of the algorithm in the form of linear temporal logic. Then we encode the algorithm using the model checker tool state Machine Meta-model-based Language and verify the accuracy of the algorithm based on the expected properties, reachability, fairness, and deadlock-free. In order to demonstrate the effectiveness of our method we: (1) extended the WorkflowSim tools, (2) applied it to both balanced and imbalanced workflows and (3) compared results to algorithms, Strength Pareto Evolutionary Algorithm-2, Non-dominated Sorting Genetic Algorithm-2, Multi-Swarm MultiObjective Optimization, Intelligent Water Drops algorithm and Genetic Algorithm and Pareto-based Grey Wolf Optimizer. The comparisons show that by increasing the number of users requests and their correlations, the proposed algorithm can find more optimal Pareto front.