基于規則學習的差異工件隨機批調度策略

楊子豪，譚 琦，夏田林，戴 飛

（合肥工業大學 電氣與自動化工程學院，合肥 230009）

0 引言

批處理機是一類在滿足約束的前提下可以同時處理多個工件的設備，目前已廣泛應用于制造業中，例如金屬加工、半導體生產、紡織品染整作業等相關領域[1]。同時批處理問題也引起了眾多學者的關注。Dupont等[2]研究了一類差異工件單機批調度問題，提出了兩種啟發式算法SKP（Successive Knapsack Problem）和BFLPT（Best-Fit Longest Processing Time）。Chen等[3]對于單機批調度問題，提出浪費比的概念，并以此為基礎定義了批間距離度量，設計了一種分批約束聚類算法。Li等[4]針對不相容工件族的批調度問題設計了啟發式算法來優化系統的最大延期時間。

在實際的制造系統中，加工制造過程存在很多不確定的隨機因素，例如上游系統故障，加工訂單隨機到達等。調度過程中的隨機事件往往使得原有靜態調度方法具有不可預測性，無法達到理想效果。因此，考慮隨機因素的調度模型是一種更貼近實際加工環境的調度模型。隨機調度問題近年來引起眾多學者的關注，然而基于隨機批調度問題的研究目前還不多。Germs等[5]使用馬爾科夫決策過程對一類訂單隨機到達的單機調度問題進行了研究，給出了最佳訂單接受策略和批調度方案。Duenyas等[6]研究了不相容工件族隨機到達的批調度問題，提出了一種啟發式算法對平均單位時間成本進行優化。John等[7]利用動態規劃的方法對工件到達時間隨機的相容工件族批調度問題的進行求解，并給出一種啟發式算法。上述研究僅僅考慮工件尺寸相同的情況，然而實際生產中工件尺寸的差異是必然存在的，這使得隨機批調度問題更加復雜。本文考慮差異工件隨機到達下的單機批調度問題，由于尺寸的差異，加工系統會不可避免的出現機器加工資源浪費的情況，同時工件成批的組合方式也更多，問題規模急劇增加。因此，如何在這種情況下合理調度隨機到達的工件使加工率最大是本文的研究重點。

在實際生產調度中，由于啟發式規則簡單、易于實施從而得到了廣泛的應用。但是，這些規則一般只用于特定調度環境，并不具備隨著環境改變而變化的優化能力[8]，無法滿足復雜問題的需求。

相比之下，強化學習在動態環境中有較好的優化能力，它能賦予系統一定的學習性，使系統能夠根據當前環境（即生產環境）的性能反饋修正系統在動態過程中采取的行動，從而適應生產環境的變化。強化學習是一種重要的機器學習方法，由于它良好的自適應性，使其在實際中的應用也越來越廣泛[9]。Shahrabi等[10]使用強化學習的方法解決作業車間工件隨機到達的問題。Chen等[11]針對動態環境下汽車配裝線的物料運輸問題，利用強化學習中的Q學習對問題進行求解。Ou等[12]利用Q學習方法解決了一類利用龍門架裝卸物料的調度問題，給出了最優龍門架移動策略。

盡管強化學習方法有較好的優化性能，但是當系統狀態總數增多或可選行動集合變大時，算法的搜索空間將急速增長，這會大幅降低算法的優化能力。基于此，在綜合考慮優化性能和計算效率的情況下，本文將啟發式規則與強化學習相結合，在底層利用啟發式規則直接調度系統加工，在上層使用強化學習方法為系統的每個狀態搜索合理的規則。這樣即避免了算法搜索空間過大，也避免了人工指定規則的主觀性。

本文以提升系統加工率為目標，考慮有尺寸差異工件隨機到達的批處理機調度問題。在分析問題模型的基礎上，設計出兩類啟發式規則，并將其與Q學習相結合提出基于Q學習的啟發式選擇調度算法（Heuristic Q-learning HQ）。最后通過仿真實驗將所提算法與原有算法進行對比，驗證了所提算法的有效性。

1 系統模型

1.1 問題描述和假設

本文研究的隨機批處理問題的系統模型如圖1所示，系統的主體是一臺容量為C的批處理機，可以一次加工尺寸之和不超過其容量的多個工件。系統配備具有傳感器的分揀裝置可以感知到達工件的類型，并配備m個容量為N的緩沖庫用來存放不同品種的工件。

圖1 差異工件隨機到達下批處理系統示意圖

