【理论】联合作战资源调度模型研究_风闻

​                       联合作战资源调度是联合作战筹划的最后环节，过程可以描述为根据既定任务和任务的优先级、资源需求、任务间协同关系等属性，将战场空闲、可用资源分配给任务，并确定任务的具体开始时间，是典型资源受限项目调度问题（resource-constrainedprojectscheduleproblem，RCPSP），属于运筹学的动态规划范畴。2017版《JP5-0JointPlanning》将联合作战筹划分为筹划启动、使命分析、行动方案开发、行动方案分析和推演、行动方案评估、行动方案确定和计划命令开发7个步骤。其中前6步属于任务规划过程，目标是开发出可行的行动方案（courseofaction，COA），又可称为联合作战方案。第7步属于资源调度过程，目标是建立联合作战方案和兵力资源之间的连接关系，形成联合作战计划。

在智能规划领域，资源调度的基础是联合作战筹划中拟制的行动方案，行动方案一般由任务和任务之间的关系组成，资源调度的目标就是为行动方案中的每一个任务分配执行资源并安排任务开始时间，将任务之间的因果、并发等逻辑协同关系转换为时间协同关系。经典的RCPSP是在信息完备的静态环境中建模，具有任务执行时间确定、资源确定、任务间逻辑关系约束单一和任务不可中断的特征。战争具有高度对抗性，战场瞬息万变，这给联合作战方案带来高度不确定性，使得经典RCPSP的建模方法难以适应联合作战资源调度需求，需要采用不确定性资源调度框架来进行建模，这也是近年来RCPSP领域的研究热点。

1不确定性资源调度研究

1.1 联合作战方案不确定性分析联合作战方案主要由初始态势、终止态势和一组相互关联的任务集合组成，其主体是相互关联的任务集合，包括任务和任务协同关系，通常采用单代号网络（activityonnode，AON）表示，节点表示任务，边表示任务间的逻辑协同关系，节点和边都采用“属性-值”形式描述其语义内涵。不确定性资源调度就是在考虑联

合作战方案信息中存在的不确定性条件下，将资源分配给每一个任务，并根据任务的协同关系和资源就绪情况计算任务的开始时间。

联合作战方案具有任务、资源和时间3个维度的不确定性。任务不确定性是联合作战方案中任务数量增加或减少的变化，这也是联合作战方案面临的主要不确定性问题：敌我双方的高度对抗博弈条件下，战场瞬息万变，指挥员需要依据战场态势变化对联合作战方案做出快速调整，以适应作战需要。资源不确定性是指一个任务可能存在多个执行模式，不同的执行模式具有不同的资源需求，例如打击敌方机场，可以采用常导打击也可以采用空对地突击，或者混合打击，任务的执行模式需要在资源调度阶段确定。时间不确定性包括机动时间不确定性、执行时长不确定性2种。（1）机动时间不确定性是指由于联合作战资源的多站现象带来的资源从部署位置到目标空间的机动时间不确定性。多站是指同类资源分布在不同的资源站；资源站即资源的存储站点，不同的资源站具有不同的空间位置，这导致从资源站到任务目标区的机动时间不同。（2）执行时长不确定性是指任务从进入目标区域开始执行任务到结束任务退出目标区域之间时间长度的不确定性，例如执行空对地打击任务的飞机在进入目标区域雷达开机到完成投弹并退出目标区的时间长度。

1.2 不确定性资源调度研究现状经典RCPSP问题研究是在确定性环境下进行的，自Herroelen和Leus在2004年的鲁棒项目调度综述、2005年的不确定性环境下项目调度综述[8]后，RCPSP研究热点开始转向不确定性环境下的资源调度研究[9]，中国自2009年开始出现了不确定性资源调度的相关研究。不确定性环境下资源调度的研究对象是在通过调度算法生成基础调度方案的基础上，如何增加基础调度方案的鲁棒性。调度方案的鲁棒性是指当指挥员依据调度方案控制部队执行任务时，在遇到不确定性干扰情况下，不对调度方案修改或仅进行小幅度调整，仍能够完成既定作战任务的特性，也就是调度方案的抗干扰能力。

