2018数学建模国赛B题.pdf

1 RGV 动态调度模型 摘 要：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 件。 关键字：数学规划，分层预测，局部最优，最优方案矩阵 2 RGV 动态调度模型 一、问题重述 一套智能加工系统由 8 台 CNC、一辆 RGV、一条上料传送带和一条下料传送带 组成。其中，RGV 是一种在固定轨道上按照指令移动的智能车，它在这个系统中的 功能有：将上料传送带上的生料放置到对应的 CNC 上，将 CNC 已加工好的熟料放入 清洗槽中，将清洗好的成料放到下料传送带上。 图 1 智能加工系统示意图 设定以下三种不同情况： 情况 1：每种物料都只需要一道工序加工完成，每台 CNC 安装刀具相同，物料 可以在任意一台 CNC 上完成加工。 情况 2：物料需要两道工序加工完成。每台 CNC 在同一时间只能安装一种刀具 且只能加工一个物料，每个物料的第一道和第二道工艺不能在相同的 CNC 上完成。 情况 3：考虑 CNC 在加工过程中可能会发生故障的情况（故障概率约为 1%） ， 排除故障包括人工处理和未完成的物料报废两部分，排除故障时间介于 1020 分钟 之间，故障排除后 CNC 可立即开始工作。分别考虑一道工序和两道工序发生故障的 情况。 根据以上三种情况，解决下面两个任务： 任务一：建立 RGV 动态调度模型，并给出相应的算法。 任务二：根据表 1 中的三组数据，检验任务一建立的模型的实用性和算法的有 效性，并依此给出合理的 RGV 调度策略，并计算出这种策略下智能加工系统的工作 效率，将具体结果分别填入附件二的 Excel 中。 表表 1 1：智能加工系统：智能加工系统作业参数作业参数的的 3 3 组数据表组数据表 时间单位：秒时间单位：秒 系统作业参数系统作业参数 第第 1 1 组组 第第 2 2 组组 第第 3 3 组组 RGV 移动 1 个单位所需时间 20 23 18 RGV 移动 2 个单位所需时间 33 41 32 RGV 移动 3 个单位所需时间 46 59 46 CNC 加工完成一个一道工序的物料所需时间 560 580 545 CNC 加工完成一个两道工序物料的第一道工序所需时间 400 280 455 CNC 加工完成一个两道工序物料的第二道工序所需时间 378 500 182 RGV 为 CNC1#，3#，5#，7#一次上下料所需时间 28 30 27 RGV 为 CNC2#，4#，6#，8#一次上下料所需时间 31 35 32 RGV 完成一个物料的清洗作业所需时间 25 30 25 3 二、模型假设与符号说明 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 件物料的上料时间 编号为 的 CNC z z 判断 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 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 2 单工序规划模型的求解与检验单工序规划模型的求解与检验 根据模型中的目标函数和 3 个约束条件，利用 Lingo 软件求解。在求解过程中 我们发现，这种求解思路得到的时间复杂度为,非常高。当 =20，即求解该智 能加工系统加工完成 20 件物料时所需的时间时，可以运行出结果，但是 =20 这个 样本太小，不能代表整体。然后我们增加 的值，但是当 增加时，程序的时间复杂 度以指数形式上升， 当 =89 时程序已经运行的非常慢难以得到结果。 下面是单工序 规划模型在给定的 不同时计算出的时间（依据表 1 中的第 1 组数据） 。 7 加工完成物料件数 系统所用时间 t（单位：s） 20 1596 50 3921 75 5893 80 6349 88 6917 表 2 单工序数学规划模型结果 根据以上所推算的时间，我们可以估算八小时内完成的物料件数 N： 根据估算，8 个小时内系统大约可以加工 366 个物料左右，而这个模型只能求解 n=88 的情况。我们认为，这个样本太小不能有效地代表整体，也就是说根据这个模 型求解出的 366 这个数字是不准确的。因此这个模型的求解达不到要求。所以我们 判定， 单工序规划模型虽然提供了一种有效的求解思路， 但是这个模型实用性较差。 因此，我们转换了一种思路，利用算法模拟 38 小时内该智能加工系统的工作 状况，建立了分层预测模型和局部最优模型。 4.1.2 单工序分层预测模型 1 1 单工序分层预测模型的单工序分层预测模型的建立建立 单工序分层预测模型以时间效率为衡量指标，我们将时间效率定义为： 其中，为0,t时间内 8 台 CNC 工作的时间总和。 如果 RGV 在 时刻有个 CNC 的请求等待处理，RGV 会考虑到所有的情况向下预 测两层，即：在 时刻 RGV 选择执行第 个请求，假设完成这个请求用时，第 个 CNC 完成物料加工用时 。那么在时刻又会有 个 CNC 的请求等待处理，接着 RGV 选择执行第 个请求， 假设 RGV 执行请求用时， 第 个 CNC 完成物料加工用时 。 计算这种情况下的时间效率： 8 其中， 计算出分别取不同的值时的种不同的情况，对所得的时间效率进行比 较，目标函数设为： 然后找出对应的的取值，那么 RGV 在 时刻应该执行第 个请求。 RGV 执行完 时刻的请求后，下次选择请求的时候，重复此计算过程。 2 2 单工序分层预测模型的求解单工序分层预测模型的求解 44 解决这个模型的核心思想如下图所示。即当有未完成的指令时，预测下面两层 的时间效率，选取时间效率最大的一组，完成第一层的指令。 图 2 单工序分层预测的算法流程 采用贪心算法解决这个模型，以 8 小时为限定时间，分别将表 1 中第 1 组、第 2 组、第 3 组的数据代入到程序中，可以分别得到三种 RGV 调度方案，三组 8 小时 内分别可以加工的物料为：357 件、344 件、364 件。 4.1.3 单工序局部最优模型 1 1 单工序局部最优模型的建立单工序局部最优模型的建立 单工序局部最优模型中 RGV 在选择请求执行的时候有两个衡量指标： CNC 与 RGV 的距离； CNC 编号的奇偶。 9 当 RGV 进行选择的时候，指标的优先级高于指标。也就是当两个请求的指 标相同时，才考虑指标，优先考虑 CNC 编号为奇数的请求。 假设 RGV 在 t 时刻处于空闲状态， 且这一时刻有 m 个 CNC 发出的待处理的请求， 这些 CNC 与 RGV 的距离分别为。此时目标函数为： 这时 RGV 会选择执行第 个请求。 但是当存在时， RGV 会首先选择编号为偶数的 CNC 发出的请求 去执行。 2 2 单工序局部最优模型的求解单工序局部最优模型的求解 55 单工序局部最优模型与单工序分层预测模型最大的不同在于 RGV 执行请求顺序 所遵循的衡量指标不同。将这个模型用 Java 程序求解，具体流程如下图所示。 图 3 单工序局部最优模型的算法求解流程 4.1.4 三种单工序模型的比较与总结 10 第 1 组完成 的物料数目 第 2 组完成的 物料数目 第 3 组完成的 物料数目 结果准确性 单工序规划模型 366 354 372 较低 单工序分层预测 模型 357 344 364 较高 单工序局部最优 模型 357 337 346 较高 表 3 单工序三种模型的比较 系统的作业效率可以用每小时加工的物料数目来衡量，单位：件数/小时。 第 1 组系统 作业效率 第 2 组系统作 业效率 第 3 组系统作 业效率 平均作业效率 单工序规划模型 45.75 44.25 46.5 45.5 单工序分层预测 模型 44.625 43 45.5 44.375 单工序局部最优 模型 44.625 42.125 43.25 43.333 表 4 单工序三种模型系统效率对比 通过对已经建立的三种单工序模型的比较，我们发现单工序规划模型的系统作 业效率是最高的，但是这个结果是根据前 88 件物料加工的情况推算得到的，其准 确性仍有待考察。 单工序分层预测模型与单工序局部最优模型二者相比较，它们都是通过算法来 模拟该智能加工系统的工作流程，因此准确性都比较高。而且，从系统作业效率来 看，单工序分层预测模型的性能要更好一些。这是因为单工序局部最优模型仅仅是 以当前时刻 CNC 与 RGV 的距离和 CNC 编号的奇偶为衡量指标，而单工序分层预测模 型是预测了 RGV 之后两步的所有情况，从中取一个最优方案。 综合准确性和完成的物料数目两个因素考虑，判定单工序分层预测模型是建立 的三个模型中的最优模型。因此我们将单工序分层预测模型所得到的具体结果填入 Case_1_result.xls 中。 在接下来将要分析的单工序有故障模型中，我们选择在最优的单工序分层预测 模型上进行修改。 11 4.2 单工序有故障模型 4.2.1 单工序有故障模型的建立 与单工序分层预测模型相比，单工序有故障模型只是加了一步“判断这一时刻 是否有 CNC 设备发生故障” 。如果有设备发生故障，那么在这台设备上加工的物料 报废，且这台 CNC 暂停工作 1020 分钟。具体判断流程如下所示。 Step1：每秒生成一个范围在内的随机数。解释：8h 内设备产生的 故障为 1%，那么 1s 设备产生故障的概率为 Step2: 将该随机数与 CNC 编号对比， 如果产生的随机数恰好为某个 CNC 的编号， 且这台 CNC 当前不处于维修状态，那么该 CNC 发生故障。 Step3：产生一个10,20之间的随机数，作为发生故障的 CNC 的停止工作时间。 4.2.2 单工序有故障模型的求解 在单工序分层预测模型求解的算法基础上进行修改，增加了“判断 CNC 是否会 发生故障”的步骤，修改部分的流程图如下所示。 图 4 单工序有故障模型算法的部分处理流程 根据算法模拟该智能加工系统，可以得到设备会发生故障的情况下的物料加工 数目，故障率可表示为： 结果如下表所示。 12 物料加工数目 设备故障数目 故障率 系统作业效率（单 位：件数/小时） 第 1 组 307 4 1.28% 38.375 第 2 组 336 3 0.88% 45 第 3 组 319 3 0.93% 39.875 表 5 单工序有故障模型的求解结果 由表格可以看出，这些设备的故障率都在 1%左右，这也验证了模型中对故障描 述的正确性。 4.3 双工序局部最优模型 4.3.1 双工序局部最优模型的建立 在单工序局部最优模型的基础上，对模型进行些许改进。 双工序模型与单工序模型不同的地方在于：第一道工序完成后不需要经过 RGV 的清洗作业时间，而且只有当第一道工序完成后才能执行第二道工序。 已经设定 CNC 在加工的 8 小时中不能更换刀具，也就是说 8 小时内每台 CNC 的 功能是固定的。那么如何分配这 8 台 CNC 是影响结果的关键因素之一。 对于双工序模型来说， 如果依然建立数学规划模型， 约束条件会变得比较复杂， 而且规划模型的程序时间复杂度很高，整体数据只能根据部分数据推测得来，所以 数学规划模型的准确度也有待考察。因此在双工序模型中，我们舍弃了数学规划这 个思路，只通过算法模拟的方式来找到最优解。 通过遍历所有的 CNC 分配方案，从中选取系统效率最高的结果。 4.3.2 双工序局部最优模型的求解与检验 运用 Java 程序求解这个模型，与单工序局部最优模型求解的不同之处在于： 双工序模型需要建立两个队列，把不同的工序请求放在不同的队列中。双工序局部 最优模型与单工序求解流程不同的地方如下图所示。 13 图 5 双工序局部最优模型算法的部分处理流程 其实根据表 1 中 3 组数据里第一道工序和第二道工序的时间比值，可以大致推 测出每一组CNC分配在第一道工序和第二道工序的数目， 来检验模型结果的正确性。 加工第一道工 序的时间（秒） 加工第二道工 序的时间（秒） / 预测第 1 道工序 与第 2 道工序的 CNC 数目之比 第 1 组 400 378 1.06 4:4 第 2 组 280 500 0.56 3:5 / 4:4 第 3 组 455 182 2.5 5:3 表 6 第一道工序与第二道工序的 CNC 数目预测 通过 Java 程序求解得到的最优结果如下表所示。 14 第一道工序 的 CNC 数目 第二道工序 的 CNC 数目 8 小时加工 的物料数目 系统工作效率 （件数/小时） 最优 CNC 安排方案 数目 第 1 组 4 4 251 31.375 8 第 2 组 4 4 198 24.75 2 第 3 组 5 3 244 30.5 2 表 7 双工序局部最优模型求解结果 实际求解结果与预测的结果相吻合，因此判断双工序局部最优模型是符合要求 的。 为了表示每一组的 NCN 最优安排方案，引入方案矩阵的概念，将所有最优方案 用一个矩阵表示，第i行表示第i种方案，第j列表示 CNC 的编号为j。矩阵中的 值表示该 CNC 是执行第几道工序的。 例如：1 1 2 2 1 2 2 2表示这一组的最优 CNC 安排方案只有一种， 且执行第一道工序的有 CNC1#、CNC2#、CNC5#，其余的执行第二道工序。 第 1 组有 8 种 CNC 的分配方案都可以得到最优结果，将这 8 种最优的分配方案 用方案矩阵表示如下所示： 第 2 组的 CNC 分配方案矩阵如下所示。 第 3 组的 CNC 分配方案矩阵如下所示。 4.4 双工序故障模型 4.4.1 双工序故障模型的建立 15 双工序故障模型可以在双工序模型求出的多种 CNC 最优方案中，挑选一种作为 固定的 CNC 安排方案。 第 1 组的 CNC 安排方案：1 2 2 1 2 1 1 2 第 2 组的 CNC 安排方案：1 2 1 2 1 1 2 2 第 3 组的 CNC 安排方案：2 1 1 1 2 1 1 2 双工序故障模型与双工序模型的不同之处在于需要考虑哪件物料在加工过程 中会发生故障、故障产生的具体时间、故障需要维修的时间。 时间轴如下图所示。 图 6 双工序故障模型的时间轴 故障开始时刻是 CNC 加工时间段中的任意一个时间点（随机产生） ，故障持续 时间是10,20间的一个随机数。 4.4.2 双工序故障模型的求解 双工序故障模型的算法求解中，与无故障的算法相比，只是增加了故障的产生 时间、维修时间以及发生故障时的物料编号。增加的算法步骤流程图如下所示。 16 图 7 双工序故障算法部分流程图 求解得到的结果如下表所示。 加工完成的物 料数目 系统工作效率 （件数/小时） 发生故障的 CNC 数目 发生故障的概 率 第 1 组 220 27.5 4 0.90% 第 2 组 191 23.875 4 1.05% 第 3 组 225 28.125 4 0.89% 表 8 双工序故障模型得到的结果 五、模型评价 5.1 模型优缺点 5.1.1 模型优点 (1) 单工序无故障的情况下建立了 3 个模型，通过系统工作效率、结果准确性 两个指标来比较，得到最优的单工序模型。 (2) 用算法模拟智能加工系统整体工作流程，由下而上的解决问题，使建模问 题更加清晰直观。 (3) 单工序分层预测模型向下预测了两步， 从多种方案中选取一个效率最高的， 最终选择的方案更具有说服力。 (4) 物料需要两道工序加工的情况下， CNC的安排方案我们考虑了所有的情况， 每一种情况都运行出了结果，系统工作效率最高的情况对应的 CNC 安排方案一定 是最优的安排方案。 17 (5) 除了数学规划模型外，所有的模型都是基于单工序分层预测模型和单工序 局部最优模型建立的，都只是在基本模型上加了一些必要的步骤。而这两个基本模 型都是经过数据检验的，是符合要求的。因此模型都比较稳定。 (6) 引入了最优方案矩阵来描述双工序模型中的多种最优 CNC 安排方案， 使安 排方案更加清晰、具有可读性。 5.1.2 模型缺点 (1) 没有考虑 CNC 在工作的 8 小时中会更换刀具的复杂情况。 (2) 用算法模拟系统工作流程虽然清晰直观，但是从单工序数学规划模型可以 看出，算法模拟得到的结果并不是最优的。 (3) 只考虑了物料正在加工时设备发生故障的状况，没有考虑设备处于空闲状 态时发生故障的情况。 5.2 模型改进 虽然求解数学规划模型的程序的复杂度较高，我们难以得到准确的结果，但根 据单工序三种模型的比较可以得知，单工序规划模型的求解结果要优于算法模拟系 统工作所得到的结果。因此如果研究如何改进求解规划模型的算法、如何降低其时 间复杂度，意义会更加重大。 在双工序规划模型中，我们没有考虑 CNC 随时更换刀具的情况。虽然现在工厂 中随时更换刀具的情况并不常见，但是在建模中可以建立出 CNC 随时更换刀具的情 况，将其与 CNC 不能更换刀具的最优情况进行对比，如果更换道具的模型求解得到 的结果更优，那么“CNC 如何更换刀具”可以使未来的研究方向之一；如果 CNC 随 时更换刀具模型得到的结果还没有不能更换刀具的结果优，那日后就无需在 CNC 更 换道具这个问题上下功夫研究。 参考文献 1丁伟.立体物料存储 RGV 控制系统的设计J.电工技术,2018,(06):15-17+20. 2刘俏.RGV 系统设计与应用J.物流科技,2016,(05):51-54. 3陈华,孙启元.基于 TS 算法的直线往复 2-RGV 系统调度研究J.工业工程与管 理,2015,(05):80-88. 4陈华.基于分区法的 2-RGV 调度问题的模型和算法J.工业工程与管 理,2014,(06):70-77. 5张应强,魏镜弢,王庭有.RGV 控制系统设计研究J.河南科学,2012,(01):94-96. 18 附录附录 1. 单工序分层预测模型核心代码 public void workStart() while(car.getTotalTime() minCNC.getRestTime() minRestTime = minCNC.getRestTime(); /获得最短的时间之后，要开始处理等待时间 for(int i = 0 ; i = 0) tmpCnc.setTotalWorkTime(tmpCnc.getTotalWorkTime() + 1); /要将新的任务添加到临时任务列表中 if(tmpCnc.getRestTime() -2000) tmpCnc.setTaskId(Constants.TASK_WORK); tmpCnc.setRestTime(-2000); /生成一个任务 Task newTask = new Task(); newTask.setMark(tmpCnc.getMark(); newTask.setPosition(tmpCnc.getPosition(); newTask.setTaskId(Constants.TASK_WORK); newTask.setWorkTime(tmpCnc.getWorkTime(); /将新任务放到临时任务队列里 tmpTasks.add(newTask); if(tmpCnc.isIsbroken() tmpCnc.setBrokenTime(tmpCnc.getBrokenTime() - 1); if(tmpCnc.getBrokenTime() = 0) tmpCnc.setIsbroken(false); 23 /填充临时状态 moniStatus.setCNCMap(moniMap); Car moniCar = cloneCar(tmpCar); moniCar.setCurrentPostion(task.getPosition(); moniStatus.setCar(moniCar); moniStatus.setTotalTime(status.getTotalTime() + moveTime + updownTime + cleanTime); moniCar.setTotalTime(status.getTotalTime() + moveTime + updownTime + cleanTime); moniStatus.setTasks(tmpTasks); /将临时状态放入列表当中 Map map = new HashMap(); map.put(0, moniStatus); tmpStatus.put(executeIndex, map); /判断是否完毕 if(executeIndex = index) /完毕需要计算效率 long total = 0; for(Integer key : moniMap.keySet() total += moniMap.get(key).getTotalWorkTime(); double percent = total / (moniStatus.getTotalTime() * 8.0); if(percent info.getMaxEfficiency() info.setMaxEfficiency(percent); info.setEffectiveTasks(tmpStatus.get(executeIndex - 1).get(0).getTasks(); info.setTaskIndex(tmpTaskIndex); info.setMaxTmpTime(status.getTotalTime(); info.setNumber(tmpStatus.get(executeIndex - 1).get(0).getNumber(); tmpguchang = cloneGuZhang(tmpStatus.get(executeIndex - 1).get(0).guzhang); return; /还要继续模拟 /如果任务队列里面没有任务，那么小车就要等待 while(tmpTasks.size() = 0) long minRestTime = 0; 24 for(Integer key : moniStatus.getCNCMap().keySet() /获得工作剩余时间最短的那个 cnc CNC minCNC = moniStatus.getCNCMap().get(key); if(minRestTime = 0 | minRestTime minCNC.getRestTime() for(int i = 0 ; i max) 26 max = count max ? count : max; cnc = Arrays.copyOf(cncType, cncType.length); System.out.println(“MAX:“ + Arrays.toString(cnc) + “ “ + max); public int work(int cncType) int cncRemainTime = 0, 0, 0, 0, 0, 0, 0, 0; int waitTimeSum = 0; int finishCount = -5; int dealNum = 0; int remainTime = 8 * 60 * 60; int currTime = 0; int rgvSite = 1; int rgvWaitTime = 0; int dealFaultMinTime = 0; boolean isClean = false; boolean isFault = false; int nextCncType = 1; int preCnc = 0; int cncStartTime = new int28; HashMap reqMap1 = new HashMap(); HashMap reqMap2 = new HashMap(); HashMap makeInfo = new HashMap(); HashMap cncInfo = new HashMap(); HashMap faultMap = new HashMap(); for (int i = 1; i 0) if (nextCncType = 1 rgvWaitTime = findRgvWaitTime(cncRemainTime, nextCncType, cncType, faultMap); if (dealFaultMinTime 0) if (rgvWaitTime dealFaultMinTime) 27 waitTimeGo(cncRemainTime, rgvWaitTime, faultMap); remainTime -= rgvWaitTime; currTime += rgvWaitTime; if (remainTime = 0) continue; else waitTimeGo(cncRemainTime, dealFaultMinTime, faultMap); dealFaultFinish(cncRemainTime, faultMap); remainTime -= dealFaultMinTime; currTime += dealFaultMinTime; if (remainTime = 0) continue; isClean = nextCncType = 2; recReq(cncRemainTime, reqMap1, reqMap2, cncType, faultMap); CncReq currReq = choiceReq(reqMap1, reqMap2, rgvSite, nextCncType); cncInfo.get(currR cId).add(28800 - remainTime + DATA.RGV_MOVE_TIMEMath.abs(rgvSite - (currR cId + 1) / 2); if (nextCncType = 2) ArrayList list = new ArrayList(); list.add(preCnc); list.add(cncStartTime0preCnc - 1); list.add(currR cId); list.add(28800 - remainTime + DATA.RGV_MOVE_TIMEMath.abs(rgvSite - (currR cId + 1) / 2); makeInfo.put(finishCount + 1, list); else cncStartTime0currR cId - 1 = cncStartTime1currR cId - 1; cncStartTime1currR cId - 1 = 28800 - remainTime + DATA.RGV_MOVE_TIMEMath.abs(rgvSite - (currR cId + 1) / 2); preCnc = currR cId; currReq = reqMap1.containsKey(currR cId) ? reqMap1.remove(currR cId) : reqMap2.remove(currR cId); isFault = randomFault.contains(dealNum); 28 int tmp = calcReqWaitTime(currReq, rgvSite); waitTimeSum += tmp; int runTime = calcRunTime(rgvSite, currReq, isClean); rgvSite = (currR cId + 1) / 2; exeReq(currReq, cncRemainTime, runTime, reqMap1, reqMap2, isClean, nextCncType, faultMap, isFault, currTime); if (finishCount = 0) nextCncType = nextCncType = 1 ? 2 : 1; System.out.println(Arrays.toString(cncType) + “:finishCount=“ + finishCount + “, waitTimeSum=“ + waitTimeSum); for(Integer id : cncInfo.keySet() for(Integer time : cncInfo.get(id) System.out.print(time + “ “); System.out.println(); int cncIndex = 0,0,0,0,0,0,0,0; for(Integer num : makeInfo.keySet() System.out.println(num + “ CNC“ + makeInfo.get(num).get(0) + “# “ + makeInfo.get(num).get(1) + “ “ + cncInfo.get(makeInfo.get(num).get(0).get(+cncIndexmakeInfo.get(num).get(0)-1) + “ CNC“ + makeInfo.get(num).get(2) + “# “ + makeInfo.get(num).get(3) + “ “ + cncInfo.get(makeInfo.get(num).get(2).get(+cncIndexmakeInfo.get(num).get(2)-1); return finishCount; public static int calcReqWaitTime(CncReq req, int rgvSite) return req.waitTime + DATA.RGV_MOVE_TIMEMath.abs(rgvSite - ( cId + 1) / 2) + DATA.OPER_MATE_TIME cId - 1; public static void exeReq(CncReq currReq, int cncRemainTime, int runTime, 29 HashMap reqMap1, HashMap reqMap2, boolean clean, int nextCncType, HashMap faultMap, boolean isFault, int currTime) waitTimeGo(cncRemainTime, runTime, faultMap); cncRemainTimecurrR cId - 1 = clean ? DATA.CNC_DOUBLE_WORK_TIMEnextCncType - 1 - DATA.CLEAN_TIME : DATA.CNC_DOUBLE_WORK_TIMEnextCncType - 1; for (Integer id : reqMap1.keySet() reqMap1.get(id).waitTime += runTime; for (Integer id : reqMap2.keySet() reqMap2.get(id).waitTime += runTime; if (!faultMap.containsKey(currR cId) int after = random.nextInt(560); int startTime = currTime + (clean ? runTime - DATA.CLEAN_TIME : runTime) + after; int longTime = random.nextInt(600) + 600; int faultRemainTime = longTime + 560 - DATA.CLEAN_TIME; faultMap.put(currR cId, new FaultInfo(currR cId, startTime, longTime, faultRemainTime); System.out.println(“产生故障：“ + faultMap.get(currR cId); public static int calcRunTime(int rgvSite, CncReq req, boolean clean) if (!clean) return DATA.RGV_MOVE_TIMEMath.abs(rgvSite - ( cId + 1) /