作战工程保障行动中的一种战士- 装备- 任务指派模型及其求解

张超省， 王健， 李政民， 杨鑫

(陆军工程大学 训练基地， 江苏 徐州 221004)

0 引言

信息化战争条件下，只有能够快速实现作战力量机动、转移和部署，才能在瞬息万变的战场态势下捕获制胜先机，这也对承担机动保障、战斗支援等一系列作战工程保障任务的工程保障部队提出了更高要求。面对具体工程保障行动，指挥员必须精准、高效地制定出指派哪些战士操作哪些装备执行哪些任务的决策。通常，制定决策时需要考虑以下3个方面问题：

1)一般情况下，战士不会徒手完成任务，而是要操作装备，并且工程保障部队的战士多数被培养成多技能操作手。指派战士完成任务必须既要考虑到战士的操作水平对装备作业效率的影响，还要考虑到装备自身的技术状态会导致装备作业效率的差异。比如一个技术熟练的操作手操作一台装备显然比一个技术一般的操作手操作同台装备耗时更短、效率更高，同一个战士操作一台性能完好的装备显然比操作一台性能堪用的同型装备耗时更短、效率更高。

2)战场环境下，上级对工程保障任务完成时间需求非常迫切，通常需要尽可能多的装备协同作业以求最快完成任务；然而，多台装备在同一地域协同作业完成一项任务时，由于场地限制或配合影响，过多装备甚至会使彼此妨碍。比如两台甚至三台挖掘机协同挖掘大型平底坑，配合过程中不可能完全独立同步开展，必然有一定程度的彼此干涉，总作业效率显然比几台装备作业效率简单相加要小。

3)信息化战争条件下，工程装备也逐渐向多功能方向发展，可以执行多种任务。尽管战士具备多项技能，然而考虑到长时间操作产生疲劳进而带来效率降低和安全隐患，允许工程装备不间断执行多种任务，但是操作装备的战士只能执行一项任务，也就是作战工程保障行动中常说的“人歇车不歇”原则。比如某型多用途工程车，既可以进行挖掘作业，也可以进行装载作业，可以让该装备连续执行挖掘和装载两项任务，尽量不让操作该装备的战士连续疲劳作业去执行两项任务。

综上所述，作战工程保障行动中任务的完成既与操作装备的战士相关，又与战士操作的装备相关，还与“人歇车不歇”以及协同作业效率相关，本质上是一个多约束、多维度的指派问题，属于非确定性多项式- 难问题(NP-Hard问题)。

目前，分析作战工程保障行动中人员任务指派问题的研究文献尚不多见，但仍有一些其他领域的研究成果对解决前述问题具有一定的参考价值。经典指派模型仅研究一人一事、一事一人的指派问题，既不涉及装备性能的差异，也不涉及协同作业的情形，因此不能直接被用来解决上述问题[1]。文献[2]针对柔性生产系统中多技能工人不同技能熟练水平的情况，在不考虑工具影响工人工作效率的情况下，提出了一种多技能工人的分配模型。文献[3-4]考虑了维修人员的技能分级和休息时间，建立了一个适用于多技能维修人员的任务指派模型。文献[5]则考虑了维修人员的疲劳积累对维修能力的影响，建立了一个适用于维修单元的任务指派模型。文献[6]针对任务中存在并行作业环节的情况，设计了一种改进匈牙利算法，从而解决包含并行环节的指派问题，但在并行作业环节中人员是独立作业，并不存在协同作业的情形。文献[7]针对某项任务需要多人协同作业的情形，建立了非线性的指派模型，但仅给出了两人协作完成某项任务的求解过程。文献[3-7]无一例外都是二维指派问题，只考虑人员和任务之间的指派关系，不涉及其他中间环节的约束。文献[8-10]针对人力资源管理、多传感器多目标追踪、数据融合等领域的问题，分别建立了相应的三维指派模型；虽然其模型形式与本文所描述问题相差较大，但其建模过程值得借鉴。另外，上述研究也从另一角度说明了本文研究的指派问题并不是孤立的理论问题，而是一类极具应用价值的实践问题。

