2018年数模国赛B优秀论文：基于 0-1 规划的单 RGV 动态调度模型.pdf

基于0-1规划的单RGV动态调度模型

摘要

本文从规划角度出发，研究了智能加工系统中的单RGV动态调度问题。由

于RGV型号多样、功能有简有繁，因此本文从RGV是否能预判CNC加工完成时

间建立了两套单RGV动态调度模型，并进行了对比分析。

针对任务一中情况1，本题仅需考虑一个班次中单工序加工的单RGV动态调

度模型。本文以RGV的调度路径为决策变量，以获得最多成料为目标函数，约

束条件为每次调度单RGV仅能对一台CNC进行作业、每班次RGV工作时长不超

过8小时、RGV下轮作业移动起点为上轮作业终点、每台CNC每次作业仅能加

工一个物料，根据0-1规划的思想建立单目标规划模型，最终得到CNC无故障

下加工单工序物料的所获成料最多模型，通过求得每轮上下料最短所需时长的

启发信息，建立启发式算法得到近似最优解，并给出算法流程图及分析。

针对任务一中情况2，本题需考虑一个班次中加工双工序的单RGV动态调度

模型。首先，在情况1模型的基础上，增加约束条件：每台CNC仅能装配一种

刀具加工一道工序、物料工序状况与CNC加工工序类型相匹配。以获得成料尽

可能多、获得最多成料时RGV工作时间尽可能小为目标建立双目标规划模型，

并给出以循环遍历法求最优刀具分布方案以及通过求得每轮上下料最短所需时

长的启发信息，建立启发式算法得到近似最优解，并给出算法流程图及分析。

针对任务一中情况3，在任务一情况1、2模型的基础上，将CNC的故障和

维修等效转换为一次时间较长的加工作业，增加约束条件：CNC加工过程中有

1%的概率发生故障、故障发生时该CNC正加工的物料即刻报废、排除故障时长

服从10~20分钟的均匀分布，并分别建立CNC概率故障情况下的单、双工序加

工的单目标规划模型、CNC概率情况下双工序加工的双目标规划模型。在情况1

和情况2算法的基础上加入仿真随机故障得到情况3的启发式算法，并给出算

法流程图及分析。

针对任务二，利用3组系统作业参数对任务一中三种情况的规划模型进行求

解和检验，得到情况1下的产量为382、359、392；情况2下的产量为253、211、

243，得到最高产量时RGV总工作时长为28797、28755、28692，最优刀具分布

方案为[1,2,1,2,1,2,1,2]、[2,1,2,1,2,1,2,1]、[1,2,1,1,2,1,1,2]；单工序情

况3下产量为376、354、383，对应的故障次数为3、3、4；双工序情况3下产

量为239、210、240，加工工序一时故障次数为3、1、1，工序二故障次数为2、

0、2。以普适性、经济性、实施模型的可行性和CNC平均非有效工作时长作为模

型实用性指标，以程序运行时间和内存使用情况作为算法有效性指标，分别对两

种模型各12组结果进行模型的实用性与算法的有效性评价。最终计算结果反映

出本文模型实用性高、有效性强，且可预判模型结果更优。

最后，本文利用仿真数据对模型进行了再检验，分析了模型的优缺点，讨

论了模型的改进方向并对模型进行了简单的推广。

关键词：智能RGV；机器故障；动态调度；0-1规划；启发式算法

1

一、问题的提出和重述

1.1问题的提出

轨道式自动引导车（RailGuideVehicle,RGV）因为其无需人员操作且运

行速度快的特点，能实现与系统快速连接并按照计划进行物料的传输等，在当

今自动化物流系统与自动化仓库中有着重要应用，RGV的动态调度的研究对车

间的高效作业有着重要意义。

1.2问题的重述

现有8台计算机数控机床（ComputerNumberController，CNC）与1辆轨

道式自动引导车，附属设备有1条RGV直线轨道和上、下料传送带各一条等。请

针对以下三种具体情况完成两项任务。

情况（1）：物料加工仅一道工序，每台CNC安装相同刀具，物料可以在任

一台CNC完成加工；

情况（2）：物料加工有两道工序，每个物料两道工序在两台刀具不同的CNC

上依次加工完成；

情况（3）：CNC在加工过程中约有1%的可能发生故障（故障发生时该机正在

加工的物料报废），每次排除故障需要10~20分钟，故