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

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

CLC Number:

TP391

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.

Figures/Tables 10

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Table 1

Fig.6

Fig.7

Table 2

Fig.8

References 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]	Honghong ZHANG, Xusheng GAN, Ang LI, Zhiqiang GAO, Xinyu XU. UAV obstacle avoidance and track recovery strategy based onvelocity obstacle method [J]. Systems Engineering and Electronics, 2020, 42(8): 1759-1767.
[2]	Jiayi LIU, Shaohua YUE, Gang WANG, Jie ZHANG, Xiaoqiang YAO. Design of command control model based on MPC-MAS under multi-platform distributed cooperative operation [J]. Systems Engineering and Electronics, 2020, 42(7): 1582-1589.
[3]	WU Minggong, WANG Zekun, WEN Xiangxi, JIANG Xurui, SUN Qianrui. Aircraft conflict resolution model based on geometric optimization [J]. Systems Engineering and Electronics, 2019, 41(4): 863-869.
[4]	FU Xiaowei, FENG Peng, GAO Xiaoguang, LIU Zhong. Conflict resolution in multi-UAV cooperative tasks assignment withcommunication delay [J]. Systems Engineering and Electronics, 2018, 40(7): 1491-1497.
[5]	ZHENG Xueen, XU Chengdong, FAN Guochao, ZHAO Jing. Modeling method of LWF based on object-oriented Petri-net [J]. Systems Engineering and Electronics, 2018, 40(7): 1626-1632.
[6]	JIANG Xurui, WU Minggong, WEN Xiangxi, TU Congliang, NIE Dangmin. Conflict resolution of multi-aircraft based on the cooperative game [J]. Systems Engineering and Electronics, 2018, 40(11): 2482-.
[7]	CAO Wenbin, JIA Xisheng, HU Qiwei, SU Xujun. Equipment battlefield damage assessment and repair decision-making modeling based on selective maintenance [J]. Systems Engineering and Electronics, 2018, 40(1): 98-105.
[8]	DUAN Yi, TAN Xiansi, QU Zhiguo, WANG Hong, WANG Peng. Task scheduling algorithm for phased array radar based on shifting impact rate [J]. Systems Engineering and Electronics, 2017, 39(11): 2470-2476.
[9]	Lü Wei-min, HU Wen-lin, WANG Zhe, HU Dong. Missile technical preparation process optimization of based on line balancing [J]. Systems Engineering and Electronics, 2016, 38(7): 1589-1593.
[10]	ZHANG Yuan-yuan, WU Wen-hai, LIU Jin-tao, ZHOU Si-yu. Workflow net model of flight combat mission [J]. Systems Engineering and Electronics, 2016, 38(6): 1320-1325.
[11]	ZENG Bin, YAO Lu, HU Wei, YANG Guang. Scheduling algorithm for maintenance tasks under uncertainty [J]. Systems Engineering and Electronics, 2016, 38(3): 595-601.
[12]	LIU Yu, XIANG Dong-yang, ZHENG Chun-di. Scheduling and optimizing algorithm for parallel tasks in heterogeneous distributed computing systems [J]. Systems Engineering and Electronics, 2016, 38(2): 332-338.
[13]	JIANG Wei，HAO Hui-cheng，LI Yi-jun. Review of task scheduling research for the Earth observing satellites [J]. Systems Engineering and Electronics, 2013, 35(9): 1878-1885.
[14]	JIANG Wei， PANG Xiu-li， HAO Hui-cheng. Collaborative scheduling model and algorithm for imaging satellite network [J]. Systems Engineering and Electronics, 2013, 35(10): 2093-2101.
[15]	WANG Zhuo-fu, DING Ji-yong, LIU Yuan, LIU Xun. Analysis of critical path and most critical activity in PERT networks based on Monte Carlo method [J]. Journal of Systems Engineering and Electronics, 2012, 34(8): 1646-1651.

Research on task scheduling algorithm in resource-constrained environments

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 31

Related Articles 15

Recommended Articles

Metrics

Comments