Abstract:

The static task list scheduling problems in distributed heterogeneous computing environment of Internet of things was studied, and a list scheduling algorithm named Heterogeneous Dynamic Priority Task Scheduling (HDPTS) was proposed, which can dynamically change scheduling sequence based on the strategy of the earliest completion time. Concerning that the exsiting list scheduling algorithms can not accurately determine the scheduling order before scheduling, on the basis of Improved Heterogeneous Earliest Finish Time (IHEFT) algorithm, a dynamic priority scheduling policy was added to it. When precursor tasks of a node completed scheduling, the scheduling priority of this node should be changed. Scheduling priority of task was calculated on the basis of choosing the maximum value between the latest completion time of all immediate predecessor tasks and the maximum available time of all the resources. At the same time, some other factors were also considered, including the influence to the subsequent tasks of the tasks assigned to the resource, the resource load, the calculated value of uplink weight and the influence to the exit tasks. All these considerations make the priority calculation be more reasonable, so as to dynamically change the task scheduling sequence reasonably according to the task allocation situation. By a randomly generated example test, the results show that the scheduling length of HDPTS reduced by 14.29% compared with IHEFT, HEFT (Heterogeneous Earliest Finish Time); the test results on a large number of randomly generated Directed Acyclic Graph (DAG) with specific structure prove that HDPTS is more effective than IHEFT, HEFT and LDCP (Longest Dynamic Critic Path) algorithms.

摘要：

针对物联网异构调度环境下并行计算的静态任务调度问题，提出了一种基于最早完成时间策略改变调度顺序的表调度算法HDPTS。该算法针对现有表调度算法在调度前不能准确地确定调度顺序的问题，在IHEFT算法的基础上添加了一个动态优先级调度策略，当节点的前驱任务都已经完成调度任务时，就改变该节点的调度优先级。任务优先级的计算在所有前驱任务到达这个任务的最晚完成时间与所有资源上最大可以使用时间之间取最大值的基础上，同时考虑到分配到各个资源上的任务对后继任务的影响和资源上的负载情况，以及上行权重的计算值和对出口任务的影响，使得优先级计算更加合理，能够根据任务分配动态合理改变任务调度顺序。通过随机生成一个算例进行测试，结果表明HDPTS比IHEFT、HEFT在调度长度方面减少14.29%；对大量随机产生的特定结构的有向无环图(DAG)进行测试，测试结果显示HDPTS算法比IHEFT、HEFT和LDCP算法更有效。

关键词: 异构环境, 物联网, 任务调度, 表调度, 静态调度