Studies Of The Scientific Workflow Scheduling Problem On Public Cloud Environment

The public cloud offers users a pool of resources, such as virtual machines(VMs)with different performance, networks with varied bandwidth, and several sizes of storage. Scientific workflow is a series of computing tasks and it is used to accomplish some scientific goals. Scientific workflow has been adopted in astronomy, physics, earth science, neuroscience etc.. The goal of workflow scheduling problem is to generate optimal scheduling strategies by assigning computing tasks to pre-leased VMs.The problem is always modeled as an optimization problem. Many single- or multi-objective algorithms have been proposed to solve workflow scheduling problem. However, the degree of conflicts among objective functions has never been discussed. In this thesis, we use Pearson correlation coefficients to measure the degree of conflicts among objective functions.Then we propose an algorithm called ONAGAII( Orthogonal Non-dominated Sorting Genetic Algorithm II), based on NSGAII(Non-dominated Sorting Genetic Algorithm II)and Orthogonal Design(OD) approach, to solve the workflow scheduling problem.Based on the background and problem description, first, we survey all researches aiming at solving the scientific workflow scheduling problem since cloud computing concept was introduced in 2007. Six objective functions are summarized, namely execution time, monetary cost, the number of virtual machines, resource utilization, computation cost, data transfer cost. Some researchers are listed in this thesis, consisting of 9 singleobjective optimization researches and 10 multi-objective optimization researches. Then we mathematically model the scientific workflow scheduling problem. Workflow model,system model and objective functions model are formulated. Specifically, the computation method of all six objective functions are formulated.Then we mathematically analyze the correlation between objective functions by calculating the Pearson correlation coefficients. Orthogonal design method is used to reduce the size of solution space during the analysis. We describe the experimental results with heatmaps. In the figures, darker the cube is, more negative-correlated the two functions are, otherwise, more white the cube is. We analyze the correlation on 11 realistic scientific workflows, the results show that execution time and monetary cost are negative-correlated most.At last, a multi-objective optimization algorithm called ONSGAII is proposed to solve the scientific workflow scheduling problem. The algorithm is based on NSGAII algorithm and Orthogonal design method, and improves the initialization procedure and crossover operator. In the initialization procedure, to avoid the narrow distribution of solutions, we use Orthogonal design method to construct initial population, in order to make the initial population distributes evenly and widely.We execute our algorithm on 11 realistic scientific workflows and make comparisons between our ONSGAII algorithm and other similar algorithms. Similar algorithms include three meta-heuristic algorithms(NAGAII, GA and PSO) and two constructive algorithms(HEFT, Min-min). The experiment results show that our algorithm is more efficient and can achieve better scheduling solutions.