在带货盘替代通道的自动化仓库中安排整车运作【中文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 显示了人口规模为 20 和 100 的最大实例（jr 13 2）在整个迭代过程中的最佳适应值。虽然大型实例需要额外的 CPU 时间，但更大的群体规模可以获得更好的解决方案。人口规模为 100 和 32.7 秒需要 164.8 秒，实例“jr 13 2”的人口规模为 20。该算法还可以在更大的人口规模下更加稳健地执行表 7 计算结果图 6.适合度评估7.总结在这项研究中，在 AS / RS 中出现的卡车装载操作的调度被模拟为 FJSP。基于优先级的 GA 应用于真正的 AS / RS 仓库，以对检索到的托盘进行排序。 Figueiredo 等人生成的数据集6 对于同一个仓库，通过为某些操作添加替代机器进行扩展。通过这种方式，研究了通道选择灵活性的影响。生成的数据集的维度与真正的问题相同。在仓库每日问题的便利计算时间内找到合理的解决方案。证明了所提出的基于优先级的遗传算法可以用来解决仓库中现实生活中的检索排序问题。在用来说明 FJSP 优势的一组实例中，我们只考虑一个额外的过道来检索托盘。使用额外的过道具有更长的处理时间，这是我们做出的一个保守的选择，并且在真正的问题中，它可能具有相同的甚至更低的处理时间。尽管如此，如果方便的话，使用更长的处理时间会导致更低的完工时间，从而提高处理速度仓库的有效性。对于具有相似实际问题大小的实例集，FJSP 模型平均可以获得高达 11的增益和 7左右的增益。很明显，如果我们考虑使用不止一个替代通道来检索托盘，这些收益会更大。提高吞吐率，在更短的时间内为客户服务，并减少卡车和司机装货的等待时间，这些结果是其他管理方面的好处。如今，为了增加仓库的吞吐量，仓库建立了更多的过道，在卡车到达之前准备了多个缓冲区以准备货物，在通道开始时有多达 3 个收集器以及更多数量的托盘，从而导致更多昂贵的项目。从 JSP运营模式向 FSJP 运营模式的转变只需要 WMS 升级，短期内将全面回放，避免大量投资增加仓储容量。在这项研究中，通道和卡车之间的运输时间假定在整个装载过程中固定。在进一步的研究中，这个假设可以扩展到使问题更加真实。此外，产品的恶化会对生产过程产生负面影响50,51，因此可以考虑安排仓库中的托盘。致谢这项研究得到了 LATNA 实验室，NRU HSE，RF 政府资助，ag 的部分支持。 11.G34.31.0057。Applied Soft Computing 52 (2017) 566 574Scheduling the truckload operations in automated warehouses withalternative aisles for palletsDidem Cina ra,b, Jos Antnio Oliveir ac, Y. Ilker Topc ua, Panos M. Pardalo sba Department of Industrial Engineering, Faculty of Management, Istanbul Technical University, Istanbul, Turkeyb Department of Industrial and Systems Engineering, Faculty of Engineering, University of Florida, Gainesville, United Statesc ALGORITMI Research Centre, University of Minho, Braga, Portugala r t i c l e i n f o a b s t r a c tArticle history:Received 5 June 2015Received in revised form 27 June 2016 Accepted 13 October 2016Available online 19 October 2016Keywords:Automated storage and retrieval systems Truckload operations schedulingFlexible job shop scheduling Genetic algorithmsIn this study, the scheduling of truck load operations in automated storage and retrieval systems is investigated. The problem is an extension of previous ones such that a pallet can be retrieved from a set of alternative aisles. It is modelled as a exible job shop scheduling problem where the loads are considered as jobs, the pallets of a load are regarded as the operations, and the forklifts used to remove the retrieving items to the trucks are seen as machines. Minimization of maximum loading time is used as the objective to minimize the throughput time of orders and maximize the efciency of the warehouse. A priority based genetic algorithm is presented to sequence the retrieving pallets. Permutation coding is used for encoding and a constructive algorithm generating active schedules for exible job shop scheduling problem is applied for decoding. The proposed methodology is applied to a real problem arising in a warehouse installed by a leading supplier of automated materials handling and storage systems. 2016 Elsevier B.V. All rights reserved.1. IntroductionAutomated storage and retrieval system (AS/RS) is a warehous- ing system that uses mechanic devices for the storage and retrieval of products in both distribution and production environments 1,2 . Automatic cranes move through aisles between racks to put the items on the racks and retrieve those items from storage to the col- lector for fullling the customer orders. AS/RS is fully automated, because no intervention of an operator is needed for handling the pallets 2 . When an order is received for an item, a stacker crane retrieves the pallet from its storage location and carries it to the col- lector at the top of the aisle that is a gravity roller conveyor. At the end of the roller conveyor, the conveyed pallet is picked up using a forklift truck. High space utilization, improved material ow, and improved inventory control are some of the advantages of AS/RS 3 . The best utilization from such a system can be succeed by optimal design and optimal scheduling of the system.Warehouse scheduling optimization is a combinatorial opti- mization problem which cannot be solved with exact algorithms in reasonable computational time for high dimensional instances. Corresponding author at: Department of Industrial Engineering, Faculty of Man- agement, Istanbul Technical University, Istanbul, Turkey.E-mail addresses: cinard.tr (D. Cinar), zandps.uminho.pt(J.A. Oliveira), topcuil.tr (Y. Ilker Topcu), (P.M. Pardalos).Because of the high complexity of the problem, simulation and metaheuristics have been widely used in warehouse scheduling optimization 4 . A detailed literature review about the method- ologies developed for AS/RS design and scheduling is given in Section 3.In this study, the scheduling of truck load operations arising in AS/RS is investigated. The problem is modelled as a exible job shop scheduling problem (FJSP) by considering the loads as jobs and pallets of a load as its operations. The forklifts which are used for transportation of pallets from collectors to trucks are considered as machines. The main contributions of this paper are twofold: (1) scheduling of truck load operations is modelled as a exible job shop scheduling problem, (2) a real problem arising in an AS/RS warehouse installed by a leading supplier of automated materials handling and storage systems is solved by using a priority based genetic algorithm and the effect of aisle selection exibility is inves- tigated. To the best of the authors knowledge, this work is the rst time that the FSJP is used to model the retrieving operation of pallets in an AS/RS warehouse.The paper is organized as follows. Section 2 provides a brief explanation on investigated automated storage system. In Sec- tion 3, a literature review on scheduling of truck load operations is given. Section 4 represents a mixed integer programming (MIP) formulation for a truckload operations scheduling problem in AS/RS and discusses the modelling of the problem as a exible job shop scheduling problem. Section 5 presents the devoted methodology./10.1016/j.asoc.2016.10.0131568-4946/ 2016 Elsevier B.V. All rights reserved.Contents lists available at ScienceDirectApplied Soft Computingj ournal homepage: /locate/asoc D. Cinar et al. / Applied Soft Computing 52 (2017) 566 574 567Fig. 1. Schema of the warehouse.Section 6 gives the computational results for a real life AS/RS ware- house problem. Finally, Section 7 presents the conclusion.2. Storage systemThe methodology proposed in this study is applied to an AS/RS warehouse in Italy which works as a distribution center. Products are stored by the warehouse and loaded to the trucks to fulll the orders of customers. Routes of the trucks, which are known in advance, are determined considering the delivery deadline of cus- tomer orders. The warehouse consists of eleven aisles constituted by pallet racks with the capacity of 40,000 pallets. An automatic stacker crane or S/R machine works in each aisle to move the pallets from their respective rack to the collector at the beginning of the aisle. Forklifts transport the pallets to the trucks. The warehouse has 13 docking bays to load the trucks. A scheme of the loading process in this warehouse is shown in Fig. 1.Warehouse Planning System (WPS) and Warehouse Manage- ment System (WMS) are used to operate the warehouse. Daily planning of loadings for each truck is executed by WPS. The sequence of retrieving pallets and the movement of S/R machines and forklifts are determined by WMS. Approximately one hun- dred loads are retrieved per day by a truck. Each truck has its own delivery time which is considered by WPS and loading must not be delayed. In the strategy dened for the WPS, the whole set of loads are divided into subsets called batches. Loads in a batch are processed simultaneously. Loading of a batch cannot be started before the loads of previous batch are nished. The size of a batch is determined with respect to delivery deadlines and the number of docking bays. A standard daily plan includes 1520 batches with 613 loads for each one.An order of a customer consists a product or a set of products that are delivered on one or more pallets. The set of products for an order is known in advance, and it is available in the warehouse. A truck load consists of a set of pallets transported for one or more clients. The sequence of loading pallets on the truck is determined by WMS with LIFO (Last In First Out) rule. Since the sequence of pallets in a load is predetermined and cannot be changed, precedence relations exist between pallets of a load.The pallets of a load can be retrieved from any aisle. To facilitate the assignment of the trucks to the docking bays, several palletsare placed in different aisles to reduce the time of load prepara- tion, allowing a pallet to be selected in an aisle that is close to the truck and respecting the FEFO (First-Expired-First-Out) rule. The S/R machine is programmed to retrieve the pallets from the corresponding aisle.We assume that each forklift can work for only one aisle. After a forklift receives a pallet from its own aisle, it can carry the pallet to any truck. For safety reasons, more than one forklift cannot be allowed to place pallets in a truck at the same time. So, one load should receive one pallet at a certain time. After a pallet is loaded to the truck, the forklift returns to its aisle and communicates to WMS that it is available for a new transportation. Then the next pallet for the same load is programmed. A forklift can receive only one pallet at each transportation. Detailed information about the analysed AS/RS warehouse can be obtained from 5 .Different sequences of pallets in a batch retrieved by S/R machines result in different processing times. An illustrative exam- ple is the following. Assume that there are 5 aisles in the warehouse represented by A1, A2, . . ., A5. The problem is planning the retriev- ing sequence of a batch including 3 loads. Each load consists of 4 pallets, which have precedence relations in advance, representing a total of 12 pallets to be retrieved in the batch. There is one forklift for each aisle to carry the pallets from the aisle to the correspond-ing truck. Although a pallet can be retrieved from several aisles, in previous studies 5,6 it was assumed that it is the WMS that previ- ously selects the pallets considering the distance to the aisle where the load is prepared. The aisle for each pallet and the processing times are given in Table 1.The aisle storing pallet j and the transportation time between related aisle and truck are shown as (Ak, t) where Ak refers the kth aisle and t is the transportation time from aisle Ak to truck.For example, the rst pallet of the second load must be retrievedTable 1An illustrative example for real problem.jth palletLoad i 1 2 3 41 (A1 ,1) (A2 ,2) (A3 ,3) (A4 ,4)2 (A3 ,1) (A1 ,3) (A3 ,1) (A4 ,2)3 (A4 ,2) (A4 ,2) (A3 ,3) (A5 ,1)568 D. Cinar et al. / Applied Soft Computing 52 (2017) 566 574Fig. 2. Two different schedules for retrieving the pallets.from the third aisle with time 1. For convenience, the pallets were consecutively numbered from 1 to 12.Fig. 2 shows two different sequences of retrieving pallets. The numbers inside the rectangles identify the pallets. For each sequence, Fig. 2 presents the Gantt chart for the set of aisles (left side) and the Gantt chart for the set of loads (right side), which represents better the processing time of the batch. The sequences for retrieving pallets only differ at Aisle 3, where the pallet 11 is collected either after pallets 3 and 7 (Fig. 2(a), or before pallets 3 and 7 (Fig. 2(b). The decision when to retrieve pallet 11 produces signicantly different processing times for the entire batch of loads. Fig. 2(a) presents the optimal solution for this small example.3. Literature reviewIn an AS/RS, planning and performing of accurate loading pro- cesses are very important to meet the customer orders at the proper time 5 . Among previous studies, analysis oriented ones constituted the majority of the literature rather than those devel- oping models and techniques for warehouse design 7 . Simple heuristics and simulation techniques were used for storage and retrieval problems in automated warehousing systems. Bozer and White 8 proposed travel time models for automated S/R machines with single and dual command mode. Han et al. 9 proposed a nearest neighbour heuristic for retrieval sequencing in AS/RS with dual command cycles and used Monte Carlo simulation for eval- uation. Eben-Chaime 10 also used a nearest neighbour heuristic to sequence the retrievals. Hausman et al. 3 compared several storage assignment rules to determine the optimal storage assign- ment policy. Schwarz et al. 11 analysed both storage assignment and interleaving rules with a simulation model. Lee and Schae- fer 12 formulated the problem, which is also handled by Han et al. 9 , as an assignment problem. They proposed a methodology combining the Hungarian method and the ranking algorithm for the assignment problem with the tour-checking and tour-breaking algorithms.In the last few years, besides the mathematical modeling and simulation approaches, metaheuristics have been used in these areas. Comprehensive reviews of warehouse design and control can be found in de Koster et al. 13 , Gu et al. 14 and Baker and Canessa 15 . Moreover, detailed explanations of the current state of the art in AS/RS design are provided by Roodbergen and Vis 2 and Vasili et al. 16 . Manzini et al. 17 developed a multi-parametric dynamic model for a product-to-picker storage system with class- based storage allocation of products. They investigated the factors affecting the warehousing system performance. Yin and Rau 18 combined simulation and genetic algorithms for the dynamic selec- tion of sequencing rules for a class-based unit-load AS/RS. Chang et al. 19 proposed a multi-objective mathematical programming model and a genetic algorithm for the order picking of stacker cranes. Kung et al. 20 developed a dynamic programming based order scheduling methodology for the AS/RS with multiple stacker cranes on a common rail. The problem includes both assignment of orders to each crane and scheduling of cranes without collision. Brezovnik et al. 21 used a multi-objective ant colony optimization method for the storage allocation problem in an AS/RS. Based on the computational results obtained from a home appliance devices warehouse, it was shown that optimal space utilization can be achieved when the products with lower weight and height are stored at higher levels. Yang et al. 22 inferred that the speed prole of an S/R machine has an important effect on the optimal stor- age rack for a multi-deep AS/RS. Atmaca and Ozturk 4 proposed a mathematical programming model and a simulated annealing approach for the storage allocation and storage assignment prob- lems to minimize storage costs. Optimal solution was obtained by the proposed mathematical model for problems having up to 103 materials. Dooly and Lee 23 modelled a shift-based sequencing problem for twin-shuttle AS/RS as a minimum-cost perfect match- ing problem and presented a polynomial-time exact algorithm.Oliveira 5 and Figueiredo et al. 6 modelled the truck load operations on an AS/RS warehouse as a job shop scheduling prob- lem (JSP) with recirculation 5 . Oliveira 5 assumed identical processing times to transport pallets independently of the locationD. Cinar et al. / Applied Soft Computing 52 (2017) 566 574 569of the aisle and the truck. Figueiredo et al. 6 extended the problem by considering different processing times and solved it by genetic algorithms with random keys representation. Both Oliveira 5 and Figueiredo et al. 6 assumed that a pallet can be retrieved from one aisle previously decided by WMS, considering the proximity to the docking bay. In this study, this assumption is extended by consid- ering alternative aisles for pallets. The selection of the aisle where the pallets are retrieved is determined with truck load scheduling simultaneously. So the problem consists of both selection of an aisle to retrieve the pallet, which is currently performed by WMS, and the scheduling of pallets transportation from collector to truck. In this way, the benet of combining these two operations is inves- tigated. No study which addresses this problem as a FJSP has been encountered in the scope of this study.4. Modelling AS/RS warehouses as FJSPIn this section, a MIP formulation for the truckload operation scheduling problem is presented. We do not consider cross-docking or order picking to produce a pallet. The assumptions considered in this study are given as follows: an order is formed by only (complete) pallets of products that are stored in the warehouse. an S/R machine is faster to put a pallet on the collector than a forklift to remove a pallet and an S/R machine operates in advance of the forklift, a collector works as a buffer with capacity for several pallets, the ow of pallets in the collector (gravity roller conveyor) follows the FIFO rule, an S/R machine takes zero units of time to put a pallet in the collector.The notation used hereafter is given in Table 2. The MIP formu- lation for truckload operations scheduling is given as follows:min Cb (1)subject toXijk = 1 i L, j Pi (2)k FijSijk + Cijk MXijk i L, j Pi, k Fij (3) Cijk Sijk + tijk M(1 Xijk) i L, j Pi, k Fij (4) Sijk Ci1 j1 k MYiji1 j1 k i i1 , j Pi, j1 Pi1 , k Fij Fi1 j1 (5)Si1 j1 k Cijk M （1 Yiji1 j1 k）i i1 , j Pi, j1 Pi1 , k Fij Fi1 j1 (6)Table 2Notation for MIP.Indices:i loads (i, i1 L)j pallets (j, j1 P)k forklifts (k F )Sets:L set of loadsP set of palletsF set of forkliftsPi ordered set of pallets of load i (Pi P)Pil(i) the last pallet of PiFij set of alternati
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号