物流工程 交互式存取在自動化立體倉庫中的應(yīng)用論文-

1、交互式存取在自動化立體倉庫中的應(yīng)用STEPHEN C.GRA VES, W ARREN H.HAUSMAN AND LEROY B SCHW ARZ 本文對之前報道的關(guān)于自動化立體倉庫系統(tǒng)分配規(guī)則進(jìn)行了擴(kuò)展,也就是,存取需求的程序化。通過連續(xù)和離散解析模型的評價程序,本文比較了分配存儲交互存儲的操作性能。結(jié)果表明通過分配存儲交互存儲在一些現(xiàn)實(shí)情況和之前模擬情形下可以得到堆垛機(jī)的行走時間(方向上有了重大的減少。這樣的減少可能直接解釋為:在現(xiàn)有的系統(tǒng)中增加了生產(chǎn)能力。分配存儲交互存儲可能會用于改善系統(tǒng)實(shí)現(xiàn)吞吐量和存儲容量的平衡。雖然這個系統(tǒng)測試高層自動化立體倉庫,但是這個結(jié)果呈現(xiàn)出倉儲功能的一般含

2、義。1.介紹自動化倉儲系統(tǒng)徹底改變了倉庫的設(shè)計和大量的操作能力和設(shè)施。這些系統(tǒng)工作如下:所有的入庫物品都被分配到托盤上,有時兩種或更多的物品品種被分配到同一個托盤上。這托盤內(nèi)容信息將會與一臺分配并記錄托盤在貨架存儲位置的微型電腦通信。這些托盤將通過自動巷道堆垛機(jī)存儲。當(dāng)系統(tǒng)接到一則請求的時候,電腦將通過電腦存儲系統(tǒng)獲得托盤位置信息,并指導(dǎo)巷道堆垛機(jī)取出托盤。貨物揀選或移動完成后,托盤會返回到物品入庫處進(jìn)行儲存,加固或重新利用。自動化存儲系統(tǒng)調(diào)度由三個基礎(chǔ)原理組成:托盤分配,存儲分配和交互存儲。早期的工作關(guān)注于存儲分配,也就是分配托盤在貨架中的存儲位置。交互存儲是通過假設(shè)一個操作不是一個交互系統(tǒng)

3、來進(jìn)行排除的。在一個非交互系統(tǒng)中,所有的存取請求都是從堆垛機(jī)的輸入輸出點(diǎn)開始的:給予一個存儲請求,堆垛機(jī)就從輸入輸出點(diǎn)移動到貨架分配位置,存儲托盤貨物,然后空程返回輸入輸出點(diǎn)。同樣的,給予一個出庫請求,堆垛機(jī)就空著從輸入輸出點(diǎn)移動到適當(dāng)?shù)呢浖芪恢蒙?移動托盤,然后移動到輸入輸出點(diǎn)。非交互系統(tǒng)有時候叫“單地址”系統(tǒng),因?yàn)槎讯鈾C(jī)在一次連續(xù)的兩個輸入輸出點(diǎn)之間只能訪問單一的貨架位置(地址。交互系統(tǒng)有時候也叫“雙地址”系統(tǒng),它在一次連續(xù)的兩個輸入輸出點(diǎn)之間有能力訪問兩個貨架位置。給予一個完整的存儲請求后,堆垛機(jī)可以直接移動到指定的貨架位置上然后到下一個取貨位置而不用返回到輸入輸出點(diǎn)。很明顯,交互存儲系

4、統(tǒng)比非交互系統(tǒng)允許有更大的潛在生產(chǎn)能力。然而,雙地址系統(tǒng)最大的生產(chǎn)力只可能從最佳的分配存儲交互存儲聯(lián)合中獲得。在這篇文章中,我們對分配存儲交互存儲的幾個改變做個測驗(yàn)?；镜姆治龇椒ㄊ沁B續(xù)解析模型。通過使用這種連續(xù)解析模型,我們可以深入分析堆垛機(jī)系統(tǒng)在處理各種各樣分配存儲交互存儲下預(yù)期行走時間的表達(dá)式。通過離散評價模型,我們也可以測試各種各樣條件改變,和連續(xù)解析模型本身。通過分配存儲交互存儲在一些現(xiàn)實(shí)情況和之前模擬情形下可以得到堆垛機(jī)的行走時間(方向上有了重大的減少。這些政策可能直接用于當(dāng)前系統(tǒng)提高系統(tǒng)生產(chǎn)力,或者為了達(dá)到系統(tǒng)生產(chǎn)力與存儲能力的一個令人滿意的平衡而間接設(shè)計一個新的系統(tǒng)。本文的組織

5、結(jié)構(gòu)如下:在§2中我們介紹我們的假設(shè),概述連續(xù)模型,以及回顧以前研究中最相關(guān)的結(jié)果。在§3中,我們描述一下被Martin K.Starr所接受的存儲變量。在§4中,我們報告一下我們的分析和經(jīng)驗(yàn)結(jié)果。在§5中,討論這個結(jié)果2.假設(shè),連續(xù)模型,之前的結(jié)果假設(shè)以下是我們做出的十條假設(shè):1.每一個托盤都只包含一部數(shù)量或者一類物品。這從我們的托盤分配分析中引用。2.所有的存儲位置都是一樣的尺寸。3.這個系統(tǒng)分析由一臺堆垛機(jī)服務(wù)一個單面的通道構(gòu)成。這個分析和結(jié)果對一個兩面的通道直接超過搬動范圍。4.這個系統(tǒng)在堆垛機(jī)和輸入輸出輸送機(jī)輸送托盤上是有界限的。入庫口和出庫口

6、是一樣的,表示輸入輸出點(diǎn),這個輸入輸出點(diǎn)在貨架的一邊。5.在通道的一側(cè)是一個R行C列的存儲位置。堆垛機(jī)能夠同時在垂直方向和水平方向移動,垂直方向和水平方向上的速度是這樣的:從輸入輸出點(diǎn)到達(dá)行的最遠(yuǎn)處的時間和到達(dá)列的最遠(yuǎn)處的時間是相等的(就是這個系統(tǒng)在時間上是“正方形”。堆垛機(jī)行走測量是用時間而不是用距離。時間是標(biāo)準(zhǔn)化的,也就是堆垛機(jī)最大存儲或取出的行走時間是1時間單元。6.堆垛機(jī)在輸入輸出點(diǎn)或在存儲位置上的裝載卸載時間(轉(zhuǎn)換時間是忽略不計的。7.每一種的物品的周轉(zhuǎn)量的已知的而且是不變的,周轉(zhuǎn)量就是在一定的時間周期內(nèi),給定的一種物品的需求數(shù)量。一定時間周期指的是一天,一個月,一年等等。事實(shí)上,對

7、于每一種貨物,長度和存儲時間是相互的。當(dāng)基礎(chǔ)流量被考慮到的時候,這個假設(shè)有部分是不嚴(yán)格的。8.在給予一部分?jǐn)?shù)量或物品種類時,物品單元和托盤基于FIFO原則在貨架系統(tǒng)上移動。9.存儲需求是基于FCFS服務(wù)的,也就是先到先服務(wù)。10.短距離動力因數(shù)是被忽略的,我們在這只對系統(tǒng)長期的平均行為感興趣。對于這些假設(shè)更深入的討論可以在【3】中看到。在本文中,對【3】中非交互存儲假設(shè)允許交互存儲是不嚴(yán)格的。事實(shí)上,為了改變交互存儲的影響,我們假設(shè)堆垛機(jī)問情隔行的。我們稱之為強(qiáng)制性交互存儲。如果這個系統(tǒng)有一個真實(shí)的存儲和取出請求隊列緩沖區(qū),這個MIL假設(shè)就是現(xiàn)實(shí)的。我們將在§5中解釋對于沒有這樣的緩

8、沖隊列的交互系統(tǒng)。我們也假設(shè)存取內(nèi)部之間的統(tǒng)計獨(dú)立性(例如,我們假設(shè)一個給定的交互存儲概率是相應(yīng)的產(chǎn)品存取的概率這個假設(shè)應(yīng)該滿足系統(tǒng)的最真實(shí)的利益。連續(xù)模型【3】介紹了連續(xù)模型在堆垛機(jī)行走時間和托盤周轉(zhuǎn)的公式。在這些描述中,y(i表示堆垛機(jī)從輸入輸出點(diǎn)到貨架在100ith分位處的時間,也就是 同樣的,在適當(dāng)?shù)募僭O(shè)(“ABC”庫存分析法,EOQ模型等下,托盤周轉(zhuǎn)量包含在物品在100jth處的分布,也就是 其中,K是庫存持有成本,s是一個影響該公司的“ABC”曲線的形狀參數(shù)。之前的結(jié)果在非交互存儲假設(shè)下,存儲分配使堆垛機(jī)運(yùn)行時間最短原則是最大周轉(zhuǎn)原則,也就是分配最高周轉(zhuǎn)托盤到最近的位置上。一個最真

9、實(shí)的規(guī)則版本就是最基本的版本,托盤和貨架被分成一些較小的分區(qū)。在這些分區(qū)里,托盤是隨機(jī)分配的。在【3】中我們證明了這些規(guī)則明顯高于那些使用隨機(jī)規(guī)則來存儲的。3.替代的調(diào)度策略替代存儲分配規(guī)則學(xué)習(xí)以下存儲分配規(guī)則:(1隨機(jī)存儲分配。在這個規(guī)則中,托盤被存儲于每一個開放的貨位的的機(jī)會是相同的。(2基本存儲分配(C2或C3。在這個規(guī)則中,所有的貨物和存儲貨架將被分成幾個種類(2個或3個。周轉(zhuǎn)量最高的貨物將與最靠近輸入輸出點(diǎn)的位置相匹配。一個托盤是隨機(jī)存儲于它所屬的類別中的。圖1顯示了一個貨架被連續(xù)劃分成3個“L“形的邊界形式。 圖1(3基于全周轉(zhuǎn)形的存儲分配。在這個規(guī)則中,周轉(zhuǎn)量最高的托盤被分配到最

10、靠近輸入輸出點(diǎn)的貨位上。這是一種基于L形邊界的限制情形。所有的貨位都是不同的。我們的分析包括最大潛力存儲分配規(guī)則的情況。交互存儲規(guī)則以下交互存儲規(guī)則會被查驗(yàn),除了非交互存儲規(guī)則:(1帶有先到先服務(wù)隊列指導(dǎo)的交互存取。(MIL/FCFS在這個規(guī)則與每一個存儲有關(guān),通過從取出隊列中按先到先服務(wù)原則選擇。(2擁有K線檢索選擇隊列的強(qiáng)制交互存儲規(guī)則。(KIL/Q=K在這里,交互存儲再一次被強(qiáng)制執(zhí)行,但是,檢索需要的不是帶有第一K 線檢索的先進(jìn)先出規(guī)則。4.結(jié)果:分析和經(jīng)驗(yàn)在這部分里,我們將對各種各樣的存儲作業(yè)/交互存儲規(guī)則的操作性能進(jìn)行檢測。操作性能通過以下進(jìn)行衡量:(a預(yù)期的單程運(yùn)行時間(例如:堆垛

11、機(jī)從輸入輸出點(diǎn)到存儲位置的平均運(yùn)行時間;(b預(yù)期的交互時間(堆垛機(jī)從一位貨位到下一個貨位的平均運(yùn)行時間;(c預(yù)期的往返時間。這預(yù)期的往返時間指的是系統(tǒng)完成一個存儲和一個取出動作的時間。在MIL規(guī)則中,預(yù)期的往返時間是兩次單程時間加上預(yù)期的交互時間。在NIL規(guī)則中,預(yù)期往返時間是四次單程時間。結(jié)果表現(xiàn)在兩方面:依照在§3中的連續(xù)模型分析,和依照R=10,C=30的離散系統(tǒng)的經(jīng)驗(yàn)。為了獲得離散結(jié)果,編寫一個計算機(jī)程序去列舉出從輸入輸出點(diǎn)到每一個可能的貨位(300個貨位的單程時間和每一對貨位(89700對之間的交互時間,平均它們,通過合適的概率權(quán)重確定各種存儲作業(yè)/交互存儲策略。離散枚舉作

12、為檢查連續(xù)模型進(jìn)行有效性預(yù)測。結(jié)果顯示出了四個庫存周轉(zhuǎn)率分布:20/60;20/70;20/80和20/90,X/Y的意思是最高需求量X%與所有的需求量Y%的比例。我們通過公式: (0=siiG s來進(jìn)行近似庫存周轉(zhuǎn)率分布,其中G(i表示托盤累i,10,><計需求量與通過ith的最高需求量的比例。(詳見【3】結(jié)果顯現(xiàn)出以下幾點(diǎn):1.RAN/NIL/FCFS.隨機(jī)分配存儲;非交互存儲;FCFS取出隊列。2. FULL/NIL/FCFS.全周轉(zhuǎn)型存儲;非交互存儲;FCFS取出隊列。3. C2/NIL/FCFS.兩種類型存儲分配;非交互存儲;FCFS取出隊列。4. C3/NIL/FCFS

13、.三種類型存儲分配;非交互存儲;FCFS取出隊列。5. RAN/MIL/FCFS.隨機(jī)分配存儲;強(qiáng)制交互存儲;FCFS取出隊列。6. FULL/MIL/FCFS.全周轉(zhuǎn)型存儲;強(qiáng)制交互存儲;FCFS取出隊列。7. C2/MIL/FCFS.兩種類型存儲分配;強(qiáng)制交互存儲;FCFS取出隊列。8. C3/MIL/FCFS.三種類型存儲分配;強(qiáng)制交互存儲;FCFS取出隊列。9. C2/MIL/Q=K. 兩種類型存儲分配;強(qiáng)制交互存儲;K線檢索選擇隊列。10. C3/MIL/Q=K. 三種類型存儲分配;強(qiáng)制交互存儲;K線檢索選擇隊列。詳細(xì)結(jié)果出在表1中;連續(xù)模型往返時間繪在圖2中,離散模型在圖3中NIL

14、策略。NIL存儲分配/交互策略的分析結(jié)果(1到4點(diǎn)的推斷在【3】中。為便于比較,連續(xù)和離散模型的計算結(jié)果列于表1的1-4部分和圖2和圖3中。RAN/NIL/FCFS.通過強(qiáng)制性交互存儲,預(yù)期往返時間等于2倍的單程時間加上預(yù)期交互時間。在連續(xù)模型在預(yù)期單程運(yùn)行時間是隨機(jī)存儲分配的2/3(見【3】。同樣的,任何定制預(yù)期交互時間策略是由所有堆垛機(jī)行走于所有貨位之間的運(yùn)行時間之和的權(quán)重確定。加權(quán)調(diào)度策略確定相應(yīng)的交互存儲概率。附錄列出的細(xì)節(jié)。對于RAN/NIL/FCFS,預(yù)期交互時間等于7/15.所以,預(yù)期往返時間表示為RT(RAN/MIL/FCFS,即 FULL/NIL/FCFS。在全周轉(zhuǎn)型存儲中,

15、最快的周轉(zhuǎn)貨物被分配到最靠近輸入輸出點(diǎn)的貨位上的,次快的分配到次靠近的貨位上,依此類推。這種分配存儲規(guī)則有最小的單程預(yù)期運(yùn)行時間。這可能不是最小的往返預(yù)期運(yùn)行時間(見以下的討論。對于FULL的單程預(yù)期運(yùn)行時間在【3】中的(17給出,是4s/(5s+1.對于制定時間策略,預(yù)期交互時間,L 可以由以下方法推導(dǎo)出: * R1,R2值由表格搜尋決定。表格的大小使用,使用電網(wǎng)的大小,取決于所需的計算復(fù)雜性其中z=2s/(s+1。對于FULL/NIL/FCFS的往返時間是8s/(5s+1加上表達(dá)式(4.對于s,RT(FULL/MIL/FCFS的評估可能相當(dāng)于周轉(zhuǎn)分布。對于之前顯現(xiàn)的基本策略結(jié)果,一些邊界的

16、形狀的有一定順序討論的。對于以上規(guī)定,通過NIL策略很容易推斷出其它條件不變,最好的基本存儲分配策略是使用遠(yuǎn)離邊界的政策(見圖1。我們稱之為“直角-L”邊界。這原因是堆垛機(jī)的速率在橫向和縱向上是相等的,并且在NIL策略上所有運(yùn)行到輸入輸出點(diǎn)都一樣(堆垛機(jī)運(yùn)行在貨位之間的時間(x1,x2和輸入輸出點(diǎn)的最大值x1,x2。在交互系統(tǒng)中,運(yùn)行同樣出現(xiàn)在存儲貨位之間。因此,最好的類邊界形狀在往返時間需求 上不是很可能不是-“直角-L”邊界。準(zhǔn)確的最佳邊界是相當(dāng)難以列舉的,盡管它們是在從輸入輸出點(diǎn)到另外一個對角的貨架單元的直線上是對稱的(因?yàn)槎讯鈾C(jī)運(yùn)行時間的一樣的。“直角-L”邊界控制著對稱性質(zhì)。一種替代

17、的邊界配置,也控制著正方形邊界和對稱性質(zhì)。這種邊界圖案可以顯示出最短的預(yù)期交互時間,但不是預(yù)期單程時間。最佳的邊界是最短的往返時間,就是兩次預(yù)期單程時間和預(yù)期交互時間之和。為了研究預(yù)期堆垛機(jī)運(yùn)行時間對邊界形狀的影響,“直角-L ”的離散求值,同心方和其它邊界被創(chuàng)建。我們的經(jīng)驗(yàn)發(fā)現(xiàn):(1預(yù)期交互時間對于邊界形狀是相當(dāng)敏感的,例如:“直角-L ”邊界的預(yù)期交互時間僅超過最佳同心方見附件的10%;(2預(yù)期交互時間對于往返時間貢獻(xiàn)大約1/3的時間,例如:對于“直角-L ”邊界交互時間大約是往返時間的30%。給定一個低些的標(biāo)準(zhǔn),預(yù)期往返時間是最短預(yù)期單程時間的兩倍(通過“直角-L ”邊界取得加上最短預(yù)期

18、交互時間(通過同心方邊界取得,這些經(jīng)驗(yàn)發(fā)現(xiàn)“直角-L ”邊界預(yù)期往返時間是勘測超過最佳時間的3%(30%中的10%。無論如何,我們不能找到任何邊界形狀的預(yù)期往返時間比從“直角-L ”邊界得到的時間更短。因?yàn)檫@些原因隨后的分析都是基于“直角-L ”邊界的。C2/MIL/FCFS 。這個策略的預(yù)期單程時間表達(dá)式在【3】中給出,因此,這個預(yù)期交互時間,L ,是: 其中p(X,Y表示從貨位X 到貨位Y 的可能交互時間,L X 表示類X 預(yù)期交互時間,L I ,II 表示在貨位類I 和類II 之間預(yù)期交互時間。L I , L II 和L I ,II 在附錄中引出。將其代入表達(dá)式(5是: 其中R 1表示類

19、I 和類II 之間的邊界,z=2s/(s+1。(表達(dá)式(6和(7被寫得與表達(dá)式(5一樣。RT(C2/MIL/FCFS是兩倍的預(yù)期單程時間加上表達(dá)式(6或(7,依據(jù)R 1的值,對于給定值s ,R 1可能選擇用數(shù)字表示最短的RT(C2/MIL/FCFS。C3/MIL/FCFS 。這結(jié)果得出完全相同的方式,也就是兩個類似的種類。為簡潔起見,推導(dǎo)公式被省略去。C2/MIL/Q=K.這個策略與C2/MIL/FCFS 是相似的除了出庫是不是先到先服務(wù)以外。在完成存儲后,出庫隊列的第一K 線繼續(xù)檢查相同類型的出庫操作。如果發(fā)現(xiàn)一個它將會操作。如果沒有,第一類的出庫隊列被出庫。注意K=1等價于FCFS 的出庫

20、策略。所以C2/MIL/Q=1的結(jié)果與C2/MIL/FCFS 的結(jié)果是一樣的。K=是在特殊情況下,總是能找到一種相同策略的存儲方式。這策略下預(yù)期往返時間是: 其中p(X是類X 可能的存儲或取出,W X 是類X 預(yù)期單程時間,L I ,L II 和LI ,II是類I ,類II 和類I ,類II 之間的預(yù)期交互時間。很可能僅找到類II 出庫隊列在第一K 線隊列中即 p (II /K 。因此,很可能找到一個類I 的出庫是(1- p (II /K 。對于類II 是一樣的。這些概率的穩(wěn)態(tài)概率派生形成一個檢索隊列的馬爾科鏈分析。詳見【2】1?？梢赃x擇數(shù)值的固定值R1的價值,最大限度地減少(8。C3/MIL

21、/Q=K 。這個策略與C2/MIL/Q=K 是相似的除了有三種類。選擇隊列中檢索指定的優(yōu)先級設(shè)置如下:如果存儲的是類I ,取出優(yōu)先級是類I ,II ,III 的順序。相同的,如果存儲的是類II ,取出優(yōu)先級是II ,III ,I 的順序;如果存儲的是類III ,取出優(yōu)先級是III ,II ,I 的順序。這種策略的預(yù)期往返時間可能與C2/MIL/Q=K 推導(dǎo)出相同的方式。不幸地,找到一個類X 的穩(wěn)態(tài)概率之間的第一個K 隊列檢索,從二元馬爾可夫鏈分析而得,沒有封閉的形式表達(dá)。因此,優(yōu)化是相當(dāng)困難,除了相對簡單的情況下的K= 2,K = 時的特殊情況。5. 結(jié)果討論使用連續(xù)模型的分析結(jié)果在圖2中顯現(xiàn)

22、;離散結(jié)果在圖3中顯現(xiàn)。自然結(jié)果是與兩圖相同的。結(jié)果最大的不同是當(dāng)出現(xiàn)大量的庫存周轉(zhuǎn)率。這種現(xiàn)象是由于前幾托盤(高周轉(zhuǎn)率的重要性日益增加以及“離散”和連續(xù)之間的關(guān)聯(lián)。由于列舉結(jié)果較為保守,隨后進(jìn)行的討論將集中于他們。最差的調(diào)度策略是RAN /NIL/FCFS ,它的預(yù)期往返時間是2.66。使用此策略的系統(tǒng)可能有吞吐量急劇增加有三種方式:采用基于類的存儲分配;采用強(qiáng)制性交互存儲策略;或兩者兼用。采用RAN /NIL/FCFS調(diào)度策略,預(yù)期往返時間可能減小32%到1.80,不管周轉(zhuǎn)分布。當(dāng)然,在一個真實(shí)的MIL系統(tǒng)中,因?yàn)榕既坏那闆r下所需的緩沖區(qū)隊列,一些堆垛機(jī)往返過程中包含交互過程。到這個程度,真實(shí)的運(yùn)行時間將是NIL和MIL表現(xiàn)的加權(quán)平均值。另外,RAN /NIL/FCFS系統(tǒng)的周轉(zhuǎn)量可能會通過保留2到3種分配存儲而增加。例如, C2/NIL/FCFS預(yù)期往返時間是從對于20/60的庫存周轉(zhuǎn)分布的2.63(一個16%的減少量到對于20/90庫存周轉(zhuǎn)分布的1.77(一個33%的減小量不等