劉貴軍

（廣東工業(yè)大學廣東省計算機集成制造系統(tǒng)重點實驗室，廣東廣州 510006）

0 引言

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

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

1 問題描述

1.1 問題描述

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

圖1 分揀系統(tǒng)概念圖

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

1.2 數學模型

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

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

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

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

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

概率結構：

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

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

設S為狀態(tài)空間。當系統(tǒng)在時刻tk∈T處于任意狀態(tài)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]。與四類狀態(tài)相對應的四類決策集合分類列如表1所示。

表1 狀態(tài)相對應的決策集合分類列表

回報與成本函數：

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

決策規(guī)則與策略：

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

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

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

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

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

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

2 仿真模型的建立

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

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

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

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

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

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

圖2 分揀單元仿真模型

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

3 實例與結果分析

3.1 四種備選調度規(guī)則

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

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

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

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

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

3.2 其他的仿真實驗因素

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

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

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

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

3.3 仿真實驗設計

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

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

表2 包裝要求對應關系表

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

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

3.4 仿真實例結果及分析

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

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

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

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

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

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

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

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

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

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

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

5 結束語

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