智能化倉儲中箱式緩存區調度算法的設計與應用

段旭磊　張仰森　張濤

摘 要： 在傳統的智能化立體倉庫中，成品將被直接存儲，這種模式對于多品種、多批次的產品生產方式而言，極大地浪費了設備資源，增加了整個調度系統的成本和難度。提出箱式緩存道的概念，將不同成品在緩存區進行積存，當達到一定數量時，將成品統一存儲處理。以國藥集團致君（深圳）坪山藥業智能化立體倉庫系統為研究對象，其中的箱式緩存區調度算法將主要研究智能調度系統中成品合理的分道緩存積放和釋放碼垛，及在節省緩存道占用的前提下合理分配緩存道的問題。箱式緩存道的應用，解決了產品分品種、分批次統一存放的問題，能夠對不同品種、不同規格、不同批次的成品進行準確地分道緩存，提高了生產和存儲效率。

關鍵詞： 智能化立體倉庫； 智能調度； 箱式緩存道； 生產方式

中圖分類號： TN915.5?34 文獻標識碼： A 文章編號： 1004?373X（2017）16?0086?04

Abstract： The final products are stored directly in the traditional intelligent stereoscopic warehouse system （ISWS）. This mode， for multispecies and multi?batch production pattern， is a waste of equipment resources， and increases operating cost and difficulty of the entire dispatching system. The concept of box?type cache is proposed in this paper. According to this concept， the different final products are stored in the cache area firstly， and then the products are released when the number of the products is accumulated to a certain quantity. Taking the intelligent stereoscopic warehouse system （ISWS） of Shenzhen Pinshan Pharmacy as the research object， its final products are distributed into cache and release stacking temporarily in the pipeline in this system. The algorithm that how to split different batches， different specifications and different finished kits into some rails called the multi?objective optimization is proposed. This algorithm improved the utilization of emergency stopping lane， and speed and efficiency of storage.

Keywords： ISWS； intelligent scheduling； box?type cache； production pattern

隨著物流技術和工業生產的快速發展，現代企業對物料搬運和貯存提出了更高的要求，倉儲方式也逐漸發生改變，從最初人力手工作業的簡單堆積，到通過叉車等簡單設備的倉庫式存儲，發展到如今的采用高位叉車、堆垛機、無人導引小車、箱式輸送線、拆/碼垛機器人等自動化設備的立體倉庫存儲。智能化立體倉庫系統（Intelligent Stereoscopic Warehouse System，ISWS），是一種新型的倉儲技術，是物料搬運和倉儲科學中的一門綜合科學技術工程。它是以先進的計算機控制技術為主要技術支持，以高層立體貨架和托盤系統為主要手段對貨物進行存儲，以自動化搬運設備為基礎，能夠適應現代化大批量生產、存儲和物資流通的需要，并且在溝通物流信息、銜接產需、進行科學儲備和企業經營決策等方面也起到了特殊的作用。

智能化立體倉庫軟件系統，主要包括管理及調度系統，而調度系統關乎整個系統的自動化程度和成本支出。在現代企業的生產?存儲?銷售鏈條中，產品品種眾多，批次嚴格，傳統的邊生產邊存儲的方式已經不能滿足實際需求。本文以國藥集團致君（深圳）坪山藥業智能化立體倉庫為基礎，探討調度系統開發與實現中采用箱式緩存道的方法解決產品分品種分批次存儲問題。

1 相關工作

美國學者J.A.White將倉儲中自動化技術的發展分為5個階段[1]：人工倉儲→機械化倉儲→自動化倉儲→集成化倉儲→智能自動化倉儲。隨著計算機智能化技術的快速發展，智能自動化倉儲成為自動化技術的主要發展方向和研究重點。

國內外許多研究學者針對智能化立體倉庫的調度問題進行了大量的研究，并取得了不少的研究成果。在國內，田國會等利用計算機仿真技術分別使用Petri網、時態邏輯、模擬退火、遺傳算法、神經網絡等方法對調度優化問題進行了研究[2?5]；常發亮等通過對物資配送中心的庫存管理與布局優化的研究提出了貨位的布局策略以及優化算法[6]；周奇才提出立體倉庫運行控制的優化準則[7]，分析確定倉庫系統控制的優化控制數學模型，并運用有關原理，提出倉庫巷道堆垛機及出入庫系統貨箱運行的優化控制程序。徐香玲等通過歸納ISWS作業調度的相關原則，建立了專家系統知識庫，并對專家系統在ISWS調度中的應用可行性進行了分析研究[8]。李詩珍，李振等也分別通過不同的研究方法對調度優化問題進行了深入的分析與研究[9?19]。endprint

