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

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

0 引言

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

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

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

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

盡管強化學習方法有較好的優(yōu)化性能，但是當系統(tǒng)狀態(tài)總數(shù)增多或可選行動集合變大時，算法的搜索空間將急速增長，這會大幅降低算法的優(yōu)化能力?；诖?，在綜合考慮優(yōu)化性能和計算效率的情況下，本文將啟發(fā)式規(guī)則與強化學習相結(jié)合，在底層利用啟發(fā)式規(guī)則直接調(diào)度系統(tǒng)加工，在上層使用強化學習方法為系統(tǒng)的每個狀態(tài)搜索合理的規(guī)則。這樣即避免了算法搜索空間過大，也避免了人工指定規(guī)則的主觀性。

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

1 系統(tǒng)模型

1.1 問題描述和假設

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

圖1 差異工件隨機到達下批處理系統(tǒng)示意圖

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

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

1）每類工件按照泊松隨機過程到達生產(chǎn)系統(tǒng)。

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

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

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

1.2 決策過程

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

1.3 優(yōu)化目標

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

其中，Gprocess（T）和Garrive（T）分別表示在0到T時刻內(nèi)加工的總工件量和到達系統(tǒng)的總工件量。

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

2 HQ調(diào)度算法

2.1 算法概述

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

2.2 啟發(fā)式規(guī)則設計

本文設計的啟發(fā)式規(guī)則分為兩類:對緩沖庫中所有工件完全分批后挑選特定批的選擇式啟發(fā)式規(guī)則和以基準工件構(gòu)造成批的構(gòu)建式啟發(fā)式規(guī)則。系統(tǒng)在決策時刻選擇某啟發(fā)式規(guī)則作為行動，機器再根據(jù)該啟發(fā)式規(guī)則調(diào)度工件進行加工。

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

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

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

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

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

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

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

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

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

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

FB（fullest buffer，存量最滿）規(guī)則

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

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

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

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

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

LPT（longest processing time，最長加工時間）規(guī)則

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

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

SPT（shortest processing time，最短加工時間）規(guī)則

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

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

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

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

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

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

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

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

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

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

當系統(tǒng)選擇批處理機加工一批工件時，

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

2.4 算法步驟

為了更好的平衡Q學習探索和利用的問題，本文引入模擬退火的Metropolis準則代替?zhèn)鹘y(tǒng)的貪婪策略（ε-greedy）來控制算法探索率。HQ調(diào)度算法具體實施步驟可概括如下。

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

Step2：根據(jù)當前狀態(tài)Sk，分別計算出所有選擇式和構(gòu)建式啟發(fā)式規(guī)則所對應的加工批;

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

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

Step5：執(zhí)行所選行動對應的啟發(fā)式規(guī)則，觀察狀態(tài)轉(zhuǎn)移信息并得到系統(tǒng)的下一狀態(tài)Sk+1，根據(jù)式(4)或(5)計算轉(zhuǎn)移代價并根據(jù)式(3)更新Q值表。令k=k+1，z=z+1。若z＜Z，則轉(zhuǎn)跳到step2。

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

3 仿真實驗

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

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

表1 系統(tǒng)參數(shù)設置表

表2 Q學習參數(shù)設置表

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

3.1 系統(tǒng)優(yōu)化效果

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)。在上述參數(shù)設置下，算法的系統(tǒng)代價優(yōu)化曲線和加工率優(yōu)化如圖2、圖3所示。

圖2 平均代價優(yōu)化曲線

圖3 加工率優(yōu)化曲線

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

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

3.2 不同工件參數(shù)設置下算法優(yōu)化效果

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

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

表3 三品種不同工件參數(shù)下各算法優(yōu)化效果

表4 四品種不同工件參數(shù)下各算法優(yōu)化效果

表5 五品種不同工件參數(shù)下各算法優(yōu)化效果

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

4 結(jié)語

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