对于不确定性RCPSP研究，Demeulemeester和Her?roelen将求解过程划分为3个阶段：第1阶段，基于任务的协同关系约束和资源约束求解可行调度方案；第2阶段，利用主动式调度模型增强方案的鲁棒性；第3阶段，利用反应式调度模型在执行时对受到干扰破坏的调度方案进行修复。可见，按照调度方案鲁棒性模型的作用时机，可以将不确定性资源调度方法分为主动式调度模型和反应式调度模型2种，这2种模型都不能独立解决不确定性问题，需要相互配合，区别是研究侧重点不同。当前主动式调度模型研究成果角度，包括时间缓冲、资源缓冲、累计不稳定性权重和最坏情形分析等方法；反应式调度模型研究成果较少，包括完全重新调度、修复调度、应急调度和赶工策略等方法。

1.3 联合作战方案不确定性研究框架1.3.1联合作战方案鲁棒性策略分析

常说“大炮一响，计划归零”，联合作战方案的主要不确定性来自任务不确定性，也就是根据战场态势变化，对联合作战中任务的动态增加、删除和参数修改等临机决策带来的不确定性。当前主动式调度模型主要针对时间和资源2个维度的不确定性，采用的手段通常是插入冗余时间、增加战役总时长，或者增加冗余资源来提高方案的鲁棒性。但是在信息化战争中，“观察-判断-决策-行动”（observe-orient-decision-action，OO-DA）循环的时间越短，则战争越具有主动性，插入冗余时间和增加战役时长与信息化战争的高时效形成矛盾，在战役资源总量确定条件下，增加冗余资源会减少瞬时资源可用量，进一步增加调度方案的执行时间，加深这种矛盾。此外，随着计算机硬件和云计算技术的发展，反应式调度面临的计算瓶颈正在逐步缓解。综上分析，反应式资源调度模型更适合联合作战资源调度问题。

反应式鲁棒策略包括修复和再规划2种。修复是指针对任务的增加、删除、参数修改，对调度方案结构进行局部调整，适用于对反应速度敏感的调度方案；再规划是将未执行的全部任务看作完整方案，重新执行调度算法，适用于对反应速度不敏感的调度方案。修复策略包括右移、赶工2类，右移是在时间轴上将受增加或延时任务影响的任务向后移动，实现方案的鲁棒性，适用于针对干扰修复速度敏感的方案；赶工是通过调整任务参数实现部分或全部任务的执行时间对齐，适用于需要考虑时间、费用均衡问题或者时间、资源均衡问题的方案。联合作战方案在执行过程中，需要针对不确定性场景进行快速调度，宜采用修复中的右移方法。虽然目前右移研究较少，但是主动式调度方案中插入时间缓冲和资源缓冲的方法给右移策略提供了很好的借鉴，Leus提出了活动依赖浮动因子（activitydependentfloatfac?tor，ADFF）模型，VandeVonder等提出了资源流依赖浮动因子（resourceflowdependentfloatfactor，RFDFF）模型，可以作为改进右移方法的参考。

1.3.2基于资源流建模方法研究

资源流网络综合考虑任务间的协同关系和资源的流转关系，是一种有效的鲁棒性资源调度方法[16]，常见于主动式调度模型中针对时间不确定性的时间缓冲方法。从资源调度视角来看，资源不确定性、任务不确定性都可以转化为等待资源就绪的时间不确定性。故本文在任务和任务协同关系构成的任务网络的基础上构建资源流网络，通过任务子网和资源流子网的加权分析，研究战场态势变化带来任务增加不确定性的调度方案鲁棒性策略。

对于任务时间不确定性通常有概率描述、区间数和模糊数描述3种方式。概率描述的前提是通过历史数据分析出任务执行时间的概率分布函数；区间数方法是指通过统计，整理出任务执行时间的区间，采用的形式描述任务的执行时间，其中表示任务执行时间的下限，表示任务执行时间的上限；模糊数描述是结合历史数据和指挥员先验知识，采用隶属度函数来描述任务时间的不确定性。由于前2种方法都需要较大数据样本，而数据的稀少和战争的一次性、不可类比性，致使前2种方式具有很大局限性；基于模糊集的方法能够将历史数据和专家经验相融合，比基于概率的方法更符合实际和有效。本文采用三角模糊数对任务的执行时间、开始时间、结束时间进行描述，并将采用模糊数描述的任务构成的任务子网和资源流子网合称模糊网络。

