基于粒子群算法的工程机械机群动态调度问题的求解

李金鑫，何晓晖

（1.中国人民解放军 32382部队，河南 洛阳 471000；2.陆军工程大学 野战工程学院，南京 210007）

0 引言

道路抢修是工程机械机群工程保障任务之一。通常可将其分为清除塌方、填塞弹坑、壕沟、修复崩塌路基4种任务，往往需要在不同地域同时开展。每种任务均涉及到推土机、挖掘机、装载机等多种类型军用工程机械协同作业。当前工程机械机群实际运用过程中，机群往往是多点同时开展工作，指挥员通常是根据主观经验来确定机群的动态调度，工程机群开始工作后各工作点之间基本没有动态调度。由于每个点的工作量不同，任务难度不同，故工程进度也会不同。因此，合理地调度各个工作点的工程机械，才能保证任务顺利完成，使工作效率达到最大化。如何利用有限资源在最短时间内完成道路抢修任务成为检验战斗力的标准。因此，研究工程机械机群优化调度方法，有助于合理、高效地使用工程机械，进而为指挥员定下方案提供依据。

1 模型构建

工程机械的调度需要依据任务类型、工程量及机械的作业能力确定，因此必须对调度问题进行建模分析，以制定最优的调度方案。

1.1 任务描述

道路抢修一般分为4种任务：新筑道路，清除塌方，填平弹坑、壕沟，修复崩塌道路。一般情况下，往往同时、不同地点展开，且都需要推土机、挖掘机、装载机协同完成。由于不同任务的难易程度不同，故任务进展不同，现其中一点的任务已经完成，为使整体作业效率最大化，需将这一点的工程机械调度至其他任务点。将工程机械机群中的每一台工程机械看做一个单位，单位集：

1.2 问题建模

合理调度工程机械，使总任务完成的时间最少。总任务完成的时间等于各任务完成时间的最大值。工程机群调度模型目标函数为

2）时间约束。

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

2 模型求解

工程机械机群调度模型求解可以看做是一个寻找最优解的过程，即离散组合优化问题；解决此类问题的有效方法是启发式算法，主要包括离散粒子群算法[1]、遗传算法[2]、隐枚举法[3]等算法。本文采用粒子群算法求解动态调度模型。该算法具有收敛速度快、全局优化性好的特点，其应用领域已从连续空间优化问题扩展到离散组合优化问题[4]，在解决机群动态调度问题上优势尤为明显。

2.1 算法流程

PSO算法中每一个潜在的解都被称为一个“粒子”，粒子在解空间内“运行”，随着算法运行，粒子不断逼近函数的最值[5]。在每次进化过程中，粒子通过跟踪2个“极值”来更新自己所在的位置。第一个极值为粒子自身找到的最优位置，相对应的适应值为pBest；另一个极值是整个种群当前找到的最优位置，相对于的适应值称为全局极值为gBest[6]。其流程图如图1所示。在得知最优方案后，即可得调度方案。

图1 算法流程图

2.2 粒子编码的设计

每个粒子位置对应一个新的分配方案，这样就将每一种配置方案映射成一个粒子，粒子的飞行表示从一个调度方案到另一个调度方案的选择。随着算法的收敛，粒子逐渐逼近最优调度方案。机群的调度矩阵为

种群中粒子位置如图2所示。

图2 种群粒子位置

例如，任务1、任务2、任务3分配推土机、挖掘机、装载机各1台，其中任务2已完成，将任务2的各类工程机械任意调度到任务1、任务3，其矩阵粒子编码可表示为

这样的编码方式的优点是直观地将各任务的机群调度情况表示出来，将任务2的1台推土机、挖掘机、装载机调度给任务1，2台挖掘机、装载机调度给任务3。

2.3 粒子位置更新方式

由于每个单位只能被分到1个任务，每个任务至少分配1个单位，所以位置矩阵每行的和大于1，每行每列任意互换。同时满足以下束缚条件：

3 案例分析

本文以文献[3]中的构筑急造军路任务为例。该急造军路共有3条道路的构筑任务，各道路的侦查情况为：道路1大面积塌方，道路2有连续弹坑，道路3路基崩塌，据此将任务区分为：任务1清除塌方，任务2克服连续弹坑，任务3修复崩塌路基，各任务工程量如表1所示。因突发情况导致任务1和任务2的机械作业效率降为一半。现有推土机10台、挖掘机7台、装载机6台，各类机械在不调度的情况下，各任务的作业率如表2所示。文献[3]完成总任务时间为7.86 h。

表1 各任务工程量

表2 各任务工程机械作业率 h

根据本文建立的数学模型，以最小化总任务完成时间为优化目标，用粒子群算法求解，用Matlab R2015b编程计算。模型求解的优化过程如图3所示。

图3 模型求解优化过程

可见，目标函数适应值在算法迭代75次左右达到收敛，总任务完成时间最小值为6.895 h，优于未调度工程机械的任务完成时间7.86 h。最优结果的机群调度矩阵为：

矩阵中“-1”代表调出一辆，“1”代表调入一辆。故方案为将任务2的4辆推土机和任务3的1辆推土机调到任务1，将任务1的3辆挖掘机和任务2的1辆挖掘机调到任务3，将任务1的1辆装载机和任务3的1辆装载机调至任务2。

4 结论

本文对军用工程机械遂行构筑急造军路任务面临的多型装备、多种任务、多点同时作业的机群动态调度问题进行分析，提出了基于离散粒子群算法求解模型的机群动态调度方法。该方法能有效解决机群的动态调度问题，提高军用工程机械的保障能力。