A task duplication algorithm based on dynamic critical path and edge-zeroing

Task scheduling is critical for a parallel and distributed system. The task duplication and scheduling algorithm and other typical algorithms cannot obtain the optimal solutions for scheduling length even under optimal conditions. Moreover, they are constrained by the node selection scope and node execution time scope when allocating nodes, being unable to minimize the number of processors required by the algorithms. To carry out the static scheduling of the related tasks in the parallel and distributed system, this paper proposes the task in the parallel and distributed system, this paper proposes the task duplication algorithm based on dynamic critical path and edge-zeroing, whose main objective is to reduce the number of resources. The algorithm develops the principles that the scheduling length of sub-nodes that are duplicated with no constraints should not increase, that the scheduling length of sub-nodes that are duplicated with constraints should not increase and the scheduling length of dynamic critical path clustering should not increase, thus reducing the task execution time and the number of resources used. The algorithm does not limit the task computing time and the task communication time. The comparison o the task duplication algorithm proposed in the paper with other algorithms show that the former is superior to the latter in terms of scheduling length and number of processors used.