对于求解策略，研究RCPSP问题产生几十年以来，国内外学者对求解方法的研究成果，可以将其划分为精确式方法和启发式方法2种。精确式求解方法包括分支定界法、整数规划法和枚举法等；启发式方法包括基于规则的启发式方法和元启发式方法。基于优先规则的启发式方法，常用的优先规则包括最小化完成时间、最小化资源总需求、最大化资源利用率等；元启发式方法是根据生物的运动形态抽象成的数学模型，包括遗传算法、蚁群算法、粒子群算法、禁忌搜索算法等。由于RCPSP 已经被证明为Non-deterministic  Poly-nomial-hard（NP-hard）问题，随着资源数量和资源约束的增加，算法复杂度成指数方式增长，所以启发式方法是一种有效的求解策略。在启发式算法中，遗传算法是目前应用较为成熟的一种方法，并被广泛用于任务规划、资源调度等领域。本文采用遗传算法对反应式模糊网络调度模型进行求解，并将这种融合遗传算法的模糊网络调度模型称为遗传模糊网络模型（Genet-ic Fuzzy Network, GFN） 。

2基于GFN 的联合作战资源调度建模

2.1 问题假设1）任务描述假设。采用AON 方式对任务子网和资源流子网进行描述，节点为任务和资源站，任务节点集合描述为，其中K 为任务总数，边为任务之间的资源流转关系和协同关系、资源站和任务之间的资源调度关系。增加虚拟开始任务节点Begin和虚拟结束任务节点End，为Begin 与任务子网的最早开始任务之间设置因果关系边，为End 与任务子网最后结束任务之间设置因果关系边，将全部资源站资源调入Begin 节点，任务所需资源除了Begin 节点外，全部通过任务间资源流转实现。

2）任务关系假设。任务之间存在协同关系和资源流转关系。 用于描述任务节点和之间的协同关系，具有方向性，并称为的协同前序任务，例如当Rqk 为因果协同时，表示 必须在 结束后才能执行；用于描述任务节点 和之间的资源流转关系，即资源从流转到。

3）任务优先级假设。任务优先级描述为Y={1, 2,3, …, M}，1 表示最大任务优先级，M 表示最小任务优先级，Y 值大的任务先分配资源，具有相同Y 值的任务在进行资源分配时不区分先后顺序。

4）执行模式假设。任务存在一种或多种执行模式，不同执行模式具有不同资源需求，在对任务进行资源分配前必须确定任务的执行模式，执行模式确定规则为，其中为任务执行时间最短规则，为获取可用资源时间最早规则。首先令，判断当前可直接使用资源是否满足全部模式的执行资源需求，如果只能满足该任务的一个模式，则选择该模式为任务执行模式，否则令，选择执行时间最短模式作为任务的执行模式，并将选定执行模式的资源需求向量作为任务的资源需求向量。

5）任务执行假设。任务必须在全部资源满足后才能执行，执行过程不可被中断，执行完毕后，释放全部资源。

6）资源类型假设。本文研究只针对可更新资源，也就是可以被重复使用的资源，例如飞机、舰艇、坦克等资源；不考虑不可更新资源，即消耗性资源，例如导弹、火箭弹、油料等。

2.2 模型参数1）：任务节点的协同前序任务集合，，q为的协同前序任务总数，协同前序任务即与之间存在直接或间接的协同关系，方向为。

2）U：资源集合，，其中i为资源种类标识，I为资源类型总量，j为资源站标识，J为第I类资源的资源站总量，为第i类资源第j站的资源数量。

3）：分配给任务Tk的第i类第j站资源数量。

4）：任务的资源需求，，i 为资源类型，I 为资源类型数量，为任务第i 类资源的需求量。

5）：任务的模糊开始时间。

