論匈牙利算法在倉儲指派作業(yè)中的應用

朱傳棟

(北京物資學院 北京 101149)

一、引言

在社會經(jīng)營管理中，經(jīng)常將人、物和事進行適當調(diào)配，以充分發(fā)揮人盡其才、物盡其用和事得其人的作用，提高管理效率。倉儲作業(yè)中也是如此，對于一批入出庫任務，如何指派入出庫作業(yè)效率最高，能夠使得總費用最少，這是一項典型的分配問題。以U形多道式倉儲系統(tǒng)為例，其模型的特殊性，一般都采用特殊的解法——匈亞利算法，其也是目前指派問題求解方法中應用最廣泛的解法。

二、匈牙利算法解決指派問題的基本思想

圖1 匈牙利算法流程圖

算法原理如下：C=(Cij)n·n為研究問題的目標系數(shù)矩陣，且滿足Cij≥0，首先需對每行/列元素減去該行/列最小元素，得到n個具有不同行/列的獨立0元素Cij，若獨立0元素數(shù)小于矩陣階數(shù)，進行覆蓋操作，直到含有n個獨立0元素，該方法得到的矩陣具有和原矩陣相同的最優(yōu)解。其中，算法流程如圖1所示。

三、貨位分配優(yōu)化方案

其中，物資存儲采取就近貨位分配和隨機分配相結(jié)合的ABC貨位分類方法，即在物資存儲工作中，都存在“少數(shù)關(guān)鍵和多數(shù)一般”這種規(guī)律，少數(shù)重要可對系統(tǒng)起到?jīng)Q定性作用，多數(shù)一般甚至不大重要但又不可或缺。如果能夠?qū)⒅攸c工作用于解決這些少數(shù)但關(guān)鍵重要的事物上，對多數(shù)但一般重要事物進行一般管理，比起不分輕重同等對待，顯然前者效果要好得多。ABC貨位分類法，就是基于這種思想，并進行與之相應的管理。這里以入出庫頻率為主要指標，A類作業(yè)頻率較高，較靠近入出庫口；B類作業(yè)頻率中等，距離一般；C類作業(yè)頻率較低，距離較遠。

所以，根據(jù)存儲物資種類、特性及該系統(tǒng)運行特點，為集中巷道作業(yè)，提高堆垛機運行效率，需要對貨架區(qū)進行貨位分配優(yōu)化。這里，不同于以往研究，即一巷道貨架放部分A類物資和部分B、C類物資，將剩余A、B和C類物資安排在另一條巷道兩排貨架上，具體如下圖所示。

圖2 ABC貨位分區(qū)安排示意圖

四、匈牙利算法在具體指派中的應用

以某U型多道式倉儲系統(tǒng)為研究對象，該系統(tǒng)貨架共4排、30列(雙貨位貨格)、12層，配有一臺轉(zhuǎn)彎型堆垛機，可管理兩條巷道、四排貨架。具體數(shù)據(jù)獲取方面，貨格規(guī)格為長1980mm*高925mm*寬1200mm。堆垛機直道階段水平方向速度為vXmax=1.67m/s，水平方向加速度為aX=±0.3m/s2；垂直方向速度為vYmax=0.5m/s，垂直方向加速度為aY=±0.3m/s2。彎道階段，為保證堆垛機安全，其水平方向速度較低且載貨臺降至較低位置，速度v彎=0.5m/s。ta、tb分別表示單一命令和復合命令作業(yè)巡回中包括定位、貨位探測和貨叉作業(yè)巡回等固定不變的時間總和，其中，ta=4s，tb=7.9s。進行換巷道作業(yè)時，為便于優(yōu)化，不考慮堆垛機本身體積、直軌與彎軌間切換和轉(zhuǎn)彎前載貨臺降至較低位置等因素對實驗結(jié)果的影響。

表1為系統(tǒng)一初始任務單，作業(yè)位置(x,y,z)中x、y、z分別表示排、列、層。

表1 初始任務單數(shù)據(jù)

對任務單數(shù)據(jù)進行分析，平衡其入、出庫貨位數(shù)量，使入出庫貨位數(shù)量能夠配對一致，其入出庫貨位之間運行時間如下表2所示。

表2 系統(tǒng)一組各入出庫貨位之間堆垛機運行時間(s)

由于復合作業(yè)作業(yè)效率較高，因此其倉儲作業(yè)以復合作業(yè)為主，并基于ABC貨位分配優(yōu)化、集中巷道方式為前提進行的。這里運用Matlab編程，可得表3最優(yōu)指派方案。

表3 最優(yōu)指派方案

為提高系統(tǒng)運行效率，我們以集中巷道作業(yè)為前提，對上述最優(yōu)指派方案進行排序，并假設以跨巷道作業(yè)組合中入庫貨位巷道為堆垛機所在巷道，對每一巷道進行入出庫作業(yè)組合隨機排序，并用跨巷道作業(yè)組合銜接，其中，系統(tǒng)一任務序列如下：4-0，7-6，1-2，9-3，5-8。優(yōu)化前總作業(yè)完成時間432.58s，優(yōu)化后總作業(yè)完成時間為223.13s,不考慮其他影響因素，系統(tǒng)優(yōu)化前后效率能夠提升45%以上。

五、結(jié)論

通過以上分析，可以得出以下結(jié)論：第一，合理進行貨位優(yōu)化能夠提高系統(tǒng)運行效率；第二，復合作業(yè)較單一作業(yè)效率更高，利用匈牙利算法求解U形多道式倉儲系統(tǒng)作業(yè)指派問題具有良好的效果。