Research On Multi-workflow Scheduling Model And Algorithms In Distributed Environment

Workflow scheduling is a key component of the distributed computing platform scheduling strategy,which not only affects the user experience,but also affects the operating cost of the platform.Workflow scheduling has been proved to be an NP-hard problem.The existing research can be divided into two types: single workflow scheduling algorithm and multi-workflow scheduling algorithm.Multi-workflow scheduling algorithm can schedule multiple workflows at the same time,which has higher efficiency and can improve the resource utilization of the platform.Existing multi-workflow scheduling algorithms often seek a balance between the efficiency of the algorithm and the optimality of the scheduling strategy.For multi-workflow scheduling scenes with high real-time requirements,there is a lack of a fast and efficient scheduling algorithm that has a scheduling strategy that is close to the optimal solution.However,for multi-workflow scheduling scenes that require short workflows completion time,there is no algorithm that can obtain the global optimal scheduling strategy.In view of this,the thesis takes the total scheduling time as the goal,study the multi-workflow scheduling model in a heterogeneous distributed environment,and propose two algorithms solution models for these two special scenes to obtain multiworkflow scheduling strategies.The research results of this thesis are as follows:1.This thesis study an efficient multi-workflow scheduling model and algorithm for the scenes with high real-time requirements.First of all,this thesis take the task completion time as the optimization goal and establish a multi-workflow scheduling model in the distributed environment.Secondly,according to different business requirements,the average computation time,average communication time,critical path value,horizontal division level and random value are used as the priority of the workflows,and the workflows are sorted according to the priority.Then,sorting all the subtasks of the workflow by the turntable method.Finally,the insertion method is used to allocate the optimal processor resources for each task.Experiments show that the algorithm proposed in this paper can quickly obtain a satisfactory multi-workflow scheduling scheme in a short time,and the algorithm has high real-time performance,which makes this algorithm feasible for processing large-scale workflows in a heterogeneous environment.2.This thesis propose a hybrid genetic algorithm to obtain the global optimal workflow scheduling strategy,including task scheduling sequence and resource allocation strategy for the workflow scheduling scenes with high task completion time.First,an efficient encoding method is designed according to the characteristics of the multi-workflow scheduling problem,which can effectively reduce the complexity of the operation operators.Secondly,the heuristic algorithm proposed above is used to generate some individuals in the initial population to improve the quality of the solution in the initial population and speed up the convergence speed of the algorithm.Then,a load balancing operator is designed to iteratively adjust the task allocation on the fastest processor and other processors to achieve the purpose of load balancing.Finally,simulation experiments show that the proposed algorithm has strong search ability and can converge to the global optimal solution of the problem,that is,obtain the optimal workflow scheduling scheme to make the total task completion time shortest.