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

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 methodstosolvesuchproblems.hypervolumeisoneofthemostimportantcriteriathat 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 mul- tiobjective algorithm is proposed for driving the Pareto front. To this end, we extend thesingle-objective Blackholeheuristicalgorithmbasedontheadopted θ-dominance relationtoimprovingthediversityandconvergencetoanoptimalParetofront.Thecon- flicting objectives are resource utilization, resource cost, and the workflow makespan (completion time). Also to presenting the appropriate scheduling algorithm, we have proventhecorrectnessoftheproposedalgorithmbyprovidingthebehavioralmodelof 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 thealgorithmusingthemodelchecker toolAbstractstateMachine 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 ourmethodwe:(1)extendedtheWorkflowSimtools,(2)appliedittobothbalancedand imbalanced workflows and (3) compared results to algorithms, Strength Pareto Evo- lutionary Algorithm-2, Non-dominated Sorting Genetic Algorithm-2, Multi-Swarm MultiObjective Optimization, Intelligent Water Drops algorithm and Genetic Algo- rithmandPareto-basedGreyWolfOptimizer.Thecomparisonsshowthatbyincreasing the number of users requests and their correlations, the proposed algorithm can find more optimal Pareto front.