物流工程 交互式存取在自动化立体仓库中的应用论文-

1、交互式存取在自动化立体仓库中的应用STEPHEN C.GRA VES, W ARREN H.HAUSMAN AND LEROY B SCHW ARZ 本文对之前报道的关于自动化立体仓库系统分配规则进行了扩展,也就是,存取需求的程序化。通过连续和离散解析模型的评价程序,本文比较了分配存储交互存储的操作性能。结果表明通过分配存储交互存储在一些现实情况和之前模拟情形下可以得到堆垛机的行走时间(方向上有了重大的减少。这样的减少可能直接解释为:在现有的系统中增加了生产能力。分配存储交互存储可能会用于改善系统实现吞吐量和存储容量的平衡。虽然这个系统测试高层自动化立体仓库,但是这个结果呈现出仓储功能的一般含

2、义。1.介绍自动化仓储系统彻底改变了仓库的设计和大量的操作能力和设施。这些系统工作如下:所有的入库物品都被分配到托盘上,有时两种或更多的物品品种被分配到同一个托盘上。这托盘内容信息将会与一台分配并记录托盘在货架存储位置的微型电脑通信。这些托盘将通过自动巷道堆垛机存储。当系统接到一则请求的时候,电脑将通过电脑存储系统获得托盘位置信息,并指导巷道堆垛机取出托盘。货物拣选或移动完成后,托盘会返回到物品入库处进行储存,加固或重新利用。自动化存储系统调度由三个基础原理组成:托盘分配,存储分配和交互存储。早期的工作关注于存储分配,也就是分配托盘在货架中的存储位置。交互存储是通过假设一个操作不是一个交互系统

3、来进行排除的。在一个非交互系统中,所有的存取请求都是从堆垛机的输入输出点开始的:给予一个存储请求,堆垛机就从输入输出点移动到货架分配位置,存储托盘货物,然后空程返回输入输出点。同样的,给予一个出库请求,堆垛机就空着从输入输出点移动到适当的货架位置上,移动托盘,然后移动到输入输出点。非交互系统有时候叫“单地址”系统,因为堆垛机在一次连续的两个输入输出点之间只能访问单一的货架位置(地址。交互系统有时候也叫“双地址”系统,它在一次连续的两个输入输出点之间有能力访问两个货架位置。给予一个完整的存储请求后,堆垛机可以直接移动到指定的货架位置上然后到下一个取货位置而不用返回到输入输出点。很明显,交互存储系

4、统比非交互系统允许有更大的潜在生产能力。然而,双地址系统最大的生产力只可能从最佳的分配存储交互存储联合中获得。在这篇文章中,我们对分配存储交互存储的几个改变做个测验。基本的分析方法是连续解析模型。通过使用这种连续解析模型,我们可以深入分析堆垛机系统在处理各种各样分配存储交互存储下预期行走时间的表达式。通过离散评价模型,我们也可以测试各种各样条件改变,和连续解析模型本身。通过分配存储交互存储在一些现实情况和之前模拟情形下可以得到堆垛机的行走时间(方向上有了重大的减少。这些政策可能直接用于当前系统提高系统生产力,或者为了达到系统生产力与存储能力的一个令人满意的平衡而间接设计一个新的系统。本文的组织

5、结构如下:在§2中我们介绍我们的假设,概述连续模型,以及回顾以前研究中最相关的结果。在§3中,我们描述一下被Martin K.Starr所接受的存储变量。在§4中,我们报告一下我们的分析和经验结果。在§5中,讨论这个结果2.假设,连续模型,之前的结果假设以下是我们做出的十条假设:1.每一个托盘都只包含一部数量或者一类物品。这从我们的托盘分配分析中引用。2.所有的存储位置都是一样的尺寸。3.这个系统分析由一台堆垛机服务一个单面的通道构成。这个分析和结果对一个两面的通道直接超过搬动范围。4.这个系统在堆垛机和输入输出输送机输送托盘上是有界限的。入库口和出库口

6、是一样的,表示输入输出点,这个输入输出点在货架的一边。5.在通道的一侧是一个R行C列的存储位置。堆垛机能够同时在垂直方向和水平方向移动,垂直方向和水平方向上的速度是这样的:从输入输出点到达行的最远处的时间和到达列的最远处的时间是相等的(就是这个系统在时间上是“正方形”。堆垛机行走测量是用时间而不是用距离。时间是标准化的,也就是堆垛机最大存储或取出的行走时间是1时间单元。6.堆垛机在输入输出点或在存储位置上的装载卸载时间(转换时间是忽略不计的。7.每一种的物品的周转量的已知的而且是不变的,周转量就是在一定的时间周期内,给定的一种物品的需求数量。一定时间周期指的是一天,一个月,一年等等。事实上,对

7、于每一种货物,长度和存储时间是相互的。当基础流量被考虑到的时候,这个假设有部分是不严格的。8.在给予一部分数量或物品种类时,物品单元和托盘基于FIFO原则在货架系统上移动。9.存储需求是基于FCFS服务的,也就是先到先服务。10.短距离动力因数是被忽略的,我们在这只对系统长期的平均行为感兴趣。对于这些假设更深入的讨论可以在【3】中看到。在本文中,对【3】中非交互存储假设允许交互存储是不严格的。事实上,为了改变交互存储的影响,我们假设堆垛机问情隔行的。我们称之为强制性交互存储。如果这个系统有一个真实的存储和取出请求队列缓冲区,这个MIL假设就是现实的。我们将在§5中解释对于没有这样的缓

8、冲队列的交互系统。我们也假设存取内部之间的统计独立性(例如,我们假设一个给定的交互存储概率是相应的产品存取的概率这个假设应该满足系统的最真实的利益。连续模型【3】介绍了连续模型在堆垛机行走时间和托盘周转的公式。在这些描述中,y(i表示堆垛机从输入输出点到货架在100ith分位处的时间,也就是 同样的,在适当的假设(“ABC”库存分析法,EOQ模型等下,托盘周转量包含在物品在100jth处的分布,也就是 其中,K是库存持有成本,s是一个影响该公司的“ABC”曲线的形状参数。之前的结果在非交互存储假设下,存储分配使堆垛机运行时间最短原则是最大周转原则,也就是分配最高周转托盘到最近的位置上。一个最真

9、实的规则版本就是最基本的版本,托盘和货架被分成一些较小的分区。在这些分区里,托盘是随机分配的。在【3】中我们证明了这些规则明显高于那些使用随机规则来存储的。3.替代的调度策略替代存储分配规则学习以下存储分配规则:(1随机存储分配。在这个规则中,托盘被存储于每一个开放的货位的的机会是相同的。(2基本存储分配(C2或C3。在这个规则中,所有的货物和存储货架将被分成几个种类(2个或3个。周转量最高的货物将与最靠近输入输出点的位置相匹配。一个托盘是随机存储于它所属的类别中的。图1显示了一个货架被连续划分成3个“L“形的边界形式。 图1(3基于全周转形的存储分配。在这个规则中,周转量最高的托盘被分配到最

10、靠近输入输出点的货位上。这是一种基于L形边界的限制情形。所有的货位都是不同的。我们的分析包括最大潜力存储分配规则的情况。交互存储规则以下交互存储规则会被查验,除了非交互存储规则:(1带有先到先服务队列指导的交互存取。(MIL/FCFS在这个规则与每一个存储有关,通过从取出队列中按先到先服务原则选择。(2拥有K线检索选择队列的强制交互存储规则。(KIL/Q=K在这里,交互存储再一次被强制执行,但是,检索需要的不是带有第一K 线检索的先进先出规则。4.结果:分析和经验在这部分里,我们将对各种各样的存储作业/交互存储规则的操作性能进行检测。操作性能通过以下进行衡量:(a预期的单程运行时间(例如:堆垛

11、机从输入输出点到存储位置的平均运行时间;(b预期的交互时间(堆垛机从一位货位到下一个货位的平均运行时间;(c预期的往返时间。这预期的往返时间指的是系统完成一个存储和一个取出动作的时间。在MIL规则中,预期的往返时间是两次单程时间加上预期的交互时间。在NIL规则中,预期往返时间是四次单程时间。结果表现在两方面:依照在§3中的连续模型分析,和依照R=10,C=30的离散系统的经验。为了获得离散结果,编写一个计算机程序去列举出从输入输出点到每一个可能的货位(300个货位的单程时间和每一对货位(89700对之间的交互时间,平均它们,通过合适的概率权重确定各种存储作业/交互存储策略。离散枚举作

12、为检查连续模型进行有效性预测。结果显示出了四个库存周转率分布:20/60;20/70;20/80和20/90,X/Y的意思是最高需求量X%与所有的需求量Y%的比例。我们通过公式: (0=siiG s来进行近似库存周转率分布,其中G(i表示托盘累i,10,><计需求量与通过ith的最高需求量的比例。(详见【3】结果显现出以下几点:1.RAN/NIL/FCFS.随机分配存储;非交互存储;FCFS取出队列。2. FULL/NIL/FCFS.全周转型存储;非交互存储;FCFS取出队列。3. C2/NIL/FCFS.两种类型存储分配;非交互存储;FCFS取出队列。4. C3/NIL/FCFS

13、.三种类型存储分配;非交互存储;FCFS取出队列。5. RAN/MIL/FCFS.随机分配存储;强制交互存储;FCFS取出队列。6. FULL/MIL/FCFS.全周转型存储;强制交互存储;FCFS取出队列。7. C2/MIL/FCFS.两种类型存储分配;强制交互存储;FCFS取出队列。8. C3/MIL/FCFS.三种类型存储分配;强制交互存储;FCFS取出队列。9. C2/MIL/Q=K. 两种类型存储分配;强制交互存储;K线检索选择队列。10. C3/MIL/Q=K. 三种类型存储分配;强制交互存储;K线检索选择队列。详细结果出在表1中;连续模型往返时间绘在图2中,离散模型在图3中NIL

14、策略。NIL存储分配/交互策略的分析结果(1到4点的推断在【3】中。为便于比较,连续和离散模型的计算结果列于表1的1-4部分和图2和图3中。RAN/NIL/FCFS.通过强制性交互存储,预期往返时间等于2倍的单程时间加上预期交互时间。在连续模型在预期单程运行时间是随机存储分配的2/3(见【3】。同样的,任何定制预期交互时间策略是由所有堆垛机行走于所有货位之间的运行时间之和的权重确定。加权调度策略确定相应的交互存储概率。附录列出的细节。对于RAN/NIL/FCFS,预期交互时间等于7/15.所以,预期往返时间表示为RT(RAN/MIL/FCFS,即 FULL/NIL/FCFS。在全周转型存储中,

15、最快的周转货物被分配到最靠近输入输出点的货位上的,次快的分配到次靠近的货位上,依此类推。这种分配存储规则有最小的单程预期运行时间。这可能不是最小的往返预期运行时间(见以下的讨论。对于FULL的单程预期运行时间在【3】中的(17给出,是4s/(5s+1.对于制定时间策略,预期交互时间,L 可以由以下方法推导出: * R1,R2值由表格搜寻决定。表格的大小使用,使用电网的大小,取决于所需的计算复杂性其中z=2s/(s+1。对于FULL/NIL/FCFS的往返时间是8s/(5s+1加上表达式(4.对于s,RT(FULL/MIL/FCFS的评估可能相当于周转分布。对于之前显现的基本策略结果,一些边界的

16、形状的有一定顺序讨论的。对于以上规定,通过NIL策略很容易推断出其它条件不变,最好的基本存储分配策略是使用远离边界的政策(见图1。我们称之为“直角-L”边界。这原因是堆垛机的速率在横向和纵向上是相等的,并且在NIL策略上所有运行到输入输出点都一样(堆垛机运行在货位之间的时间(x1,x2和输入输出点的最大值x1,x2。在交互系统中,运行同样出现在存储货位之间。因此,最好的类边界形状在往返时间需求 上不是很可能不是-“直角-L”边界。准确的最佳边界是相当难以列举的,尽管它们是在从输入输出点到另外一个对角的货架单元的直线上是对称的(因为堆垛机运行时间的一样的。“直角-L”边界控制着对称性质。一种替代

17、的边界配置,也控制着正方形边界和对称性质。这种边界图案可以显示出最短的预期交互时间,但不是预期单程时间。最佳的边界是最短的往返时间,就是两次预期单程时间和预期交互时间之和。为了研究预期堆垛机运行时间对边界形状的影响,“直角-L ”的离散求值,同心方和其它边界被创建。我们的经验发现:(1预期交互时间对于边界形状是相当敏感的,例如:“直角-L ”边界的预期交互时间仅超过最佳同心方见附件的10%;(2预期交互时间对于往返时间贡献大约1/3的时间,例如:对于“直角-L ”边界交互时间大约是往返时间的30%。给定一个低些的标准,预期往返时间是最短预期单程时间的两倍(通过“直角-L ”边界取得加上最短预期

18、交互时间(通过同心方边界取得,这些经验发现“直角-L ”边界预期往返时间是勘测超过最佳时间的3%(30%中的10%。无论如何,我们不能找到任何边界形状的预期往返时间比从“直角-L ”边界得到的时间更短。因为这些原因随后的分析都是基于“直角-L ”边界的。C2/MIL/FCFS 。这个策略的预期单程时间表达式在【3】中给出,因此,这个预期交互时间,L ,是: 其中p(X,Y表示从货位X 到货位Y 的可能交互时间,L X 表示类X 预期交互时间,L I ,II 表示在货位类I 和类II 之间预期交互时间。L I , L II 和L I ,II 在附录中引出。将其代入表达式(5是: 其中R 1表示类

19、I 和类II 之间的边界,z=2s/(s+1。(表达式(6和(7被写得与表达式(5一样。RT(C2/MIL/FCFS是两倍的预期单程时间加上表达式(6或(7,依据R 1的值,对于给定值s ,R 1可能选择用数字表示最短的RT(C2/MIL/FCFS。C3/MIL/FCFS 。这结果得出完全相同的方式,也就是两个类似的种类。为简洁起见,推导公式被省略去。C2/MIL/Q=K.这个策略与C2/MIL/FCFS 是相似的除了出库是不是先到先服务以外。在完成存储后,出库队列的第一K 线继续检查相同类型的出库操作。如果发现一个它将会操作。如果没有,第一类的出库队列被出库。注意K=1等价于FCFS 的出库

20、策略。所以C2/MIL/Q=1的结果与C2/MIL/FCFS 的结果是一样的。K=是在特殊情况下,总是能找到一种相同策略的存储方式。这策略下预期往返时间是: 其中p(X是类X 可能的存储或取出,W X 是类X 预期单程时间,L I ,L II 和LI ,II是类I ,类II 和类I ,类II 之间的预期交互时间。很可能仅找到类II 出库队列在第一K 线队列中即 p (II /K 。因此,很可能找到一个类I 的出库是(1- p (II /K 。对于类II 是一样的。这些概率的稳态概率派生形成一个检索队列的马尔科链分析。详见【2】1。可以选择数值的固定值R1的价值,最大限度地减少(8。C3/MIL

21、/Q=K 。这个策略与C2/MIL/Q=K 是相似的除了有三种类。选择队列中检索指定的优先级设置如下:如果存储的是类I ,取出优先级是类I ,II ,III 的顺序。相同的,如果存储的是类II ,取出优先级是II ,III ,I 的顺序;如果存储的是类III ,取出优先级是III ,II ,I 的顺序。这种策略的预期往返时间可能与C2/MIL/Q=K 推导出相同的方式。不幸地,找到一个类X 的稳态概率之间的第一个K 队列检索,从二元马尔可夫链分析而得,没有封闭的形式表达。因此,优化是相当困难,除了相对简单的情况下的K= 2,K = 时的特殊情况。5. 结果讨论使用连续模型的分析结果在图2中显现

22、;离散结果在图3中显现。自然结果是与两图相同的。结果最大的不同是当出现大量的库存周转率。这种现象是由于前几托盘(高周转率的重要性日益增加以及“离散”和连续之间的关联。由于列举结果较为保守,随后进行的讨论将集中于他们。最差的调度策略是RAN /NIL/FCFS ,它的预期往返时间是2.66。使用此策略的系统可能有吞吐量急剧增加有三种方式:采用基于类的存储分配;采用强制性交互存储策略;或两者兼用。采用RAN /NIL/FCFS调度策略,预期往返时间可能减小32%到1.80,不管周转分布。当然,在一个真实的MIL系统中,因为偶然的情况下所需的缓冲区队列,一些堆垛机往返过程中包含交互过程。到这个程度,真实的运行时间将是NIL和MIL表现的加权平均值。另外,RAN /NIL/FCFS系统的周转量可能会通过保留2到3种分配存储而增加。例如, C2/NIL/FCFS预期往返时间是从对于20/60的库存周转分布的2.63(一个16%的减少量到对于20/90库存周转分布的1.77(一个33%的减小量不等。C3/NIL/FCFS更优秀些:预期往返时间是从对于20/60的库存周转分布的2.13(一个20%的减少量到对于20/90库存周转分布的1.57(一个41%的减小量不等。还注意到,由FULL/NIL/FCFS获得的收益对于2和3级存储分配收益率分别约为70%和85%。基于类的存储分配成本:如果我们