一種板材自動分揀系統的出入庫調度規則研究

劉貴軍

（廣東工業大學廣東省計算機集成制造系統重點實驗室，廣東廣州 510006）

0 引言

分揀是配送的一種特殊功能要素，要求按規則將物品分門別類存放甚至按某種順序輸送，是倉儲中勞動密集度最高成本最高的活動[1]。隨著自動化技術的發展，RFID、二維碼等技術也開始在訂單分揀中得到應用[2]，對于自動化分揀的研究也逐漸深入[3]，國內自動化分揀最先在煙草、軍工、醫藥等行業得到應用，對于分揀的研究應用也多涉及快遞、煙草行業[4]。近年來隨著“工業4.0”、“中國制造2025”概念的興起以及家居定制化的熱潮，又因為家居板材人工分揀勞動強度高，交貨周期長且易出錯的特點，一些家居企業也開始尋求自動高效的分揀方式[5]，來實現轉型升級從而提高自身市場競爭能力。國內對于定制型家具板材的生產一般采用多訂單合并統一排版下料，再細化到以板為基礎的零部件進行加工，以工藝路線為導向。排版下料后依次是開料、封邊、排孔、打膠粒清洗。這導致后期需按訂單、按包裝找齊板材再打包，即增加了分揀這個打包前的準備環節[6]，使得工作量劇增。

目前國內對于家居板材自動分揀的實際應用還較少，本文作者對一種概念型家居板材自動分揀系統的解決方案提出單元化分揀的思想，并對單元層調度規則進行探索研究。

1 問題描述

1.1 問題描述

分揀系統采用滾筒線、機械手、立體倉庫，輔以識別與控制技術實現分揀（圖1）。通常，采用這種分揀方法，分揀環節的布局、需要配置的機械手和立體書架因廠家的上游生產產能、可用空間、生產安排而異。因板材的尺寸差異大，為有效利用空間，庫位的尺寸也會有多種，庫位只能容納相對更小的板材。將一個機械手與配套的立體倉庫、輸送線、輔助裝置視為一個單元，信息層由單元管理器管理。進入分揀系統的板材會被掃碼傳感器與光眼傳感器定位到大概位置并記錄。該暫存在哪個單元由上層中央控制器的調度策略決定。而不是簡單地均勻依次分配到各單元，當板材進入到單元時觸發對該單元的入庫任務，當中央處理器檢測到分揀系統中有訂單配齊時會向含有該訂單板件的單元下達出庫任務。入庫與出庫任務執行順序由單元層調度規則確定。出庫后的板材被送到出庫的滾筒線上，最終經滾筒線在匯合處調整順序被輸送到特定的打包工位。

圖1 分揀系統概念圖

根據分揀解決方案結合分揀的實際要求可知，該類型的分揀系統單元，入庫任務（記為A任務）單個產生，具有隨機性，出庫任務（以下記為B任務）多個同時產生，產生的間隔與產生的數量具有隨機性。為了使B類任務從產生到被處理完的平均時間盡可能短即出庫效率盡可能高，同時保證A類任務能順利進入單元。顯然，直接采取出庫優先，A類任務可能在極其有限的輸送線緩存區發生堵塞，導致無法接受到新的入庫任務，降低該單元的利用率；直接采取入庫優先的策略，會使得到齊的板件在各個單元中滯留無法被及時處理，導致出庫效率低，產品部件在分揀系統中的周期延長。所以單元層應采用某種調度規則使得出入庫優先級配置合理，配齊后快速輸送至打包區，是本文作者的研究目標。

1.2 數學模型

采用數學方法描述板材分揀單元出入庫過程，是一種可稱為半馬爾可夫決策過程(Semi-Markov Decision Pro?cess，SMDP)的模型。為了說明這個模型，先介紹馬爾可夫決策過程(MDP)[7-8]。

馬爾可夫決策過程(MDP)：

設S為狀態空間。當系統在時刻tk∈T處于任意狀態s∈S時，行動集合為As。在時刻t，狀態s下，采取了行動為a，得到的回報或代價為rt(s,a)，該值必須在選擇決策a之前已知，且不受未來決策的影響。當系統狀態發生改變時（有多種可能的結果），狀態轉移的概率記為pt(·│s,a)。如果在時刻t+1時，系統狀態發生了改變，預期的回報為rt+1(s,a)=，其中pt(j│s,a)為在時刻t+1時，系統的狀態為 j∈S的條件（在時刻為t時，系統的狀態為s，采取的行動為a）概率。且有：。所有的狀態轉移概率構成一個矩陣，列出任意狀態i轉移到任意狀態j的條件概率，稱為狀態轉移矩陣。這樣的一組要素所組成的數學結構是{T,S,As,pt(·│s,a),rt(s,a)}。