在國外，美國學者Linn.R.將專家系統的思想應用到立體倉庫的控制中[20]；Kim.Byung等提出了一種基于調度和控制系統的混合智能Agent結構，并將其應用于ISWS的貨位揀選問題[21]；Donald.Tepas提出了用一種知識信息系統來輔助決策立體倉庫中的調度問題并得到了應用[22]；N.Mishra等對批量訂單調度問題進行了研究[23]。P.H.Koo等對不同的調度規則對堆垛機的運行時間的影響進行了分析研究[24]。S.R.Nenad通過提出了一種基于時間窗的調度方法對倉庫的調度問題進行了分析研究[25]。J.M.belenguer采用分支定界的方法對有一定約束條件的路徑規劃問題進行求解[26]。

盡管國內外的研究學者對智能化立體倉庫的研究的側重點不同，但是其主要的研究內容主要還是集中在對堆垛機的揀選作業的優化和入庫貨位選擇優化方面，對除堆垛機外的設備進行研究的較少。其實，在整個調度系統中針對物料如何合理入出庫的前期設計對效率的提高至關重要，箱式緩存道就是為了解決如何合理集中分配設備資源的問題而被提出。如何根據實際的情況設計出一個盡量減少優化復雜性的調度方式仍是一個重要的課題。因本實例是深圳國藥一致藥業立體倉庫，該公司集藥品的生產、存儲及銷售于一體，生產車間在打包完藥品成品后會直接將藥品放在箱式輸送線，藥品經過輸送線運送到倉庫進行存儲。由于車間會同時生產不同品種不同批次的藥品，而為了提高倉庫貨架的利用率，將在一個托盤上碼垛一定多的藥品進行存放，所以不同批次不同產品的藥品在進入倉庫時不能立即進行碼垛入庫，需要先進行分別積放，等積放一定的數量后才可進行機器人碼垛入庫。箱式緩存道就是為了能夠使藥品進行分品種分批次積放而設計。

2 箱式緩存區系統描述

深圳國藥一致藥業的生產車間共有三層，其中二層和三層分別有一道輸送線與倉庫部分相連接，所以本系統的箱式緩存區分為上、下兩層，分別有三層車間和二層車間相連接，并且上、下兩層通過再檢區相連接。上層和下層緩存區各有9條緩存道。

上層和下層緩存區俯視圖如圖1所示，再檢區俯視圖如圖2所示。

從生產車間輸送過來的成品外箱上都貼有惟一標識該成品各種信息的藥品電子監管碼，該電子監管碼為一維Code128條碼。

如圖2 所示，箱式緩存區共設有5個條碼掃描器，其中上層和下層分別設有2個，再檢區設有1個。為了加快箱子進入緩存區的節奏，默認三樓車間輸送過來的箱子優先進入上層緩存道，二樓車間運輸過來的箱子優先進入下層緩存道，只有上層或下層的緩存道已經積放滿后才考慮進行換層存放。現以下層緩存道為例描述箱子入緩存道流程，如圖3所示。

3 系統原則及算法

本系統中箱式緩存區的作用主要就是對藥品成品進行分品種分批次緩存積放，由于緩存道的數量已經確定而生產車間的生產產品的品種數量并不能確定，所以為了盡可能地合理利用緩存道，對箱式緩存區的調度要求應具備以下幾點：

（1） 按照成品批次分配緩存道，即不同產品不同批次的成品分配不同的緩存道。

（2） 按照生產車間與上下層緩存道對應原則優先分道，即二層車間的成品優先分配下層緩存道，三層車間的成品優先分配上層緩存道，以此減少成品的換層時間，加快成品緩存的節奏。

（3） 如果同品種同批次的產品占用兩條以上的緩存道，那么優先分配給數量多的緩存道使其優先達到滿托盤數緩存道。

（4） 對于同品種同批次的緩存道可以實現緩存道的同時釋放及同時進入，盡量減少緩存道的占用，提高緩存道的利用率。

（5） 為了減少異常產品占用緩存道，只對異常產品開放第九道緩存道。

（6） 如果緩存道全滿，提示釋放，暫停輸送機上產品調度。

（7） 如果當前產品可用緩存道滿，并且后續產品有可用緩存道，對當前產品進行循環換層處理（大批量產品的效率要求）。

根據系統提出的調度原則以及在實際應用中成品入緩存道的情況，提出以下算法：

