李金鑫 何晓晖 杜毛强 王金康

（1.陆军工程大学野战工程学院 南京 210007）（2.中国人民解放军32382部队 洛阳 471000）（3.中国人民解放军32228部队 厦门 361100）

1 引言

工程机械机群同时开展多任务作业时，受不确定因素影响，某一任务可能会面临任务时限提前的情况，指挥中心依据实时的调度相关信息调度，将其他任务的工程机械调度到该任务协助作业，使得任务在规定时间内完成。本文基于时空网络，建立机群动态调度时的时空网络模型［1］，进而对问题进行求解。

2 基于时空网络建立动态调度模型

2.1 问题描述

工程机械机群在执行任务的过程中因突发情况导致某一任务需要提前完成，这一情况的出现要求任务执行过程中必须临时从其他任务调度工程机械来增援该任务，即开展任务间的交叉调度。将各个任务的空闲装备充分调度起来，尽可能地在不影响其他任务完成的情况下使得该任务在最短时间完成，是解决这一问题的最佳方法。如图1 所示。任务1到任务n在前期机群配置的基础上开展作业，当任务n 存在空闲装备时，将其调度至不存在空闲装备的任务上，当任务n 即将饱和作业时，调度的装备应该在饱和作业前返回，避免出现任务n延时完成的情况。

图1 动态调度问题描述实例图

图2 遗传算法流程图

综上所述，工程机械的动态调度方案，由于其工作性质的特殊性，其优化的目标是工程机械的空闲率最低、完成时间最短，即在不影响任务完成的情况下，将各任务点的工程装备充分地调动起来，在为简化模型［2］故作以下假设。

1）调度达到的工程机械到达施工现场后可第一时间开展作业。

2）工程机械机群的燃料及资源等充足，在各任务的抢修完成前，并不需要返回营地进行维修资源的补给。

3）工程机械的施工效率不因工程机械的增多而变化。

4）一般情况下，机群工程机械型号是不相同的，不同型号机械的工作效率、转运速度也会存在偏差，为了简化问题的复杂程度，故不考虑机型的问题。

5）由于任务之间的距离较近所以不考虑工程机械调度转移的时间。

6）在已知机群配置和各任务工程量的情况下，基于动态规划法可得出，个任务工程机械的空闲时间。

7）紧急时期道路为军车优先使用或专用。所以行驶速度不受车流量的影响，因此各路段的旅行时间可认为己知。

2.2 模型构建

通过分析工程机械机群的动态调度问题可知，要解决这一问题，核心问题要实时了解各个任务点工程机械的使用情况，在静态调度模型的基础上，将任务点的实时空闲装备这一因素考虑进去，建立数学模型。因此，基于对机群动态调度问题的定义以及模型假设，本文采用时空网络建模方法构建工程机械机群的动态调度方案的混合整数模型。

1）参数定义

为方便后续模型描述和读者理解，这里对模型的参数、变量进行介绍。

表1 中n∊N+的，如u1代表推土机、u2代表挖掘机、u3代表装载机等等。

表1 面向任务时限提前的工程机械机群动态调度参数表

2）建立模型

本文以工程机械机群完成任务时间最短为优化目标，考虑机械数量约束、机械调度数量约束和任务完成时间约束，制定机群调度策略。利用时空网络精确性和直观性的特点，可以比较方便地解决上文提出的机群静态调度问题。

工程机械机群静态调度模型的目标函数为

需要满足的约束条件有：

（1）机械数量约束条件

①在机群的调度中，T 时刻任务i 的调度弧上的第n 种工程机械的数量小于等于任务i 的第n 种工程机械的空闲机械数量。其约束条件如下：

②机群调度结束后，机群工程机械的总数之和应不变。其约束条件如下：

（2）时间约束

③各任务必须在要求时间限制内完成：

综上，工程机械机群的静态调度模型为

3 基于遗传算法求解

面向任务时限提前的工程机械机群动态调度问题是一个将空闲的工程机械如何调度和调度几次的组合优化问题，是机群科学配置的基础上开展的。在之前研究的基础上，可以得出启发式算法［12］是解决此类问题的常用算法。因此本文采用启发式算法中的遗传算法［3］来求解。

3.1 算法流程

在遗传算法中染色体可以用行数为一的矩阵表示，矩阵中的每一列对应一个基因。将许许多多的行数为一的矩阵汇聚在一起，便组成算法解的种群。对每个矩阵进行选择运算、交叉运算和变异运算等。从中选取出算法的最优解。

最优解遗传算法的基本运算过程如算法流程图1～2所示。其到达进化条件［7］后结束。

3.2 算法设计

1）染色体的编码设计

