【国赛优秀论文】RGV 的动态调度优化问题

普大帝

你好！我是陪你一起进阶人生的普大帝！愿你成才！祝你成长！
国赛前我会陆续更新一些国赛的优秀论文，大家根据下图箭头所示，在网页的搜索框内搜索“国赛优秀论文”就可以搜索到相关内容，并且可在线查看摘要、问题重述、问题分析等部分内容。本次的论文为2018年的国赛优秀论文，使用 Python和 C++ 做的程序 。

RGV 的动态调度优化问题

摘要

本文对智能加工系统中 RGV 的动态调度优化问题进行研究。针对任务一，我们首先对系统进行分析，给出了几个重要定义和优化指导原则，例如 RGV 工作循环定义、系统效率均衡原则、CNC 满载工作上限等。同时，给出了相关分析和证明，包括在一定条件下的 RGV 循环的最短用时证明，系统最优上限的证明等。这些理论为我们建立最优化模型和模型评估指标提供了依据。
对于情景一，我们对原有模型进行转化，将其转化为时间维度上的多队列任务调度优化模型，并基于事件对时间进行离散化，为减少迭代步数，根据划分结果构建最优状态转移图模型，利用状态向量和状态转移矩阵完成系统工作的模拟和决策优化。考虑到求解该优化问题计算开销较大，采用多阶段决策模型进行求解，即将最优状态转移图模型中的优化原则结合已明确的优化准则构建各个阶段的决策方案，从而完成问题的求解，得到在 8 个小时内三组参数下系统可产生最大熟料数量分别为 382、359、391；经检验，在求解效率和求解质量上都达到了很好的效果。对于情景二，我们分析了两类 CNC 在系统中共存时产生的复杂约束情况，结合系统效率均衡对应系统整体较大效率的规律，近似确定了两种 CNC 的数量比例。再通过搜索找到了最优的 CNC 空间排布方案，从而建立带工序约束的最优状态转换图模型。在求解时，通过改进的状态转移优化准则对模型进行求解，得到在该约束条件下，8 个小时内三组参数下系统可产生最大熟料数量分别为 253、210、240；对于情景三，需要引入了负载因子进行了故障的随机模拟。该过程的本质是在状态转移时引入不确定性。由此引入新的变量，对状态转移矩阵和转移约束进行拓展补充，并对评价函数进行修正，从而建立了带有故障风险的最优状态转换图模型。在使用多阶段决策求解时，除了追求完成物料数最大，还要保持系统内两类 CNC 工作能力均衡以取得更高的工作效率。由于情况较多，结果可见附件 Excel。针对任务二，我们结合证明的结论，构建了结果偏差率计算公式，并为该标准提供了必要的理论支持，具有较高参考意义。经过验证，模型求解算法结果与最优解有很好的近似。针对系统效率，我们构建了系统效率评价指标，用于刻画系统整体效率与各部
分效率均衡情况。
关键字： 状态图模型 多阶段决策模型 非线性优化模型 RGV 最优调度

问题背景与重述

