智能RGV的动态调度策略

闫洁 王一宁 宋善洋

摘 要：研究智能轨道式自动导引车在两道工序的物料加工作业过程中的动态调度策略，以时间轴为主线，以各个调度操作的时间不冲突为约束条件，建立动态规划模型，采用遗传算法对模型进行求解，从而得出轨道式自动导引车的动态调度策略以及作业效率。

关键词：动态规划；遗传算法；动态调度

中图分类号：TP18；TP278 文献标识码：A 文章编号：2096-4706（2019）04-0170-03

Dynamic Scheduling Strategy for Intelligent RGV

YAN Jie1，WANG Yining2，SONG Shanyang1

（1.School of Management Engineering，Qingdao University of Technology，Qingdao 266520，China；

2.School of Information and Control Engineering，Qingdao University of Technology，Qingdao 266520，China）

Abstract：This paper studies the dynamic scheduling strategy of intelligent RGV in the process of material processing in two processes. With the time axis as the main line and the time conflict of each scheduling operation as the constraint condition，a dynamic programming model is established，and the genetic algorithm is used to solve the model，so as to obtain the dynamic scheduling strategy and operation efficiency of RGV.

Keywords：dynamic programming；genetic algorithm；dynamic scheduling

0 引 言

轨道式自动导引车（Rail Guide Vehicle，以下简称RGV）在智能化加工系统中有着非常广泛的应用，它可大大提高加工系统的作业效率。在实际生产环境中，单个RGV通常需要为多个生产线运输物料，由于系统的生产任务和生产线状态是变化的，所以传统的静态调度方案将会在一定程度上限制智能加工系统的生产效率，对RGV动态调度的优化的研究已经成为生产调度研究中的热点之一。动态调度的概念最初是由美国加州大学的Jackson[1]提出，Sabuncuoglu等提出了针对在生产加工过程中，由于机器故障和加工时间改变等情况的变周期重调度策略，并分别于在线与离线状态下进行实验，最终验证了调度策略的有效性[2]。Nelson和Holloway提出了以一个周期性的调度算法来解决工作间隔到达的生产调度问题，即所形成的调度方案一直执行到下个周期开始前，中间不进行任何的修改[3]。Yamamoto和Nof[4]则研究了随机机器发生故障時事件驱动的重调度策略。刘爱军等设计了以最小化加工时间和最小化拖期为目标，并用一种自适应的遗传算法对的柔性作业车间动态调度进行求解和检验的调度策略[5]。智力学者Doris Saez和Cristian E.Cortes[6]等提出了提前预测将要发生的任务，利用遗传算法以更有效地解决多个RGV的动态调度问题。

以上针对动态调度问题[7]的研究提出了许多有价值的思想和方法，但当RGV应用在多道工序的智能化加工车间执行生产时，由于生产任务的工序、时间、数量会经常变化，欲在未知动态环境下寻找智能RGV的最优调度策略，关键是要确定RGV接收到的指令来自于哪一台CNC、其接受指令的时间点以及位置如何，这也是突破RGV动态调度问题的核心之处。针对该问题，本文基于动态规划和遗传算法的理论进行数学建模，并通过MATLAB[8]软件编写程序，以求解智能RGV的最优调度策略，从而实现智能加工车间的最大生产效率。

1 动态任务调度模型

1.1 模型建立

本文针对车间生产线动态调度任务分配问题的特点，基于动态规划理论，将生产线执行任务决策的过程描述为在限定时间段内有序增加生产任务分配决策问题，建立基于动态规划的动态任务分配模型[9]。RGV的动态任务分配模型由四个参数表示：加工任务、加工设备、时间、数量[7]。

1.1.1 加工任务

将加工设备执行加工物料的加工工序过程中出现的任务按时间顺序进行编号，表示为Wirk。在每一时刻，进入系统中的任务数目不超过一个班次中总的需要加工的物料个数m的最大值，且为随机数值，系统在有限时间段内出现的任务数为非无穷大的数值。