半馬爾可夫決策過程(Semi-Markov Decision Process，SMDP)：

SMDP中，時間是連續型隨機變量，狀態是離散型隨機向量。SMDP與MDP的差異就在于，不是每個系統狀態發生改變的時刻都可以去決策，只是在部分系統狀態發生改變的時刻才可以進行決策。

概率結構：

針對面臨的問題，狀態在時刻tk改變（有A任務到達；有B任務到達；上一個任務剛完成）。系統狀態向量：等待中的A任務數量NA，等待中的B任務數量NB。狀態轉移矩陣為，到達一個A任務的概率，同時到達i個B任務的概率p[i]，i=1,…,M，p[1]+...+p[M]=1。決策時刻：前一個任務執行完畢的時刻（執行該任務的時間段tk+1-tk為隨機變量F(t│s,a)，當執行A任務時是一個給定的分布，當執行B任務時是另一個給定的分布）；或者機器人處在等待狀態時，系統狀態發生變化的時刻（即有新的A任務到達，或者有新的B任務下達）。由于任務執行過程的不可中斷性，在每個任務執行過程中不能再采取決策，在此期間系統的狀態變化對決策者而言也不必知道。但是在計算等待時間這樣的優化目標時，系統的狀態變化過程就需要確切地知道。在當前決策（采取了行動a）的時刻tk之后，經過時間t，系統的狀態由s自然變成j的概率記為p(j│t,s,a)，注意，下一個決策時刻tk+1很可能晚于時刻t，即t＜ tk+1，tk+1取決于分布F(t│s,a)，轉移概率p(j│t,s,a)是用來計算每個決策階段中的累積回報量或累積支出的成本。如果在該決策階段系統的狀態沒有發生變化的話，p(s│t,s,a)=1，0≤t≤tk+1。為了避免在有限長的時間內產生無限多次決策，對決策時間間隔的分布F(t│s,a)做以下的假設：

假設2.1：存在一個ε＞0和δ＞0，使得：F(δ│s,a)≤1-ε對所有的s∈ S和a∈ As都成立。

假設系統在時刻tk時狀態為s，并且采取了行動a，到了決策時刻tk+1時狀態為j，相應的概率可以記為Q(tk+1,j│s,a)。但是由于模型的復雜性，這一概率難以采用A任務到達概率、B任務到達概率以及執行A任務或B任務的持續時間概率分布的顯式表達式表述。

設S為狀態空間。當系統在時刻tk∈T處于任意狀態s∈S時，行動集合為As。這里包括4種類型： As0={W}，s0=[0,0]； AsA={A}，sA=[NA,0]（沒有等待中的B任務）； AsB={B}，sB=[0,NB]（沒有等待中的A任務）；As={A,B}，s=[NA,NB]。與四類狀態相對應的四類決策集合分類列如表1所示。

表1 狀態相對應的決策集合分類列表

回報與成本函數：

在面臨的問題中，將B任務在分揀庫中的平均處理時間作為系統的成本。該成本不僅與以前的決策有關，而且與上個決策至下個決策之間的時段內系統的狀態變化有關。

決策規則與策略：

d表示決策規則，DK表示決策規則類。D則專門用來表示確定性的MDP策規則類。π表示任意一個特定的策略，就是一個特定的決策規則序列，即：π=[d1,d2,…,]，π∈ΠK為一個策略類。對于一個特定的確定性MDP決策規則 d，定義 pd(j│t,s)=p(j│t,s,d(s))，Fd(t│s)=F(t│s,d(s))，Qd(t,j│s)=Q(t,j│s,d(s))，kd(s)=k(s,d(s))為決策者在狀態s，并采取決策d(s)后一段時間內的累計回報值。

定義 坐 標 隨 機 變 量 ：Xn(ω)=sn∈S ，Yn(ω)=an∈A ，τn(ω)=tn∈T，其中ω表示隨機元。在時刻t，自然過程的狀態是Wt。在第n個決策點至第n+1個決策點之間的決策執行時段內，瞬時回報速率記為c(Wt,Xn,Yn)。

經過時間(elapsed time)過程σn(ω)：，注意：。

在第一個決策時刻，系統的狀態為s時，定義N個時段累計期望回報值(s)為：

在上述中，σ0，σ1，…表示后續的決策時間時刻，第一項對應著成本的累積和，第二項對應著第n個決策點至第n+1個決策點之間的決策執行區間中，動態成本率c(Wt,Xn,Yn)在該時間段上的累積效應。