本文创新性主要包括以下3个方面：1)通过对作战工程保障行动特点的分析，将工程保障行动中任务的派遣定义为一个由“战士- 装备- 任务”构成的三维指派问题；2)综合考虑战士的多技能、装备的多功能以及多台装备协同作业的相互影响，建立了作战工程保障行动的三维指派模型；3)基于“人歇车不歇”的原则，设计了虚拟装备法，实现了三维指派模型的快速求解。

1 三维指派模型建立

假设某项工程保障行动可以分为l项阶段任务串联执行，指挥员要指派n名战士操作m台装备完成l项阶段任务，其中n>m. 为了解决上述指派问题，按以下步骤构建指派问题的数学模型：

1)定义决策变量为

(1)

式中：xijk=1表示第i个战士被指派操作第j台装备完成第k项任务，xijk=0表示第i个战士未被指派操作第j台装备或未被指派完成第k项任务。

2)按照“人歇车不歇”原则，每名战士最多被指派去执行一项任务，因此必须满足如下约束条件：

(2)

3)按照“人歇车不歇”原则，每台装备都应该尽量多地参与各个阶段的任务，但同时应该满足该装备的参与不会导致整体作业效率的降低，也即某台装备可能参与多个阶段任务，也可能不参与任意一项阶段任务，因此必须满足如下约束条件：

(3)

4)每个阶段任务的完成最少需要一台装备，参与的装备数量最多不超过具有完成该项任务功能的装备数量mk，因此必须满足如下约束条件：

(4)

5)引入tijk表示第i个战士操作第j台装备独立完成第k项任务所需的时间，可以通过(5)式计算：

tijk=tjk/(cjeij),

(5)

式中：tjk表示理想状态下(战士熟练程度和装备技术状态均为最好)第j台装备独立完成第k项阶段任务的耗时；cj表示第j台装备的技术状态影响系数，取值区间为[0,1]，数值越大表示作业效率越高；eij表示第i个操作手操作第j台装备的熟练程度影响系数，取值区间为[0,1]，数值越大表示熟练程度越高。

6)各阶段任务耗时之和便是整个工程保障行动的耗时，优化目标即找到一组决策变量，使得完成工程保障行动耗时最短，即目标函数可表述为

(6)

综上所述，(6)式描述了指派模型的目标函数，(2)式、(3)式和(4)式则共同组成了指派模型的约束条件。不难发现，本文所描述的模型不仅考虑了战士的操作水平，还考虑了装备的技术状态和协同作业的影响系数。该模型随着参与协同作业装备数量mk的增加变成了mk次整数规划问题，本质上属于大规模非线性整数规划问题。

2 快速求解算法设计

对于大规模非线性整数规划问题，极特殊情形下可以通过变换将指派模型转换为整数线性规划问题，进而按照整数线性规划方法求解；大部分情形下不能求出精确解，通常采用扩展割平面法[11]、广义Benders分解[12]、分支定界算法[13]、外逼近算法[14]来获得近似解，这些方法均是通过求解原非线性整数规划问题的松弛问题或者线性子问题来进行求解[15]。然而，不同于现有的绝大多数非线性整数规划问题，本文所描述指派模型的目标函数形式复杂且是高阶非线性的，既不能变换为整数线性规划问题，又难以找到对应的松弛问题或线性子问题，因此很多快速求解非线性整数规划的优秀算法都不能直接用来求解本文模型。

如果没有快速求解算法，通常的解法是：首先，构建一个由2l×m×n个解构成的较大可行域；然后，逐个判断是否满足(2)式、(3)式和(4)式给出的约束条件以缩小可行域；最后，通过(6)式求解可行域中最优化的决策变量。如果按照上述思路，完成求解将相当耗时，不能满足信息化战争条件下快速决策的需要。

通过(3)式，不难发现：由于xijk为0-1变量，该公式所描述的约束条件实际上是无效的，导致不能为模型的求解构建一个较小可行域。进一步，如果将所有多功能装备看作是多台单功能装备的虚拟集合，这样(3)式所描述的约束条件就可以转换为

