Research On Cloud Workflow Scheduling Algorithm Based On Evolutionary Multi-objective Optimization

As the latest distributed system model,cloud computing provides easy access,flexible and scalable hardware and software services,which no longer makes users waste too much money and time for the management of the underlying hardware and software.Users would only focus on their problem solving process.C loud computing satisfies the needs of the users greatly by prvoiding tremendous computing and storage resources.Workflow provides a simple and effective way to represent the complex problems.Workflow takes full advantage of the cloud computing environment whose computing resources are distributed in different geographical locations.In order to solve the complex problems,more and more users start to deploy and run their tasks in the cloud computing environment.In the cloud computing environment,how to allocate the appropriate computing resources to each workflow task effectively is the cloud service providers' main concern.Besides the traditional scheduling method only consider the single objective,such as minimizing the run time or minimize the operating costs.This kind of traditional scheduling method is no longer applicable to the cloud environment,due to the characteristic of pay as you go model in the cloud environment.Users are always eager to get better service quality while spending less money.For cloud service providers,market-oriented cloud computing also makes it a must to consider the user's such needs.In order to provide a better and more competitive service,the problem of cloud workflow scheduling based on multi-objective optimization is becoming more and more important for the cloud service providers.The main work of this thesis is as follows:(1)Analyze the conflicting relationships of cloud workflow scheduling problem's objectives.The choosing of conflicting objectives is the basis of multi-objective optimization.The existing multi-objective optimization of cloud workflow scheduling has certain subjectivity when choosing the optimization objectives.The conflicting relationships between their choosing objectives are unknown.If the choosing objectives have strong correlation,it will affect the scheduling algorithm's results greatly.Based on the research of existing literature on cloud workflow scheduling,this thesis draws out six commonly used cloud workflow scheduling objectives,and conducts the conflict analysis of the six objectives.The conflict analysis 's results can be used to guide the objective selection of cloud workflow scheduling based on multi-objective optimization.The cloud workflow scheduling problem is a typical NP hard proble m,their decision space is at exponential level.Because the orthogonal experiment design can get uniform and representative decision samples,this thesis uses it to sample the decison space.This thesis evaluates these samples' objectives based on the clo ud workflow scheduling model.In order to evaluate the non-linear conflict relationships between these objectives,we use a non-linear conflict indicator to analyze the conflict relationships between the six objectives.Based on the results of analysis,two cloud workflow scheduling models are established,one is to optimize time and execution cost and the other is to optimize time and data transfer cost.(2)Propose an algorithm which is based on weight adjustment strategy and local search strategy in the MOEA/D(Multiobjective Evolutionary Algorithm Based on Decomposition)algorithm framework,and apply the algorithm to solve the established cloud workflow scheduling models.When solving the multi-objective optimization problem,we always want to obtain a set of Pareto solutions with uniform distribution in the objective space.The original MOEA/D can only obtain solutions with uniform distribution for the problem with the regular hyperplane Pareto front.If this hypothesis is not true,the obtained solutions will not distribute uniformly.The fact is that most existed real multi-objective optimization problem's Pareto front is complex.Based on the analysis of MOEA/D,this thesis adopts a strategy of weight adjustment which can obtain a more uniform solutio n for the complex Pareto front problem.Besides we also hope to speed up the convergence of problem solving process.In our algorithm,the local search is used to achieve this.Based on the two strategy,this thesis proposes the improved MOEA/D algorithm which is based on weight adjustment and local search.This thesis uses the proposed algorithm to solve the two cloud workflow scheduling models,compared with MOEA/D algorithm and NSGA-II algorithm,this thesis' s algorithm can obtain a more uniform distributed solutions while getting a faster convergence speed.Thus the proposed algorithm can provide a set of better decision supports for cloud workflow scheduling problem.