由于最優決策規則序列難以獲得，在實際應用中，往往采取近似求解規則求解該數學模型。這里，本文作者提出4種常規規則，并通過仿真比較這些規則與策略之間的相對優劣。

2 仿真模型的建立

結合實際情況，為研究不同出入庫調度方法在不同場景下的應用效果并比較優劣，忽略其他無關的具體物理仿真細節，對模型做一定的簡化抽象，搭建基于Tecnomatix Plant Simulation 12(eM-Plant)仿真軟件的仿真模型，如圖2所示，給出仿真模型的假設條件如下：

假設1：考慮兩種任務輸入系統，A類任務到達的時間間隔服從均值為λ1的負指數分布。B類任務到達的指令間隔服從均值為λ2的負指數分布，一個指令中包含的任務數量是某范圍內的隨機整數，長時間內單元中A類任務與B類任務產生的數量期望值相等。

假設2：A類任務的單元內緩存區長度為4，滾筒線輸送能力相對機械手處理能力足夠，A類任務具有長度屬性值，單元內緩存區不能容納屬性值之和超過自身長度的A類任務。

假設3：A類任務的長度屬性隨機且符合某廠多年來的歷史統計數據的概率分布。

假設4：未配齊的板件無法被處理，不記為任務，立體倉庫的容量足夠容納這些板件。

假設5：機械手處理一個任務的時間為 ρ，假設服從正態分布（有上下界約束），執行任務不可中斷。

圖2 分揀單元仿真模型

這里值得注意的是Bag_Source表示訂單或包配齊后下達一次出庫指令，Source在出庫指令下達后同時產生隨機數量的B類任務，存放在緩存區B2中待處理。

3 實例與結果分析

3.1 四種備選調度規則

（1）入庫優先：機械手空閑或剛完成一個任務后優先檢測是否有入庫任務，有入庫任務時，先處理入庫任務，無入庫任務時才檢測是否有出庫任務，有出庫任務則執行一個出庫任務。

（2）出庫優先：機械手空閑或剛完成一個任務后優先檢測是否有出庫任務，有出庫任務時，先處理出庫任務，無出庫任務時才檢測是否有入庫任務，有入庫任務則執行一個入庫任務。

（3）輪流優先：如果機械手剛處理完的是入庫，采用入庫優先的規則。如果機械手剛處理完的是出庫，則采用一次出庫優先規則。

（4）參考警戒線優先：給入庫緩存區設置警戒線系數（取值范圍0～1），如果緩存被占用量達到警戒線水平（滾筒緩存區的長度*警戒線系數），機械手采用入庫優先的規則。如果未達到警戒線則采用出庫優先規則。

以上4種調度規則對應著實驗中自變量?的4種水平值（1，2，3，4），其中機械手在無任務時保持等待狀態，等待狀態采用先到先服務的規則。

3.2 其他的仿真實驗因素

（1）輔助實驗因素一：板材的尺寸屬性

因為超大板材所占的比例極小，且容易區別于其他板材，在實際操作時就直接將其輸送至包裝區，無需自動分揀，這樣可降低分揀硬件的設計性能要求。因此，是否剔除超大板材，對應著仿真實驗中兩種板材尺寸隨機分布形式α兩種的水平值（1,2）。

（2）輔助實驗因素二：板材的包裝屬性

根據工廠的實際包裝需求差異，既要求一個訂單（產品）的板件都在立體倉庫中配齊后才輸送至包裝區，又要求一個包的板件在立體倉庫中配齊后即可出庫。兩種板材的包裝屬性分別對應著仿真實驗中包裝要求 β兩種水平的值（1，2）。

3.3 仿真實驗設計

設定A類任務到達相互獨立且服從均值為λ=21的負指數 分布，緩存滾筒線長度為4 m，機械手處理一個入庫任務所需時間為7.5～13 s，服從均值為10.5，方差為1.5的有邊界約束的正態分布。處理一個出庫任務所需時間為7～12.5 s，服從均值為9.5，方差為1.5的有邊界約束的正態分布。

從實驗設計的三要素：調度規則、板件的尺寸屬性、板材的包裝屬性來看，這里3個實驗因素的不同水平的全部搭配方式共有4×2×2=16種，即16個仿真場景，在任務拒絕率小于預設值2%的前提下，比較平均出庫任務時間（主要評價指標）。此外，還有一些其他的評價指標，如拒絕率（次要指標）、最大庫容占用量（參考指標）、機械手的利用率（參考指標）等。其中包裝要求對應關系如表2所示。

表2 包裝要求對應關系表

系統的評價指標是B任務平均處理時間AveTime，A任務拒絕率RejectRate。其他參考指標有：B任務最大堆積量（MaxVB），機械手利用率（RobotUtiRate）。

