论文部分内容阅读
摘 要：本文针对基于CNC和RGV构成的智能加工系统的动态调度进行了详细研究，建立了2道工序在无故障的动态优化模型，并分别利用贪心算法和遗传算法对所建优化模型进行求解。本文运用搜索树对每一次RGV确定CNC的上下料作业顺序进行决策，搜索域为与RGV距离最短的3个CNC，寻找最短的遍历3个CNC的路径，通过运行算法输出第一组、第二组、第三组产出熟料的数量分别为371、346、371。
关键词：动态调度模型 粒子群算法 搜索树
中图分类号：TP39 文献标识码：A 文章编号：1674-098X（2019）04（a）-0124-02
智能RGV加工系统主要由8台计算机数控机床（CNC）、1辆自动引导车（RGV）、1条上料传送带和1条下料传送带构成，其中RGV是一种根据指令在固定轨道上自动控制移动方向和距离的智能车，并自一个带机械手臂、两只机械手爪和物料清洗槽，从而完成上下料及清洗物料等任务。
RGV系统由中间至两边分别为自动引导车RGV、物料传送带和数控机床CNC。自带机械手和清洗槽的自动引导车RGV，机械手臂前端的两个手爪通过旋转可先后抓取一个物料（未加工生料或已加工熟料），从而完成上下料任务；清洗槽每次仅可清洗1个熟料（不可清洗生料）。RGV系统的工作流程为：（1）RGV位于初始位置，所有CNC空闲→（2）空闲CNC向RGV发上料信号→（3）RGV收到信号，确定CNC上下料次序并完成上下料→（4）每完成一次上下料进行清洗作业→（5）REV完成一项任务后执行下一指令或原地等待→（6）重复步骤（3）～（5）直至系统停止作业。
对于有n（n=2）道加工工序的物料，将RGV的工作状态分为为第 道工序进行上下料几个作业状态，并考虑到n道加工顺序和CNC出现故障后维修时间的连续性，找到一种可行的调度方案，使CNC在时间约束下空闲时间最小。
1 符号说明
符号说明，如表1所示。
2 模型假设
（1）CNC系统在整个系统运行过程中，保持正常运行；（2）每台CNC前的传送带提供物料量远大于RGV的需求量，由于传送带造成的微小误差可忽略不计；（3）CNC在换刀片的过程中可以直接更换，不需要更换的时间；
3 模型的建立与求解
有2道工序的物料进行加工，目标为使得8h内完成的熟料个数最多。由于本题有2道工序，首先根据加工第1道工序所用时间与加工第2道工序所用时间的按比例分配加工2道工序CNC数量分别为N1、N2；其次对于RGV的线路规划秉承距离近的CNC先进行上下料作业的原则，可使得8h内CNC作业时间多。由于具有2道加工工序的物料加工总时间远大于RGV移动、上下料和清洗的时间，即出现多个CNC同时发出需求信号的几率是非常小的，秉承模型合理性以及实用性的原则，本模型对RGV的线路规划秉承距离近的CNC先进行上下料作业的原则。
在RGV系统整个运行过程中，RGV可分为3个主要阶段：为执行第1道工序的CNC进行上下料操作、为执行第2道工序的CNC进行上下料操作和休息。假设RGV携带已完成第1道工序的物料，此时用于加工第2道工序的CNC是n（n≤N2）个发出需求、用于第2道工序的CNC中距RGV最近的CNC，从而使CNC的时间利用尽可能的充分，达到完成数量足够多的目的。
算法设计：
除了的位置、完成本次加工物料时刻以及加工单个物料所需时间三个属性，RGV的位置和时刻两个属性以外，由于需要确定RGV下一阶段将对第几道工序的CNC进行上下料作业，因此对CNC增加是否携带物料属性，此物料为仅完成第一道加工工序的物料，由于不是加工完成的熟料，故此物料不用执行清洗作业。
本算法仍以RGV的时刻变化作为整个智能RGV系统的工作时间。对于RGV来说，只有为加工第1道工序的CNC换料、为加工第2道工序的CNC换料和原地等待三种状态，且同一时间内RGV只能执行其中一项，因此可将RGV整个工作程序分解为RGV为执行某一道工序的CNC进行上下料的小步骤。
下面给出算法的详细步骤：
（1）初始化CNCi的位置CNCi pos、完成本次加工物料时刻CNCi time、加工单个物料所需的时间t和CNCi是否携带物料，RGV的时间RGVt与RGVpos位置，用于加工第一道工序的CNC集合A以及用于加工第二道工序的CNC集合B。
（2）时间约束：判断RGV的时间是否小于8h：如果是，执行步骤（3）；如果不是，运行停止。
（3）判断RGV上是否有物料：如果是，执行步骤（4）；如果不是，执行步骤（7）；
（4）判断集合B中是否有CNC发送需求：判断用于加工第二道工序的CNC集合B中是否有RGV的时间RGVt大于CNCi的时间：如果是，执行步骤（5）；如果不是，执行步骤（6）；
（5）决定对集合B中的CNC作业顺序并对CNCi和RGV的属性更新：秉承距离近的CNC先进行上下料作业的原则寻找全局最优线路，确定RGV下一个进行上下料作业的CNCi，并对CNCi的时间、RGV的时间、位置和是否携带物料进行更新，应注意此时对RGV时间RGVt的更新不包括对物料清洗的步骤，因为此物料为仅完成第一道加工工序的物料，下转步骤（2）；
（6）集合B中没有CNC发送需求信号，对RGV的时间进行更新，RGV的时间CNCi为集合B中所有CNC时间中最小值，下转步骤（4）；
（7）判断集合A中是否有CNC发送需求：判断用于加工第一道工序的CNC集合A中是否有RGV的时间RGVt大于CNCi的时间：如果是，执行步骤（8）；如果不是，执行步骤（9）；
（8）决定对集合A中的CNC作业顺序并对CNCi和RGV的属性更新：确定RGV下一个进行上下料作业的CNCi，并对CNCi的时间、RGV的时间、位置以及是否携带物料进行更新，下转步骤（2）；
（9）集合A中没有CNC发送需求信号，对RGV的时间进行更新，RGV的时间CNCi为集合A中所有CNC时间中最小值，下转步骤（7）。
4 模型结果
在2道工序中，我们计算出的结果示237，所得到的顺序为0256。在2道工序模型的整个建立的过程中，采用粒子群算法进行分配工序给CNC，这样通过大量交叉、变异的方案，能做到相對最优，得到次优解，对CNC进行动态调度以时间优先，RGV做决策也会影响CNC的等待时间，我们建立了RGV的搜索树，进行广度搜索，这样保证了不会陷入局部最优解。
参考文献
[1] 杨红红，吴智铭.基于自适应遗传算法的柔性动态调度研究[J].中国机械工程，2002（21）：1845-1848.
[2] 唐然，龙腾锐，龙向宇宙.基于模糊聚类的改进遗传算法[J].重庆大学学报：自然科学版，2008，31（2）：166-169.
[3] 殷文.改进的并行遗传模型的构建及应用[J].计算机工程，2008，34（4）：203-206.
关键词：动态调度模型 粒子群算法 搜索树
中图分类号：TP39 文献标识码：A 文章编号：1674-098X（2019）04（a）-0124-02
智能RGV加工系统主要由8台计算机数控机床（CNC）、1辆自动引导车（RGV）、1条上料传送带和1条下料传送带构成，其中RGV是一种根据指令在固定轨道上自动控制移动方向和距离的智能车，并自一个带机械手臂、两只机械手爪和物料清洗槽，从而完成上下料及清洗物料等任务。
RGV系统由中间至两边分别为自动引导车RGV、物料传送带和数控机床CNC。自带机械手和清洗槽的自动引导车RGV，机械手臂前端的两个手爪通过旋转可先后抓取一个物料（未加工生料或已加工熟料），从而完成上下料任务；清洗槽每次仅可清洗1个熟料（不可清洗生料）。RGV系统的工作流程为：（1）RGV位于初始位置，所有CNC空闲→（2）空闲CNC向RGV发上料信号→（3）RGV收到信号，确定CNC上下料次序并完成上下料→（4）每完成一次上下料进行清洗作业→（5）REV完成一项任务后执行下一指令或原地等待→（6）重复步骤（3）～（5）直至系统停止作业。
对于有n（n=2）道加工工序的物料，将RGV的工作状态分为为第 道工序进行上下料几个作业状态，并考虑到n道加工顺序和CNC出现故障后维修时间的连续性，找到一种可行的调度方案，使CNC在时间约束下空闲时间最小。
1 符号说明
符号说明，如表1所示。
2 模型假设
（1）CNC系统在整个系统运行过程中，保持正常运行；（2）每台CNC前的传送带提供物料量远大于RGV的需求量，由于传送带造成的微小误差可忽略不计；（3）CNC在换刀片的过程中可以直接更换，不需要更换的时间；
3 模型的建立与求解
有2道工序的物料进行加工，目标为使得8h内完成的熟料个数最多。由于本题有2道工序，首先根据加工第1道工序所用时间与加工第2道工序所用时间的按比例分配加工2道工序CNC数量分别为N1、N2；其次对于RGV的线路规划秉承距离近的CNC先进行上下料作业的原则，可使得8h内CNC作业时间多。由于具有2道加工工序的物料加工总时间远大于RGV移动、上下料和清洗的时间，即出现多个CNC同时发出需求信号的几率是非常小的，秉承模型合理性以及实用性的原则，本模型对RGV的线路规划秉承距离近的CNC先进行上下料作业的原则。
在RGV系统整个运行过程中，RGV可分为3个主要阶段：为执行第1道工序的CNC进行上下料操作、为执行第2道工序的CNC进行上下料操作和休息。假设RGV携带已完成第1道工序的物料，此时用于加工第2道工序的CNC是n（n≤N2）个发出需求、用于第2道工序的CNC中距RGV最近的CNC，从而使CNC的时间利用尽可能的充分，达到完成数量足够多的目的。
算法设计：
除了的位置、完成本次加工物料时刻以及加工单个物料所需时间三个属性，RGV的位置和时刻两个属性以外，由于需要确定RGV下一阶段将对第几道工序的CNC进行上下料作业，因此对CNC增加是否携带物料属性，此物料为仅完成第一道加工工序的物料，由于不是加工完成的熟料，故此物料不用执行清洗作业。
本算法仍以RGV的时刻变化作为整个智能RGV系统的工作时间。对于RGV来说，只有为加工第1道工序的CNC换料、为加工第2道工序的CNC换料和原地等待三种状态，且同一时间内RGV只能执行其中一项，因此可将RGV整个工作程序分解为RGV为执行某一道工序的CNC进行上下料的小步骤。
下面给出算法的详细步骤：
（1）初始化CNCi的位置CNCi pos、完成本次加工物料时刻CNCi time、加工单个物料所需的时间t和CNCi是否携带物料，RGV的时间RGVt与RGVpos位置，用于加工第一道工序的CNC集合A以及用于加工第二道工序的CNC集合B。
（2）时间约束：判断RGV的时间是否小于8h：如果是，执行步骤（3）；如果不是，运行停止。
（3）判断RGV上是否有物料：如果是，执行步骤（4）；如果不是，执行步骤（7）；
（4）判断集合B中是否有CNC发送需求：判断用于加工第二道工序的CNC集合B中是否有RGV的时间RGVt大于CNCi的时间：如果是，执行步骤（5）；如果不是，执行步骤（6）；
（5）决定对集合B中的CNC作业顺序并对CNCi和RGV的属性更新：秉承距离近的CNC先进行上下料作业的原则寻找全局最优线路，确定RGV下一个进行上下料作业的CNCi，并对CNCi的时间、RGV的时间、位置和是否携带物料进行更新，应注意此时对RGV时间RGVt的更新不包括对物料清洗的步骤，因为此物料为仅完成第一道加工工序的物料，下转步骤（2）；
（6）集合B中没有CNC发送需求信号，对RGV的时间进行更新，RGV的时间CNCi为集合B中所有CNC时间中最小值，下转步骤（4）；
（7）判断集合A中是否有CNC发送需求：判断用于加工第一道工序的CNC集合A中是否有RGV的时间RGVt大于CNCi的时间：如果是，执行步骤（8）；如果不是，执行步骤（9）；
（8）决定对集合A中的CNC作业顺序并对CNCi和RGV的属性更新：确定RGV下一个进行上下料作业的CNCi，并对CNCi的时间、RGV的时间、位置以及是否携带物料进行更新，下转步骤（2）；
（9）集合A中没有CNC发送需求信号，对RGV的时间进行更新，RGV的时间CNCi为集合A中所有CNC时间中最小值，下转步骤（7）。
4 模型结果
在2道工序中，我们计算出的结果示237，所得到的顺序为0256。在2道工序模型的整个建立的过程中，采用粒子群算法进行分配工序给CNC，这样通过大量交叉、变异的方案，能做到相對最优，得到次优解，对CNC进行动态调度以时间优先，RGV做决策也会影响CNC的等待时间，我们建立了RGV的搜索树，进行广度搜索，这样保证了不会陷入局部最优解。
参考文献
[1] 杨红红，吴智铭.基于自适应遗传算法的柔性动态调度研究[J].中国机械工程，2002（21）：1845-1848.
[2] 唐然，龙腾锐，龙向宇宙.基于模糊聚类的改进遗传算法[J].重庆大学学报：自然科学版，2008，31（2）：166-169.
[3] 殷文.改进的并行遗传模型的构建及应用[J].计算机工程，2008，34（4）：203-206.