各類工件不斷地隨機到達當前站點，ti和di分別表示第i類工件的加工時間和尺寸，分揀裝置將到達的工件放入相應的緩沖庫中等待加工。由于工件隨機到達，系統需要實時的進行調度決策。系統的工作過程可概括為:在決策時刻，系統根據當前緩沖庫狀態選擇加工一批工件或等待后續工件到達。當選擇加工時，系統從緩沖庫中選取一批工件放入批處理機中加工。當選擇等待時，批處理機處于空閑狀態，直到有后續工件到達系統。由于緩沖庫容量有限，如果工件到達系統時，存放該類工件的緩沖庫已滿，則該工件流失。本文要解決的關鍵問題就是在決策時刻如何合理調度機器，減少系統生產代價，避免工件流失從而提高系統加工率。

為了有效描述該問題，同時做出如下假設：

1）每類工件按照泊松隨機過程到達生產系統。

2）在滿足容量約束的前提下，機器每次可加工由任意工件構成的批。

3）機器加工時間等于加工批中所有工件加工時間的最大值。

4）機器一旦開始加工則不允許中斷。

1.2 決策過程

記ni為第i類工件在緩存庫中的個數，也表示第i類工件在系統中的狀態，其狀態空間為Φi={0,1,...,N}，系統狀態即為m類工件緩沖庫容量所組成的聯合狀態，sn1,n2,...nm=｛n1,n2,...nm｝。在控制策略的作用下，系統從決策時刻T0=0開始工作，在第k個決策時刻Tk時，假設當前狀態為sn1,n2,...nm，系統根據當前調度策略采取的行動為vsn1,n2,...nm。若此時vsn1,n2,...nm為等待，則機器閑置并等待下一工件到達，記下一個工件的到達時間為ωk，則系統下一決策時刻為Tk+1=Tk+ωk，若到達的工件為第i類工件，下一決策時刻的系統狀態即為Sn'1,n'2,...,n'i,...nm，其中n'i=min{ni+1,N}。若vsn1,n2,...nm為加工一批工件，則系統從緩沖庫中選出其指定的工件進行加工，記加工時間為τk，則系統的下一個決策時刻為Tk+1=Tk+τk，下一決策時刻的狀態為Sn'1,n'2,...,n'm，其中n'i=ni-ai+bi，ai和bi分別表示本次決策時刻內第i類工件的加工個數和隨機到達并存儲的個數。

1.3 優化目標

本文的調度目標是提高系統加工效率減少生產代價。由于問題中各種類工件間存在著尺寸的不同，若用一定時間內加工的工件個數來衡量系統加工率顯然是不合理的，因此借鑒文獻[3]中的方法，引入工件量的概念對各類工件進行統一度量，一個工件的工件量等于其尺寸與加工時間的乘積。因此定義系統的加工率如下

其中，Gprocess（T）和Garrive（T）分別表示在0到T時刻內加工的總工件量和到達系統的總工件量。

當系統穩定運行時，到達系統的工件要么被系統存儲加工要么因緩沖庫滿而流失。因此，系統的工件量流失是優化的重要目標。另外從短期效益來看，提高加工時的機器利用率也能一定程度上提升加工率，同時在實際生產系統中也需要考慮少量的庫存管理成本。因此，系統代價被定義為：工件量存儲代價、工件量流失代價和機器浪費代價。其中在第k個決策周期內，將機器浪費代價定義為：

2 HQ調度算法

2.1 算法概述

由系統工作模式可知，批處理機的調度過程是由時間軸上一系列的決策所組成，系統需要在隨機環境中不斷的做出決策，因此可引入強化學習中的Q學習方法進行求解。考慮到本文提出的問題規模較大，所需算法不僅要有對隨機系統較好的全局優化能力，而且要具備較高的計算效率。在本文中，只要滿足批處理機容量約束的前提，任意組合方式形成的工件批都可以被系統作為動作進行加工。當批處理機容量較大或工件類型增多時，這種排列組合方式定義的可選動作將會非常多，Q學習的動作空間將急劇增加。這會導致算法的搜索空間激增，使得計算效率大幅降低。因此，本文在分析系統特性的基礎上，設計出兩類啟發式規則作為Q學習行動來取代傳統直接選取工件組合的行動，以提升算法的計算效率。同時，引入模擬退火搜索機制，提高算法的搜索能力。

2.2 啟發式規則設計

本文設計的啟發式規則分為兩類:對緩沖庫中所有工件完全分批后挑選特定批的選擇式啟發式規則和以基準工件構造成批的構建式啟發式規則。系統在決策時刻選擇某啟發式規則作為行動，機器再根據該啟發式規則調度工件進行加工。