(7)

式中：mv表示将多功能装备拆分为虚拟装备之后实际装备与虚拟装备数量之和，因此mv≥m.

上述方法之所以称为虚拟装备法，是因为分解后具有单功能的装备物理上是不存在的，即虚拟的集合。通过虚拟装备法，(3)式的约束力得到了增强，从而极大地缩小了指派模型的可行域。不仅如此，基于虚拟装备法修改指派模型的约束条件后，本文设计了一套快速求解算法，以下是具体实现步骤：

1) 按阶段任务进展的时间顺序，给各阶段任务进行编号，得到阶段任务编号数组。

2)引入Ik,mk表示能够协同完成第k项阶段任务所有可能的装备组合方案，可以指派到第k项阶段任务中装备组合方案的数量为

(8)

进一步，引入I表示整个工程保障行动中装备组合方案的组合，由于整个工程保障行动是由各阶段任务串联而成，因此I=I1,m1∪I2,m2∪…∪Il,ml，整个工程保障行动对应的装备组合方案数量为

(9)

3)从所有装备组合方案选择某一个装备组合方案，并按装备编号顺序排列得到装备编号数组。

4) 按照“人歇车不歇”的原则，要求每名战士只需要执行一项任务，因此战士的指派要综合考虑工程保障行动的装备组合和战士的数量。那么，被指派到某一装备组合方案中战士组合方案的数量为

(10)

式中：mw=card(I)表示某一装备方案组合对应的装备数量，由于每台装备分配一名战士，实际上也就是某一装备方案对应的战士数量。

5)从所有战士组合方案中选择某一个战士组合方案，并按战士编号进行全排序得到战士编号数组。

6) 由于决策变量矩阵中元素的坐标是根据战士编号、装备编号和任务编号而给定的，可以根据步骤2、步骤4、步骤6确定决策变量中战士、装备、任务的坐标，可以得到一组决策变量x.

7)遍历所有装备组合方案的集合，再遍历该装备组合方案对应战士组合方案的集合，可以得到所有决策变量x，逐次代入(6)式计算，得到最优决策变量及对应的任务耗时。

3 实例分析

某班要执行一项构筑掩蔽工事的行动，该行动主要由开挖平地坑(挖坑)、设置支撑结构(起重)、覆土作业(覆土)3个阶段任务串联而成，必须完成上一个阶段任务之后才能进入下一个阶段。该班共编有8名战士，配备5类6台工程装备(2台挖掘机、1台挖坑机、1台起重机、1台推土机和1台装载机)。各阶段任务出动最多工程装备的组合可以由这些装备的功能明确给出，进而给出整个构筑掩蔽工事一种可能的装备组合方案，称为最大装备组合方案，如图1所示。由图1可以看出，装载机既可以参与挖掘作业，又可以参与覆土作业。

图1 最大装备组合方案图Fig.1 Maximum combination scheme of equipment

每名战士的编号和操作各类工程装备的熟练程度如表1所示，其中，熟练程度A、B、C、D对应的影响系数分别是1.0、0.8、0.6、0.

表1 战士编号和操作水平

每台工程装备的技术状态如表2所示，其中，技术状态A、B、C对应的影响系数分别是1.0 、0.8、0.6.

表2 工程装备技术状态

结合测算和经验，可以得到理想状态下(熟练程度为A的操作手操作单台技术状态为A的工程装备)完成各阶段任务耗时，如表3所示。

表3 理想状态下各阶段任务耗时

采用虚拟装备法，将装载机看作两台虚拟装载机(装载机v1和装载机v2)，一台只能进行挖坑，另一台只能进行覆土，按照图1所示的最大装备组合方案，由左到右、由上到下给出工程装备的编号，如表4所示。

表4 基于虚拟装备法的装备编号及任务耗时

各阶段任务的编号及在该阶段内多台装备协作的影响系数，如表5所示，数值越大表示越碍事。

表5 各阶段任务的协作影响系数

