基于优先排序与粒子群优化的装备保障任务规划方法

彭鹏菲，于钱，李启元（海军工程大学电子工程学院，湖北武汉430033）



基于优先排序与粒子群优化的装备保障任务规划方法

彭鹏菲，于钱，李启元
（海军工程大学电子工程学院，湖北武汉430033）

摘要：针对装备保障任务规划过程中保障资源占用冲突及保障任务逻辑关系约束的实际问题，构建基于任务优先排序的解空间模型，并进一步提出基于优先排序与改进粒子群优化的装备保障任务规划方法。该方法将分解后的保障任务按照其重要性和逻辑顺序进行优先排序，并根据排序结果对粒子群优化算法得到的任务与资源匹配解空间进行调整，以解决资源占用冲突和逻辑顺序问题。为保证每次迭代后的粒子为可行解，提出不可行粒子的多维异步处理机制，提高了粒子群优化算法的搜索效率。通过实例应用仿真分析，验证了该方法在装备保障任务规划中的有效性和优越性。

关键词：兵器科学与技术；装备保障；任务规划；优先排序；粒子群优化；异步处理

0　引言

装备保障方案是指依据装备使用特点和上级保障决心，以完成保障任务及实施相应措施的基本设想［1-2］。其中，装备保障力量的编成及部署是装备保障方案的核心内容，关键问题是装备保障任务的规划，即保障任务与保障资源间的匹配。装备保障任务由装备保障部门根据保障需求来确定，装备保障资源是指保障作战行动所需要的弹药、装备、人员等［3］。信息化条件下，保障任务属性、保障资源属性、保障时限和保障环境等多种因素均会影响到装备保障任务规划。因此，运用更加有效的保障任务规划方法能够进一步优化装备保障方案，缩短响应时间，对实现装备保障的精确化、信息化及智能化具有重要意义。

对于任务规划问题的解决通常有两类方法：第一类方法是致力于寻找最优解的精确求解方法，通常包括整数规划、分支定界法以及枚举法［4］，这类方法求解中占用大量计算机内存，并且求解时间较长［5］，不适用于问题规模较大、约束复杂、实时性强的任务规划问题。第二类方法是启发式方法，包括各类规划表算法［6-7］以及蚁群算法、遗传算法［8-9］等。启发式方法基于直观以及经验构造，在可以接受的时间与空间开销范围内求解出约束之下问题的可行解。其中，粒子群优化算法具有编码简单、易于实现等特点，而且具有更强的全局搜索及快速收敛能力。

当前面临的装备保障任务规划是一个典型的多约束离散优化问题，其任务间存在一定的逻辑关系，资源存在占用冲突。而传统的粒子群优化算法只能完成任务与资源的匹配，但无法对资源占用冲突问题以及任务逻辑关系的约束进行很好处理。因此，本文提出采用任务优先排序的方法对粒子群优化算法求解的解空间进行规划，以解决考虑资源占用冲突及任务逻辑关系的任务规划问题；同时，引入了多维异步［10］的粒子调整处理机制，从而给出了基于优先排序与改进粒子群优化的装备保障任务规划方法，真正实现了装备保障任务规划与调配的科学性和有效性。

1　问题描述

装备保障辅助决策中的关键问题是装备保障任务的最优规划［11］，而装备保障任务规划问题实质上是保障任务、保障资源和保障时间三者之间的匹配问题，而保障任务、保障资源及保障任务和保障资源之间通常存在着复杂的约束关系。在任务与资源的匹配过程中，通常须严格按照逻辑顺序的先后进行资源分配；对于没有严格逻辑关系的任务，则需要对任务进行优先排序，排序在前的优先占用资源，以解决资源占用冲突。

1.1保障任务、保障资源与保障时间

1）保障任务的分解及描述。根据保障任务的性质、保障装备的类型以及保障地点，对保障任务进行分解，得到子任务。对保障任务分解的目的是保证分解后的子任务能够由某个资源独立完成，不需要其他资源参与。保障任务的数学模型为

式中：T表示整个装备保障任务；Tj表示子任务，｛Tj｝表示子任务集合；n表示子任务的总数；GT= ｛G_S，G_B｝表示各个子任务之间的关系，G_S表示顺序关系，G_B表示并发关系；ATj表示对应子任务的属性，ATj=｛EqTj，MountTj，LocTj，StartTj，EndTj｝，EqTj表示装备，MountTj表示装备数量，LocTj表示保障任务的部署位置，StartTj表示任务的开始时间，EndTj表示任务的结束时间；（2）式表示原任务TOj分解后对应的子任务集为｛Tp，Tp+1，…，Tq｝，是子任务集｛Tj｝的子集；p、q为子任务的编号。

