搜索
1RGV动态调度模型摘要：RGV是智能加工系统的中间环节，控制RGV的动态调度也就是控制了智能加工系统的工作流程。需要在四种不同的情况下对RGV进行调度分析:单工序、单工序有故障、双工序、双工序无故障。单工序的情况下建立了三个模型：数学规划模型、单工序分层预测模型、单工序局部最优模型。数学规划模型将第i件物料的上料时间、下料时间、CNC编号等设为自变量，以RGV的15个初始状态、一台CNC上相邻处理的两件物料的上料时间关系等因素作为约束条件，以最后一件物料的上料时间最小为目标函数。但因为求解这种模型的程序时间复杂度较高，准确度较低，又建立了单工序分层预测模型和单工序局部最优模型，用算法模拟该智能加工系统的工作流程。单工序分层预测模型中，RGV每次判断执行请求的次序时，都会预先模拟系统向下选择两次，找到效率最高的一种方案。单工序局部最优模型是以发出请求的CNC与RGV之间的距离为衡量指标，优先选择距离最近的请求，如果距离一样，优先选择CNC编号为奇数的请求。三种模型的运行结果表明：系统工作效率由高到低依次是数学规划模型、单工序分层预测模型、单工序局部最优模型。但是数学规划模型只能算出前88件物料所用时间，8个小时内可以加工的总物料数目只能推测出来，准确度有待验证。因此判定单工序分层预测模型是三个模型中最优的模型，该模型下得到的第1组、第2组、第3组在8小时内分别可以完成的物料数目为357件、364件、344件。单工序有故障的情况下，我们在单工序分层预测模型的基础上进行修改。将1%的故障率转化为每秒钟CNC发生故障的概率，然后产生一个[10,20]间的随机数作为CNC的维修时间，其他算法步骤与无故障的相同。得到的第1组、第2组、第3组在8小时内分别可以完成的物料数目为307件、336件、319件。双工序的情况下，我们依然采用局部最优模型。与单工序不同的是，双工序模型中，当一个物料加工完第一道工序时，发出的请求不是下料而是加工第二道工序。我们假定在CNC加工的8小时不可以更改刀具，为了找到将CNC分配给第一道工序和第二道工序最合理的方案，我们遍历了所有可能的情况，从中选出系统工作效率最大的一种方案作为最优方案。每组的CNC最优安排方案都不止1种，为了更好的描述这些方案，我们引入了最优方案矩阵，第i行表示第i种方案，第j列表示CNC的编号为j。最后得到的第1组、第2组、第3组在8小时内分别可以完成的物料数目为251件、198件、244件。双工序有故障的情况下，每一组从双工序模型中任意挑选一种CNC最优安排方案。然后将1%的故障转化为每件物料在加工过程中产生故障的概率，提前判定是哪些物料在加工过程中会发生故障。在会发生故障的物料的加工时间段里，随机选取一个时间点作为故障开始的时间，然后随机产生一个[10,20]间的数字作为设备维修时间。得到的第1组、第2组、第3组在8小时内分别可以完成的物料数目为220件、191件、225件。关键字：数学规划，分层预测，局部最优，最优方案矩阵2RGV动态调度模型一、问题重述一套智能加工系统由8台CNC、一辆RGV、一条上料传送带和一条下料传送带组成。其中，RGV是一种在固定轨道上按照指令移动的智能车，它在这个系统中的功能有：将上料传送带上的生料放置到对应的CNC上，将CNC已加工好的熟料放入清洗槽中，将清洗好的成料放到下料传送带上。图1智能加工系统示意图设定以下三种不同情况：情况1：每种物料都只需要一道工序加工完成，每台CNC安装刀具相同，物料可以在任意一台CNC上完成加工。情况2：物料需要两道工序加工完成。每台CNC在同一时间只能安装一种刀具且只能加工一个物料，每个物料的第一道和第二道工艺不能在相同的CNC上完成。情况3：考虑CNC在加工过程中可能会发生故障的情况（故障概率约为1%），排除故障包括人工处理和未完成的物料报废两部分，排除故障时间介于10~20分钟之间，故障排除后CNC可立即开始工作。分别考虑一道工序和两道工序发生故障的情况。根据以上三种情况，解决下面两个任务：任务一：建立RGV动态调度模型，并给出相应的算法。任务二：根据表1中的三组数据，检验任务一建立的模型的实用性和算法的有效性，并依此给出合理的RGV调度策略，并计算出这种策略下智能加工系统的工作效率，将具体结果分别填入附件二的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完成一个物料的清洗作业所需时间2530253二、模型假设与符号说明2.1模型假设1.假设传送带运输生料和熟料的时间比RGV上下料的时间短，即每台CNC前面的传送带上一直保持有生料；2.假设初始状态下CNC都是空闲的；3.假设CNC更换刀具的时间可忽略不计；4.假设CNC设备故障发生的概率为1%；5.假设RGV在工作过程中不会发生故障；6.假设每一组工作的8小时内CNC不能更换刀具。2.2符号说明符号含义RGV移动1个单位所需时间RGV移动2个单位所需时间RGV移动3个单位所需时间CNC加工完成一道工序所需时间CNC加工两道工序物料时第一道工序所需时间CNC加工两道工序物料时第二道工序所需时间RGV为CNC1#，3#，5#，7#一次上下料所需时间RGV为CNC2#，4#，6#，8#一次上下料所需时间RGV完成一个物料的清洗作业时间第i件物料的上料时间编号为的CNCz判断CNC编号奇偶的0-1变量时间效率所有CNC工作的时间总和4三、问题分析3.1单工序RNG调度分析智能加工系统的工作主要是依靠RGV来协调。因此控制RGV执行请求的顺序就可以控制系统的工作流程。单工序物料的处理流程为：上料→加工→从CNC下料→清洗作业→放至下料传送带这一件物料从CNC下料时间恰好为下一件物料的上料时间。对于此类离散问题，首先考虑数学规划模型。该问题是希望智能加工系统的工作效率最大，即8小时内加工完成尽量多的物料。为了使数学规划模型便于求解，我们将求解目标转换为该系统完成n件物料加工所用时间最短（n为定值）。在完成根据附件Excel中给出的上料时间、CNC机器编号等要求解的问题，设未知量；再根据RGV初始的几个状态、第件物料的上料时间与第i+1件物料上料时间的关系、在同一台CNC上相邻加工的两件物料之间的时间关系建立约束条件。规划模型问题可以用Lingo求解，但是我们分析这种模型的时间复杂度会较高，因此n的值不能太大。但是我们了解到8小时内系统大约可以加工400件左右物料[1]，因此n的值也不能太小，否则不能代表系统工作8小时的整体效率。鉴于数学规划模型的时间复杂度较高，该模型并不能得到8小时内可加工的所有物料的件数和信息。因此我们希望可以用算法模拟该系统的工作流程。在RGV选择执行哪一条请求时，可以根据发出请求的CNC与RGV的距离以及CNC编号的奇偶来判定，也可以通过预测系统的工作效率来判定。为此可以分别建立局部最优模型和分层预测模型。然后将表1中的数据代入到这两个模型中，根据每个模型所得出的8个小时内可加工的物料件数来判断模型的优劣。3.2单工序有故障情况下的RGV调度分析如果CNC以1%的概率出现故障，也就是说8小时内每台设备发生故障的概率为1%。在CNC发生故障的时候，正在这台CNC上加工的物料报废，而且需要维修10-20分钟。维修好之后CNC立即恢复工作。单工序无故障情况下建立了3个模型，根据运行结果的比较可以比较出性能较好的模型——单工序分层预测模型，单工序有故障模型就在这个模型上进行改动。与无故障模型相比，单工序有故障模型每秒都会判断有没有设备发生故障，这就需要将1%这个概率转化为每秒设备发生故障的概率[2]。如果判断到有设备会发生故障，接下来产生一个[10,20]间的随机数，这个数值作为故障设备的维修时间。3.3双工序RGV调度分析双工序物料的处理流程为：上料→第一道工序→下料→第二道工序→下料→清洗作业→放至下料传输带与单工序相比，物料在加工第一道工序后，不需要RGV的清洗作业时间，而物料加5工第二道工序的过程与单工序物料加工过程一样。当一件物料需要经过两道工序时，需要在不同的CNC上进行加工。我们假定一组工作的8小时内CNC不会更换刀具，也就是说每一组的物料在加工时，能完成第一道工序和第二道工序的CNC都是固定的。那么如何分配CNC将是我们面临的新的问题。其实在用算法模拟双工序系统流程时，可以遍历CNC的所有可能情况（共种），输出每一种情况对应的加工的物料数目，数目最多的一组便是分配CNC的最佳方案。3.4双工序有故障情况下的RGV调度分析这种模型下，故障发生概率为1%，设定为每件物料加工时会有1%的概率发生故障。当第i件物料进行加工时，会产生一个[0,99]的随机数，如果产生的数为0就认为现在会发生故障。而且物料在加工过程中的哪个时间点发生故障、维修故障需要的时间都是随机的。四、模型建立与求解4.1单工序模型4.1.1单工序规划模型对于此类离散问题，首先考虑数学规划模型求解。1单工序规划模型的建立假设表示第件物料的上料时间，表示编号为的CNC。此题是希望智能加工系统的作业效率越高越好，即在8小时内加工完成的物料数目越多越好。但是由于规划模型的复杂度较高，不能处理较多数据，于是我们把衡量指标改为“加工完成n件物料所用的时间越短越好”,也就是“第件物料的上料时间越早越好”。因此目标函数可以设为：下面是对约束条件的求解。①初始条件约束：不妨假设第1件物料在CNC1#工作台上加工，上料时间记为0，即：那么为了使效率最大，第2件物料应该在CNC2#工作台上加工，且当第1件物料完成上料后，RGV可立即为第2件物料上料。则它的上料时间可以记为：6第三件物料应该在CNC3#工作台上进行加工，待RGV完成第2件物料的上料且移动1个单位后，可为第3件物料上料：依次类推可以得到：且为奇数且为偶数根据表1中第1组的数据，在第1件物料加工完成之前，至多可以完成15件物料的上料任务因此需要.②第件物料的上料时间一定大于第件物料的上料时间+上料所用时间，用表示上料所用时间，即：其中，在奇数编号和偶数编号的CNC上加工，上料所用时间不同。为了解决这个问题，引入0-1变量.即为奇数时，，即上料所用时间为;为偶数时，，上料所用时间为,则可表示为：③如果第件物料在编号为的CNC上加工，且下一个在上加工的是第件物料，那么：2单工序规划模型的求解与检验根据模型中的目标函数和3个约束条件，利用Lingo软件求解。在求解过程中我们发现，这种求解思路得到的时间复杂度为,非常高。当=20，即求解该智能加工系统加工完成20件物料时所需的时间时，可以运行出结果，但是=20这个样本太小，不能代表整体。然后我们增加的值，但是当增加时，程序的时间复杂度以指数形式上升，当=89时程序已经运行的非常慢难以得到结果。下面是单工序规划模型在给定的不同时计算出的时间（依据表1中的第1组数据）。7加工完成物料件数系统所用时间t（单位：s）201596503921755893806349886917表2单工序数学规划模型结果根据以上所推算的时间，我们可以估算八小时内完成的物料件数N：根据估算，8个小时内系统大约可以加工366个物料左右，而这个模型只能求解n=88的情况。我们认为，这个样本太小不能有效地代表整体，也就是说根据这个模型求解出的366这个数字是不准确的。因此这个模型的求解达不到要求。所以我们判定，单工序规划模型虽然提供了一种有效的求解思路，但是这个模型实用性较差。因此，我们转换了一种思路，利用算法模拟[3]8小时内该智能加工系