6）：任务从资源所在位置机动到任务目标位置的时间，其计算公式为

其中，为第i 类第j 资源站的坐标，为任务的目标坐标，为第i 类第j 站资源的机动速度，的机动时间取全部资源运动到的最长时间。

7）：任务的模糊执行时间，由历史数据统计结合专家经验预先给出参数。

8）：第i 类第j 站资源的维护时间，预先给定参数。

2.3 调度模型

其中，式（2）表示RCPSP问题目标函数，要求联合作战方案执行时间最小；式（3）表示当两个任务之间存在因果协同关系时，这两个任务开始时间的约束；式（4）表示联合作战方案的总执行时间不能超过预定的战役总时长；式（5）表示时间取值约束，任务的开始执行时间必须为正模糊数；式（6）表示资源总量约束，在任何时刻Ht正在执行的任务占用第i类第j站资源总量不能超过第i类第j站资源总量；式（7）表示任务资源需求约束，只有任务的全部需求资源被满足后才开始执行。

2.4 鲁棒模型鲁棒模型是在调度模型产生的最优调度方案的基础上，通过增加反应式鲁棒性机制，提高调度方案的鲁棒性。本文鲁棒性针对任务增加和执行时间延长的不确定性，其中执行时间延长可以看作原任务按时完成并增加一个新的任务。对于任务增加，鲁棒性策略主要是寻找增加任务的最优插入位置，模型如下：

式（8）表示获取候选插入位置的规则，其中为新增任务，为的资源前序任务的开始时间，Hcur为方案执行过程中插入新增任务的时间，为的开始时间，为从 向流转的资源类型，为执行所需要的资源类型，为执行所需第i 类资源数量，为执行所需第i 类资源数量；式（9）表示候选插入位置的权重计算方法，其中为带插入位置的权重，表示 是否为基线任务，是则=1，不是则=0，基线任务为从虚拟开始任务到虚拟结束全部路径中总时间最长路径上的任务集合，表示调度方案所有任务节点出度的最大值，表示是否为基线任务，是则=1，不是则=0，表示 和之间存在资源流边，表示和之间存在协同边；式（10）表示最优插入位置选择规则，K 为候选插入位置数量。

3实验验证

3.1 实验环境介绍以红蓝双方海、空、导、网电多维联合体系对抗想定为背景，设计22个任务，如图1所示。

图1任务子网示意

Fig.1Tasksubnetdiagram

任务的优先级取值范围Y={1,2,3}，每个任务的优先级采用随机赋值；任务间的协同关系取值范围={1,2}，表示任务节点和之间的关系为因果协同关系，即执行完才能执行，=2表示任务节点和之间的关系为时间协同关系，即和必须同时开始执行；任务目标区域随机生成。

设计9类14站资源，空间位置随机生成，数量如表1所示。

3.2 基于遗传算法的调度模型求解3.2.1预处理

预处理的目标是将任务网络根据任务关系类型，转化为任务深度网络，为任务深度网络中的每一个任务赋予深度层信息，具有协同、并发关系的任务处在同一深度层，具有因果关系的任务处在不同深度层，进行资源分配时逐深度层展开，这是一种用空间换时间的算法优化方法，乔士东在其基于个体修正的MMGRCP-SP（multi- mode generalized resource constrained project scheduling）算法中也采用了该方法。

3.2.2遗传编码

设计染色体的编码是遗传算法的关键问题，按照基因位的符号类型，可以划分为二进制编码、实数编码、字母编码等，在资源调度领域，按照基因所表示的含义，可以划分为随机优先级编码、时间编码、资源编码等，张迎新的资源调度算法和何立华的FDFRCPSP（fuzzy duration and fuzzy resource-constrained project scheduling problem）算法采用的是随机优先权编码， Kevin M. Calhoun 的MMGRCPSP 算法和乔士东基于个体修正的MMGRCPSP 算法就是采用的时间编码。由于随机优先权编码为整数编码，且基因位数少，计算机处理速度快，故采用随机优先权编码。

3.2.3遗传解码流程