2）保障资源的分解及描述。将保障资源按照保障装备类型、保障单位及保障性质进行分解，得到子资源。分解后的子资源均具有单独承担某项或某几项子任务的能力，且均能同时被占用。保障资源的数学模型为

式中：Ci表示子资源；YCi表示子资源间的约束；ACi= ｛EqCi，UnitCi，LocCi，TimeCi，vCi，StateCi｝表示保障资源的属性，属性包括可保障装备、保障单位、所在位置、单枚保障时间、机动速度和空闲状态；（4）式表示原资源COi分解后对应的子资源集为｛Cp，Cp+1，…，Cq｝，是子资源集的子集。

3）保障时间的描述。子任务占用不同子资源，其执行时间是不同的。将子任务与子资源匹配的相应执行时间用矩阵表示为

式中：tcij表示任务Tj与资源 Ci匹配的执行时间，“tcij=—”表示对应的任务与资源不可匹配。

1.2基于优先排序的解空间构建

而对于一系列的任务，通过任务的优先排序可以对任务-资源的解空间在时间上进行规划，为各任务分配执行时间，以解决装备保障任务规划的资源占用冲突问题。

1）解空间模型装备保障任务规划是求保障任务与保障资源匹配可行解的离散问题，其匹配结果可用一个0-1矩阵表示。n个任务与m个资源匹配的可行解矩阵为

式中：sij表示任务Tj和资源Ci之间的匹配结果，其取值为1表示任务Tj占用资源Ci，0表示任务Tj未占用资源Ci.S矩阵的各列表示任务被执行情况，即表示任务被执行。S矩阵的各行表示资源被占用的情况，在某一时刻：，表示资源空闲；，表示资源被占用；，表示资源占用发生冲突。可行解矩阵中每个任务与资源的匹配是可行的，即资源可以满足任务的执行。在（6）式中，对于每一个具体的可行解矩阵，各子任务的执行时间timeTj是确定的，但子任务的开始时间和结束时间是未知的。在可行解矩阵已知的情况下，为了求解任务的开始时间和结束时间，还需要对任务与资源匹配的解空间在时序上进行调整。约束条件为

式中：ΩCd表示在资源Cd上发生占用冲突的任务集合，d为资源编号；StartTa和 EndTa分别为子任务 Ta的开始时间和结束时间，其执行的起止时间表示为［StartTa，EndTa］（其中EndTa=StartTa+timeTa），其他子任务起止时间的表示方式与Ta相同；a、b为子任务的编号。（6）式的意义是：同一时刻不存在多个子任务占用一个资源；另外，对于带有顺序关系的子任务Ta和Tb，其逻辑顺序为Ta→Tb.根据其顺序关系，解空间按照（8）式约束进行规划：

通过调整任务执行的起止时间对解空间进行规划，直至满足（7）式和（8）式的约束条件，最终解空间模型为

（9）式意义为：任务Ta在时间段［StartTa，EndTa］被资源Cd执行。

2）优先排序。要满足（7）式和（8）式的约束条件，需要对子任务进行优先排序，排序包括两个方面：1）资源占用冲突时子任务的优先顺序；2）子任务执行先后的逻辑顺序。根据子任务的排序对解空间进行时序规划，即排序在前的子任务优先占用冲突资源，且具有逻辑顺序的子任务要严格按照时序关系占用资源。由于任意子任务间都有可能出现资源占用冲突的情况，因此需要对所有子任务进行优先排序，各子任务优先排序表为

式中：aj表示任务的序号，序号越靠前表示该任务的优先级越高。对于带有顺序关系的子任务，必须严格按照其逻辑先后的顺序执行，具有强制性。为了计算和表示方便，对于（10）式的任务优先排序需要根据子任务的逻辑顺序进行调整，使其优先顺序与逻辑顺序相一致。调整后得到的优先排序表为

式中：pj表示任务的序号，意义同aj.对于所有的子任务在发生资源占用冲突的情况下，对其时间分配进行调整。对于具有逻辑顺序关系的子任务，在时间分配上还应强制其符合逻辑顺序要求，如（8）式。

2　基于优先排序与改进粒子群优化的装备保障任务规划

装备保障任务规划的目的是针对现有保障任务对保障资源进行编成和部署［11］。结合装备保障任务规划的数学模型，对传统离散粒子群优化算法进行了适应性改进：1）采用多维异步的处理机制调整粒子的位置，保证每一次迭代粒子的可行性，即资源与任务之间可匹配；2）对于解矩阵中的资源占用冲突情况和子任务逻辑顺序关系约束，则通过优先排序的方法使各子任务按照一定的顺序占用资源。经过改进的粒子群优化算法能够实现保障任务和保障资源在时间上的最优规划，具体步骤如下：