当情况发生后，将完成时限提前的任务放入待优化任务集合σ中，设每个任务提前后的完成时限为tig，对于未进入集合σ的任务，设它们空闲的工程机械数量为n，将其组成行数为1 列数为n 的矩阵，则每列中的元素代表一个空闲装备。则空闲装备存在两种状态［8］调度和不调度，其等于1 则说明该空闲装备调度，反之不调度。如Z=[1,0,1,0] ，则表示有4台空闲装备。代号为第1、4空闲装备参与调度，代号为2，4装备不参与。

2）染色体的适应值

适应值［4］由目标函数决定，当机群的调度问题以待优化任务在规定时间内完成任务为目标时，则适应值为根据染色体当前代表的机群调度方案得到的任务完成时间。

3）染色体的更新方式

（1）选择运算

用适应度比列选择法［9］，把优良个体选择［11］出来传到下一代。设种群规模为J，第i 个个体的适应度值为F(i)，则被选择的概率为

（2）交叉运算

①将R1,R2除了起点和终点之外的其他共同节点作为潜在的交叉节点，并将这些节点组成集合R；

②将R中节点前后信息不一致的任意一个节点作为交叉点

③新个体产生后，检查新个体中是否存在环路，若无，操作结束；若有，将相同节点之间的基因和相同节点一起删掉。

具体实例如图3所示。

图3 交叉操作实例

（3）变异运算

变异运算是模仿生物遗传基因中的基因突变，同交叉算法一样是产生新个体的重要方法，使种群的多样性更加丰富，防止算法陷入局部最优解。其具体操作如下：

①删除基因。

在课堂教学中主要表现为教师对自身的情感、仪表、举止等方面的约束能力。这是实现课堂教学控制的根本前提。著名教育家加里宁曾经指出：“一个教育工作者,必须很好地收敛自己,他应该感到,他的一举一动都处在严格的监督之下,世界上任何人也没有受到这样严格的监督。”教师的情感、仪表、举止等直接影响到融洽的课堂气氛的形成,影响教学效果的实现。

第一步：在R1中选择变异节点［10］。

第二步：判断选中节点的前后节点否相连通，即前一节点与后一节点直接相连，若相连通，则开始下一步；否则改用下面的单点或两点变异，以增加种群的多样性。

第三步：删除选择的的节点，判断其适应度值是否优于R1的适应度值，优于，进入下一步；反之，改用下面的单点或两点变异，以增加种群的多样性。

具体实例如图4所示。

图4 变异运算实例1

②基因变异。

第一步：从父代个体R1根据变异概率p中随机选择变异节点，标记起点到该点前一节点的基因组成基因片段a；

第二步：标记该点到终点的基因产生新的基因片段b，基因片段a,b相连得到新个体，判断基新的染色体是否存在相同基因，若有，转到第三步；无，则转到第四步；

第三步：将相同节点合并操作产生最新个体，用来代替第二步中的新个体；

第四步：新个体的适应度值是否优于父代个体的适应度值，若优于，则用新个体进入下一代种群；否则，则转到第五步；

第五步：进行两点变异，以增加种群的多样性。

具体实例如图5所示。

图5 变异运算实例2

4 案例分析

以文献［5］中的构筑急造军路任务为例。该急造军路共有3 条道路的构筑任务，各道路的侦查情况为：道路1 大面积塌方，道路2 有连续弹坑，道路3 路基崩塌，据此将任务区分为：任务1 清除塌方，任务2克服连续弹坑，任务3修复崩塌路基，各任务工程量如表2所示，机群配置如表3所示，完成时间如表4所示。

表2 各任务工程量

表3 机群配置

表4 各任务完成时间

机群任务作业1 小时后，指挥中心接到任务，将任务2 提前30 分钟完成，同时其他任务按时完成，故需要对机群开展任务交叉调度，调度的对象为任务1、3 的空闲装备，设机群转移路途为10 分钟，任务开始作业时为12：00。其个任务中工程机械的空闲情况如表5。

表5 任务1、任务2的装备空闲情况

指挥中心接受任务后，任务2 需在3 小时内完成，及在15 时前完成，由表1～9 可知可供调度的空闲装备为推土机6 台次、挖掘机6 台次、装载机1 台次，闲置时间均为1小时。

按照本文建立的数学模型，以规定时间完成为优化目标，用遗传算法求解，用Matlab R2021a 编程计算。可得调度矩阵如图6所示。

图6 调度矩阵

得其调度矩阵为

［0 1 1 1 1 1 0 0 1 1 1 1 0］

模型求解的优化过程如图7所示。

图7 模型求解优化过程

按表6 调度方案开展调度，可在不影响任务1和任务3的情况下，使任务2在3h内完成。

表6 机群动态调度方案

5 结语

本文基于时空网络建立面向任务时限提前的军用工程机械机群动态调度模型，以在规定时间内完成任务为优化目标建立数学模型，并基于遗传算法求解，最后利用Matale2021a 进行编程设计，通过实例验证，得出该方法可以快速、科学得出调度方案。