全国大学生数学建模竞赛2018年B题智能的动态调度策略及论文精选

2018年高教社杯全国大学生数学建模竞赛题目（请先阅读“全国大学生数学建模竞赛论文格式规范”）问题B智能RGV的动态调度策略图1是一个智能加工系统的示意图，由8台计算机数控机床（ComputerNumberController，CNC）、1辆轨道式自动引导车（RailGuideVehicle，RGV）、1条RGV直线轨道、1条上料传送带、1条下料传送带等附属设备组成。RGV是一种无人驾驶、能在固定轨道上自由运行的智能车。它根据指令能自动控制移动方向和距离，并自带一个机械手臂、两只机械手爪和物料清洗槽，能够完成上下料及清洗物料等作业任务（参见附件1）。图1：智能加工系统示意图针对下面的三种具体情况：（1）一道工序的物料加工作业情况，每台CNC安装同样的刀具，物料可以在任一台CNC上加工完成；（2）两道工序的物料加工作业情况，每个物料的第一和第二道工序分别由两台不同的CNC依次加工完成；（3）CNC在加工过程中可能发生故障（据统计：故障的发生概率约为1%）的情况，每次故障排除（人工处理，未完成的物料报废）时间介于10~20分钟之间，故障排除后即刻加入作业序列。要求分别考虑一道工序和两道工序的物料加工作业情况。请你们团队完成下列两项任务：任务1：对一般问题进行研究，给出RGV动态调度模型和相应的求解算法；任务2：利用表1中系统作业参数的3组数据分别检验模型的实用性和算法的有效性，给出RGV的调度策略和系统的作业效率，并将具体的结果分别填入附件2的EXCEL表中。表1：智能加工系统作业参数的3组数据表时间单位：秒系统作业参数第1组第2组第3组RGV移动1个单位所需时间202318RGV移动2个单位所需时间334132RGV移动3个单位所需时间465946CNC加工完成一个一道工序的物料所需时间560580545CNC加工完成一个两道工序物料的第一道工序所需时间400280455CNC加工完成一个两道工序物料的第二道工序所需时间378500182RGV为CNC1#，3#，5#，7#一次上下料所需时间283027RGV为CNC2#，4#，6#，8#一次上下料所需时间313532RGV完成一个物料的清洗作业所需时间253025注：每班次连续作业8小时。附件1：智能加工系统的组成与作业流程附件2：模型验证结果的EXCEL表（完整电子表作为附件放在支撑材料中提交）1基于多原则比较和蒙特卡洛模拟的RGV动态调度模型摘要本文从规划模型、多原则求解的角度，综合了蒙特卡洛模拟与机器学习的思想，研究了由8台CNC、1辆RGV以及其他附属设备组成的智能加工系统的动态调度问题，并给出了不同工序情况下的具体调度方案。针对情况一：单工序的作业流程较为简单。首先，利用规划的各个约束条件，刻画了RGV在CNC之间的运动过程、单个物料的加工过程、“上下料”时RGV手爪的旋转过程、清洗作业的过程、RGV移动至下一个机床进行加工的过程等等。此外，还刻画了物料加工与运送的“唯一性”，以及利用0-1变量构造的目标函数。规划的目的是，在给定的时间内，使得加工出的物料数量最多。然而，这样的规划是一个NP问题，无法通过传统的方法求解，所以进而寻求模拟的方法求得局部最优解。本文选取了“就近原则”——构造时间代价函数，“FIFO原则”——考虑各台CNC的等待时间，以及“HRRN原则”——将时间代价与等待时间进行综合考虑，分别对情况一进行了模拟。事实上，每种原则的结果相同：第一组数据加工完成了383件物料，第二组数据加工完成了360件物料，第三组数据加工完成了393件物料。并且，调度的方案全部为1→2→…→8→1→…此外，第三组数据的系统效率最高，为49.125件/h.针对情况二：双工序的作业流程十分复杂。首先，在情况一的基础上，对规划的各个约束条件进行修正；并着重刻画了RGV移动至下一个机床进行加工的过程。此外，双工序流程中各台CNC所负责的工序也是不确定的；因此，本文对256种工序布局方案，结合三种选取原则，进行了遍历。得到的结果是：第一组数据的各台CNC最优工序分配为1-2-1-2-1-2-1-2，三种原则结果一致，最终加工出253件物料；第二组数据的各台CNC最优工序分配为2-1-2-1-2-1-2-1，“FIFO原则”和“HRRN原则”更优，最终加工出212件物料；第三组数据的各台CNC最优工序分配为1-1-2-1-2-1-1-2，“就近原则”最优，最终加工出241件物料。此外，所有的调度方案均呈现有规律的循环状态。然后，利用“基于蒙特卡洛的学习算法”，在构造正反馈的前提下“随机”地尝试以获得更优解。结果反映了，三种原则中的最优原则，已非常接近全局最优。此外，第一组数据和第三组数据的作业效率一样高，均为30.125件/h.针对情况三：同时考虑单工序流程与双工序流程。构造了随机变量“是否故障”、“故障发生时间”和“故障排除时间”，并将它们融合进入规划模型。求解结果显示，遭遇故障后，单工序流程系统效率最多下降了2.25件/h，而双工序流程系统效率最多下降了1.875件/h.本文的亮点在于：首先，利用一般化的公式对系统调度进行了较为细致的机理分析，使得模型具有普适性；其次，给出了多个调度原则相互比较，从而有利于结果更优；最后，将蒙特卡洛模拟与机器学习的思想相结合，对上述调度原则的有效性进行验证，增强了模型的说服力。关键词规划模型；多原则比较；蒙特卡洛模拟；机器学习；动态调度21.问题的重述现有一个智能加工系统，由8台CNC、1辆RGV以及其他附属设备组成。RGV能够根据指令与决策，在水平的轨道上自动控制移动的方向和距离，并通过机械手爪、机械臂等部件完成“上下料”、“清洗作业”等诸多过程。对于以下三种情况：①加工过程包含1道工序且每台CNC都可以进行加工；②加工过程包含2道工序且每台CNC只能完成1道工序；③某CNC在加工过程中发生故障，故障需人工排除，且该CNC上的物料报废；考虑完成两个任务：首先，给出一般的模型，并给出模型的求解算法；然后，检验模型的实用性和算法的有效性，并给出具体调度策略和系统作业效率。2.问题的分析对于情况（1），整个加工系统仅有一个工序。从物料的形态演化过程来看，生料经过CNC的加工成为熟料，而熟料经过RGV的清洗成为成料。从RGV的作业过程来看，RGV首先需要选取一台候选CNC，然后移动至该CNC，放入生料，取出熟料，再将熟料进行清洗使之变为成料（包括送出系统）——最终RGV将进入下一轮选择CNC的阶段。图1情况（1）物料的形态演化对于情况（2），整个加工系统有两个工序。从物料的形态演化过程来看，生料经过“一工序CNC”的加工成为半熟料，而半熟料经过“二工序CNC”的加工成为熟料，最后熟料经过RGV的清洗成为成料。图2情况（1）物料的形态演化对于情况（3），整个系统出现了故障。根据题目所给条件，需要依此考虑对于某个物料的加工，是否发生故障，故障发生的时间，以及故障排除时间这三个随机变量。本文拟构建一般性的规划，理清系统内部的机理关系。然后，通过提出不同的原则，编写算法，解决该规划问题；并通过“基于蒙特卡洛的学习算法”，比较、检验不同原则的优劣。3.模型的假设与符号的说明3.1模型的假设（1）生料的供应是无限的。生料熟料成料生料半熟料熟料成料3（2）不考虑RGV转向的时间，即RGV从CNC1#到CNC2#，从CNC3#到CNC4#，从CNC5#到CNC6#，从CNC7#到CNC8#的时间全部为0.（3）上料传送带可以及时将生料运往需要的CNC正前方，下料传送带可以及时将成料运出整个系统。3.2符号的说明表1符号的说明符号说明单位𝑑𝑑𝑖𝑖RGV移动𝑖𝑖个单位所需时间秒𝑡𝑡𝑎𝑎𝑎𝑎RGV从机床𝑎𝑎移动到机床𝑏𝑏的时间秒𝑎𝑎𝑗𝑗𝑎𝑎𝑎𝑎号机床所加工的第𝑗𝑗𝑎𝑎个物料件𝑡𝑡0物料加工时间秒𝑡𝑡1物料清洗时间秒𝑡𝑡2(𝑎𝑎)第𝑎𝑎台机床“上下料”时间秒𝑅𝑅𝑎𝑎𝑗𝑗𝑎𝑎生料𝑎𝑎𝑗𝑗𝑎𝑎“上料”完成时刻秒𝐶𝐶𝑎𝑎𝑗𝑗𝑎𝑎熟料𝑎𝑎𝑗𝑗𝑎𝑎“下料”完成时刻秒𝐻𝐻𝑎𝑎𝑗𝑗𝑎𝑎成料𝑎𝑎𝑗𝑗𝑎𝑎完成清洗时刻秒𝑦𝑦𝑎𝑎𝑗𝑗𝑎𝑎,𝑎𝑎𝑗𝑗𝑏𝑏两件独立熟料下机床时间的先后顺序0-1变量𝑧𝑧𝑎𝑎𝑎𝑎RGV是否从𝑎𝑎移动至𝑏𝑏0-1变量4.模型的建立、求解与分析4.1情况（1）模型的建立、求解与分析4.1.1单工序的作业流程在情况（1）中，物料加工程序仅由一道工序组成。其中，每台CNC安装同样的刀具，而物料可以在任意一台CNC上加工完成。纵观整个单工序的加工过程，可以发现，当某台CNC完成加工，即完成“生料→熟料”的过程时，便处于等待状态，并向RGV发出需求信号。当RGV移动至该CNC正前方时，连续完成下述步骤：（1）上下料：将熟料取出CNC，并向CNC放入新的生料，这两步同时完4成；（2）清洗作业：将取出的熟料进行清洗，完成“熟料→成料”过程，而后将成料放入传送带送出系统，此时RGV在轨道上位置不变。此后，RGV需要根据需求信号的先后顺序、距离的远近等信息，寻找下一个作业候选CNC，然后重复上述（1）（2）两个步骤，周而复始，直至8个小时结束。4.1.2单工序的调度模型考虑到模型的一般化问题，此处本文拟利用规划的方法，寻找并构建各台CNC以及生产物料的数量关系。1.RGV在CNC之间运动时间的刻画不妨设，现有任意两台CNC，分别记作𝑎𝑎，𝑏𝑏，其中𝑎𝑎=1,2,…,8;𝑏𝑏=1,2,…,8.考虑到机床安放的位置关系——偶数号码机床位于系统左侧，奇数号码机床位于系统右侧——则RGV从机床𝑎𝑎移动到机床𝑏𝑏的时间为：𝑡𝑡𝑎𝑎𝑎𝑎=⎩�����⎨�����⎧0,��𝑎𝑎+12�−�𝑏𝑏+12��=0𝑑𝑑1,��𝑎𝑎+12�−�𝑏𝑏+12��=1𝑑𝑑2,��𝑎𝑎+12�−�𝑏𝑏+12��=2𝑑𝑑3,��𝑎𝑎+12�−�𝑏𝑏+12��=3其中，𝑑𝑑𝑖𝑖为RGV移动𝑖𝑖个单位所需时间。2.基于单个物料加工过程的刻画Step1.将𝑎𝑎号机床所加工的第𝑗𝑗𝑎𝑎个物料记为𝑎𝑎𝑗𝑗𝑎𝑎.经过粗略的计算，在8小时内该系统可加工完成的物料数量级为102，所以准备103个生料一定足够。因此，参数取值范围可以取为𝑗𝑗𝑎𝑎=1,2,…,1000.相对应地，将尚为生料的𝑎𝑎𝑗𝑗𝑎𝑎被RGV放入𝑎𝑎号机床（“上料”过程完成）的时刻，记为𝑅𝑅𝑎𝑎𝑗𝑗𝑎𝑎；将已加工为熟料的𝑎𝑎𝑗𝑗𝑎𝑎被RGV取出𝑎𝑎号机床（“下料”过程完成）的时刻，记为𝐶𝐶𝑎𝑎𝑗𝑗𝑎𝑎.此外，物料加工时间记为𝑡𝑡0，清洗时间记为𝑡𝑡1，第𝑎𝑎台机床“上下料”时间记为𝑡𝑡2(𝑎𝑎).𝑡𝑡2(𝑎𝑎)=⎩�⎨�⎧𝑡𝑡2(1),mod(𝑎𝑎2)≠0𝑡𝑡2(2),mod(𝑎𝑎2)=0.其中，𝑡𝑡2(1)为RGV为CNC1#，3#，5#，7#进行一次上下料所需时间，𝑡𝑡2(2)为RGV为CNC2#，4#，6#，8#进行一次上下料所需时间。5Step2.基于上述符号的定义，可以得到：�𝐶𝐶𝑎𝑎𝑗𝑗𝑎𝑎−𝑅𝑅𝑎𝑎𝑗𝑗𝑎𝑎≥𝑡𝑡0+𝑡𝑡2(𝑎𝑎),𝐶𝐶𝑎𝑎𝑗𝑗𝑎𝑎≤8×60×60−𝑡𝑡1𝐶𝐶𝑎𝑎𝑗𝑗𝑎𝑎=0,其他（1）（1）式的意义为，若物料𝑎𝑎𝑗𝑗𝑎𝑎加工完成时间在8小时终止以前，那么物料𝑎𝑎𝑗𝑗𝑎𝑎从被放入CNC开始，直至被取出CNC，所经历的时间至少为加工时间𝑡𝑡0与“上下料”时间𝑡𝑡2(𝑎𝑎)两者之和。𝐶𝐶𝑎𝑎𝑗𝑗𝑎𝑎−𝑅𝑅𝑎𝑎𝑗𝑗𝑎𝑎之所以可能大于𝑡𝑡0+𝑡