采用串行调度生成机制（serial schedule generation scheme，SSGS）方式将染色体解码成一个满足资源约束的调度方案，解码需要考虑任务深度、任务优先级、随机优先级和任务执行模式优先级4 个因素。解码流程分为资源流网络生成和时延计算2 个子流程（图2）。

图2 解码流程

Fig. 2 Decoding process

其中资源流网络生成子流程如下。

1）初始化。

设置虚拟开始节点时间参数：

设置两个任务和，存储已完成资源分配任务节点，存储未分配资源队列，并将任务Begin 放入，其他任务全部放入。

2）对中任务排序。

按照任务的深度值 E 对中任务进行升序排序，深度值越小位置越靠前，相同深度值的任务不区分先后顺序。

按照任务优先级Y={1,2,3}对具有相同深度值的任务进行升序排序，1 表示最大任务优先级，3 表示最小任务优先级，表示任务的优先级越高，位置越靠前，具有相同Y 值的任务不区分先后顺序。

按照随机优先级X={1, 2, …, K}对当前深度层具有相同E 值和Y 值的任务进行升序排序，K 为任务的数量，任务的X 值越大，表示任务的优先级越高，位置越靠前。

3）调度终止测试。

获取中第一个任务为当前任务，如果为End 任务，则转入步骤8），否则转入步骤4）。

4）计算当前任务资源需求向量。

针对当前任务，根据2.1 小节模式优先级规则假设选择执行模式，并将选定执行模式的资源需求向量作为任务的资源需求向量。

5）生成当前任务的资源流边。

按照任务结束时间依次获取中任务，如果包含当前任务需要的资源，根据任务的资源剩余数量和的需求数量在 与之间生成资源流边，资源流向为，如果中所需的第i 类资源来自多个资源站，则依据公式（13）计算需要调度的资源站

其中，表示资源流边调度任务中的资源站，表示第i 类、第j 站资源的坐标，J 表示第i 类资源的资源站总量，表示任务目标区域的坐标，

为第i类第j 站资源的机动速度，min 表示获取第i 类资源中最近资源站的资源。

6）当前任务模糊时间计算。

根据当前任务生成的资源流边，获取的资源前序任务集合，资源前序任务即当2 个任务节点和之间存在资源流边，称为的资源前序任务计算的模糊开始时间，公式为

并根据的模糊开始时间、模糊执行时间、机动时间计算结束时间，公式为

7）更新。

将Tk 放入，并转入步骤3）。

8）终止。

根据公式（10）计算End 的模糊开始时间，并将End 添加到。为遗传算法的适应度计算参数。

时延计算就是在资源流子网的基础上，根据模糊任务子网的任务协同关系，计算每个任务因为协同关系产生的延迟，该子流程步骤如下。

1）获取当前任务。

依次从中获取一个任务作为当前任务。

2）更新当前任务的任务结束时间。

获取的全部协同前序任务，依次根据和之间的协同关系，计算给带来的执行时间延迟，计算规则为

其中，为的任务结束时间，为的任务开始时间，为的任务开始时间。

最后根据的任务开始时间计算其任务结束时间，计算公式为（10）。

3.2.4 遗传选择

采用轮盘赌方法进行选择操作，首先生成随机数，然后根据式（16）进行选择计算

式中s 为种群规模，g(x)表示适应度函数。然后根据式（17）求其对应的适应度函数

其中为虚拟结束任务End 的模糊开始时间的α 截集。

3.2.5遗传交叉操作

交叉操作是随机选择2 个父代染色体，根据交叉概率进行重组，以形成子代染色体，其作用是让遗传算法进行全局寻优，交叉的方法有单点交叉、多点交叉等， 本文采用单点交叉操作。随机优先级染色体的交叉操作步骤如下。

1）设置交叉概率。

2）随机选择两个染色体和作为交叉操作的父代，交叉操作的两个子代用和表示。

3）随机生成交叉操作概率，当时，执行交叉操作。

4）生成随机整数作为交叉点，K 为任务总数，交叉点前面的父代基因直接继承，交叉点后面的基因进行交叉操作。

