肖 偉，彭汝佳，曹 偉

XIAO Wei1,2,3, PENG Ru-jia2,3, CAO Wei1,3

（1.湖南大學 工商管理學院，長沙 410079 ；2.湖南大學 經濟與貿易學院，長沙 410079；3.湖南省物流信息與仿真技術重點實驗室，長沙 410079）

0 引言

分揀作業(yè)是配送的核心作業(yè)，決定了配送中心的工作效率和經營業(yè)績，占配送中心總作業(yè)成本的40%以上。隨著消費時代的來臨，終端客戶要求配送中心以高速度完成工作，在短時間內完成大批量、多種類的配送任務，這就提高了分揀作業(yè)的難度。特別是快遞業(yè)務的發(fā)展，倉儲式配送中心向通過式配送中心發(fā)展，優(yōu)質高效的分揀作業(yè)有助于物流企業(yè)的競爭力成長。

以往的研究表明，就如何改善分揀作業(yè)，提高分揀效率等問題，國內學者做了如下探討。一類研究認為應從硬件環(huán)節(jié)改善分揀作業(yè)，提高設備自動化水平。李哲峰（2001）提出了在貨物識別中使用計算機圖像處理技術，替代出錯率較高的人工識別方式。朱錚濤（2001）提出了使用PLC現(xiàn)場工業(yè)總線連接分揀設備與計算機，實現(xiàn)智能化控制。楊庚（2003）提出了一類分揀控制軟件的結構，但執(zhí)行成本較高，選擇在卷煙物流中進行了測試。張君等人（2003）提出使用RS串行總線連接分揀設備與計算機，可降低執(zhí)行成本，但同時有性能損失。田景賀（2006）提出采用RFID技術，實現(xiàn)分揀系統(tǒng)的無人值守工作方式。

另一類研究則認為應從管理角度出發(fā)改善分揀作業(yè)，提高分揀方式的效率。謝偉東（2007）提出虛擬容器隊列算法，將原有的同步分揀方式改進為異步分揀方式，有效提高了卷煙分揀效率。張貽弓（2008,a）提出了一類訂單排序算法，將訂單排產作為TSP問題，采用最大最小蟻群算法求解。張貽弓（2008,b）還提出了卷煙分揀系統(tǒng)設備選型的優(yōu)化原則。李豐（2009）提出了一類異步分揀算法，將分揀時間視作虛擬時間窗口分配給分揀設備，改善了分揀系統(tǒng)性能。李歧強（2001）提出了一類受控時滯PN工具，并證明了描述分揀系統(tǒng)方面的有效性。黃銀娣（2006）利用PN工具建立了離散仿真模型，檢驗了分揀系統(tǒng)性能指標。李暄（2009）利用商業(yè)仿真軟件Flexsim建立了離散仿真模型，優(yōu)化了分揀設備數(shù)量。

本文的研究與前述研究略有不同，在信息技術和自動化技術高度發(fā)達的今天，配送中心大量采用自動化技術與IT技術，作業(yè)系統(tǒng)和上位系統(tǒng)之間應保持合理有效的通信機制，才能改善分揀作業(yè)效率，避免出現(xiàn)異常流程。因而，以分揀作業(yè)系統(tǒng)和上位信息系統(tǒng)之間的通信機制為研究對象，采取有窮自動機建立了通信過程圖，并插入了異常流程。建立了基于STPN的通信機制模型。算例仿真表明，該通信機制具有可達性，在性能上較現(xiàn)實系統(tǒng)有明顯改善。

1 分揀系統(tǒng)的有窮自動狀態(tài)機描述

分揀系統(tǒng)是配送中心的主要作業(yè)系統(tǒng)，擔負著訂單切割、貨物分選的工作。其內部由三個主要子系統(tǒng)構成，分別為負責補充貨物的補貨系統(tǒng)，負責分揀工作的分揀線路，負責包裝輸送的包裝線路。

分揀系統(tǒng)在空閑中偵聽線路信號，如上位系統(tǒng)發(fā)送訂單到來消息，則回復一個空閑等待消息。分揀系統(tǒng)在運轉狀態(tài)、檢修狀態(tài)或故障狀態(tài)時不偵聽線路信號，同時也不回復上位系統(tǒng)的訂單消息。分揀系統(tǒng)在完成訂單作業(yè)后，回復上位系統(tǒng)執(zhí)行完畢消息，并回到空閑狀態(tài)，繼續(xù)偵聽線路信號，因而根據(jù)以上的說明，有如下圖所表示。

圖1 分揀系統(tǒng)的有窮自動狀態(tài)機

