Scheduling scientific workflows on virtual machines using a Pareto and hypervolume based black hole optimization algorit
- PDF / 3,298,021 Bytes
- 54 Pages / 439.37 x 666.142 pts Page_size
- 39 Downloads / 193 Views
Scheduling scientific workflows on virtual machines using a Pareto and hypervolume based black hole optimization algorithm Fatemeh Ebadifard1 · Seyed Morteza Babamir1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract 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 θ -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 Abstract 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 Abstract 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.
B 1
Seyed Morteza Babamir [email protected] Department of Computer Engineering, University of Kashan, Kashan, Iran
123
F. Ebadifard, S. M. Babamir
Keywords Workflow scheduling · Multiobjective optimization · Pareto front · Hypervolume · Black hole algorithm
1 Introduction Scientific applications have huge workflows consisting of many tasks, which is represented as Directed Acyclic Graphs (see Sect. 3.2). When all of the tasks were executed, the final result is provided for the user. The main user’s concern is minimizing the response time of reaching the final result, which is equal to the makespan (completion time) (see Sect. 3.2.A) of the workflow. The makespan
Data Loading...
