| 资源约束条件下任务调度算法研究 |
| |
| 引用本文： | 路程昭,龚建兴,朱雷,刘权. 资源约束条件下任务调度算法研究[J]. 系统工程与电子技术, 2021, 43(12): 3586-3593. DOI: 10.12305/j.issn.1001-506X.2021.12.21 |
| |
| 作者姓名： | 路程昭 龚建兴 朱雷 刘权 |
| |
| 作者单位： | 国防科技大学智能科学学院, 湖南 长沙 410073 |
| |
| 基金项目： | 国家重点研发计划资助课题(2018YFC1504402) |
| |
| 摘 要： | 如何解决资源约束条件下的任务调度问题,保证在资源使用存在冲突情况下, 多个任务高效执行, 其中合理的任务调度和资源冲突消解是影响任务执行效果的关键因素。基于工作流图模型提出了一套资源约束条件下任务调度的框架, 并针对调度过程中产生的资源冲突, 提出了两种任务调度算法: 一种算法通过任务关键度确定优先级, 并基于贪心策略和调整工作流图拓扑结构的方法, 在任务开始前确定任务调度方案; 另一种算法采取弹性资源调度的方式, 使产生冲突的任务优先在资源不足的条件下开始执行, 任务调度和执行交替进行。最后, 通过地震救援案例验证了相关算法可行性, 与求解资源约束条件下任务调度问题的两类典型方法中具有代表性的算法进行对比实验, 分析了所提两种算法的优势与意义。仿真结果表明,所提算法具有适用地震救援资源紧缺特点的优势。
|
| 关 键 词： | 任务调度 资源约束 冲突消解 关键路径 工作流 |
| 收稿时间： | 2021-01-07 |
Research on task scheduling algorithm in resource-constrained environments |
| |
| Chengzhao LU,Jianxing GONG,Lei ZHU,Quan LIU. Research on task scheduling algorithm in resource-constrained environments[J]. System Engineering and Electronics, 2021, 43(12): 3586-3593. DOI: 10.12305/j.issn.1001-506X.2021.12.21 |
| |
| Authors: | Chengzhao LU Jianxing GONG Lei ZHU Quan LIU |
| |
| Affiliation: | College of Intelligence Science and Technology, National University of Defense Technology, Changsha 410073, China |
| |
| 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. |
| |
| Keywords: | task scheduling resource constraint conflict resolution critical path workflow |
|
| 点击此处可从《系统工程与电子技术》浏览原始摘要信息 |
|
点击此处可从《系统工程与电子技术》下载全文 |
|