1）粒子编码。每个粒子表示任务与资源匹配的一个解，根据（6）式中的解矩阵S构建粒子：用矩阵各列的行标作为粒子的各个维，粒子各维表示的意义为各个子任务所占用的资源序号。粒子k的位置和速度数学表示为

式中：xkj（t）∈［1，2，…，m］表示t时刻第k个粒子、第j个子任务在资源序列（共m个资源）中的位置；vkj（t）表示相应粒子的速度。

2）初始化。粒子群的初始化实际上是对每个粒子的位置和速度的初始化［12］。对粒子k位置的初始化实质上是给各个子任务选定一个资源，需要注意的是粒子的初始位置必须是可行的（任务与资源可匹配）；对粒子速度的初始化就是对进行第一次迭代的粒子各维移动距离的初始化；根据问题规模设置种群大小N；计算各粒子适应函数值，初始个体最优位置pBest和全局最优位置gBest.

3）粒子移动。移动速度的调整根据（14）式：

式中：ω是惯量权值；c1和c2为加速因子；r1和r2为［0，1］区间上的随机数［13］。通过向量的计算对粒子速度的各维进行改变，为防止粒子过快地从搜索空间的一个区域飞向另一个区域，将粒子各维速度限制在［-vmax，vmax］范围之内，即

式中：vmax应小于粒子活动范围，这里活动范围指可用子资源的个数。

4）位置的更新与越界修正。

式中：对粒子的位置坐标值进行四舍五入取整处理，对于越界的粒子，其越界的维取靠近的边界值。

5）解空间异步处理。粒子的某个维不可行时，如果按照迭代速度继续更新位置，将改变所有维，既降低了搜索效率，又容易错过最优位置。针对这种情况，对粒子进行异步处理，只对不可匹配的粒子维进行改变，其他维保持不变。处理方法为：将速度矢量中将匹配可行的维置为0，将其他各维置为原值，按照重置的速度继续更新粒子位置，直到粒子所有维的匹配均为可行。

6）基于优先排序的解空间规划。

①对各子任务进行排序，并结合子任务逻辑顺序生成子任务优先排序表，如（11）式。

②对于每一次迭代得到的任务与资源匹配的解矩阵，按照子任务的优先排序表依次对各子任务进行时间分配，每次分配后相应资源被占用的时间段将会被标记，后续的任务将不能在该时间段内占用此资源。为了减少资源处于空闲状态的时间，对于资源占用冲突的子任务Ta和Tb（Ta优于Tb），做如下处理：

③对于带有逻辑顺序的子任务时间分配，首先按照②处理。然后判断其是否满足（8）式，对于不满足的情况，对逻辑顺序的子任务（Ta→Tb）按照（17）式进行处理，如果处理后发生资源占用冲突，则将该子任务排至该资源当前被占用时间段的最后，使其强制满足时序要求，并避免资源占用冲突。

7）保障任务的时限约束。任务完成的时间必须小于给定的时限，总时限约束为mtot，单个时限约束表示为

式中：timeTa表示任务Ta的执行时间；mTa为任务Ta完成的时限约束。

8）计算适应值。考虑以最短保障时间为目标，通过计算所有子任务的最长结束时间来得到保障任务完成的最终时间。其适应度函数为

9）算法结束。通过迭代次数E判断算法是否终止。经过E次迭代之后，获取当前全局最优粒子，即为装备保障任务规划的最佳方案。

算法流程如图1所示。

3　应用实例及对比分析

3.1应用实例

某个装备保障任务描述为：在大规模联合火力打击海上作战的背景下，我方出动多艘舰艇执行某海上作战任务，需完成相应的各类技术准备、临抢修等装备保障任务，该任务可进一步分解为10个子任务：｛T1，T2，T3，T4，T5，T6，T7，T8，T9，T10｝，保障任务完成的总时限为mtot=18，单个子任务完成时限约束为mT8=5.其中的带有顺序关系的任务及其顺序为T3→T4→T5.子任务的优先排序为P=（1，3，7，4，9，2，5，8，6，10）（数值为子任务的序号），可用保障资源分为12个子资源：｛C1，C2，C3，C4，C5，C6，C7，C8，C9，C10，C11，C12｝.分别使用粒子群优化和遗传算法对实例进行对比仿真，各子任务对应各子资源的执行时间矩阵T_C（单位：h）为

图1　算法流程图Fig.1 Flow chart of algorithm

3.2算法初始化