1) 選擇式啟發式規則從全局角度考慮，對當前緩沖庫中所有工件進行分批，然后再從分好的批中基于目標準則選取待加工批。因此，該類啟發式規則優先考慮所有工件分批的優劣，使每個批盡可能的高效利用機器加工能力，在此基礎上再考慮調度目標。在進行分批時，首先對緩存庫中所有工件進行排序，排序方法按照工件加工時間由高到低。排序完成后，對序列利用Best-Fit方法進行分批，然后采用不同的選批規則從所有批中選一批工件進行加工。各選擇式啟發式規則的選批標準如下：

SPT-LPR（shortest processing time-largest proce-ssing rate，最短加工時間-最大加工率）規則

選擇所有批中加工時間最短的批進行加工，若有多個批同時滿足，則選擇其中加工率最大的批進行加工，其中，加工率等于加工工件量與加工時間的比值。

LCW-SPT（least capacity waste-shortest processing time，最小加工能力浪費-最短加工時間）規則

選擇所有批中機器加工能力浪費最小的批進行加工，若有多個批同時滿足，則選擇其中加工時間最短的批進行加工。

FB-LPR（fullest buffer-largest processing rate，緩存庫存量最滿-加工率最大）規則

選擇所有批中含最滿庫存工件個數最多的批進行加工，若有多個批同時滿足，則選擇其中加工率最大的批進行加工。

LQ-SPT（largest quantity-shortest processing time，最大工件量-最短加工時間）規則

選擇所有批中所含工件量最大的批進行加工，若有多個批同時滿足，則選擇其中加工時間最短的批進行加工。

2) 構建式啟發式規則優先考慮要優化的目標，在緩存庫中選擇最符合規則優化目標的工件構成批，在此基礎上再考慮該加工批的機器利用率的情況，并不考慮剩余工件的分批情況。各構建式啟發式規則具體實施步驟如下：

FB（fullest buffer，存量最滿）規則

Step1：在滿足批的容量約束的前提下，從當前存量最大的緩存庫中盡可能多的選取工件放入批中，若有多種工件的存量相同，則選擇尺寸較大的工件類型；

Step2：計算批中剩余容量，在尺寸小于剩余容量的工件類型中選擇存量最大的工件放入批中，重復該步驟直到沒有工件可以放入批中為止。

FB-CPT（fullest buffer-closest processing time，存量最滿-最相近加工時間）規則

Step1：在滿足批的容量約束的前提下，從當前存量最大的緩存庫中盡可能多的選取工件放入批中，若有多種工件的存量相同，則選尺寸較大的工件類型；

Step2：計算批中剩余容量，在尺寸小于剩余容量的工件類型中選擇加工時間與當前批加工時間絕對值差最小的工件放入批中，若絕對值差相同，優先選擇加工時間較小的工件，重復該步驟直到沒有工件可以放入批中為止。

LPT（longest processing time，最長加工時間）規則

Step1：在滿足批的容量約束的前提下，盡可能多的選擇加工時間最長的工件放入批中，若有多種工件的加工時間相同，則選擇存量最多的工件類型；

Step2：計算批中剩余容量，在尺寸小于剩余容量的工件類型中選擇加工時間最長的工件放入批中，重復該步驟直到沒有工件可以放入批中為止。

SPT（shortest processing time，最短加工時間）規則

Step1：在滿足批的容量約束的前提下，盡可能多的選擇加工時間最短的工件放入批中，若有多種工件的加工時間相同，則選擇存量最多的工件類型；

Step2：計算批中剩余容量，在尺寸小于剩余容量的工件類型中選擇加工時間最短的工件放入批中，重復該步驟直到沒有工件可以放入批中為止。

LSTR（largest size time rate，最大尺寸時間比率）規則

Step1：在滿足批的容量約束的前提下，盡可能多的選擇工件尺寸與加工時間比率最大的工件放入批中，若有多種工件比率相同，則選存量最多的工件類型；

Step2：計算批中剩余容量，在尺寸小于剩余容量的工件類型中選擇工件尺寸與時間比率最大的工件放入批中，重復該步驟直到沒有工件可以放入批中為止。

要注意的是，若多個啟發式規則在某系統狀態下選出的待加工工件相同，表明這些規則在該狀態下效果一致。為了避免行動冗余，應在Q學習選擇動作前，從這些狀態的行動集合中刪除多余規則。

2.3 基于性能勢的Q學習算法