上圖中，為簡化討論采取有窮自動狀態(tài)機的方式描述了分揀系統(tǒng)的5種狀態(tài)和狀態(tài)轉換條件。其中，狀態(tài)P1為空閑狀態(tài)，且在偵聽線路消息。狀態(tài)P2為工作狀態(tài)。狀態(tài)P3為完成狀態(tài)，且在檢修中。狀態(tài)P4為掛起狀態(tài)，表明工作中出現(xiàn)故障。狀態(tài)P5為排查狀態(tài)，表明分揀系統(tǒng)正在排查隱患。轉換條件T1表明線路上無消息傳來。條件T2表明線路傳來分揀任務。條件T3表明分揀機存在缺貨。條件T4為補貨系統(tǒng)補貨到位。條件T5為分揀任務結束，分揀系統(tǒng)發(fā)送停機請求。條件T6為上位系統(tǒng)確認分揀任務完成，分揀系統(tǒng)回到偵聽狀態(tài)。條件T7為分揀系統(tǒng)進入檢修。條件T8為分揀系統(tǒng)完成檢修。條件T9為分揀系統(tǒng)排查隱患。條件T10為補貨系統(tǒng)停頓。條件T11為訂單等待超時。根據(jù)以上的狀態(tài)和狀態(tài)轉移條件，設分揀系統(tǒng)的當前狀態(tài)為P0，轉移條件為T0，可得到如下通信機制表達式。

步驟1，如分揀系統(tǒng)當前狀態(tài)為P1，同時分揀系統(tǒng)在偵聽線路消息，如無消息傳來，則分揀系統(tǒng)保持當前狀態(tài)P1。如有消息傳來，則進入步驟2。

步驟2，分揀系統(tǒng)置當前狀態(tài)為P2，進入工作狀態(tài)，如各項工作條件滿足，則工作完畢后，分揀系統(tǒng)置當前狀態(tài)為P3，同時發(fā)送完成消息給上位系統(tǒng)。

步驟3，如分揀系統(tǒng)當前狀態(tài)為P2，進入工作狀態(tài)，如各項工作條件有未滿足條件，如補貨條件不滿足，則分揀系統(tǒng)置當前狀態(tài)為P4，系統(tǒng)中的作業(yè)流程被掛起。直到各項工作條件滿足后，分揀系統(tǒng)置當前狀態(tài)為P2，進入工作狀態(tài)，解除作業(yè)流程的掛起狀態(tài)。

步驟4，如分揀系統(tǒng)當前狀態(tài)為P3，且已收到上位系統(tǒng)停機指令，則分揀系統(tǒng)轉入狀態(tài)P5，進入檢修狀態(tài)。分揀系統(tǒng)進入檢修狀態(tài)后不響應上位系統(tǒng)指令，亦不偵聽線路消息，所有線路消息掛起。

步驟5，如分揀系統(tǒng)完成檢修，則置分揀系統(tǒng)當前狀態(tài)為P3，如收到上位系統(tǒng)歸位指令，則分揀系統(tǒng)置當前狀態(tài)為P1，開始偵聽線路消息，所有線路消息掛起狀態(tài)解除，返回步驟1。

2 上位信息系統(tǒng)的有窮自動狀態(tài)機描述

上位信息系統(tǒng)是配送中心的訂單處理機構，負責訂單的接受、確認、切割排序和退回處理。在結構上，上位信息系統(tǒng)由三個隊列組成，分別為等待訂單隊列、處理訂單隊列、完成訂單隊列。上位信息系統(tǒng)具有幾類狀態(tài)，工作狀態(tài)、等待狀態(tài)、掛起狀態(tài)、偵聽狀態(tài)等。

上位信息系統(tǒng)的等待訂單隊列如存在等待訂單，則進入偵聽狀態(tài)。如分揀系統(tǒng)發(fā)來請求消息，則上位信息系統(tǒng)將等待訂單隊列中的訂單取出后發(fā)送副本，并將訂單置入處理訂單隊列。上位信息系統(tǒng)處于等待狀態(tài)。如分揀系統(tǒng)結束作業(yè)并發(fā)送完畢消息，則上位信息系統(tǒng)轉出等待狀態(tài)，轉入等待狀態(tài)。如上位信息系統(tǒng)等待隊列已滿，則掛起呼叫中心傳來的訂單。如上位信息系統(tǒng)內訂單為空，則進行偵聽狀態(tài)，偵聽線路傳來的訂單。根據(jù)以上的說明，有如下圖所表示。

圖2 上位信息系統(tǒng)的有窮自動狀態(tài)機

