Page 151 - 公共安全与应急管理研究

第五章 应急通信

调，增加了问题的建模难度和计算复杂度。
（三）任务调度求解
随着网络中任务和资源规模的增加，任务调度问题的复杂度将会呈指数性增

长。在此驱动下，研究包括调度模型和算法在内的高效任务调度求解技术的重要
性也日益凸显。
1. 任务调度模型
调度模型是任务调度的重要基础，是决定问题描述方式和指导算法设计的关

键因素。现阶段，线性规划模型、约束满足模型、图论模型、马尔可夫决策过程
等各类调度模型已被广泛运用于任务调度问题研究中。数学规划模型的基本思想
是将任务调度问题转化为一个数学模型，然后使用线性规划和非线性规划等方法，

求解出最优的任务调度方案。约束满足模型类似，在对任务的约束条件进行建模
的基础上，使用搜索算法、人工智能等方法，寻找满足所有约束的可行任务调度
方案。相比以上两种数学化的模型，图论模型则更加直观，不仅能描述出任务和
资源之间的关系，还能适用动态变化的网络拓扑结构。马尔可夫决策过程（MDP，
Markov Decision Process）则主要用于建模随机的决策过程，通过选择不同的策

略，使得获得的奖励最大化。这些调度模型表现出鲜明的问题特色与针对性，引
入了与调度问题紧密相关的约束和决策手段的同时，也表现出了较大的相似性，
例如总是以任务和资源在时域和空域的可见性作为建模的出发点。值得注意的

是，尽管各调度模型存在一定相似，但对不同调度场景的适用程度却是不同。在
SAGIECN 中，由于任务需求和约束条件的多样化和复杂化，研究统一的建模方
法理论成为提高应急调度效率的重要趋势。
2. 任务调度算法
调度算法是任务调度的优化手段，是实现模型解算、输出调度方案、决定问

题求解质量的关键因素。当前，精确求解算法、启发式算法和元启发式算法等一
系列形式各异的调度算法被应用于任务调度问题的求解中。精确求解算法是一种
通过穷举所有可能的解来找到最优解的算法，主要包括分支定界算法和动态规划

算法等。
与精确求解算法不同，启发式算法在许多实际问题中能够快速找到接近全局
最优解的方案，因此在任务调度问题中的应用非常广泛。常见的启发式算法包括
优先级排序算法、冲突消解算法和任务分配算法。元启发式算法则通过组合多种

137