Optimization Algorithms For Workflow Scheduling Time And Reliability Under Heterogeneous Distributed Computing Systems

With the rapid development of information technology,heterogeneous distributed computing systems have gradually become a powerful technical support for many scientific fields including scientific computing and engineering applications.In a heterogeneous distributed computing system,workflow is a common execution object,and the merit of workflow scheduling strategy will influence the execution efficiency of workflow and system efficiency of resources directly.This study addresses the optimization of workflow scheduled execution time and reliability under heterogeneous distributed computational systems by conducting the following two main studies.(1)A task merging and duplication algorithm MDMR(Merging and Duplication for Makespan and Reliability)is proposed for the problem of minimizing the execution time and maximizing the reliability of single workflow under heterogeneous computing system to achieve the time optimization under the workflow reliability constraint.The MDMR algorithm is divided into Three phases: task merging,entry task replication,and reliability determination with non-entry task replication.Task merging simplifies the DAG workflow and reduces the workflow completion time;entry task replication reduces the workflow completion time while improving the reliability;reliability detection and non-entry tasks ensure that the workflow reliability is higher than the target value.The experimental results show that the MDMR algorithm has more advantages in time and reliability compared with other similar algorithms.(2)A workflow scheduling algorithm GAMDMR(Genetic Algorithm in Merging and Duplication for Makespan and Reliability)combining genetic algorithm is proposed for the problems of minimizing execution time and maximizing reliability of multiple workflows under heterogeneous computing systems.The GAMDMR algorithm consists of three steps: task merging,task assignment,reliability determination and task replication.Task merging reduces the cost of inter-task communication and reduces the search space of the genetic algorithm;task assignment minimizes the task execution time and maximizes the reliability;reliability judgment and task replication ensure that the workflow reliability is higher than the target value.Specifically,GAMDMR employs a random integer sequence-based encoding/decoding strategy to ensure that the algorithm is effective in maintaining prior-order constraints on the workflow while it is performing its select,intersection,as well as variance algorithms.Experimental results show that the GAMDMR algorithm has greater advantages in time and reliability than other algorithms in multiple workflow scheduling.