上圖中，為簡化討論，采取有窮自動狀態(tài)機的方式描述了上位信息系統(tǒng)的5種狀態(tài)和狀態(tài)轉換條件。其中，狀態(tài)B1為空閑狀態(tài)，且未在偵聽線路消息。狀態(tài)B2為等待狀態(tài)，上位信息系統(tǒng)在線等待分揀系統(tǒng)的申請消息。狀態(tài)B3為工作狀態(tài)，上位信息系統(tǒng)發(fā)出訂單副本，并等待接收來自分揀系統(tǒng)的完成回執(zhí)。狀態(tài)B4為上位系統(tǒng)處于偵聽狀態(tài)。狀態(tài)B5為掛起狀態(tài)，表明各個消息隊列已滿，不滿足繼續(xù)執(zhí)行條件。轉換條件K1表明線路上無消息傳來。條件K2和條件K3表明線路持續(xù)傳來訂單任務。條件K4、條件K7和條件K10為分揀系統(tǒng)持續(xù)發(fā)出申請消息。條件K5為分揀系統(tǒng)處于離線維修狀態(tài)，線路無應答。條件K6為分揀系統(tǒng)發(fā)回任務完成回執(zhí)。條件K8和條件K12為上位信息系統(tǒng)接到分揀系統(tǒng)發(fā)送的故障停機請求。條件K9為上位信息系統(tǒng)接到分揀系統(tǒng)發(fā)送的復位請求。條件K11為上位信息系統(tǒng)掛起超時。設上位信息系統(tǒng)的當前狀態(tài)為B0，轉移條件為K0，可得到如下通信機制表達式。

步驟1，如上位信息系統(tǒng)當前狀態(tài)為B1，且未偵聽線路，如呼叫中心傳來訂單副本消息，則上位信息系統(tǒng)置當前狀態(tài)為B2，偵聽下位作業(yè)系統(tǒng)申請消息；

步驟2，如上位信息系統(tǒng)當前狀態(tài)為B2，且線路完好，偵聽到下位作業(yè)系統(tǒng)發(fā)來的申請消息，則上位信息系統(tǒng)從等待訂單隊列中取出訂單副本，下發(fā)給下位作業(yè)系統(tǒng)，并上位信息系統(tǒng)置當前狀態(tài)為B3。上位信息系統(tǒng)偵聽下位作業(yè)系統(tǒng)線路消息，如此時有呼叫中心發(fā)來訂單副本，則訂單副本入上位信息系統(tǒng)等待訂單隊列。

步驟3，如上位信息系統(tǒng)當前狀態(tài)為B3，且下位作業(yè)系統(tǒng)發(fā)來任務完成回執(zhí)，則上位信息系統(tǒng)置當前狀態(tài)為B4。上位信息系統(tǒng)重整等待訂單隊列，已發(fā)出訂單副本進入完成訂單隊列。在下位作業(yè)系統(tǒng)未發(fā)送申請消息之前，上位信息系統(tǒng)處在B4狀態(tài)。

步驟4，如上位信息系統(tǒng)當前狀態(tài)為B3，且下位作業(yè)系統(tǒng)發(fā)來條件不滿足消息、故障消息、停機消息，則上位信息系統(tǒng)轉入狀態(tài)B5，掛起當前已發(fā)送的訂單副本，并開始計時。

步驟5，如上位信息系統(tǒng)當前狀態(tài)為B5，且計時器已超過訂單副本時間標識上限，則上位信息系統(tǒng)取消已發(fā)送的訂單副本，并將訂單副本歸位到等待訂單隊列隊尾。處理完畢后，上位信息系統(tǒng)置當前狀態(tài)為B2，回到步驟2。

步驟6，如上位信息系統(tǒng)當前狀態(tài)為B5，且收到下位作業(yè)系統(tǒng)的條件滿足消息、故障排除消息、重啟消息后，則上位信息系統(tǒng)置當前狀態(tài)為B3，重新發(fā)送已發(fā)送訂單副本。

步驟7，如上位信息系統(tǒng)當前狀態(tài)為B4，如接受到下位作業(yè)系統(tǒng)的申請消息，則上位信息系統(tǒng)置當前狀態(tài)為B3，從等待訂單隊列中取出下一訂單副本發(fā)送。如未接受到下位作業(yè)系統(tǒng)消息，或接受到下位作業(yè)系統(tǒng)的條件不滿足消息、故障消息、停機消息，則維持當前狀態(tài)不變。

步驟8，回到步驟1，直到等待訂單隊列為空，或已到工作時間上限，上位信息系統(tǒng)關閉偵聽端口。

3 基于STPN的通信機制仿真

假設存在一個五元組{ti,pi,bi,ki,mi}，其中ti表示分揀作業(yè)系統(tǒng)的狀態(tài)變遷條件集合，pi為分揀作業(yè)系統(tǒng)的狀態(tài)庫所集合。bi表示上位信息系統(tǒng)的狀態(tài)庫所集合，ki為上位信息系統(tǒng)的狀態(tài)變遷條件集合。mi為上位信息系統(tǒng)和下位作業(yè)系統(tǒng)所構成的整體系統(tǒng)的全部狀態(tài)集合。根據(jù)圖1和圖2中有窮自動狀態(tài)機的結構，可以采用隨機事件Petri net構建整體系統(tǒng)的仿真模型如下。

