资源约束条件下任务调度算法研究

doi:10.12305/j.issn.1001-506X.2021.12.21

摘要/Abstract

摘要：

如何解决资源约束条件下的任务调度问题，保证在资源使用存在冲突情况下, 多个任务高效执行, 其中合理的任务调度和资源冲突消解是影响任务执行效果的关键因素。基于工作流图模型提出了一套资源约束条件下任务调度的框架, 并针对调度过程中产生的资源冲突, 提出了两种任务调度算法: 一种算法通过任务关键度确定优先级, 并基于贪心策略和调整工作流图拓扑结构的方法, 在任务开始前确定任务调度方案; 另一种算法采取弹性资源调度的方式, 使产生冲突的任务优先在资源不足的条件下开始执行, 任务调度和执行交替进行。最后, 通过地震救援案例验证了相关算法可行性, 与求解资源约束条件下任务调度问题的两类典型方法中具有代表性的算法进行对比实验, 分析了所提两种算法的优势与意义。仿真结果表明，所提算法具有适用地震救援资源紧缺特点的优势。

关键词: 任务调度, 资源约束, 冲突消解, 关键路径, 工作流

Abstract:

How to solve the task scheduling problem under resource constraints to ensure the efficient execution of multiple tasks in the presence of conflicts in resource use, among which reasonable task scheduling and resource conflict resolution are the key factors that affect the effect of task execution. Based on the workflow graph model, a framework for task scheduling under resource constraints is proposed, and for resource conflicts generated in the scheduling process, two task scheduling algorithms are proposed: one algorithm determines priority by task criticality, is based on greedy thinking and adjusting the topological structure of the workflow graph, and determines the task scheduling plan before the task starts; the other algorithm adopts the flexible resource scheduling method, so that the conflicting task will be executed first under the condition of insufficient resources, and the task will be scheduled and executed alternately. Finally, the feasibility of related algorithms is verified through earthquake rescue cases, contrasting experiments with typical representatives of two types of typical resource-constrained project scheduling algorithms are conducted, and the advantages and significance of the two algorithms proposed in this paper are analyzed. The simulation results show that the algorithm proposed in this paper has the advantage of being suitable for cases with the shortage of earthquake rescue resources.

Key words: task scheduling, resource constraint, conflict resolution, critical path, workflow

中图分类号:

TP391

路程昭, 龚建兴, 朱雷, 刘权. 资源约束条件下任务调度算法研究[J]. 系统工程与电子技术, 2021, 43(12): 3586-3593.

Chengzhao LU, Jianxing GONG, Lei ZHU, Quan LIU. Research on task scheduling algorithm in resource-constrained environments[J]. Systems Engineering and Electronics, 2021, 43(12): 3586-3593.

图/表 10

图1

图2

图3

图4

图5

表1

图6

图7

表2

图8

参考文献 31

1	BLYTHE J, JAIN S, DEELMAN E, et al. Task scheduling strategies for workflow-based applications in grids[C]//Proc. of the IEEE 5th International Symposium on Cluster Computing and the Grid, 2008: 759-767.
2	HU Y N , WANG H , MA W G . Intelligent cloud workflow management and scheduling method for big data applications[J]. Journal of Cloud Computing, 2020, 39 (9): 13677.
3	DEVI K , PAULRAJ D , MUTHUSENTHIL B . Deep learning based security model for cloud based task scheduling[J]. KSⅡ Transactions on Internet & Information Systems, 2020, 14 (9): 3663- 3679.
4	MAURYA A K , TRIPATHI A K . ECP: a novel clustering-based technique to schedule precedence constrained tasks on multiprocessor computing systems[J]. Computing, 2019, 101 (8): 1015- 1039. doi: 10.1007/s00607-018-0636-3
5	PEI S J , ZHANG Y , LIANG C . Fast pruning algorithm and task scheduling under map/reduce[J]. International Journal of Performability Engineering, 2020, 16 (10): 1627- 1636. doi: 10.23940/ijpe.20.10.p14.16271636
6	XIAO F Y , ZHANG Z L , ABAWAJY J . Workflow scheduling in distributed systems under fuzzy environment[J]. Journal of Intelligent and Fuzzy Systems, 2019, 37 (4): 5323- 5333. doi: 10.3233/JIFS-190483
7	BOVEIRI H R , JAVIDAN R , KHAYAMI R . An intelligent hybrid approach for task scheduling in cluster computing environments as an infrastructure for biomedical applications[J]. Expert Systems, 2020, 38, e12536.
8	WU C X , LIAO M H , KARATA S , et al. Real-time neural network scheduling of emergency medical mask production during COVID-19[J]. Applied Soft Computing Journal, 2020, 97 (A): 106790.
9	ORR M , SINNEN O . Integrating task duplication in optimal task scheduling with communication delays[J]. IEEE Trans.on Parallel and Distributed Systems, 2020, 31 (10): 2277- 2278. doi: 10.1109/TPDS.2020.2989767
10	KRISHNAKUMAR A , ARDA S E , GOKSOY A A , et al. Runtime task scheduling using imitation learning for heterogeneous many-core systems[J]. IEEE Trans.on Computer Aided Design of Integrated Circuits and Systems, 2020, 39 (11): 4064- 4077. doi: 10.1109/TCAD.2020.3012861
11	田启华, 黄佳康, 明文豪, 等. 资源约束下产品开发任务调度的多目标优化[EB/OL]. [2021-01-06]. https://kns-cnki-net-s.nudtproxy.yitlink.com:443/kcms/detail/11.5946.TP.20200718.1741.006.html.
	TIAN Q H, HUANG J K, MING W H, et al. Multi-objective optimization of product development task scheduling under resource constraints[EB/OL]. [2021-01-06]. https://kns-cnki-net-s.nudtproxy.yitlink.com:443/kcms/detail/11.5946.TP.20200718.1741.006.html.