針對所有因素的16種組合情形分別進行實驗，并比較實驗結果。因為任務到達、任務屬性、機械手處理速率都是隨機分布，為了得到可靠的描述仿真實驗的結果，對每組實驗仿真時間設置為1 000天，且每組實驗重復10次。在顯著性水平小于0.05的情況下，基于大樣本統計學原理，認為從仿真實驗數據統計獲得的系統評價指標的統計結果是可靠的。

3.4 仿真實例結果及分析

在使用警戒線調度規則（調度規則4）時，首先需要確定警戒系數。由表3可知，從部分仿真實驗的結果看，警戒系數設定為0.34較為合理，因為在滿足約束條件的情況下，警戒系數為0.34導致系統B類任務的平均處理時間較短（主要性能指標較好）。警戒系數過大，導致A類任務的拒絕率（次要性能指標）超過預設的比例要求，所以不能接受。

表3 警戒系數多級實驗結果

多種因素的水平值組合，如111，表示調度方法參數?=1，隨機尺寸分布參數α=1，包裝要求參數 β=1。即采用入庫優先，不剔除超大板，按訂單包裝的實驗。為方便直觀地比較調度方法與應用場景的影響，將主要約束與目標的相關數據繪制在圖3、4中。圖3中剔除了調度規則2的繪制，因其拒絕率高達7%～13%，顯然不符合要求。

圖3 各因素對拒絕率的影響

圖4 各因素對B類任務平均處理時間的影響

根據圖3、4對實驗數據進行比較，其中橫坐標表示應用場景，后綴兩位數字分別對應隨機尺寸分布參數α，包裝要求參數 β的水平值。如RejectRate11表示α=1，β=1，即不剔除超大板、按訂單出庫的應用場景。同一線條上的點表示同一種調度方法，對應?的一個水平值。

對以上的實驗結果進行分析，初步得到以下幾點結論：

（1）橫向依次比較調度方法與包裝要求相同的情況下，比較任務尺寸屬性不同的情況下（α=1，與α=2）的仿真系統輸出結果?？芍蕹蟀逵欣诮档虯類任務的拒絕率，但對B類任務的平均處理時長無明顯影響。

（2）同理比較，調度方法相同，任務尺寸屬性相同情況下，包裝要求對系統指標的影響?？芍窗鰩煊欣跍p少B類任務平均處理時間，而對A類任務的拒絕率無明顯影響。

（3）縱向依次比較，同種應用場景（即任務尺寸屬性，處理要求相同的情況下），調度規則對兩者都有一定影響。從入庫優先，輪流優先，參考警戒線優先，出庫優先。拒絕率逐漸提高，而B類任務平均處理時間逐漸減少。

綜上可知，在滾筒緩存區容量有限的情況下，剔除超大板或提高入庫優先程度，有利于降低入庫任務的拒絕率；按包出庫或提高出庫的優先程度，有利于減少出庫任務在系統中的滯留時間。在實際應用中，一般應用場景（就是說板材的尺寸屬性與包裝屬性）都已經確定，只有通過調整調度規則來使其滿足A類任務的拒絕率約束，同時使得B類任務的平均處理時間盡量短。而參考警戒系數這類方法，可以通過調整警戒系數來“恰好”滿足約束條件。警戒系數越大，出庫優先程度越高，警戒系數最大為1時，即出庫優先；警戒系數越小，則入庫優先程度越高，警戒系數最小為0時，即入庫優先。因此調整警戒系數，可以在滿足一定的約束條件下，盡可能獲得出庫優先，提高系統的主要性能指標。這樣有利于減少出庫任務在系統中的平均滯留時間，提高出庫打包的效率。

5 結束語

針對某公司家具板材分揀系統的出入庫調度問題，建立數學模型，并提出4種近似求解策略（調度規則）。為將所提出的方案應用于實際，將實際應用場景的因素映射為仿真系統的參數與變量，將調度規則用程序邏輯表示。在此基礎上，建立系統的仿真模型，進行大量的系統仿真實驗，統計仿真數據獲得系統的性能指標來分析比較不同的應用場景、不同的調度規則對板材出入庫性能的影響。通過仿真實驗，發現板材的尺寸屬性和包裝屬性不影響4種不同的調度規則之間的相對優劣，而采用警戒系數的調度規則，可以在滿足一定的約束條件下，盡可能使得出庫優先，提高系統的主要性能指標。這樣有利于減少出庫任務在系統中的平均滯留時間，提高出庫輸送至打包區的效率。因此該調度策略可靈活調整任務的優先程度來配置兩類任務的優先級，使得系統在滿足入庫任務拒絕率不超過預設的約束條件下，出庫任務總的平均處理時間縮短。