圖3 基于STPN的上位信息系統(tǒng)與作業(yè)系統(tǒng)通信機制

圖3為采用STPN建立的通信機制仿真模型，模型參數(shù)選取為如下形式。仿真周期為1000個周期，設下位作業(yè)系統(tǒng)和上位信息系統(tǒng)的工作節(jié)拍均為1個節(jié)拍。上位信息系統(tǒng)掛起10個周期后返回初始狀態(tài)，上位信息系統(tǒng)故障后5個周期后重新啟動返回初始狀態(tài)。下位作業(yè)系統(tǒng)條件不滿后10個周期返回初始狀態(tài)，或5個周期后條件滿足返回工作狀態(tài)。下位作業(yè)系統(tǒng)在停機檢修狀態(tài)20個周期后返回初始狀態(tài)。

在1000個仿真周期中，上位信息系統(tǒng)共有783個周期內處在工作狀態(tài)，下位作業(yè)系統(tǒng)共有744個周期內處在工作狀態(tài)。使用率較我們在實際當中對白沙物流長沙站的平均觀察數(shù)據(jù)高9%。在仿真過程中，未發(fā)現(xiàn)有令牌死鎖情況，表明通信機制具有一致性和各狀態(tài)可達性，證明基于狀態(tài)機構建的通信機制具有可行性。但在沖突檢測中表明，下位作業(yè)系統(tǒng)存在工作狀態(tài)和故障狀態(tài)之間的爭用問題，因而導致上位信息系統(tǒng)存在工作狀態(tài)和掛起狀態(tài)之間的爭用問題，需要進一步設計機制解決令牌爭用問題，避免可能存在的令牌無效循環(huán)。

4 結論

消費時代加快了包裝的發(fā)展和通過型配送中心的產生，對分揀作業(yè)提出了高速度、低成本、大批量、多種類、多目的地的特殊要求。以往的研究方式以改進分揀設備，提高分揀性能為主。區(qū)別于以往的研究，以分揀系統(tǒng)與上位信息系統(tǒng)之間的通信機制為研究對象，建立了通訊過程的有窮自動機。在建模過程中，考慮了上位信息系統(tǒng)和下位作業(yè)系統(tǒng)可能存在的異常狀態(tài)，如掛起狀態(tài)、停機狀態(tài)、條件不具備狀態(tài)等。采用STPN工具，將分別建立的有窮自動機組成算例仿真。仿真結果證明采用有窮自動機建模，STPN仿真的方式能夠有效描述通信機制，并能在仿真中檢驗通信機制的可達性和一致性，能夠判斷通信機制的效率。但在不同狀態(tài)之間還存在令牌爭用，不能避免令牌的無效循環(huán)，因而需進一步設計新的通信機制以避免該問題。

[1]李哲峰.智能控制分揀系統(tǒng)的研制[J],現(xiàn)代制造工程,2001,11.

[2]朱錚濤.基于計算機控制的自動分揀智能系統(tǒng)設計[J].組合機床與自動化加工技術,2001,03.

[3]楊庚.分揀系統(tǒng)的軟件結構與應用研究[J].計算機應用研究,2003,05.

[4]張君.基于RS-485及UDP的郵包自動分揀與郵單自動生成系統(tǒng)的設計——條碼掃描儀與原分揀控制系統(tǒng)的連接[J].計算機應用與軟件,2003,07.

[5]田景賀.基于RFID的煙草物流分揀系統(tǒng)設計[J].儀器儀表學報,2006.

[6]謝偉東.條煙自動分揀的異步法及其裝置[J].工程設儀儀學報,2007,02.

[7]張貽弓.可合流的自動分揀系統(tǒng)訂單排序優(yōu)化[J],山東大學學報(工學版),2008,05 .

[8]張貽弓.卷煙分揀設備選型與優(yōu)化[J].物流技術與應用,2008,09.

[9]李豐.基于虛擬空間的煙草自動分揀算法的分析[J].物流科技,2009,01.

[10]李歧強.基于受控計時擴展Petri網的分揀系統(tǒng)建模[J].計算機仿真,2001,05.

[11]黃銀娣.基于Petri網的物流分揀系統(tǒng)的建模與仿真[J],物流技術,2006,03,

[12]李暄.Flexsim系統(tǒng)仿真軟件在配送中心分揀系統(tǒng)設計的應用[J],物流工程與管理,2009,01.