Study On Efficient Multi-workflow Scheduling Algorithm Based On Genetic Algorithm

With its "elastic distribution,on-demand use" feature,cloud computing is attracting more and more users to deploy applications(workflows)on the cloud platform.The workflow scheduling strategy is not only related to the user experience,but also has a great impact on the cloud provider's operating costs.Therefore,how to efficiently and reasonably schedule workflows is one of the key technical issues to be solved urgently.The existing literature has proposed many single-objective or multi-objective optimization algorithms to solve the workflow scheduling problem,but most of these algorithms are derived from the scheduling algorithms in the traditional heterogeneous environment.These algorithms assume that the execution time of tasks and the transmission time between tasks can be accurately obtained before the workflow is scheduled.However,in a cloud environment with uncertainty,the pre-scheduling schemes generated by these algorithms often lose their original advantages or cannot be implemented smoothly.In view of the shortcomings of the existing scheduling algorithms,the main contents of this thesis are as follows:(1)A multi-workflow scheduling model based on uncertainty in the cloud environment is proposed.In this model,the virtual machine is allocated to a task only when the task becomes ready,which effectively controls the number of waiting tasks on the virtual machine.Moreover,when a task is completed,the completion time of the task is available,which means that the uncertainty of the task will disappear,and the subsequent waiting tasks on the same virtual machine will not be affected.(2)A multi-workflow genetic scheduling algorithm based on deadline in the cloud environment is proposed.The workflow submitted by users to the cloud platform has a deadline limit,the competition of multi-workflow resources is likely to lead to the failure of workflow execution due to the preemption of resources in the process of executing tasks.In this thesis,on the premise of ensuring workflow deadline,Pareto thought of using the NSGA-II algorithm is introduced to minimize the economic cost and to maximize resource utilization.In addition,heuristic methods and random methods are used to jointly initialize the population and improve the search ability of NSGA-II.A new crossover and mutation operation have been designed for individual effectiveness.The simulation experiment proves that the scheduling model can effectively mitigate the uncertainty propagation,and validates the multi-workflow scheduling algorithm based on NSGA-? is better than the existing scheduling algorithm from three aspects of the deadline,the workflow arrival rate and uncertain parameters.