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.
叶佳 周鸣争. 物联网环境下具有顺序约束关系的静态任务表调度算法[J]. 计算机应用, 2014, 34(9): 2491-2496.
YE Jia ZHOU Mingzheng. List scheduling algorithm for static task with dependence in Internet of things environment. Journal of Computer Applications, 2014, 34(9): 2491-2496.
ATZORI L, IERA A, MORABITO G. The Internet of things: a survey [J]. Computer Networks, 2010, 54(15): 2787-2805.
[2]
TANG X, LI K, LI R, et al.Reliability-aware scheduling strategy for heterogeneous distributed computing systems [J]. Journal of Parallel and Distributed Computing, 2010,70(9): 941-952.
[3]
MENG X, LIU W. A DAG scheduling algorithm based on selected duplication of precedent tasks [J]. Journal of Computer-Aided Design and Computer Graphics, 2010, 22(6): 1056-1062. (孟宪福,刘伟伟.基于选择性复制前驱任务的DAG调度算法[J].计算机辅助设计与图形学学报,2010,22(6):1056-1062.)
[4]
YIN J, GU G, ZHAO J. Dynamic scheduling algorithm for hybrid real-time tasks with precedence constraints[J]. Computer Integrated Manufacturing Systems, 2010, 16(2):411-416, 422. (殷进勇,顾国昌,赵靖.优先约束的混合实时任务动态调度算法[J].计算机集成制造系统,2010,16(2):411-416,422.)
[5]
XIE Z, XIN Y, YANG J. Machine-driven integrated scheduling algorithm with rollback-preemptive[J]. Acta Automatica Sinica, 2011, 37(11): 1332-1343. (谢志强,辛宇,杨静.可回退抢占的设备驱动综合调度算法[J].自动化学报,2011,37(11):1332-1343.)
[6]
LAN Z, SUN S. An algorithm of allocating tasks to multiprocessors based on dynamic critical task [J]. Journal of Computers, 2007,30(3): 454-462. (兰舟,孙世新.基于动态关键任务的多处理器任务分配算法[J].计算机学报,2007,30(3):454-462.
[7]
TOPCUOGLU H, HARIRI S, WU M-Y. Performance-effective and low-complexity task scheduling for heterogeneous computing [J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260-274.
[8]
DAOUD M I, KHARMA N. A high performance algorithm for static task scheduling in heterogeneous distributed computing systems [J]. Journal of Parallel and Distributed Computing, 2008, 68(4): 399-409.
〖HJ〗[9]WANG X, HUANG H, DENG S. List scheduling algorithm for static task with precedence constraints for cyber-physical systems [J]. Acta Automatica Sinica, 2012, 38 (11): 1870-1879. (王小乐,黄宏斌,邓苏.处理顺序约束的信息物理融合系统静态任务表调度算法[J].自动化学报,2012,38(11):1870-1879.)
[10]
LI J, ZHANG B, WANG X. Heterogeneous multiprocessor task scheduling algorithm based on PSO[J]. Application Research of Computers, 2012, 29(10): 3621-3624. (李静梅,张博,王雪.基于粒子群优化的异构多处理器任务调度算法[J].计算机应用研究,2012,29(10)2622-2624.)
[11]
LI J, ZHANG B. Heterogeneous multiprocessor task scheduling based on PSO algorithm[J]. Computer Engineering and Design, 2013, 34(2): 2622-2624. (李静梅,张博.基于粒子群优化算法的群异构多处理器任务调度[J].计算机工程与设计,2013,34(2):2622-2624.)
[12]
LI J, JIN S. Research on static scheduling based on heterogeneous multi-core processors [J]. Computer Engineering and Design, 2013, 34(1):178-184. (李静梅,金胜男.基于异构多核处理器的静态任务调度研究[J].计算机工程与设计,2013,34(1):178-184.)
[13]
LEE Y C, ZOMAYA A Y. A novel state transition method for metaheuristic-based scheduling in heterogeneous computing systems [J]. IEEE Transactions on Parallel and Distributed Systems, 2008, 19(9): 1215-1223.
[14]
YANG J, XU H, PAN L, et al. Task scheduling using Bayesian optimization algorithm for heterogeneous computing environments [J]. Applied Soft Computing, 2011, 11(4): 3297-3310.
[15]
MENG X, WANG M. Peer to peer task scheduling based on improved immune clonal selection algorithm [J]. Computer Integrated Manufacturing Systems, 2009,15(9):1795-1802. (孟宪福,王敏.基于改进免疫克隆选择的对等网络任务调度机制[J].计算机集成制造系统,2009,15(9):1795-1802.)
[16]
TANG X, LI K, LIAO G, et al. A stochastic scheduling algorithm for precedence constrained tasks on grid [J]. Future Generation Computer Systems, 2011, 27(8): 1083-1091.