处理顺序约束的信息物理融合系统静态任务表调度算法

List Scheduling Algorithm for Static Task with Precedence Constraints for Cyber-physical Systems

针对异构环境并行计算的静态任务调度问题,以最小化有向无环图(Directed acyclic graph,DAG)的执行跨度为目标,改变HEFT(Heterogeneous earliest finish time)算法中任务上行权重的计算方法,获得更加合理的任务顺序排列,提出了一种最早完成时间优先的表调度算法IHEFT(Improvement heterogeneous earliest finish time).该算法在计算任务的上行权重时,分别计算该任务分配给不同资源的上行权重,取其最小值,比使用所有资源对该任务的平均处理时间进行计算的HEFT算法更为准确.确定任务的处理顺序后采用最早完成时间越小越优先的策略将任务分配给最优资源,并使得任务的开始执行时间和结束时间满足DAG中有向边的通讯时间约束.通过使用部分文献中的算例数据以及随机生成满足一定结构要求的DAG进行算法测试,将IHEFT与HEFT,CPOP(Critical-path-on-a-processor)和LDCP(Longest dynamic critical path)进行了比较,结果显示IHEFT算法更有效,而且时间复杂度较低.

In this paper, we study the static task scheduling problems in distribution heterogeneous computing envi- ronment such as cyber-physical system （CPS）. We present a list scheduling algorithm named improvement heterogeneous earliest finish time （IHEFT） algorithm for minimizing makespan of the precedence constrained applications which can be modelled as a directed acyclic graph （DAG）. We acquire a better task list by changing the task＇s upward rank weight calculation method in heterogeneous earliest finish time （HEFT）. In IHEFT, the different computing time not the average computing time in each resource is considered for each task when calculating the upward rank weight. After the priority list is determined, tasks axe assigned to the resource based on the earliest finish time first policy and the precedence con- straints. Comparison on performance evaluation using both the case data in the recent literature and randomly generated DAGs show that the IHEFT list scheduling algorithm has outperformed the HEFT, CPOP （Critical-path-on-a-processor） and LDCP （Longest dynamic critical path） algorithms both in makespan and scheduling time consumed.