1）改进粒子群优化算法初始化。各参数初始赋值如表1所示。粒子初始种群和初始速度由随机方式产生，并满足任务与资源的匹配限制。

表1　改进粒子群优化算法参数初始值表Tab.1 Initial value table of PSO algorithm parameters

2）遗传算法初始化。实例中共有10个子任务和12个子资源，因此遗传编码的染色体有种基因。染色体编码为0-1编码［9］，对染色体进行随机初始化，并将不合法的基因（任务与资源不能匹配）置为“0”。其余初始参数与粒子群优化算法相同。

3.3仿真结果与分析

1）对比仿真。对实例的应用求解过程进行数值仿真。图2为本文中提出的粒子群优化算法得到的仿真结果，粒子群体经过85次迭代后收敛至最优适应值，为14.5 h；图3为由遗传算法得到的仿真结果，算法进化至150次获得最优适应值为14.7 h.

由图2和图3对比可知，改进的粒子群优化算法收敛速度明显快于遗传算法，且优化效果更好（14.5 h＜14.7 h）。另外，在装备保障任务规划问题中，遗传算法存在编码复杂、计算速度慢等特点。仿真结果对比如表2所示。

图2　改进粒子群优化算法最优适应值变化曲线Fig.2 Changing curve of PSO adaptive value

图3　遗传算法最优适应值变化曲线Fig.3 Changing curve of GA adaptive value

表2　仿真结果对比表Tab.2 Comparison of simulated results

2）装备保障任务规划方案。根据仿真计算结果，此时最优解粒子的位置gBest=［10 3 5 6 6 7 6 4 5 10］，gBest对应的最优解矩阵为

图4是基于优先排序和粒子群优化算法得到的装备保障任务规划甘特图，表示任务与资源在时序上的分配结果。

图4　装备保障任务规划甘特图Fig.4 Gantt chart of equipment support task planning

每次迭代后，都要基于优先排序对匹配结果进行规划。根据优化结果（见图4）可得到：①子任务的执行时间满足T3→T4→T5的逻辑顺序；②T3和T9均占用资源C5，根据子任务优先排序表P=（1，3，7，4，9，2，5，8，6，10）（T3在前，T9在后）对两个任务的执行时间进行解空间规划，得到两个任务执行的起止时间按照优先排序表错开的匹配结果，解决了资源占用冲突的问题；③对于T1和T10均占用资源C10以及T4、T5和T7均占用资源C6的情况，均按照优先排序原则进行了合理规划。

4　结论

本文针对装备保障任务规划的求解问题，对传统的粒子群优化算法进行了适应性改进，通过引入多维异步处理机制提高了粒子群优化算法的搜索效率；同时，将任务优先排序思想与粒子群优化算法相结合，提出了基于优先排序和改进粒子群优化的装备保障任务规划方法，从而有效解决了装备保障任务规划中保障资源占用冲突问题和保障任务逻辑顺序关系处理问题。结合具体的应用实例，将该方法与遗传算法的求解过程及应用效果进行了相应的对比仿真求解与分析，从而进一步验证了方法的有效性和优越性。仿真分析表明：提出的方法充分考虑了任务规划的时序关系，通过优先排序解决了资源占用冲突问题，并与改进的粒子群优化算法相结合，能够很好地解决装备保障任务规划及保障方案拟制过程中的关键问题，与基于遗传算法的求解相比，具有更好的快速收敛性，应用简捷，易于实现。

参考文献（References）

［1］ 高飞，徐英，张英，等.基于军事概念模型的装备保障方案生成研究［J］.价值工程，2010，29（28）：112-113. GAO Fei，XU Ying，ZHANG Ying，et al.Equipment support plan evaluation software designing based on the military conceptual mode［J］.Value Engineering，2010，29（28）：112-113.（in Chinese）

［2］ 杨英杰，张柳，聂成龙，等.使用阶段装备保障方案评价研究［J］.火力与指挥控制，2015，40（10）：5-7. YANG Ying-jie，ZHANG Liu，NIE Cheng-long，et al.The evaluation research summary of equipment support concept in operational phase［J］.Fire Control&Command Control，2015，40（10）：5-7.（in Chinese）

［3］ 朱石坚.舰船装备保障资源需求半结构化预测方法［J］.海军工程大学学报，2015，27（4）：54-59. ZHU Shi-jian.Semi-structural prediction method study on support resources demand of warship equipment［J］.Journal of Naval University of Engineering，2015，27（4）：54-59.（in Chinese）

［4］ 李敏.资源约束下多项目调度问题遗传算法研究［D］.杭州：浙江大学，2008. LI Min.Research on genetic algorithm of resource constrained multi-project scheduling problem［D］.Hangzhou：Zhejiang University，2008.（in Chinese）

