在带货盘替代通道的自动化仓库中安排整车运作【中文8400字】
收藏
资源目录
压缩包内文档预览：
编号：10346001
类型：共享资源
大小：2MB
格式：ZIP
上传时间：2018-08-02
上传人：闰***
认证信息
个人认证
冯**（实名认证）
河南
IP属地：河南
15
积分
- 关 键 词：
-
带货盘
替代
替换
通道
自动化
仓库
安排
支配
整车
运作
中文
- 资源描述：
-
在带货盘替代通道的自动化仓库中安排整车运作【中文8400字】,带货盘,替代,替换,通道,自动化,仓库,安排,支配,整车,运作,中文
- 内容简介：
-
【中文 8400 字】在带货盘替代通道的自动化仓库中安排整车运作Didem Cinar，JosAntnioOliveira，Y. Ilker Topcu，Panos M. Pardalos土耳其伊斯坦布尔伊斯坦布尔技术大学工业工程系管理学院美国盖恩斯维尔佛罗里达大学工程与系统工程系葡萄牙布拉加 Minho 大学 ALGORITMI 研究中心在这项研究中，调查了自动化存储和检索系统中卡车装载操作的调度。旨在于以前的出现问题的扩展，例如托盘可以从一组替代通道中取出。它被模拟为灵活的作业车间调度问题，其中负载被视为工作，负载的托盘被视为操作，并且用于将检索物品移除到卡车上的叉车被视为机器。最大限度缩短装载时间是为了尽量减少订单的吞吐时间，并最大限度地提高仓库的效率。提出了基于优先级的遗传算法来对检索托盘进行排序。置换编码被用于编码，并且生成用于灵活作业车间调度问题的构造性算法生成活动调度被应用于解码。所提出的方法适用于由自动化材料处理和存储系统的领先供应商安装的仓库中出现的实际问题。1.简介自动化存储和检索系统（AS / RS）是一种仓储系统，它使用机械设备在分销和生产环境中存储和检索产品1,2。自动起重机通过机架之间的过道移动，将物品放在机架上，并将这些物品从存储器取回到收集器，以完成客户订单。 AS / RS 是完全自动化的，因为操作人员不需要操作托盘2 。当收到一件物品的订单时，堆垛起重机将托盘从其存放位置取回，并将其运送到重力滚筒输送机通道顶部的收集器。在滚筒输送机的末端，使用叉车拾取所输送的货盘。 AS / RS 3的一些优点是空间利用率高，材料流量得到改善，库存控制得到改善。通过系统的优化设计和优化调度，这种系统的最佳利用率可以成功。仓库调度优化是一个组合优化问题，在高维实例的合理计算时间内无法用精确的算法求解。由于问题的复杂性高，模拟和 metaheuristics 已被广泛应用于仓库调度优化4。第 3 节给出了关于为 AS / RS 设计和调度开发的方法的详细文献综述。在这项研究中，调查了在 AS / RS 中发生的卡车装载操作的调度。通过将负载视为作业的作业和托盘作为其操作，该问题被模拟为灵活的作业车间调度问题（FJSP ）。用于从收集器到卡车运输托盘的叉车被视为机器。本文的主要贡献有两个：（1）卡车装载作业的调度被模拟为灵活的作业车间调度问题;（2）由领先的自动化物料处理供应商安装的 AS / RS 仓库中出现的真正问题;存储系统通过使用基于优先级的遗传算法来解决，并且通道选择灵活性的影响被调查。就作者所知，这项工作是 FSJP 第一次用于模拟 AS / RS 仓库中托盘的检索操作。本文的结构如下，第 2 节对调查的自动化存储系统进行了简要说明。在第3 节中，给出了关于卡车装载作业调度的文献回顾。第 4 节表示 AS / RS 中的整车运行调度问题的混合整数规划（MIP）公式，并讨论将该问题建模为灵活的作业车间调度问题。第 5 节介绍了专门的方法。第 6 节给出了现实 AS / RS 仓库问题的计算结果。最后，第 7 节给出了结论。图 1.仓库的模式2.存储系统本研究中提出的方法适用于作为配送中心的意大利 AS / RS 仓库。产品由仓库储存并装载到卡车上以满足客户的需求。预先知道的卡车路线是根据客户订单的交付截止日期确定的。仓库由 11 个过道组成，托盘架可容纳 40,000 个托盘。自动堆垛起重机或 S / R 机器在每个过道中工作，以将托盘从其各自的机架移动到过道开始时的收集器。叉车将货盘运送至卡车。仓库有 13 个停靠海湾装载卡车。图 1 显示了该仓库的装货流程。仓库计划系统（WPS）和仓库管理系统（WMS ）用于操作仓库。每辆卡车的每日装载计划由 WPS 执行。 WMS 确定回收托盘和 S / R 机器和叉车的运动顺序。一辆卡车每天可以检索大约一百个货物。每辆卡车都有自己的交货时间，这是由 WPS 考虑的，并且装载不得延迟。在为 WPS 定义的策略中，整套负载被分成称为批次的子集。同时处理一批中的加载。在完成前一批次的加载之前，无法启动加载批次。批量的大小是根据交货期限和停靠海湾的数量来确定的。标准的每日计划包括 15-20 批次，每批 6-13 批次。客户的订单包括一个或多个托盘上交付的产品或一组产品。订单的产品组是预先知道的，并且在仓库中可用。卡车负载由一组托盘运送给一个或多个客户。 WMS 使用 LIFO（后进先出）规则确定卡车上装载货盘的顺序。由于负载中的托盘序列是预先确定的并且不能改变，因此负载的托盘之间存在优先关系。货物的托盘可以从任何通道中取出。为了便于将卡车分配到停靠海湾，几个托盘放置在不同的通道中，以减少准备工作的时间，允许在接近卡车的通道中选择托盘并尊重 FEFO（First -Expired-First-Out）规则。 S / R 机器编程为从相应通道取回托盘。我们假设每台叉车只能为一个通道工作。叉车从自己的过道收到托盘后，可将托盘运送到任何卡车。出于安全原因，不允许多台叉车同时将货盘放在卡车上。所以，一个负载应该在特定时间收到一个托盘。托盘装入卡车后，叉车返回到其通道并与 WMS 通信，以便它可用于新的运输。然后为相同的负载编程下一个托盘。叉车在每次运输时只能接收一个托盘。有关分析的 AS / RS 仓库的详细信息可以从5中获得。由 S / R 机器检索的批次中不同的托盘序列会导致不同的处理时间。一个说明性的例子如下。假设 A1，A2 ，.表示仓库中有 5 个过道。 。 A5。问题在于规划包含 3 个负载的批次的检索顺序。每个负载由 4 个托盘组成，这 4 个托盘预先具有优先关系，代表该批次中将检索的总共 12 个托盘。每个过道有一个叉车将托盘从过道搬运到相应的过道，虽然托盘可以从几个通道上取回，但在之前的研究中5,6，人们认为这是WMS 以前选择的托盘，考虑到准备装载货物的通道的距离。表 1 给出了每个托盘的通道和处理时间。通道存放托盘 j 和相关通道与卡车之间的运输时间表示为（Ak，t），其中Ak 表示第 k 通道，t 是从通道 Ak 到卡车的运输时间。例如，第二个货物的第一个托盘必须在时间 1 时从第三通道中取回。为方便起见，托盘从 1 到 12 连续编号。表 1 真正问题的一个说明性例子图 2.用于检索托盘的两种不同时间表图 2 显示了两个不同的检索托盘序列。矩形内的数字标识托盘。对于每个序列，图 2 显示了该组通道（左侧）的甘特图和该组负荷（右侧）的甘特图，其表示更好的处理时间。取回托盘的顺序仅在走道 3 处不同，托盘 11 在托盘 3和 7（图 2（a）之后或托盘 3 和 7（图 2（b）之前收集。决定何时检索托盘 11 会对整批货物产生明显不同的处理时间。图 2（a）给出了这个小例子的最优解。3.文献回顾在 AS / RS 中，计划和执行准确的装载流程对于在适当的时间满足客户订单非常重要5。在以前的研究中，面向分析的构成了文献的大部分，而不是那些用于仓库设计的开发模型和技术7。简单的启发式和模拟技术被用于自动化仓储系统中的存储和检索问题。 Bozer 和 White 8提出了具有单指令和双指令模式的自动化 S / R 机器的行程时间模型。 Han 等人9提出了一种最近邻启发式方法用于在 AS / RS 中进行双重命令周期的检索测序，并使用 Monte Carlo 仿真进行评估。Eben-Chaime 10也使用最近邻居启发式对检索进行排序。豪斯曼等人3比较了几种存储分配规则来确定最优的存储分配策略。施瓦茨等人。 11分析存储分配和交错规则与模拟模型。 Lee 和 Schaefer 12提出了这个问题，这也是由 Han 等人处理的。 9，作为一个分配问题。他们提出了一种将匈牙利方法和分配问题的排序算法与巡回检查和巡回演算算法相结合的方法。在过去的几年里，除了数学建模和模拟方法之外，metaheuristics 已经用于这些领域。仓库设计和控制的综合评论可以在 de Koster 等人的文章中找到。 13，顾等人。 14和贝克和卡内萨15 。此外，Roodbergen 和 Vis 2和 Vasili等人提供了 AS / RS 设计中现有技术状况的详细解释。 16。曼齐尼等人。 17开发了一个多参数动态模型，用于产品到采摘器的存储系统，并具有基于类的产品存储分配。他们调查了影响仓储系统性能的因素。 Yin 和 Rau 18将动态选择排序规则的模拟和遗传算法结合起来，用于基于类别的单位负载 AS / RS。 Chang 等人19提出了一个多目标数学规划模型和堆垛起重机订单拣选的遗传算法。 Kung 等人20开发了一种基于动态规划的订单调度方法，用于在共轨上使用多台堆垛起重机的 AS / RS。问题包括为每台起重机分配订单以及在没有碰撞的情况下安排起重机。 Brezovnik 等人21采用多目标蚁群优化方法处理 AS / RS中的存储分配问题。根据从家电设备仓库获得的计算结果，显示当重量和身高较低的产品存储在较高级别时，可以实现最佳空间利用率。杨等人。 22推断S / R 机器的速度曲线对多深度 AS / RS 的最佳存储机架有重要影响。 Atmaca 和Ozturk 4提出了一种用于存储分配和存储分配问题的数学规划模型和模拟退火方法，以最大限度地降低存储成本。通过提出的数学模型获得了最多 103 种材料问题的最优解。 Dooly 和 Lee 23将双梭 AS / RS 的基于移位的测序问题建模为最小成本完美匹配问题，并提出了多项式时间精确算法。Oliveira 5和 Figueiredo 等人。 6将 AS / RS 仓库中的卡车装载作业模拟为带再循环的作业车间调度问题（JSP）5。奥利维拉 5假定运输托盘的处理时间相同，而不依赖于过道和卡车的位置。 Figueiredo 等人6 通过考虑不同的处理时间来扩展该问题，并通过具有随机密钥表示的遗传算法来解决该问题。 Oliveira 5和 Figueiredo 等人 6认为托盘可以从以前由 WMS 决定的一个通道检索，考虑到靠近停靠湾。在这项研究中，这个假设通过考虑托盘的替代通道来扩展。卡车装载调度同时确定托盘取回过道的选择。因此，问题包括选择通道来检索托盘（目前由 WMS 执行），以及托盘从收集器到卡车的运输安排。通过这种方式，结合这两种操作的好处被调查。在本研究的范围内没有发现将这个问题作为 FJSP 的研究。4.将 AS / RS 仓库建模为 FJSP在本节中，介绍了用于整车运行调度问题的 MIP 公式。我们不考虑交叉对接或订单拣选生产托盘。本研究考虑的假设如下：订单仅由存储在仓库中的（完整）托盘产品组成。S / R 机器比叉车更快地将托盘放在收集器上，以卸下托盘并且 S / R 机器在叉车之前运行，收集器作为一个缓冲器，可以处理多个托盘，收集器（重力滚筒输送机）中托盘的流量遵循 FIFO 规则，S / R 机器需要零时间将托盘放入收集器中。表 2 给出了后面使用的表示法。整车运行调度的 MIP 公式如下：表 2 MIP 的表示法（1）0 中给出了目标函数，以使批次的总加载时间最小化。约束条件（2）保证每个托盘仅由一台叉车运输。约束条件（3）确保如果托盘未分配给叉车，则该叉车托盘的运输开始和结束时间为零。如果在叉车 k 上分配，则约束条件（4）保证该托盘的运输完成时间不能小于其起始时间和运输时间之和。约束条件（5）和（6）满足叉车在将当前托盘运送到相应的叉车之前不能开始运送下一个托盘。在（7）中给出了每个载荷的优先约束，这确保了在相同载荷的前一个托盘的运输完成之前不能运载载荷的托盘。约束条件（8）和（9）分别给出了每个负载和批次的完成时间。约束（10） - （14）表示决策变量的二元约束和符号限制。由（1） - （14 ）给出的模型是 zgven 等人提出的模型的调整版本。 24 FJSP。这个问题可以被归类为 FJSP，其中货物被认为是工作，货物的货盘被认为是工作的操作，并且用于将检索物品移除到货车的叉车被视为机器。最小化完工时间（运输时间）是目标，因为这样可以最大限度地减少订单的吞吐时间并最大化仓库效率。在 FJSP 中，不能同时在机器上处理多个操作。此外，对于满足托盘优先关系的所有工作，都存在技术限制。在仓库中，叉车只能像 FJSP 中的机器一样在一定时间只运载一个托盘。同样，对于每个应该保证的负载，都有一个接收订单托盘。在前一个之前没有装载 palletcan。换句话说，不允许重叠相同载荷的货盘的运输。每个负载的托盘顺序可以作为技术限制来考虑。在仓库中，装载可以同时实现，并应在由 WPS 确定的时间窗内结束。所有负荷应尽快结束以方便装入下列批次。在加载当前批次的所有装载之前，无法启动新批次的准备。尽快终止批量加载并减少码头占用是通过缩短完工时间来实现的。表 3 一个真正问题的例子下面的例子是以前的例子的扩展。现在有些托盘可以从两个通道中取出，而前一个托盘和一个处理时间更长的新替代物。每个托盘的替代通道和处理时间在表 3 中给出。例如，第二个负载的第一个托盘可以从处理时间 2 的第二个通道或第一个时间的第三个通道中获取。当所有托盘从处理时间最短的通道中取出时，可获得一个可行的时间表，如图 3（a）所示，即图 2（a）所示的相同解决方案。让我们分配走道 2，即使它的处理时间比负载 2 的第三个托盘的走道 3 和负载 2 的第四个托盘的走道 1的处理时间更长。此分配的最佳时间表如图 3（b）所示。尽管将两个托盘分配到较大的处理时间，但是就批次的完成时间而言获得了更好的时间表。5.方法FJSP 是一个 NP 难题，因为更简单的问题是 JSP，在强烈意义上是 NP 难的问题25 。因此，在合理的时间内不可能用精确的解决方案获得最佳的解决方案。已经开发了各种近似算法来获得大尺寸调度实例的良好结果26。遗传算法（GAs）27-33，粒子群优化算法34,35，蚁群算法36,37，模拟退火算法38，变邻域搜索算法39,40和禁忌搜索算法 42已被用于最小化文献中 FJSP的完工时间。在这项研究中，Cinar 等人为 FJSP 开发了一个基于优先级的 GA。 27用于解决整车运行调度问题。5.1 表象染色体的每个基因代表用于解码的构造性算法的操作的优先级。置换代码被选择来引用优先值。在这项研究中，每个染色体中的基因数量等于相应替代机器处理的可能操作数量。图 4 说明了图 3（b）给出的时间表的样本染色体。较高的优先值意味着在施工过程中安排较高的优先级，这将在下一小节中解释。例如，负载 1 的第一个托盘的优先级在 A1 上是 18，在 A3 上是 14。如果在建构性算法的迭代中在这些替代方案之间进行选择是必要的，则将选择 A1，因为它具有更高的优先级。5.2 解码解决方案由 Chang 和 Sullivan 43开发的构造算法进行解码，该算法可以为FJSP 生成所有有效的时间表 27。活动时间表构成可行时间表的一个子集，包括最佳时间表。构造性算法仅根据染色体上的信息生成时间表。通过这种方式，可以保证最佳的解决方案包含在搜索空间中，不可能生成不可行或不可行的解决方案。另一方面，编码和解空间之间发生 n 对 1 的关系。换句话说，多于一个染色体可以代表相同的时间表27 。图 3.说明性示例的示例时间表图 4.说明性例子的样本染色体。5.3.Genetic 操作符精英规则和轮盘赌被用作选择操作员的方法。应用两个交叉操作符：循环交叉（CX）和基于作业的交换（JOX）。 CX 是用于排列编码问题的通用算子。绝对基因位置是从父母遗传到后代。 JOX 是由44开发的基于问题的交叉操作符，用于 JSP 以满足几代人继承工作顺序的需求。基于优先级的置换编码可以轻松实现 JOX，并且不需要任何修复机制。应用机器变异和序列变异来重新分配操作，移植变异用于全局搜索。机器突变是为了替代机器（货架/ 叉车）上的操作（货盘）而开发的。它使用基于关键路径的邻域结构。由于不属于关键路径的操作的重新分配不会改变完工时间，因此从关键路径中随机地选择操作以进行重新分配。从替代机器中随机选择一台机器，并将操作安排到随机位置。为了增强邻域搜索，开发了一种基于块结构的序列变异来重定位当前机器上的操作。从关键路径中随机选择一项操作。它在相应块的所有操作之前或之后重新安排。迁移是一种全局搜索的变异算子，通过在每一代中随机产生一个染色体来替代至少一个染色体，从而增强基因库中的多样性。在遗传算法的每次迭代中，确定具有相同财富价值的个体，并将移民程序应用于他们。通过这种方式，减少了 n 对 1 映射的限制。5.4 基于优先级的遗传算法最初的人口是随机产生的。建构性算法用于评估个体。在每次迭代开始时，执行移民程序以减少当前人群中具有相同财富价值的人数。包括父母在内的交配池由选择构建。交配池的 2由精英规则选择，并由轮盘选择。交叉操作符用于生成后代。如果选择两个父母进行交叉，则每个交叉运算符（CX，JOX）有50的机会被应用。在交叉过程终止后，将变换运算符应用于生成的个体。就像在交叉过程中一样，如果个体会发生变异，每个突变算子（机器，序列）有50的概率。在遗传算法的每个重现过程结束时，迭代局部搜索（ILS）被应用于群体中具有最佳适应度值的小量染色体。 ILS 用于搜索更好的解决方案。由于计算量很大，因此只适用于少数人。下一代通过成对比较来确定，其中每个种群中的一个个体（当前和由遗传操作者产生的）在适应值方面进行比较。更好的一个被转移到下一代。 GA 的迭代一直持续到达到最大代数。基于优先级的 GA 的流程图在图 5 中给出。表 4 从 BC 数据集 avRD 获得的平均相对偏差6.计算结果Cinar 等人27将基于优先级的遗传算法与文献中为 FJSP 开发的其他算法进行了比较。基于优先级的遗传算法得到的结果与文献中的算法和给出基于优先级的遗传算法获得的改进百分比的相对偏差进行了比较。 Cinar 等人获得的结果。 27总结在表 4 和表 5 中。表 4 和 5 包括 Chambers 和 Barnes 45（BC 数据集）和 Hurink 等人生成的实例的平均相对偏差（avRD）。 （HU 数据集）。表格的第一列和第二列表示每个实例的作业数量和机器数量。第三列给出了相应数据集中具有指定大小的实例的数量。例如，在 BC 数据集中有两个实例有10 个作业和 11 个机器（表 4）。基于优先级的 GA 与 Mastrolilli 和 Gambardella 47和 Gao 等人的结果进行了比较。对于 BC 实例，以 avRD（表 4 的最后两列）以及 Behnke 和 Geiger 49对于 HU 实例（表 5 的最后一列）来表示。根据这些结果，基于优先级的遗传算法是一种有效的算法，相对于平均遗传算法为 FJSP获得接近最优的结果27。因此，在本研究范围内，选择基于优先级的遗传算法来解决 AS / RS 中卡车负荷运行的调度问题。表 5 从 HU 数据集中获得的平均相对偏差。图 5.基于优先级的 GA。Oliveira 5使用代表性的相关 AS / RS 问题实例和 JPS 文献中的测试实例进行计算机实验。真正问题的代表性实例是随机生成的，代表一个 JSP 进行再循环。这些实例的维度与实际问题的定义的最大维度相同。 Figueiredo 等人6 为相同的真实问题生成随机实例。我们使用 Figueiredo 等人提出的实际问题的相同代表性实例。 6通过为一些货物托盘添加替代通道。表 6 Figueiredo 等人使用的操作分布 6卡车的装载（作业）由 35 个托盘（作业）组成，这些托盘来自靠近停靠站的 5 个走道（机器）。 Figueiredo 等人6 根据表 6 中定义的分布确定了存放 35个托盘的一个货物的通道。例如，货物 5 以相等的概率存储在 5 个通道（通道2-6）之一中，即 20/100 = 0.5。在这项研究中，一个程序可以将 JSP 的实例转换为 Figueiredo 等人生成的再循环。 6 FJSP 实例和基于优先级的 GA 在 Microsoft Visual C + V7.0 中编码。为每个货物随机选择的托盘添加一个替代通道。替代通道和相应卡车之间的处理时间大于 JSP 数据和卡车中确定的通道之间的时间。通过这种方式，研究了将检索序列建模为 FJSP 的好处。每个实例都有两种不同的人口规模：20 人中的小人口和 100 人中的大一人。突变和交叉概率都被确定为 0.5。计算结果在表 7 中给出。第一列至第四列代表实例名称，人口规模（弹出大小），装载/作业数量（n）以及托盘/操作总数（操作）。第五和第六列表示菲格雷多等人 15 次获得的最佳平均完工时间。 6。第七和第八列表示通过基于优先级的 GA 获得的 15 次运行的最佳平均完工时间。第九列给出了获得最小值的实验数量，而第十列表示 15 次运行中的有价值的标准偏差。第十一列代表平均 CPU 时间。对每个实验执行 500 次迭代。根据计算结果，包括灵活性会给出更好的结果，特别是对于那些有大量工作的实例。拟议的 GA 发现 FJSP 数据集的结果比 JSP 数据的结果更好或相同。因此可以得出结论，检索排序问题可以更好地模拟为 FJSP。图 6 显示了人口
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号