Efficiency Scheduling Algorithm For Heterogeneous Distributed System With Task Duplication

The optimal scheduling problem in heterogeneous distributed computing systems attracts much attention.With the limitation of bandwidth and transmission speed limits of communication network,the impact of communication cost cannot be ignored.Therefore,optimizing the scheduling length by reducing the communication cost during scheduling has become one of the research focuses.Scheduling algorithms based on task duplication have emerged which allows additional computations to reduce communication cost and achieve excellent results.However,scheduling problems with task duplication is more difficult to solve.How to use task duplication to provide high-quality scheduling schema while considering the running time performance is a major challenge.This work decomposes the scheduling problem into allocation and ordering subproblems to improve the efficiency.A two-stage scheduling algorithm based on task duplication is proposed,and each solution phase is optimized contrapuntally to improve the efficiency.The main contributions of this paper are as follows:1.This paper analyzed and defined the scheduling length optimization problem of heterogeneous distributed systems based on task duplication.The problems of solution space expansion,chain reaction and duplication anomaly faced by the scheduling algorithm design based on task duplication are analyzed in detail.And by modeling the heterogeneous distributed system and the tasks in these systems,the scheduling length optimization problem of heterogeneous distributed system based on task duplication is formally defined.2.This paper proposes a task allocation algorithm based on branch and bound search.It is used to search for task allocation with the upper bound of the schedule length as the optimization goal.The algorithm uses topological order to perform branch operations to eliminate redundant states during the search,and cuts the solution space according to the resource constraints of the system and the optimization objective,and efficiently finds the best allocations with and without duplication.3.This paper proposes a dynamic priority task sorting algorithm based on slack interval.According to the precedence constraints and the task allocation scheme given in the allocation phase,the dynamic priority of the tasks is calculated and sorted based on the slack interval to obtain the final scheduling scheme.In addition,to solve the duplication anomaly,the algorithm enables each task to obtain input data from the predecessor on any processing unit during sorting process,and further optimizes the schedule length.4.This paper implements a heterogeneous distributed systems scheduling tool.The tool provides an easy-to-use human-computer interface and implements the and algorithm proposed.This tool is able to give scheduling schemes for different system and task configurations.Furthermore,analysis experiments are designed to verify the effectiveness and efficiency of the proposed algorithm under different system configuration and task configuration.Compared with the state-of-the-art heuristic scheduling algorithm and genetic scheduling algorithm,the proposed algorithm provide scheduling schemes with higher quality,and the running time is significantly better than the one stage genetic scheduling algorithm.