［5］ 黄敏镁，江涛.资源约束项目调度问题研究综述［J］.科协论坛，2007（2）：45-46. HUANG Min-mei，JIANG Tao.Comprehensive description of resource constrained project scheduling problem［J］.Science& Technology Association Forum，2007（2）：45-46.（in Chinese）

［6］ Levchuk Y N，Levchuk G M，Pattipati K R.A systematic approach to optimize organizations operating in uncertain environments：design methodology and applications［C］//7th International Command and Control Research and Technology Symposium.Quebec City，QC，Canada：IC2I，2002：170-230.

［7］ Levchuk G M，Levchuk Y N，Luo J.Normative design of organizations-part I：mission planning［J］.IEEE Transactions on Systems，Man and Cybernetics，2002，32（3）：346-359.

［8］ 邓向阳，张立民，黄晓冬.一种基于蚁群优化的装备保障任务调度方法［J］.计算机工程，2013，39（2）：284-287. DENG Xiang-yang，ZHANG Li-min，HUANG Xiao-dong.An equipment support task scheduling method based on ant colony optimization［J］.Computer Engineering，2013，39（2）：284-287. （in Chinese）

［9］ 张杰勇，姚佩阳，周翔翔，等.基于DLS和GA的作战任务-平台资源匹配方法［J］.系统工程与电子技术，2012，34（5）：947-954. ZHANG Jie-yong，YAO Pei-yang，ZHOU Xiang-xiang，et al.Approach to operation task and platform resource matching based on DLS and GA［J］.System Engineering and Electronics，2012，34（5）：947-954.（in Chinese）

［10］ 陈君彦，齐二石，刘亮.多维异步随机扰动的粒子群优化算法［J］.计算机应用，2009，29（12）：3267-3269. CHEN Jun-yan，QI Er-shi，LIU Liang.Particle swarm optimization algorithm with multi-dimensional asynchronism and stochastic disturbance［J］.Journal of Computer Applications，2009，29（12）：3267-3269.（in Chinese）

［11］ 张春润，熊林伟，赵坤，等.装备保障任务规划系统体系结构研究［J］.中国管理信息化，2012，15（16）：55-57. ZHANG Chun-run，XIONG Lin-wei，ZHAO Kun，et al.Research on the system architecture of the equipment support task planning system［J］.China Management Informationization，2012，15（16）：55-57.（in Chinese）

［12］ 黄竞伟，朱福喜，康立山.计算智能［M］.北京：科学出版社，2010. HUANG Jing-wei，ZHU Fu-xi，TANG Li-shan.Computational intelligence［M］.Beijing：Science Press，2010.（in Chinese）

［13］ 郭文忠，陈国龙.离散粒子群优化算法及其应用［M］.北京：清华大学出版社，2012. GUO Wen-zhong，CHEN Guo-long.Discrete particle swarm optimization algorithm and its application［M］.Beijing：Tsinghua U-niversity Press，2012.（in Chinese）

中图分类号：TP301；E917

文献标志码：A

文章编号：1000-1093（2016）06-1082-07

DOI：10.3969/j.issn.1000-1093.2016.06.016

收稿日期：2015-10-14

基金项目：湖北省自然科学基金项目（2014EKB013）

作者简介：彭鹏菲（1977—），男，副教授。E-mail：pengpengfei@126.com

A Planning Method of Equipment Support Task Based on Priority Ordering and Particle Swarm Optimization Algorithm

PENG Peng-fei，YU Qian，LI Qi-yuan
（College of Electronic Engineering，Naval University of Engineering，Wuhan 430033，Hubei，China）

Abstract：A solution space model based on task priority ordering is constructed according to the practical problem of support resource occupancy conflicts and logical relationship among support tasks in the process of equipment support task planning.A planning method of equipment support task based on priority ordering and improved particle swarm optimization is further proposed.In the proposed method，the decomposed support tasks are ordered by priority according to their importance and logical order.According to the sorted results，the task and the resource matching solution space obtained by the particle swarm optimization algorithm are adjusted for solving the problem of resource occupancy and logical sequence.A multi-dimensional asynchronous processing mechanism is proposed to ensure that the particles are feasible，so that the search efficiency of the particle swarm optimization algorithm is improved.The effectiveness and advantage of the method in the planning of equipment support tasks are verified by examples and contrastive simulation analysis.The method has broad application prospects in the field of equipment support assistant decision-making technology.

Key words：ordnance science and technology；equipment support；task planning；priority ordering；particle swarm optimization；asynchronous processing