1.1.2 加工设备

将加工系统中每一个加工设备表示为i，在开始阶段设备正常运行，加工时有一定概率出现故障，并需要一定的时间进行维修。

1.1.3 时间

动态规划模型中，以连续时间序列为约束条件[10，11]，如下：

（1）在引导车进行调度的时候，加工设备对未加工生料进行加工的某一道工序的开工时间Brk和该工序的加工时间xirk·Tirk应该不能大于该物料的完工时间Erk，即：

Brk+xirk·Tirk≤Erk，（i=1，2…n，r=1，2…m；k=1，2 …kr）

（2）下一道工序的开工时间Br（k+1）要应该不小于上一道工序的完工时间Erk、引导车为CNC一次上下料所需时间tir、引导车在这个过程中移动的时间p，即：

p+Erk+tir≤Br（k+1），（r=1，2…m；k=1，2…kr-1）

（3）每一个未加工生料加工完成并经过清洗后变为成料的时间应该不大于总的完工时间Emax，即：

（4）在进行不同的未加工生料之间的工序约束的时候，应该满足同一台引导车上某物料的工序完成时间不大于上一件物料的工序完成时间，即：

Brk+Tirk≤Bsl+M（1-yirksl），（i=1，2…n；r，s=1，2…m；k=1，2…kr；l=1，2…ks）

（5）物料r的第k道工序加工开始时间应该大于该物料的上料时间并且小于该物料的加工完成时间，即：

uri≤Brk≤dri-Tirk，（i=1，2…n；r=1，2…m；k=1，2 …kr）

1.1.4 数量

在进行RGV的动态调度过程中，除了要求的物料r（假设一个班组中加工物料数的最大值为m）的加工完成的最大拖延时间最短之外，还应该要求在一个班次内的CNC有较大的加工效率，即物料完成所有加工工序的物料数是最多的，即：

1.2 动态规划任务调度寻优算法

考虑到基于自然选择原理的搜索寻优算法在解决最优化问题中的优势，我们利用遗传算法来求解。遗传算法的实质是通过在一个种群中进行搜索，以适者生存为寻优原则，通过个体的随机交叉和突变等过程生成下一代群体，并按照上述方法使一个种群中的群体不断进化，直到满足最后的终止条件。遗传算法的具体步骤如下[11，12]。

Step1：编码策略。在解决上述RGV的动态调度问题中，将8台CNC当作8个染色体，并依次为基础进行编码。

Step2：设置初始参数。设置初始种群的大小为32，交叉概率为10%，变异概率为50%，最大的迭代次数为100。

Step3：适应度函数的确定。为了便于模型的求解，我们以动态规划模型的目标函数作为适应度函数：

Step4：遗传操作。该过程包括三个基本的遗传算子：选择、交叉以及变异。

Step5：终止条件。按照上述方法在迭代次数范围内逐代进化，或者当最优个体的适应度达到给定的阈值时，进化过程结束，算法终止。

对于车间生产线任务分配问题，经过上述算法，得到最优的策略方案。

2 仿真实例

以2018年全国大学生数学建模竞赛B题[13]——《智能RGV的動态调度策略》中两道工序的物料加工作业为例，实例问题基于求解两道加工作业对RGV的最优动态调度策略这一情形。利用本文所建立的动态任务调度模型，并通过遗传算法结合MATLAB编程进行求解，得出结果。

遗传算法在产生新一代的过程中，每次运行的结果都是不一样的，经过多次仿真模拟得到如下适应度曲线，见图1、图2。

在遗传算法运行一次后，如图1所示，种群的适应度曲线振荡程度较大，此时还未找到最优解，即在现有的CNC设备和加工条件的约束下，仍存在对RGV更优的动态调动策略。当遗传算法运行两次后，如图2所示，随着代数的增加，种群的平均适应度逐渐向最大适应度收敛，在这个范围内存在全局最优解，结合先后两次的运行结果可以认定，在现有约束条件的限制下实现了对RGV最优的动态调度。