Q學習的基本原理可概括為:決策主體與外界環境不斷地交互，進行自主學習，通過觀察系統狀態轉移信息（環境反饋）來迭代每個狀態-行動對的Q值，進而學得最優或近優策略[13]。第k個決策周期的狀態轉移信息可表示為＜Sk,vSk,Sk+1,ΔTk,f(Sk,vSk,Sk+1)＞，其中，ΔTk和f(Sk,vSk,Sk+1)分別為狀態的轉移時間和轉移所產生的代價。根據文獻[14]中性能勢的理論，平均準則下狀態-行動對的Q值更新公式為：

其中，γ（Sk,vsk）是Q值更新的學習步長，其隨著訪問次數增多而不斷衰減，ηTk是系統平均代價的估計值。

f（Sk,vsk,Sk+1）的計算公式如下，當系統選擇批處理機等待時，

當系統選擇批處理機加工一批工件時，

其中k1、k2和k3為存儲代價、流失代價和機器浪費代價的權重，Gl為在轉移過程中流失的工件量。AS為轉移過程中到達并存儲的工件個數，?j和Gj分別為第j個工件的到達時間和工件量。

2.4 算法步驟

為了更好的平衡Q學習探索和利用的問題，本文引入模擬退火的Metropolis準則代替傳統的貪婪策略（ε-greedy）來控制算法探索率。HQ調度算法具體實施步驟可概括如下。

Step1：初始化Q值表、每次迭代中學習步數Z，總迭代次數Y、模擬退火溫度Ttemp和退火系數t?temp。隨機初始化系統狀態，并令k=0，z=0，y=0。

Step2：根據當前狀態Sk，分別計算出所有選擇式和構建式啟發式規則所對應的加工批;

Step3：若有多種啟發式規則對應的加工批相同，則剔除多余相同的加工規則，由剩余規則組成該狀態下的可選行動集合；

Step4：根據Q值表得到當前狀態下的最優行動v*sk，即v*sk=argminQ（sk,v*sk），并從當前狀態的行動空間中隨機選取一個動作記為vrandsk。若exp{[Q（sk,v*sk）-Q（sk,vrandsk）/Ttemp]}＜rand(0,1)，則選擇最優動作v*sk作為當前行動，否則隨機選取一個行動vrandsk。

Step5：執行所選行動對應的啟發式規則，觀察狀態轉移信息并得到系統的下一狀態Sk+1，根據式(4)或(5)計算轉移代價并根據式(3)更新Q值表。令k=k+1，z=z+1。若z＜Z，則轉跳到step2。

Step6：令y=y+1，若y＜Y，則令z=0，ζtempTtemp，并返回step2，否則算法結束。

3 仿真實驗

實驗中，將本文所提HQ算法與Q學習在工件品種數為3、4和5的情況下進行對比。用服務強度的概念（Traffic Intensity，TI）來定義工件的到達率，其公式為TI=∑m

i=1λiditi/C，其中λi即為第i類工件的泊松到達率。在參考文獻[7]實驗設置的基礎之上，將品種數為3、4和5情況下的TI分別設置為0.85、0.95和0.95，其余系統參數設置如表1所示。由于品種數增多后，Q學習算法動作空間急劇增加，此時，為了保證傳統Q學習的算法效果，在實驗中加大Q學習的學習步數，雖然HQ可以避免該類問題，但為了確保實驗合理，HQ仍與Q學習使用相同數據，如表2所示。

表1 系統參數設置表

表2 Q學習參數設置表

本實驗由兩部分組成：第一部分析兩種方法的代價優化曲線和加工率優化曲線。第二部分對比在不同工件參數情況下HQ對于原Q學習算法的優化情況，驗證所提啟發式規則和HQ算法的有效性。

3.1 系統優化效果

Q學習和HQ每迭代一次，對當前學到的策略進行一輪評估，每輪評估利用當前學到的策略獨立仿真10次，每次仿真50萬步，取平均值作為當前策略對應的代價。仿真所用工件實例為d=(5,4,2)、(5,3,4,2)、(4,5,2,3,2)，t=(3,4,4)、(2,3,3,4)、(2,2,3,4,5)。在上述參數設置下，算法的系統代價優化曲線和加工率優化如圖2、圖3所示。

圖2 平均代價優化曲線

圖3 加工率優化曲線

