论文部分内容阅读
[摘 要]本文主要研究智能RGV动态调度策略问题，通过分析智能加工系统的组成与作业流程，利用运筹学与统计学的基本原理建立了三个模型。定量地分析了RGV的路径对规定时间内加工成料数量的影响，同时通过仿真分析，使模型具有较好的稳定性。情况一，我们运用了最短路径法和遗传算法分别建立了两个模型，模型一中利用最短路径方法最终求得局部最优解，一个班次可以生产309个成料，模型二利用遗传算法做出了全局最优解，一个班次可以生产368个成料。通过结果分析，得出第二组数据中空闲总时间为838秒，即总的空闲时间也只够一个物料加工时间，单个CNC空闲时间只有105秒，利用率已经达到了极限了，空闲率只有0.36%。情况二，我们采用目标规划法，以CNC空闲总时间最少为最优解建立基本模型，利用遗传算法得出的相对最优解为在一个班次中成料的为234件，经过第一道工序的熟料有237件。然后通过仿真运行，得出第一组数据的空闲率约为2.6%。情况三，根据统计学原理，在模型二和模型三中加随机函数，并且认为随机生成数小于0.01的都是有故障的，利用MTLAB程序，不断迭代选取优先权最高的值作为下一轮初始群体，求出最优解。最后在模型二中得出的数据为360件成料；在模型三中得出的227件成料，第一道工序产生的熟料有228件。
通过分析模型二、三的建立，我们发现在利用RGV仿真运行时，运动轨迹逐渐趋向于最优化，证明了模型的实用性和算法的有效性。
[关键词]RGV ；CNC；最短路径法；遗传算法；MATLAB；仿真运行
中图分类号：TP759 文献标识码：A 文章编号：1009-914X（2018）10-0350-02
1问题的分析
本文主要对一般问题进行研究，给出RGV动态调度模型使其工作效率最高，在一个班次中产生的成料最多。在该智能加工系统工作的过程中CNC加工完成一个一道工序的物料所需时间、RGV为CNC1#，3#，5#，7#一次上下料所需时间、RGV为CNC2#，4#，6#，8#一次上下料所需时间以及RGV完成一个物料的清洗作业所需时间都是一个定值，在工作过程中是必须经历不能简化的，因此该问题就简化為规划RGV的最短路径，使所有CNC所空闲的时间最短。
智能加工系统通电启动后，RGV在CNC1#和CNC2#正中间的初始位置，所有CNC都处于空闲状态。RGV在1和2之间选择，因为RGV为CNC1#，3#，5#，7#一次上下料所需时间小于RGV为CNC2#，4#，6#，8#一次上下料所需时间，所以应先服务于CNC1。要想使得CNC空闲出来的时间最短，就必须使RGV空闲出来后需要优先服务最早可以开始加工的CNC，即RGV应服务于从上一个CNC的时刻到当前CNC等待时间所用时间最小的路径。
2模型假设与符号约定
2.1模型假设
（1）同一时间RGV只能处于一个状态，服务一个CNC。（2）RGV调度系统无故障，可实时知道材料加工情况和小车实时位置。（3）当多个CNC同时发出需求指令时，RGV依照距离RGV路程由近到远上下料。（4）传送带运行速度很快，可忽略不计。
2.2符号说明
（1）Tm：物料加工时间；（2）Tud：上下料时间；（3）Tmt：移动时间向量，i=123；（4）Tij：物料加工完成时间，第i个CNC完成第j个物料完工的时间；（5）Tsij：物料上料时刻；（6）Tc：清洗时间；（7）表示mi第i个CNC加工工件的数量。（8） 表示工件k的工序1完成加工时间。（9） 表示工s件k在CNCi的上下料时间，（10）Tc2表示工序2加工时间。
3模型的建立
3.1模型的准备
RGV英文全称为Rail-GuidedVehicle，即轨道式导引小车，国内一般称为穿梭小车或者穿梭车，是一种在车间或者自动化立体仓库中沿着轨道（可以是铁轨或者合金轨道）运行的物料运送工具，相对AGV（自动导引小车）等其他的运送工具，有以下特点：
（1）移动速度和加速度快，能够运送重型物料。（2）运行平稳，停车位置准确且易于精确控制。（3）设计制造较简单且可靠性高，能够大面积推广。
本题目中RGV为直行轨道式，又称直线往复式RGV，其在一段直线型轨道上运行一个或者多个RGV，通过往复运行可以实现运送物料的目的。这种RGV的优点是系统简单，制造成本和工艺简单，并且占地面积小和输送物流快捷方便，适合中小型物流的运送。缺点是运送能力有限，在轨道上不能同时运行太多的RGV。
3.2模型一
根据任务一中的第一种情况，目标是要建立数学模型来研究当一道工序的物料加工作业情况，每台CNC安装同样的刀具，物料可以在任一台CNC上加工完成时，RGV动态调度模型和相应的求解算法。根据运筹学相关知识，我们很容易可以得出可以用最短路径算法来建立RGV动态调度模型。
因为该题目中RGV移动的距离与所需时间成线性关系，在两边加料和下料花费的时间不同，并且所有的成品都必须经过一个清洗过程，花费的时间相同。所以我们可以将此时间问题转化为路径问题，将RGV在一维线上运动转化为二维平面上求最短路径问题，将所有任务点按照泊松分布策略生成，将RGV初始时间和速度做标记，根据任务点生成的时间和位置进行动态标记，也就是对TSP算法的一个改进算法。
在图中，我们可以建立一个平面图，将八台CNC按照顺序依次标记，RGV的初始位置标记为点9。假设RGV距离点1，3，5，7距离为0.1，距离点2，4，6，8距离为0.2.运行的路径与时间成线性关系。建立方程，并用MATLAB来模拟路线；
最后我们可以在MATLAB中得到一组最优路线，即9→1→2→3→4→5→6→7→8→9.
模型稳定性分析： 由于我们只分析了刚开始的情况，没有讨论到后来当RGV收到的信号距离自己最近时应该先去，路径最优原理。所以使我们建造的模型并不是全局最，而是局部最优模型。所以，运用目标规划基本原理建立新的模型（即模型二）
图4.2 CNC#1工作情况
3.3模型二
目标函数为：CNC总空闲时间最短。
约束条件：1、同一时间RGV只能处于一个状态，服务一个CNC。2、每个物料的上料加工清洗下料顺序一致。3、每台CNC同一时间只加工一个物料。4、CNC在RGV上料之后才进行加工，下料清洗上料这段时间是处于空闲状态，但此时间段内不计入空闲时间。
列出公式：
用MATLAB编程解决此问题，即可实现对原模型的求解。
对模型的稳定性分析：
同一CNC上第3、4列之间的时间间隔，即为空闲时间，总的空闲时间最小，加工的工件越多，即CNC利用率越高，根据程序得出结果第二组数据中空闲总时间为838秒，即总的空闲时间也只够一个物料加工时间，单个CNC空闲时间只有105秒，利用率已经达到了极限了，空闲率只有0.36%
3.4模型三
本模型主要是研究当两道工序的物料加工作业情况，每个物料的第一和第二道工序分别由两台不同的CNC依次加工完成时，智能RGV的路径和CNC数量和位置的安排对在规定时间内产生成料（即CNC总空闲时间）的影响。我们同样可以利用目标规划来建立模型。但必须分开讨论两种情况。
1、加工第一道工序的CNC的台数和位置。2、RGV的路径问题。
针对调度策略，仍以空闲时间最短为目标，数学模型仍以问题一的模型为基础。
约束条件：
1、每台CNC同一时间只能安装1种刀具加工1个物料。2、RGV同一时间只能执行移动、停止等待、上下料和清洗作业中的一项，且同一时间只能为一个CNC服务。3、CNC在RGV上料之后才进行加工，下料清洗上料这段时间是处于空闲状态，但此时间段内不计入空闲时间。4、清洗槽每次只能清洗一个物件。5、在RGV为某CNC完成一次上下料作业后，就会转动机械臂，将一只机械手上的熟料移动到清洗槽上方，進行清洗作业（只清洗加工完成的熟料）。6、工序1完工时刻就小于等于工序2上料时刻。
模型求解算法仍以RGV为状态为核心，运用贪心算法RGV总是优先服务最早可加工完成下一个工件的CNC，当工序为两步时，RGV的服务过程是先服务工序1的CNC，在换下工序1的工件后立即将工件传送至执行工序2的CNC。两步都选择最早完成加工工件CNC作为服务对象。
最后经过层层迭代可以得出最优解，当时间达到28800S时，共生成成料227件，熟料为228件，经过遗传算法得出其最优，然后经过仿真实验可以画出生成料和熟料。
图4.4模型二中成料和熟料与时间的关系图
4故障时，模型的改进
CNC在加工过程中可能发生故障（据统计：故障的发生概率约为1%）的情况，每次故障排除（人工处理，未完成的物料报废）时间介于10～20分钟之间，故障排除后即刻加入作业序列。要求分别考虑一道工序和两道工序的物料加工作业情况。
我们就是在其前两个模型中加入一个条件约束，用同样的数学编程去解决该类问题的方法。由前两个模型做一下模型改进可以得出模型，当在模拟的过程中每个CNC加入故障模拟，利用rand函数随机使机器产生故障，产生故障的机器在维修过程中不可使用，这段时间相当于只有剩余机器在工作，对剩余CNC进行动态调控，过程和无误差一样。
5、模型评价
5.1模型优点
5.1.1所建的模型较全面地刻画出了问题的目标和约束，为模型的求解提供了基础。
5.1.2模型的求解过程中，对所有可行解进行了履历，从而确保了解的最佳性。
5.1.3建立的规划模型能与实际紧密联系，结合实际情况对问题进行求解，使得模型具有很好的通用性和推广性。
5.2模型的推广
运用基于遗传算法的多目标优化模型求解初步的调度方案，再结合plantsimulation对合适的优化方案进行对比选择以得到最优动态调度方案，这样的模型与仿真的组合可以推广到绝大多数物流生产的最优调度方案设计中。
5.3模型缺点
5.3.1该模型具有局限性，只能适用于特定条件下单个RGV动态调度优化问题，但是在现代生产中，经常用到多个RGV同时工作，该模型不能满足生产使用。
5.3.2该模型由于时间关系没有做出系统的稳定性分析，得到的数据准确率有所降低。
5.4改进方法
5.4.1该模型假设不够具体，模型运用公式过于单一，应将模型中的变量加多，考虑多种情况，这样才能更加贴合实际。
5.4.2建模型的时候应该作出具体的分析，不应该写出较为简单的稳定性分析，应当对模型重新进行稳定性分析。
参考文献
[1]姜起源谢金星叶俊，《数学模型（第三版）》：高等教育出版社，2013年8月。
[2]司马奎孙玺菁，《数学建模算法与应用》：国防工业出版社，2016年7月。
[3]卓金武李必文魏永生秦健，《MATLAB在数学建模中的应用（第二版）》：北京航空航天大学出版社，2014年9月。
[4]刘永强，基于遗传算法的RGV动态调度研究，合肥工业大学，2012年3月。
[5]王靖，立体仓库时空数据模型的构建与应用研究，南京师范大学，2011年3月10号。
[6]吴冰程思微张文琼梁加红，基于相关向量回归的仿真元建模方法，计算机工程，2010年3月。
[7]田国会，张攀李晓磊，尹建芹路飞，一类仓库作业优化问题的混合遗传算法研究，系统仿真学报，2004年6月。
通过分析模型二、三的建立，我们发现在利用RGV仿真运行时，运动轨迹逐渐趋向于最优化，证明了模型的实用性和算法的有效性。
[关键词]RGV ；CNC；最短路径法；遗传算法；MATLAB；仿真运行
中图分类号：TP759 文献标识码：A 文章编号：1009-914X（2018）10-0350-02
1问题的分析
本文主要对一般问题进行研究，给出RGV动态调度模型使其工作效率最高，在一个班次中产生的成料最多。在该智能加工系统工作的过程中CNC加工完成一个一道工序的物料所需时间、RGV为CNC1#，3#，5#，7#一次上下料所需时间、RGV为CNC2#，4#，6#，8#一次上下料所需时间以及RGV完成一个物料的清洗作业所需时间都是一个定值，在工作过程中是必须经历不能简化的，因此该问题就简化為规划RGV的最短路径，使所有CNC所空闲的时间最短。
智能加工系统通电启动后，RGV在CNC1#和CNC2#正中间的初始位置，所有CNC都处于空闲状态。RGV在1和2之间选择，因为RGV为CNC1#，3#，5#，7#一次上下料所需时间小于RGV为CNC2#，4#，6#，8#一次上下料所需时间，所以应先服务于CNC1。要想使得CNC空闲出来的时间最短，就必须使RGV空闲出来后需要优先服务最早可以开始加工的CNC，即RGV应服务于从上一个CNC的时刻到当前CNC等待时间所用时间最小的路径。
2模型假设与符号约定
2.1模型假设
（1）同一时间RGV只能处于一个状态，服务一个CNC。（2）RGV调度系统无故障，可实时知道材料加工情况和小车实时位置。（3）当多个CNC同时发出需求指令时，RGV依照距离RGV路程由近到远上下料。（4）传送带运行速度很快，可忽略不计。
2.2符号说明
（1）Tm：物料加工时间；（2）Tud：上下料时间；（3）Tmt：移动时间向量，i=123；（4）Tij：物料加工完成时间，第i个CNC完成第j个物料完工的时间；（5）Tsij：物料上料时刻；（6）Tc：清洗时间；（7）表示mi第i个CNC加工工件的数量。（8） 表示工件k的工序1完成加工时间。（9） 表示工s件k在CNCi的上下料时间，（10）Tc2表示工序2加工时间。
3模型的建立
3.1模型的准备
RGV英文全称为Rail-GuidedVehicle，即轨道式导引小车，国内一般称为穿梭小车或者穿梭车，是一种在车间或者自动化立体仓库中沿着轨道（可以是铁轨或者合金轨道）运行的物料运送工具，相对AGV（自动导引小车）等其他的运送工具，有以下特点：
（1）移动速度和加速度快，能够运送重型物料。（2）运行平稳，停车位置准确且易于精确控制。（3）设计制造较简单且可靠性高，能够大面积推广。
本题目中RGV为直行轨道式，又称直线往复式RGV，其在一段直线型轨道上运行一个或者多个RGV，通过往复运行可以实现运送物料的目的。这种RGV的优点是系统简单，制造成本和工艺简单，并且占地面积小和输送物流快捷方便，适合中小型物流的运送。缺点是运送能力有限，在轨道上不能同时运行太多的RGV。
3.2模型一
根据任务一中的第一种情况，目标是要建立数学模型来研究当一道工序的物料加工作业情况，每台CNC安装同样的刀具，物料可以在任一台CNC上加工完成时，RGV动态调度模型和相应的求解算法。根据运筹学相关知识，我们很容易可以得出可以用最短路径算法来建立RGV动态调度模型。
因为该题目中RGV移动的距离与所需时间成线性关系，在两边加料和下料花费的时间不同，并且所有的成品都必须经过一个清洗过程，花费的时间相同。所以我们可以将此时间问题转化为路径问题，将RGV在一维线上运动转化为二维平面上求最短路径问题，将所有任务点按照泊松分布策略生成，将RGV初始时间和速度做标记，根据任务点生成的时间和位置进行动态标记，也就是对TSP算法的一个改进算法。
在图中，我们可以建立一个平面图，将八台CNC按照顺序依次标记，RGV的初始位置标记为点9。假设RGV距离点1，3，5，7距离为0.1，距离点2，4，6，8距离为0.2.运行的路径与时间成线性关系。建立方程，并用MATLAB来模拟路线；
最后我们可以在MATLAB中得到一组最优路线，即9→1→2→3→4→5→6→7→8→9.
模型稳定性分析： 由于我们只分析了刚开始的情况，没有讨论到后来当RGV收到的信号距离自己最近时应该先去，路径最优原理。所以使我们建造的模型并不是全局最，而是局部最优模型。所以，运用目标规划基本原理建立新的模型（即模型二）
图4.2 CNC#1工作情况
3.3模型二
目标函数为：CNC总空闲时间最短。
约束条件：1、同一时间RGV只能处于一个状态，服务一个CNC。2、每个物料的上料加工清洗下料顺序一致。3、每台CNC同一时间只加工一个物料。4、CNC在RGV上料之后才进行加工，下料清洗上料这段时间是处于空闲状态，但此时间段内不计入空闲时间。
列出公式：
用MATLAB编程解决此问题，即可实现对原模型的求解。
对模型的稳定性分析：
同一CNC上第3、4列之间的时间间隔，即为空闲时间，总的空闲时间最小，加工的工件越多，即CNC利用率越高，根据程序得出结果第二组数据中空闲总时间为838秒，即总的空闲时间也只够一个物料加工时间，单个CNC空闲时间只有105秒，利用率已经达到了极限了，空闲率只有0.36%
3.4模型三
本模型主要是研究当两道工序的物料加工作业情况，每个物料的第一和第二道工序分别由两台不同的CNC依次加工完成时，智能RGV的路径和CNC数量和位置的安排对在规定时间内产生成料（即CNC总空闲时间）的影响。我们同样可以利用目标规划来建立模型。但必须分开讨论两种情况。
1、加工第一道工序的CNC的台数和位置。2、RGV的路径问题。
针对调度策略，仍以空闲时间最短为目标，数学模型仍以问题一的模型为基础。
约束条件：
1、每台CNC同一时间只能安装1种刀具加工1个物料。2、RGV同一时间只能执行移动、停止等待、上下料和清洗作业中的一项，且同一时间只能为一个CNC服务。3、CNC在RGV上料之后才进行加工，下料清洗上料这段时间是处于空闲状态，但此时间段内不计入空闲时间。4、清洗槽每次只能清洗一个物件。5、在RGV为某CNC完成一次上下料作业后，就会转动机械臂，将一只机械手上的熟料移动到清洗槽上方，進行清洗作业（只清洗加工完成的熟料）。6、工序1完工时刻就小于等于工序2上料时刻。
模型求解算法仍以RGV为状态为核心，运用贪心算法RGV总是优先服务最早可加工完成下一个工件的CNC，当工序为两步时，RGV的服务过程是先服务工序1的CNC，在换下工序1的工件后立即将工件传送至执行工序2的CNC。两步都选择最早完成加工工件CNC作为服务对象。
最后经过层层迭代可以得出最优解，当时间达到28800S时，共生成成料227件，熟料为228件，经过遗传算法得出其最优，然后经过仿真实验可以画出生成料和熟料。
图4.4模型二中成料和熟料与时间的关系图
4故障时，模型的改进
CNC在加工过程中可能发生故障（据统计：故障的发生概率约为1%）的情况，每次故障排除（人工处理，未完成的物料报废）时间介于10～20分钟之间，故障排除后即刻加入作业序列。要求分别考虑一道工序和两道工序的物料加工作业情况。
我们就是在其前两个模型中加入一个条件约束，用同样的数学编程去解决该类问题的方法。由前两个模型做一下模型改进可以得出模型，当在模拟的过程中每个CNC加入故障模拟，利用rand函数随机使机器产生故障，产生故障的机器在维修过程中不可使用，这段时间相当于只有剩余机器在工作，对剩余CNC进行动态调控，过程和无误差一样。
5、模型评价
5.1模型优点
5.1.1所建的模型较全面地刻画出了问题的目标和约束，为模型的求解提供了基础。
5.1.2模型的求解过程中，对所有可行解进行了履历，从而确保了解的最佳性。
5.1.3建立的规划模型能与实际紧密联系，结合实际情况对问题进行求解，使得模型具有很好的通用性和推广性。
5.2模型的推广
运用基于遗传算法的多目标优化模型求解初步的调度方案，再结合plantsimulation对合适的优化方案进行对比选择以得到最优动态调度方案，这样的模型与仿真的组合可以推广到绝大多数物流生产的最优调度方案设计中。
5.3模型缺点
5.3.1该模型具有局限性，只能适用于特定条件下单个RGV动态调度优化问题，但是在现代生产中，经常用到多个RGV同时工作，该模型不能满足生产使用。
5.3.2该模型由于时间关系没有做出系统的稳定性分析，得到的数据准确率有所降低。
5.4改进方法
5.4.1该模型假设不够具体，模型运用公式过于单一，应将模型中的变量加多，考虑多种情况，这样才能更加贴合实际。
5.4.2建模型的时候应该作出具体的分析，不应该写出较为简单的稳定性分析，应当对模型重新进行稳定性分析。
参考文献
[1]姜起源谢金星叶俊，《数学模型（第三版）》：高等教育出版社，2013年8月。
[2]司马奎孙玺菁，《数学建模算法与应用》：国防工业出版社，2016年7月。
[3]卓金武李必文魏永生秦健，《MATLAB在数学建模中的应用（第二版）》：北京航空航天大学出版社，2014年9月。
[4]刘永强，基于遗传算法的RGV动态调度研究，合肥工业大学，2012年3月。
[5]王靖，立体仓库时空数据模型的构建与应用研究，南京师范大学，2011年3月10号。
[6]吴冰程思微张文琼梁加红，基于相关向量回归的仿真元建模方法，计算机工程，2010年3月。
[7]田国会，张攀李晓磊，尹建芹路飞，一类仓库作业优化问题的混合遗传算法研究，系统仿真学报，2004年6月。