随着信息技术、控制工程、机械工程等技术的发展与进步，智能加工系统日益无人化、自动化、智能化，显著提升了工业加工、物流服务等工作的效率。以本题为例，该智能加工系统由 8 台计算机数控机床（Computer Number Controller，CNC）、1 辆轨道式自动引导车（Rail Guide Vehicle，RGV）、1 条 RGV 直线轨道、1 条上料传送带、1 条下料传送带及其他附属设备组成。RGV 是一种无人驾驶的、能在固定轨道上自由运行的智能车，能够根据指令完成相关的作业任务。在该类系统中，RGV 的运行情况对整个作业系统的工作效率有着巨大影响，运行过程中，易出现因不同工作组调度不佳，而导致空闲等待的情况，降低了运行效率。能否更加合理地调度穿梭车，提高 RGV 系统的运行效率，是进一步促使智能加工系统发展的一个重要因素。
题目要求针对下面的三种具体情况：
1. 一道工序的物料加工作业，每台 CNC 安装同样的刀具，物料可以在任一台 CNC 上加工完成；
2. 两道工序的物料加工作业，每个物料的第一和第二道工序分别由两台不同的 CNC 依次加工完成；
3. CNC 在加工过程中可能发生故障（据统计：故障的发生概率约为 1%）的情况，每次故障排除（人工处理，未完成的物料报废）时间介于 102̃0 分钟之间，故障排除后即刻加入作业序列。要求分别考虑一道工序和两道工序的物料加工作业情况。
完成以下任务：
任务 1：对一般问题进行研究，给出 RGV 动态调度模型和相应的求解算法；
任务 2：利用表 1 中系统作业参数的 3 组数据分别检验模型的实用性和算法的有效性，给出 RGV 的调度策略和系统的作业效率，并将具体的结果分别填入附件 2 的Excel 表中。

问题分析

1 问题一分析
该问题要求根据一般问题，给出 RGV 动态调度模型和相应的求解算法。针对该问题，首先需要对该系统的运行特点进行一定的抽象、概括和证明，例如：在最优的调度策略下各部分机器效率应当均衡的。这些规则将用于构建 RGV 动态调度模型。

针对情况 1，结合对系统分析的结果，可以将 8 个 CNC 转换为 8 个工作队列，将物料加工作业抽象为队列中的事件，则题目第一问可以转换为完成队列中带约束条件的任务最优调度。转换完成后，可从时间维度对系统基于事件进行状态划分。基于该状态划分结果，可以构建最优状态转移图（有向有权图）模型，其中带权节点代表 CNC 的处理时间、带权有向边带代表 RGV 将清洗工作、停止等待以及移动所需要的时间，由此构建状态向量和状态转移矩阵。该模型以最大化有限时间内完成的熟料数目最多为目标，而约束则可引入总工时约束、物料加工用时约束、RGV 运动时间的约束等。此外，该问题还可以从建立物料数目确定，最小化时间的角度考虑建立相应最优化模型等。最优状态转移图模型的化简工作可以考虑以两无权点及该两点所确定的一条带权有向边代替原来的带权点，从而完成对模型的构建和化简。针对情况 2，我们可以建立带有工序约束的最优状态转移模型。该模型依然是基于系统状态转移的思想，可以证明工序一、二紧邻是系统高效率的指导原则，我们修改状态转移矩阵的约束条件，限制状态向量的转移方向从而完成问题的求解。最优化目标依然是在有限时间内最大化生产熟料数目。针对情况 3，我们可以在最优状态转移图模型和带有工序约束的最优状态转移模型的基础上引入突发事件随机变量，通过引入该随机变量限制部分状态的转移效果，同时引入等待时间变量，从而完成问题模型的建立。
对于算法的求解可以采用引入剪枝规则、回溯法、分支限界法等。值得注意的是，在该求解该模型时，分支限界法求解目标则是尽快找出满足约束条件的一个解，或在满足约束条件的解中找出在某种意义下的最优解，更适合求解离散最优化问题。但是，考虑到即使引入剪枝策略等模型求解的时间和空间复杂度可能较大，因此在求解算法时采用分阶段优化的策略完成模型的求解，同时采用基于事件的时间离散化处理，最后可以对结果进行分析比较，作为模型的近似解。除此之外，在该类最优化问题求解时，也可以采用混合遗传算法 [1]、禁忌搜索算法 [2] 等。
2 问题二分析
该问题可以通过输入题目提供的数据检验模型的实用性和算法的有效性，并对结果和系统基本上限进行比较，判断模型和算法的实用性和有效性，同时输出该过程中 RGV的调度策略。对于系统的作业效率，可以定义系统工作效率为系统中 CNC 的工作时间在一个工时内比例。此外，可从系统工作效率均衡的角度分析模型实用性和算法的有效性。