实践中，工程保障部队所属的单位、人员和装备在相应的软件系统中都会事先赋予唯一的标识码，而战士操作装备的熟练程度、装备的技术状态和多台装备协作对作业效率的影响系数一般通过部队日常训练考核、演习演练考核或装备在役考核等方式获取后录入系统。为便于计算和分析，本文中战士、装备和任务的编号均是人为指定，而熟练程度影响系数、技术状态影响系数、协作影响系数则属假设已知条件。因此，上述各种影响系数仅用来验证算法，不作其他用途。

最后，在搭载Intel Core i7 7th Gen处理器的Windows 7 64位平台上，采用本文所描述的指派模型和求解算法，基于数学仿真软件MATLAB 2017a求解上述实例，求得最优化的指派方案，如表6所示，最优指派方案对应的行动耗时为142.24 min.

表6 最优化战士- 装备- 任务指派方案

从表6中可以看出：最优化指派方案中，E4和E7分别参与了T1和T3两个阶段任务，也就是装载机共参与了挖坑和覆土两个阶段任务；而E2代表的挖掘机2并没有被指派参与挖坑作业。实际上，如果按最大装备组合方案，挖掘机2也被指派参与挖坑作业，此时最优指派方案对应的行动耗时为142.80 min，说明挖掘机2的参与并没有加快挖坑作业反而稍微妨碍了挖坑作业，也即最大装备组合方案并不一定是最优的装备组合方案。进一步分析不难发现，挖掘机2的技术状态为C，作业效率本来就不高，再加上4台工程装备协同挖坑作业的影响系数为0.3，因此才会出现“帮倒忙”的现象。不难得出结论：表6所示的决策方案更加符合实际情况，从而验证了指派模型的实用性和有效性。

另一方面，如果采用遍历全部决策变量的做法，直接在2l×m×n个决策变量构成的可行域内搜索满足约束条件的解(共28×6×3个决策变量，每个决策耗时约9.4×10-5s)，在同样配置的计算平台中估计耗时约2.1×1039s，这几乎是不可接受的；而采用本文所描述的快速求解算法可以极大地减小可行域(共284 928个决策变量)，耗时仅为26.85 s. 因此，基于虚拟装备法的快速算法能够极大地降低计算消耗，是解决上述指派模型的一种切实有效地解法。

4 结论

本文分析了作战工程保障行动的特征，设计了工程保障行动的战士- 装备- 任务的三维指派模型及其快速求解算法，并用实例对模型和求解算法进行了验证。所得主要结论如下：

1)工程保障行动中的任务指派问题应考虑战士操作水平、装备技术状态和任务协作影响等因素，因此，该问题是一个由“战士- 装备- 任务”构成的三维指派问题。

2)基于“人歇车不歇”原则的虚拟装备法，可以增强三维指派模型的约束条件，降低决策变量的可行域，从而实现指派模型的快速求解。

3)实例证明了本文建立模型及快速求解算法的实用性和有效性。

值得注意的是，根据战士和装备是否安排休息的情况，约束条件可以有4种情况：“人歇车不歇”、“人歇车歇”、“人不歇车歇”、“人不歇车不歇”。因为“人歇车不歇”是作战工程保障行动中符合作战原则的典型场景，因此本文仅针对这一种场景制定约束条件。在实际作战行动中，如果该工程装备具有完成某阶段任务的能力而且其自身技术状态是正常的，除非经过计算该装备参与协作时导致整体作业效率降低，否则是不会出现“车歇”这种场景的。反倒是在任务非常紧急的情况下，极可能出现“人不歇车不歇”的场景。关于“人不歇车不歇”这种场景下的求解，可以按作战工程保障行动中阶段任务的划分，逐阶段求解，是一种相对比较简单的情况，感兴趣的读者可以自行研究。

与所有“指派战士完成任务”的指派模型最大区别在于，本文所提出的指派模型能够帮助指挥员在考虑“指派哪些战士完成哪些任务”时，还综合考虑了装备技术状态和协作影响因素带来的影响。然而，本文尚没有考虑一台装备有多个工位需要多名战士协同作业完成某项任务的情形，这些问题将在以后的研究中继续深入。