Research On Homogeneous Distributed Multitask Scheduling Problem

Distributed task scheduling problem plays an important role in the era of big data.Task scheduling problem in the isomorphic processor environment is the basis of this kind of complicated problem.It studies how to assign multiple tasks with sequential constraints to available processors for execution,to minimize the scheduling length(makespan).This problem is NP-hard problem and can not be solved accurately in polynomial time unless P = NP,which has been extensively studied by scholars who is committed to finding efficient,simple and resource-efficient ways to solve this problem.Representative solutions at home and abroad includes priority-list-based,cluster-based,and task-based replication.The method of Combining cluster with task replication technology is generally considered as the best.The core of cluster is to put constrained tasks on the same processor as much as possible,so as to reduce the communication overhead between different processors.Besides,the core idea of task replication technology is to replicate the same task to multiple processors for execution at the expense of processor computing resources in exchange for earlier completion time,it is a method of exchanging space for time in short.In this paper,a scheduling algorithm based on Transformation Tree and Task Duplication(TTTD)is proposed,which is based on the combination of cluster and task duplication technology.The algorithm includes three important steps: preprocessing,transformation tree and sequence merging.In view of the fact that there may be insufficient number of available processors in actual work,a TTTD-based optimization algorithm will be further proposed to reduce the number of processors used.Finally,several well-known examples of distributed multi-task scheduling problems presented internationally are summarized,and the famous scheduling algorithms based on task replication type and TTTD algorithm proposed are applied to these examples.The details of each algorithm are analyzed,and the makespan of different algorithms on different examples is compared.The experimental results show that TTTD algorithm is effective,and it is superior to other similar algorithms in terms of both the quality of solutions and the number of processors used.