如圖2所示，所有曲線在開始時急劇下降，這表明Q學習方法在前期使系統快速學習認知，并向最優或者近優方向調整動作。隨著迭代次數增加，曲線下降速度逐漸變慢，系統代價收斂并穩定。圖中表明，HQ算法要明顯好于原始Q學習算法。在三品種算例下，Q學習最終在0.2528左右收斂，而HQ得到的系統最終代價約為0.2284。當工件種類為四類時，算法差距逐漸明顯，HQ可將系統代價減小到0.6654左右，但Q學習最終收斂值只有1.0607左右。當品種增至五類時，若按照原有方法，系統共有22萬個狀態動作對等待更新，龐大的搜索空間和工件到達的隨機性，使得Q學習已經很難對系統進行深度優化，而HQ只需為系統狀態選擇合適的規則，底層由提前設計好的啟發式規則高效調度工件，這極大的提高了算法的優化效率。可以看出，HQ在剛開始就可以得到代價較小的調度策略，這是因為HQ所采用的動作是啟發式規則，它們都是根據系統特性進行設計的，都有較好的求解效果，隨著學習步數的不斷增加，HQ算法逐漸為系統的每個狀態找到適合的啟發式規則，使得系統代價逐步降低。

與圖2對應的系統加工率優化曲線如圖3所示，在三品種下，Q學習經過長時間的學習優化也可以得到與HQ相近的加工率，此時HQ的優勢主要體現在算法效率上。當工件種類增多后，算法差距開始明顯加大。四品種時，Q學習的加工率從最初的70%增加到最終的92%左右，相比之下，HQ在很短的迭代步數內就將系統加工率提升到95%附近。五品種時，過于龐大的搜索空間已經很難再讓Q學習對系統進一步優化，而HQ仍可以獲得較高的系統加工率。

3.2 不同工件參數設置下算法優化效果

實際生產中，針對不同生產線和不同訂單的需求，工件的尺寸和加工時間都會有所不同。下面主要驗證算法在工件參數變化時的性能，為了直觀展示算法改進效果，用GAP1和GAP2分別表示Q學習與HQ在系統代價和加工率上的差距。為了減少系統隨機性的影響，將兩種算法所學到的最終調度策略在每個算例上各運行50次，每次運行50萬步，取其結果的平均值作為算法在該算例上的結果。3、4、5品種下各算例結果如表3、表4和表5所示。

由表3可以看出，在三品種的問題規模下，Q學習與HQ算法的差距不是特別明顯，甚至在某些算例下，Q學習得到的結果要好于HQ。這是由于，首先在三品種規模下，按照傳統排列組合方式定義的系統行動數并不會太多，并且系統的狀態個數也較少，此時Q學習通過不斷的迭代優化去搜索解空間可以得到一個較好的結果。其次，本文提出的啟發式規則是針對一類問題進行設置的，其思想是在中大規模問題中可快速和簡便的對問題進行求解，這些規則并不會根據特定算例進行優化，因此在小規模情況下，Q學習確實有可能在整個的工件排列組合空間中找到比啟發式規則更好的策略，但上述情況很難在中大規模的算例中出現。從表4和表5的結果中可以看出，在問題規模擴大后，Q學習的優化效果開始明顯降低，HQ的優勢逐步體現出來。在四品種下，相比于Q學習，HQ最終使系統代價平均降低了53%，加工率平均上升4%，五品種時，HQ使加工率平均提升16%，并且兩種算法在系統代價上的平均差距已經達到兩倍以上。這充分表明了HQ算法和本文所設計啟發式規則的有效性。

表3 三品種不同工件參數下各算法優化效果

表4 四品種不同工件參數下各算法優化效果

表5 五品種不同工件參數下各算法優化效果

上述分析表明，Q學習雖然有良好的無模型尋優能力，但是在面對搜索空間過大的情況時，求解效率明顯降低，很容易陷入局部最優，在規模較大的問題下難以得到滿意的求解效果。而HQ采用Q學習和啟發式規則結合的方法，在底層根據系統特性設計高效的啟發式規則調度工件，從而避免Q學習直接搜索工件組合造成算法搜索空間過大的問題，在上層使用Q學習為每個狀態學得最優啟發式規則規則，這也充分利用了在隨機環境下Q學習的自主學習能力。HQ相當于結合了二者的優勢，在提高算法效率的同時也充分利用了Q學習在隨機環境下的學習能力。

4 結語

本文主要研究了具有尺寸差異工件隨機到達系統情況下批處理機的優化調度問題。在建立系統優化模型的基礎上，針對規模較大的情況，設計了兩類啟發式規則，并由此給出基于Q學習的啟發式選擇算法。實驗表明所提算法有良好的求解效果，并且問題規模越大效果越明顯。在后續研究中，可考慮諸如機器故障維護，加工時間不確定等更多的隨機因素。