工程机械机群动态调度问题浅析

前言：想要写出一篇引人入胜的文章？我们特意为您整理了工程机械机群动态调度问题浅析范文，希望能给你带来灵感和参考，敬请阅读。

摘要：针对工程机群在道路抢修任务过程中，面临的多装备、多任务、多点同时作业的机群调度难题，用整数线性规划理论建立模型，用离散粒子群算法求解。实例分析表明，该机群动态调度方法可以快速、高效地提出工程机械机群动态调度方案，为充分发挥军用工程机械的保障能力提供了决策支持。

关键词：工程机械机群；道路抢修；粒子群算法；动态调度

0引言

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

1模型构建

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

1.1任务描述

道路抢修一般分为4种任务：新筑道路，清除塌方，填平弹坑、壕沟，修复崩塌道路。一般情况下，往往同时、不同地点展开，且都需要推土机、挖掘机、装载机协同完成。由于不同任务的难易程度不同，故任务进展不同，现其中一点的任务已经完成，为使整体作业效率最大化，需将这一点的工程机械调度至其他任务点。将工程机械机群中的每一台工程机械看做一个单位，单位集：X={B1，…，Bi，…，Bn；E1，…，Ei，…En；M1，…，Mi，…Mn}。式中：B为推土机；E为挖掘机；M为装载机。假设推土机b台，挖掘机e台，装载机m台，工程装备数量总共为C台，任务数量为a。机群调度的任务-单位分配关系表示为式中，各变量表示任务与单位的关系，其赋值为推土机：

1.2问题建模

合理调度工程机械，使总任务完成的时间最少。总任务完成的时间等于各任务完成时间的最大值。工程机群调度模型目标函数为mint=max{ti|i=1，2，…，a}。（4）需要满足的约束条件有：1）各工程机械调度数量不大于该项目工程机械数量。式中：j=ej=1∑eij为第i个任务点的挖掘机数量；j=ej=1∑bij为第i个任务点调度的推土机数量；j=mj=1∑mij为第i个任务点调度的装载机数量。2）时间约束。各任务必须在要求时间限制内完成：ti=Qiuini≤tL，i=1…a。（6）式中：Qi为任务i的工程量；uj为单位j的作业率；ni各任务工程机械数量。3）各任务要尽可能地同时完工，避免出现某段任务完工过早或过晚的现象，以保证机群资源更加均衡合理分配使用。0.9<maxti/minti<1.1，i=1，2，…，a。（7）4）每个任务的机械数量为整数。ni≤N，i=1，2，…a。（8）通过对问题的描述和约束条件分析，可建立如下数学模型：

2模型求解

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

2.1算法流程

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

2.2粒子编码的设计

每个粒子位置对应一个新的分配方案，这样就将每一种配置方案映射成一个粒子，粒子的飞行表示从一个调度方案到另一个调度方案的选择。随着算法的收敛，粒子逐渐逼近最优调度方案。机群的调度矩阵为XB、XE、XZ分别为推土机、挖掘机、装载机在各任务的调度情况。设种群中粒子位置的集合为X={X1，X2，…，XPOP}。（12）式中，POP为种群大小。种群中粒子位置如图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.86h。根据本文建立的数学模型，以最小化总任务完成时间为优化目标，用粒子群算法求解，用MatlabR2015b编程计算。模型求解的优化过程如图3所示。可见，目标函数适应值在算法迭代75次左右达到收敛，总任务完成时间最小值为6.895h，优于未调度工程机械的任务完成时间7.86h。最优结果的机群调度矩阵为：矩阵中“-1”代表调出一辆，“1”代表调入一辆。故方案为将任务2的4辆推土机和任务3的1辆推土机调到任务1，将任务1的3辆挖掘机和任务2的1辆挖掘机调到任务3，将任务1的1辆装载机和任务3的1辆装载机调至任务2。

4结论

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

作者:李金鑫 何晓晖 单位:中国人民解放军32382部队