5）在交叉操作中，需要考虑优先级的唯一性，和交叉点后基因值相同的基因位通过顺序右移操作后直接交叉，基因值不一致的基因位需要进行变换后再进行交叉操作，如图3 所示。

图3  交叉操作示意

Fig. 3 Cross diagram

3.2.6 遗传变异操作

变异操作是根据变异概率，随机选择染色体的一个基因位，并改变该基因位的基因值，作用是局部寻优。具体流程如下。

1）设置变异概率。

2）选择一个染色体，并产生随机数。

3）如果，则随机选择一个变异基因位，执行变异操作。由于随机优先级需要保证优先级的唯一性，所以会产生受影响基因位，如图4 所示。

图4   变异操作示意

Fig. 4 Mutation diagram

3.2.7 实验结果

采用 0.9 的交叉概率，0.03 的变异概率，种群规模

30，遗传代数30，结果如图5、6 所示。

图5 基于GFN 的调度方案

Fig. 5 Scheduling scheme based on GFN

图6 GFN 调度模型遗传优化数据

Fig. 6 Genetic optimization data of GFN scheduling model

图6显示GFN模型的调度解在第16代开始收敛于738，图5显示收敛后的联合作战资源调度结果。

3.3 反应式鲁棒模型测试假定正在利用某兵棋系统对联合作战方案进行推演，当前作战时间随机生成，且满足

其中表示联合作战方案中描述的推演开始时间，表示联合作战方案描述的预定推演结束时间，表示根据随机算法生成的当前作战时间。

随机生成一个任务，任务的资源需求中包含3个类型，数量随机赋值，针对染色体适应度为738的染色体，进行2个随机插入任务实验：一是利用优化算

法选择任务的插入位置，计算优化后时延；二是在候选可插入位置中随机产生插入位置，并计算其平均实验。实验结果如图7所示。

图7GFN鲁棒策略实验结果

Fig.7ExperimentalresultsofGFNrobuststrategy

图7中红色折线表示采用传统右移方法插入随机任务产生的时延，蓝色折线表示采用本文设计反应式鲁棒模型优化后插入随机任务产生的时延，实验结果显示，本文设计的反应式鲁棒模型在处理任务不确定性时优于传统右移方法。

3.4 结果分析目前对于鲁棒性调度方案的分析，存在解鲁棒性和质量鲁棒性2种方法。解的鲁棒性又叫方案稳定性，是指将调度方案中任务的预定开始时间和执行时的实际开始时间的偏差作为鲁棒性评估指标；质量鲁棒性不关心任务实际执行时间的分布，而是选择方案执行总时长、方案总成本最小等效能参数作为鲁棒性评估指标。对于联合作战方案来说，在执行过程中任务的高度不确定性，决定了解鲁棒性难以对其进行有效分析，需要采用总时长、总资源消耗量等质量鲁棒性类指标。由于战争以取胜为最终目标，信息化战争中，缩短我方“OODA”循环时间，提高调度方案时效性，关乎战争胜败，故选用方案总时长最短作为评估指标。根据实验，基于GFN的反应式调度模型，借鉴了主动式调度模型中的时间缓冲因子计算方法，相对于传统直接右移式修复模型，具有更好的鲁棒性。

4结论

针对联合作战筹划过程中面临的不确定性资源调度问题，提出了基于遗传模糊网络的反应式调度模型，该模型分为调度和鲁棒2个子模型，通过实验验证了调度子模型在处理存在时间、资源不确定性联合作战资源调度问题时的有效性，验证了鲁棒模型在方案执行过程中抗任务不确定性干扰的有效性。遗传模糊网络模型与传统不确定性资源受限项目调度模型的明显区别，就是突出了方案执行过程中的任务不确定性，并利用反应式鲁棒子模型来处理这种不确定性。但是模型对联合作战方案进行了大量简化，实际作战中，任务类型、任务协同关系，远比实验想定中的复杂，要想将模型进一步应用于实践，还需要对模型进行进一步优化完善。

参考文献（略）

作者：刘兆鹏，司光亚，唐宇波，柳少军

※ ※ ※

创新体系工程基础理论和方法

推动系统工程理论再发展