12	WANG J J , ZHU X M , QIU D S , et al. Dynamic scheduling for emergency tasks on distributed imaging satellites with task merging[J]. IEEE Trans.on Parallel and Distributed Systems, 2014, 25 (9): 2275- 2285. doi: 10.1109/TPDS.2013.156
13	YUAN Y C , LI X P , WANG Q , et al. Deadline division-based heuristic forcost optimization in workflow scheduling[J]. Information Sciences, 2009, 179 (15): 2562- 2575. doi: 10.1016/j.ins.2009.01.035
14	LIN J , ZHU L , GAO K Z . A genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem[J]. Expert Systems with Applications, 2020, 140, 112915. doi: 10.1016/j.eswa.2019.112915
15	KOSZTYAN ZT , SZALKAI I . Multimode resource-constrained project scheduling in flexible projects[J]. Journal of Global Optimization, 2020, 76 (1): 211- 241. doi: 10.1007/s10898-019-00832-8
16	ALI I , BAGCHI S . Isolating critical flow path and algorithmic partitioningof the and/or mobile workflow graph[J]. Future Generation Computer Systems, 2020, 103 (2): 28- 43.
17	ABRISHAMI S , NAGHIBZADEH M , EPEMA D H J . Cost-driven scheduling of grid workflows using partial critical paths[J]. IEEE Trans.on Parallel Distribution System, 2012, 23 (8): 1400- 1412. doi: 10.1109/TPDS.2011.303
18	张艳, 孙世新. 一种基于动态关键路径的递归并行调度算法[J]. 系统工程与电子技术, 2001, 23 (9): 81- 86. doi: 10.3321/j.issn:1001-506X.2001.09.026
	ZHANG Y , SUN S X . A recursive parallel scheduling algorithm based on dynamic critical path[J]. Systems Engineering and Electronics, 2001, 23 (9): 81- 86. doi: 10.3321/j.issn:1001-506X.2001.09.026
19	TAKAKURA Y , YAJIMA T , KAWAJIRI Y , et al. Application of critical path method to stochastic processes with historical operation data[J]. Chemical Engineering Research & Design: Transactions of the Institution of Chemical Engineers Part A, 2019, 149, 195- 208.
20	柳玉, 向东阳, 郑春弟. 面向异构分布式计算环境的并行任务调度优化方法[J]. 系统工程与电子技术, 2016, 37 (2): 332- 338.
	LIU Y , XIANG D Y , ZHENG C D . Scheduling and optimizing algorithm for parallel tasks in hetero geneous distributed computing systems[J]. Systems Engineering and Electronics, 2016, 37 (2): 332- 338.
21	WANG H , LAPPAS N H , GOUNARIS C E . Multi-mode resource constrained project scheduling with alternative prerequisites: new models and computational studies[J]. Industrial & Engineering Chemistry Research, 2019, 58 (39): 18253- 18266.
22	RAMEZANI R . Dynamic scheduling of task graphs in multi-fpga systemsusing critical path[J]. The Journal of Supercomputing, 2021, 77, 597- 618. doi: 10.1007/s11227-020-03281-3
23	ZHAO C , MURATA T . Hybrid approach of constraint programming and integer programming for solving resource-constrained project-scheduling problems[J]. Lecture Notes in Engineering & Computer Science, 2012, 2196 (1): 1574- 1577.
24	KOSZTYAN Z T . Exact algorithm for matrix-based project planning problems[J]. Expert Systems with Applications, 2015, 42 (9): 4460- 4473. doi: 10.1016/j.eswa.2015.01.066
25	姚文斌, 王帅元. 基于虚拟化的容灾系统任务关键性判定方法[J]. 哈尔滨工程大学学报, 2009, 30 (11): 1256- 1260. doi: 10.3969/j.issn.1006-7043.2009.11.010
	YAO W B , WANG S Y . Judging approach of mission-critical in the disaster tolerance system based on the virtualization technology[J]. Journal of Harbin Engineering University, 2009, 30 (11): 1256- 1260. doi: 10.3969/j.issn.1006-7043.2009.11.010
