Research On Makespan And Cost Of Scheduling Workflow In Heterogeneous Distributed Computing System

As a high-performance computing platform,heterogeneous distributed computing systems provide strong technical support for scientific computing,engineering applications and many other fields.Workflow scheduling as a common execution object in heterogeneous distributed computing system,the quality of its scheduling strategy directly acts the efficiency of scheduling and resource utilization,etc.Therefore,how to develop an efficient scheduling strategy for workflows is a very important research content.In this paper,the following researches are carried out on the optimization of workflow time and the optimization of workflow time and cost in heterogeneous distributed computing.(1)An improved list heuristic scheduling algorithm called LOEFT(Level & Out-degree Earliest Finish Time,LOEFT)algorithm is proposed for minimizing workflow execution time in heterogeneous computing environment.LOEFT algorithm has three major phases: task leveling,task prioritization,and processor selection.In the task leveling phase,tasks are assigned to different levels based on depth value to ensure scheduling security ensure data transmission completeness while maximize the concurrency of tasks at the same level.In the task prioritizing phase,the upward rank value is combined with the out-degree of every task to calculate the heterogeneous priority rank value on different processors and leverage the value to sort all tasks.In order to finely control the scheduling differences caused by the heterogeneity of system.In the processor selection phase,the selected task is assigned to the processor,which minimizes its earliest finish time.The experimental simulation of randomly generated DAG and real-world application workflows proves that the LOEFT algorithm can significantly reduce the workflow execution time.(2)A new multi-objective optimization scheduling algorithm called NEGA is proposed to minimize workflow execution time and cost in heterogeneous computing environment.NEGA can be divided into two phases: task merging and task allocation.In the task merging phase,the "pipeline task pairs" in the workflow are merged to reduce the search space while reducing communication cost.In the task allocation phase,a genetic algorithm is used to assign tasks to processors that minimize both execution time and cost.NEGA designs a novel encoding/decoding mechanism based on random floating point number sequences according to the workflow topology to ensure that the algorithm performs selection,crossover and mutation operations and effectively maintains workflow precedence constraints.It is experimentally demonstrated that the NEGA algorithm can better optimize the scheduling time and cost simultaneously,and that the encoding/decoding mechanism for random floating point sequences has good generalizability.