3 灵敏度分析

为了验证模型结果的准确性，根据文献[13]给出的三组数据，利用上述建立的模型及算法求出加工设备在一个班次内实际加工物料的个数m和理想状态下的加工物料个数h，求出生产效率w，即：。则，在理想状态下CNC加工物料的个数为：

，q+u=8小时

其中，T为一个班次的时间，q为加工第一道工序的加工设备数量，u为加工第二道工序的加工设备数量。

通过灵敏度分析的结果可以得出：在一定加工时间内，加工时间越长，生产效率越高；当加工时间超过了某一临界值的时候，设备加工时间越长，生产效率越低。这是因为，在一定的加工时间范围内，总时间是一定的，随着加工时间的变长，有效利用的时间变长，生产效率变大，当加工时间超过一定范围的时候，RGV等待的时间变长，生产效率变低。这一结果符合生产加工车间的实际情况，进一步验证了模型的逻辑性及准确性，使得模型更具说服力。

4 结 论

本文首先在动态规划理论研究的基础上，建立了基于RGV的车间生产线动态调度数学模型。首先，该数学模型能够清晰地描述在不确定情况下车间生产线动态调度问题；其次，该模型评价函数的目标是RGV在有限时间内加工物料个数的最大值，便于进一步应用遗传算法求解最优调度策略；接着，借助于随机数模拟了加工设备CNC发生故障的情形，使得模型的结果更加接近实际生产情况；最后，进行了灵敏度分析，分析的结果更加直接地说明了模型的准确性。

参考文献：

[1] Jackson JR. Simulation research on job shop production [J]. Naval Research Logistics Quarterly，1957，4（4）：287-295.

[2] Ihsan Sabuncuoglu，Suleyman Karabuk. Rescheduling frequency in an FMS with uncertain processing times and unreliable machines [J]. Journal of Manufacturing Systems，1999，18（4）：268-283.

[3] Rosser T. Nelson，Charles A. Holloway，Ruby Mei-Lun Wong. Centralized Scheduling and Priority Implementation Heuristics for a Dynamic Job Shop Model [J]. IIE Transactions，1977，9（1）：95-102.

[4] Yamamoto M，Nof S Y. Scheduling/rescheduling in the manufacturing operation system environment [J].International Journal of Production Research，1985，23（4）：705-722.

[5] 刘爱军，杨育，邢青松，等.柔性作业车间多目标动态调度 [J].计算机集成制造系统，2011，17（12）：2629-2637.

[6] Doris Sáez，Cristián E. Cortés，Alfredo Núez. Hybrid adaptive predictive control for the multi-vehicle dynamic pick-up and delivery problem based on genetic algorithms and fuzzy clustering [J]. Computers & Operations Research，2008：3412-3438.

[7] 陈明，周云龙，刘晋飞，等.基于MDP的多Agent生产线动态调度策略 [J].机电一体化，2017，23（11）：15-19+56.

[8] 贺超英.MATLAB应用与实验教程 [M].北京：电子工业出版社，2012.

[9] 司守奎，孙玺菁.数学建模算法与应用 [M].北京：国防工业出版社，2011.

[10] 赵月.基于动态优化的动态调度问题研究 [D].沈阳：东北大学，2013.

[11] 黄歆雨.基于混合遗传算法的柔性作业车间动态调度问题研究 [D].福州：福州大学，2016.

[12] 刘永强.基于遗传算法的RGV动态调度研究 [D].合肥：合肥工業大学，2012.

[13] 中国工业与应用数学学会.2018年全国大学生数学建模竞赛B题 [EB/OL].http：//www.mcm.edu.cn/html_cn/node/7cec7725b9a0ea07b4dfd175e8042c33.html，2019-01-22.

作者简介：闫洁（1999-），女，汉族，山东菏泽人，本科在读，主要研究方向：工程造价；通讯作者：宋善洋（1998-），男，汉族，河南濮阳人，本科在读，主要研究方向：国际工程项目管理。