26	景维鹏, 霍帅起, 陈广胜, 等. 混合关键任务可靠调度方法与调度性分析[J]. 西安电子科技大学学报(自然科学版), 2016, 43 (6): 158- 163.
	JING W P , HUO S Q , CHENG G S , et al. Novel mixed-criticality reliability scheduling strategy and schedulability test[J]. Journal of Xidian University, 2016, 43 (6): 158- 163.
27	王喆. 基于层次任务网络的应急资源规划方法[D]. 武汉: 华中科技大学, 2012.
	WANG Z. Emergency resource management approach based on HTN planning[D]. Wuhan: Huazhong University of Science and Technology, 2012.
28	RIZVI N , RAMESH D . HBDCWS: heuristic-based budget and deadline constrained workflow scheduling approach for heterogeneous clouds[J]. Soft Computing, 2020, 24 (24): 18971- 18990. doi: 10.1007/s00500-020-05127-9
29	KOLISCH R , HARTMANN S . Experimental investigation of heuristics for resource-constrained project scheduling: an update[J]. European Journal of Operational Research, 2006, 174 (1): 23- 37. doi: 10.1016/j.ejor.2005.01.065
30	ADAMU P I , OKAGBUE H I , OGUNTUNDE P E . A new priority rule for solving project scheduling problems[J]. Wireless Personal Communications, 2019, 106 (2): 681- 699. doi: 10.1007/s11277-019-06185-5
31	LIU J , LIU Y S , SHI Y , et al. Solving resource-constrained project scheduling problem via genetic algorithm[J]. Journal of Computing in Civil Engineering, 2020, 34 (2): 187- 198.

任务名称	执行时间	人员需求	救援器械需求	关联任务量	关键度
任务a	4	100	20	3	37.0
任务b	12	20	10	2	11.0
任务c	2	10	5	2	14.5
任务d	1	20	4	2	12.5
任务e	12	20	15	4	35.5
任务f	8	30	15	2	12.5
任务g	14	50	10	2	27.0
任务h	10	20	10	2	10.0
任务i	20	10	0	4	31.0
任务j	10	8	0	1	10.8

算法	运行时间/s
ER	3.78
GA	208.36
GRWC	2.58
GSTS	2.06

[1]	刘家义, 岳韶华, 王刚, 张杰, 姚小强. 多平台分布式协同作战下基于MPC-MAS的指挥控制模型设计[J]. 系统工程与电子技术, 2020, 42(7): 1582-1589.
[2]	宋敏, 戴静, 孔韬. 基于NMPC的无人机自主防撞控制方法[J]. 系统工程与电子技术, 2019, 41(9): 2092-2099.
[3]	李波, 周静杨, 高晓光. 基于拍卖算法的相控阵雷达任务调度方法[J]. 系统工程与电子技术, 2018, 40(8): 1736-1742.
[4]	符小卫, 冯鹏, 高晓光, 刘重. 通信延迟约束下多无人机任务指派冲突消解[J]. 系统工程与电子技术, 2018, 40(7): 1491-1497.
[5]	郑学恩, 许承东, 范国超, 赵靖. 基于面向对象Petri-net的LWF建模方法[J]. 系统工程与电子技术, 2018, 40(7): 1626-1632.
[6]	吕卫民, 胡文林, 王哲, 胡冬. 基于生产线平衡的导弹技术准备流程优化[J]. 系统工程与电子技术, 2016, 38(7): 1589-1593.
[7]	张源原, 吴文海, 刘锦涛, 周思羽. 飞行作战任务过程的工作流网模型[J]. 系统工程与电子技术, 2016, 38(6): 1320-1325.
[8]	曾斌, 姚路, 胡炜, 杨光. 考虑不确定因素影响的保障任务调度算法[J]. 系统工程与电子技术, 2016, 38(3): 595-601.
[9]	柳玉, 向东阳, 郑春弟. 面向异构分布式计算环境的并行任务调度优化方法[J]. 系统工程与电子技术, 2016, 38(2): 332-338.
[10]	王海波，徐敏强，王日新，李玉庆. 基于IP-ACO算法的航天器测控资源调度技术[J]. Journal of Systems Engineering and Electronics, 2012, 34(4): 719-725.
[11]	赵宇，李建勋，曹兰英，张世仓. 基于二次规划的相控阵雷达任务自适应调度算法[J]. Journal of Systems Engineering and Electronics, 2012, 34(4): 698-703.
[12]	王海波, 徐敏强, 王日新, 李玉庆. 对地观测小卫星星座长期任务规划求解技术[J]. Journal of Systems Engineering and Electronics, 2011, 33(6): 1293-1298.
[13]	陈祥国,武小悦. 任务调度启发式信息的卫星数传ACO算法应用[J]. Journal of Systems Engineering and Electronics, 2010, 32(6): 1251-1257.
[14]	朱海, 王宇平. 安全驱动的实时任务调度遗传算法[J]. Journal of Systems Engineering and Electronics, 2010, 32(4): 854-859.
[15]	陈祥国, 武小悦. 基于解构造图的卫星数传调度ACO算法[J]. Journal of Systems Engineering and Electronics, 2010, 32(3): 592-597.