Step1：設[ai]表示緩存道號，[a=1]表示下層緩存道，[a=2]表示上層緩存道，并且令[xaia=1，2 ， i=1，2，…，9]表示[ai]緩存道的狀態，[xai∈0，1]，0表示[ai]緩存道未綁定產品批號信息，1表示[ai]緩存道已綁定產品批號信息。[Nai]表示緩存道[ai]內箱子的數量，[Oai]表示緩存道[ai]剩余需要釋放的數量，[Fai]表示緩存道[ai]滿托盤的數量，[Fai]的取值根據緩存道內產品的不同取值不同，不同產品的滿道數量在入緩存道前應該維護進數據庫，轉到Step2。

Step2：箱子通過箱線進入緩存道之前有一個換層區域，這里通過條碼掃描器驗證條碼，如果條碼掃描器掃到條碼，將條碼上傳給調度系統，系統根據條碼提供的產品批號信息查詢該條碼掃描器所在層的緩存道的產品批號綁定信息，若存在[ai]緩存道綁定了此產品批號信息且未滿（[Nai+Oai

Step3：若[i=19x1i

Step4：換線再檢區，條碼掃描器掃描條碼，若掃描成功，將條碼上傳調度系統，系統獲得條碼提供的產品批號信息，依次遍歷上層和下層緩存道綁定信息，嘗試獲取綁定該批號信息且未滿的緩存道號[ai]，若獲得且緩存道號為下層，則下發換層下層命令，轉至Step2；若為上層，則下發換層上層命令。如果沒有獲取符合條件的，則遍歷依次遍歷下層和上層緩存道，獲得空緩存道號[ai]，若為下層，則下發換層下層命令，轉到Step2；若為上層，則下發換層上層命令。若沒有找到符合上面兩個條件的緩存道則下發換層下層指令，是箱子進入循環狀態直到找到符合條件的緩存道。如果掃描條碼失敗，下發剔除指令將此箱送至剔除位由人工進行后續處理，轉至Step7。

Step5：箱子進入緩存道前也需要進行掃碼，調度系統獲得條碼信息后查詢當前層的產品批號綁定信息進行分道，并將分道號迅速發送給箱線PLC控制器，PLC控制器根據分道號將箱子進行分道緩存，轉至Step6。

Step6：調度系統實時監測緩存道與機器人狀態，若存在機器人空閑且緩存區存在可釋放緩存道，則下發釋放指令，釋放緩存道箱子進入碼垛箱線，同時將產品批號信息以及釋放數量和箱型信息與碼垛機器人信息進行綁定，同時更新該釋放緩存道的數量信息，如果釋放條件為滿足一托盤釋放時，數量更新情況為[Nai=（Nai-Fai）]，[Oai=Fai]，若釋放條件為產品結批釋放，則數量更新情況為[Nai=0]，[Oai=Nai]，其中[Oai]的值是調度系統實時監控緩存道的釋放情況逐一遞減直到為0，當緩存道[Nai=Oai=0]，則表明該緩存道為空緩存道，應清空綁定情況，[Xai=0]，轉至Step7。

Step7：結束。

4 系統實現

國藥集團致君（深圳）坪山藥業立體倉庫智能調度系統采用Delphi語言開發，其開發平臺為Borland Delphi 2010。在搭建本系統的開發環境與運行環境時，還涉及到一些其他的通信軟件與技術，比如OPC技術、Delhpi多線程機制等。在整個系統設計的過程中，充分考慮了各種異常情況，并進行相應的處理。實踐表明，智能化立體倉庫箱式緩存道調度系統的研究與實現是成功的，如表1所示。

表1 管理及調度系統部分功能和性能與目前部分廠家對比

5 結 論

本文主要對箱式緩存區系統進行描述，并提出了一種對成品合理分配緩存道的算法，實現了對不同產品不同批次進行分配緩存存放，在分配緩存道方面實現同批次同緩存道的邊進邊出，大大減少了同批次產品進入不同緩存道情況，并大大提高了緩存道的利用率。在實際使用中效果良好。本智能化立體倉庫較一般的智能化立體倉庫增加了箱式緩存道。在對不同產品或同產品不同批號進行分道緩存時如何減少對緩存道的占用，在箱子的分配上如何保證緩存道分配的準確性都是系統研究的重點。在緩存道的調度分配算法中，采用持續換層的方法處理極端情況下緩存道不夠用的異常，但是在箱子進行上下層換道過程中，由于不能保證硬件的絕對正確性，比如條碼掃描器，可能出現抖動從而被多次觸發，對同一個箱子多次掃碼，現在只是在每個箱子掃碼完畢后增加延時處理信號，在邏輯上還不能完全避免掃碼異常這個問題。在實際的生產過程中，需充分考慮各種情況，才能避免不必要的錯誤。

注：本文通訊作者為張仰森。

參考文獻

[1] 呂廣明.物流設備與規劃技術[M].北京：中國電力出版社，2009.

[2] 田國會，張攀，尹建芹，等.基于混合遺傳算法的固定貨架揀選優化問題研究[J].機械工程學報，2004（2）：141?144.

[3] 田國會，張攀，李曉磊，等.一類倉庫作業優化問題的混合遺傳算法研究[J].系統仿真學報，2004，16（6）：1198?1201.

[4] 田偉，田國會，張攀，等.考慮非對稱情形的一類揀選問題的改進LK算法求解[J].中國工程科學，2004（11）：47?52.

[5] 寧春林，田國會，尹建芹，等.Max?Min蟻群算法在固定貨架揀選路徑優化中的應用[J].山東大學學報（工學版），2004，33（6）：676?680.

[6] 常發亮，劉長有.智能化立體倉庫存儲管理策略的優化[J].基礎自動化，1996（5）：6?9.

[7] 劉道華，原思聰，蘭洋，等.基于組態監控的設備運行管理系統設計[J].微電子學與計算機，2005（10）：116?119.

[8] 徐香玲，傅衛平，李德信，等.基于專家系統的智能化立體倉庫出入庫調度研究[J].物流技術，2005（2）：38?40.

[9] 常發亮，劉增曉，辛征，等.智能化立體倉庫揀選作業路徑優化問題研究[J].系統工程理論與實踐，2007（2）：139?143.

[10] 李詩珍，王轉.訂單揀取路徑優化研究：S形啟發式方法在配送中心揀貨中的應用[J].物流技術與應用，2005（5）：67?70.

[11] 李梅娟，陳雪波，劉臣奇.基于改進蟻群算法揀選作業優化問題的求解[J].計算機工程，2009，35（3）：219?221.

[12] 楊玲，關志偉.智能化立體倉庫揀選路徑優化問題研究[J].中國制造業信息化，2011，40（7）：47?50.

[13] 姜山，季業飛.GASA混合優化算法在智能化立體倉庫堆垛機作業調度問題中的應用[J].制造業自動化，2010，32（10）：63?64.

[14] 劉志雄.物流自動化倉庫揀選作業調度粒子群優化研究[J].機械制造，2010，48（1）：66?69.

[15] 楊華龍，陳志俊，計瑩峰，等.基于時間驅動作業成本法的配送中心作業優化[J].大連海事大學學報（自然科學版），2012（4）：103?106.

[16] 劉萬軍，黃楊波，丁鵬.基于單親遺傳算法的揀選作業優化研究[J].計算機應用，2010（11）：2891?2893.

[17] 計三有，陳厚松.基于蟻群算法的立體倉庫揀選作業優化[J].武漢理工大學學報，2010（23）：69?71.

[18] 李振，胡慶東，張國英，等.基于小生境遺傳算法的人工揀貨路徑優化研究[J].物流科技，2011（6）：85?88.

[19] 杜亞江，王嫻.物流中心高層貨架揀選作業的路徑優化[J].計算機系統應用，2013（9）：160?163.

[20] ZHAN Yuedong， LUO Ying. Guided and detecting technology of intelligent robot AGV and new?style AGV [C]// International Conference on Sensors and Control Techniques （ICSC 2000）. [S.l.： s.n.]， 2000： 461?464.endprint

[21] RATLIFF H D， ROSENTHAL A S. Order?picking in a rectangular warehouse： a solvable case of the traveling salesman problem [J]. Operations Research， 1983， 31（3）：507?521.

[22] TEPAS Donald. Workware decision support systems： a compare?hensive methodological approach to work?scheduling problems [J]. Theor issues in ergon， 2003， 4（7）： 1012?1018.

[23] KOO P H， JANG J. Vehicle travel time models for AGV systems under various dispatching rules [J]. International journal of flexible manufacturing systems， 2002， 14（3）： 249?261.

[24] MISHRA N， KUMAR V， KUMAR N， et al. Addressing lot sizing and warehousing scheduling problem in manufacturing environment [J]. Expert systems with applications， 2011， 38（9）： 11751?11762.

[25] SMOLIC?ROCAK N， BOGDAN S， KOVACIC Z， et al. Time windows based dynamic routing in multi?AGV systems [J]. IEEE transactions on automation science & engineering， 2010， 7（1）： 151?155.

[26] BELENGUER J M， BENAVENT E， PRINS C， et al. A branch and cut method for the capacitated location?routing problem [J]. Computers & operations research， 2006， 38（6）： 1541?1546.endprint