不相容工件組的單機隨機調(diào)度問題研究

譚 琦，王永青，戴 飛

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

不相容工件組的單機隨機調(diào)度問題研究

譚 琦，王永青，戴 飛

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

研究不相容工件組在單臺批處理機上的分批加工問題，工件具有隨機的到達時間和加工時間。不相容工件組是指屬于不同組的工件不能被安排在同一批中加工。首先，以長期平均代價最小為優(yōu)化目標，以緩沖庫中工件數(shù)為實時狀態(tài)，建立了基于半馬爾科夫決策過程的系統(tǒng)模型。然后，通過策略迭代算法對其進行優(yōu)化控制，同時為了緩解大狀態(tài)空間導(dǎo)致的維數(shù)災(zāi)問題，給出了基于模擬退火的Q學(xué)習(xí)算法。仿真實驗驗證了所提出方法的有效性。

不相容工件組；隨機調(diào)度；批處理機；Q學(xué)習(xí)

0 引言

實際生產(chǎn)環(huán)境由于受到多種不確定性或隨機性因素的影響，調(diào)度信息通常無法提前準確預(yù)知。為了克服不確定性對系統(tǒng)決策和調(diào)度可行性的影響，生產(chǎn)系統(tǒng)需要根據(jù)當前信息采取實時控制策略。文獻[1]通過前瞻區(qū)間獲取工件信息，以最小化工件制造期為優(yōu)化目標，研究了工件組數(shù)與平行機數(shù)相同的在線分批調(diào)度問題。文獻[2]建立了不相容工件組隨機調(diào)度的預(yù)測模型，并以最小化工件平均生產(chǎn)周期為優(yōu)化目標，給出了一個基于模型預(yù)測控制的在線啟發(fā)式算法。文獻[3]將不相容工件組的調(diào)度問題建模為G/G/C排隊網(wǎng)絡(luò)，并以最小化工件平均生產(chǎn)周期為優(yōu)化目標，給出了相應(yīng)的啟發(fā)式算法。文獻[4]為了實時響應(yīng)模具制造過程中的機器完工和任務(wù)到達，建立了基于事件驅(qū)動的調(diào)度機制，并給出了面向準時與節(jié)能的前攝性分批算法。文獻[5]針對模具制造過程中的隨機性問題，建立了在制項目的交貨期隨機預(yù)測模型，并通過融入多模式資源受限項目調(diào)度優(yōu)先規(guī)則，對在制項目進行演化。

本文根據(jù)不相容工件組在單臺批處理機上分批加工的特點，以長期平均代價最小為優(yōu)化目標，建立了基于半馬爾可夫決策過程的系統(tǒng)模型；然后在模型的基礎(chǔ)上，通過策略迭代算法分析了緩沖庫容量對系統(tǒng)性能的影響。最后，通過基于模擬退火的Q學(xué)習(xí)算法（Q-learning algorithm combined with a simulated annealing，SA-Q）對具有大狀態(tài)空間的分批調(diào)度問題進行了優(yōu)化控制，仿真實驗結(jié)果驗證了所提算法的有效性。

1 模型的建立

假設(shè)m組不相容工件按相互獨立的泊松過程隨機到達，待加工工件存放在容量有限的緩沖區(qū)中，且所有工件尺寸為單位大小。屬于相同組的工件能被安排在同一批中加工，加工過程不允許中斷。批的加工時間和批中工件數(shù)無關(guān)，由工件組的類型決定。不考慮批的切換時間和準備時間，且批處理機容量有限。

由于工件動態(tài)到達時，非滿批次的最優(yōu)開啟時刻為工件的到達時刻[6]，則本文選取批處理機空閑時下一個工件的到達時刻和批處理機加工時批的完工時刻為決策時刻。在決策時刻，批處理機選擇等待未來工件到達，還是選擇一批相同組中工件進行加工是重要的決策問題。在采取加工行動時，以盡可能滿的方式構(gòu)成批；采取等待行動時，只等待一個工件到達。

根據(jù)決策機制的特點，建立基于半馬爾可夫控制過程的系統(tǒng)模型。系統(tǒng)中用到的參數(shù)和變量定義如下：

j：工件組的類型索引，j=1，2，…，m。

C：批處理機容量。

B：緩沖庫容量，m類緩沖庫的容量相同。

bj：緩沖庫j中工件數(shù)，表示緩沖庫j的狀態(tài)，且

λj：工件組j的工件到達率，工件按泊松過程到達。

vj：加工工件組j中工件的行動；另外，用v0表示等待行動。

wj：工件組j的權(quán)重，表示單位時間緩沖庫j中存儲一個工件的代價。

klose：流失一個工件的代價，不相容工件組中工件的流失代價相同。

Fj(t)：工件組j中工件的加工時間分布，均值為1/μj。

hj：采取加工行動vj時，加載到批處理機中屬于工件組j的工件數(shù)，hj=min(C,bj)。

系統(tǒng)工作過程中，根據(jù)實時狀態(tài)進行決策。除了特殊狀態(tài)下需要采取特殊的行動外，其他狀態(tài)下的行動屬于有限行動空間D。系統(tǒng)的兩種特殊狀態(tài)分別為：1）緩沖庫都為空。系統(tǒng)采取等待行動直到有工件到達；2）存在緩沖庫滿。若批處理機空閑，則立即采取加工行動，否則等待當前加工完成再做決策；有多個緩沖庫滿時，則選擇大的批次進行加工。

證明：1）若緩沖庫中沒有工件，批處理機空閑等待是合理的。2）存在一個緩沖庫滿時，為了避免工件流失，應(yīng)優(yōu)先加工已滿緩沖庫中的工件；多個緩沖庫滿時，根據(jù)加權(quán)最短加工時間優(yōu)先（weighted shortest processing time first同，WSPT）規(guī)則，應(yīng)優(yōu)先加工值大的批次。由于不同工件組中工件尺寸相同，則選擇大的滿批次進行加工是合理的。

前述問題的狀態(tài)變化過程可以表示為連續(xù)時間的隨機過程Xt（t≥0），且{X0,X1,…,Xl…}是一個嵌入的馬氏鏈[7]。在決策時刻Tl，系統(tǒng)狀態(tài)可表示為Xl（令Xl=s，采取的行動可表示為系統(tǒng)在決策時刻Tl的狀態(tài)為Xl，采取行動轉(zhuǎn)移到下一狀態(tài)Xl+1，并立即進入下一個決策時刻。

下面詳細介紹半馬爾科夫決策過程模型的建立。首先，定義系統(tǒng)在策略V下的狀態(tài)逗留時間分布矩陣和嵌入鏈轉(zhuǎn)移矩陣分別為和其中，F(xiàn)ss′(t,vs)和Pss′(vs)分別表示系統(tǒng)在狀態(tài)s下采取行動vs轉(zhuǎn)移到狀態(tài)s'的狀態(tài)逗留時間分布函數(shù)和轉(zhuǎn)移概率函數(shù)。然后，由狀態(tài)逗留時間分布和轉(zhuǎn)移概率，可得到系統(tǒng)在策略V下的半馬爾科夫核

本文假設(shè)不同組中工件的加工時間服從相互獨立的指數(shù)分布，因此系統(tǒng)的狀態(tài)逗留時間服從指數(shù)分布。根據(jù)決策行動的不同，系統(tǒng)的狀態(tài)轉(zhuǎn)移概率可以分為兩類：采取等待行動時，由下一個到達的工件類型決定狀態(tài)的轉(zhuǎn)移；采取加工行動時，由于工件的到達過程相互獨立，則系統(tǒng)狀態(tài)的轉(zhuǎn)移概率由各緩沖庫的狀態(tài)轉(zhuǎn)移概率共同決定。

在狀態(tài)s下采取等待行動v0，且下一個到達的工件屬于j工件組的狀態(tài)轉(zhuǎn)移概率為：

采取加工行動vj時，令緩沖庫j由狀態(tài)bj轉(zhuǎn)移到b'j的概率為當前決策過程中，其他m-1類緩沖庫中工件沒有被加工，令其中緩沖庫i由狀態(tài)bi轉(zhuǎn)移到b'i的概率為由各緩沖庫的狀態(tài)轉(zhuǎn)移概率之積，可得到系統(tǒng)在狀態(tài)s下采取加工行動vj轉(zhuǎn)移到s'的轉(zhuǎn)移概率為：

系統(tǒng)在狀態(tài)s下采取等待行動v0轉(zhuǎn)移到下一狀態(tài)s'過程中，系統(tǒng)單位時間的平均代價為：

采取加工行動時，根據(jù)系統(tǒng)轉(zhuǎn)移到狀態(tài)s'時，緩沖庫j的狀態(tài)b'j是否為滿，可以分別計算各工件組的單位時間平均代價。當b′j≠B時，沒有工件流失，則轉(zhuǎn)移過程中緩沖庫j中的平均工件數(shù)為當b′j=B時，緩沖庫j的下一狀態(tài)為滿，可能產(chǎn)生工件流失。在緩沖庫的下一狀態(tài)為滿時，令到達的j組工件數(shù)其中個工件卸載到緩沖庫j中，其余工件流失。因此，系統(tǒng)在狀態(tài)s下采取加工行動vj轉(zhuǎn)移到下一狀態(tài)s'過程中，單位時間平均代價可表示為：

2 優(yōu)化算法

在前述半馬爾科夫決策過程模型的基礎(chǔ)上，可通過策略迭代方法對本文問題進行優(yōu)化控制。一次迭代過程可以簡單的描述為：在當前策略Vk，可通過泊松方程計算性能勢向量并通過方程進行策略更新[7,8]。由于策略迭代的每一步迭代都需要計算穩(wěn)態(tài)分布和泊松方程，當狀態(tài)空間較大時將耗費大量計算時間和存儲空間。為了有效緩解系統(tǒng)大狀態(tài)空間導(dǎo)致的維數(shù)災(zāi)問題，本文通過SA-Q來尋找次優(yōu)行動控制策略。

Q學(xué)習(xí)算法是強化學(xué)習(xí)中應(yīng)用最廣泛的學(xué)習(xí)算法之一，是一種模型無關(guān)（Model-free）的非監(jiān)督學(xué)習(xí)方法；其通過仿真或觀測系統(tǒng)的運行，不斷學(xué)習(xí)并逼近狀態(tài)-行動對的函數(shù)值而對問題進行求解，在不需要環(huán)境模型的情況下可以有效評估可用行動的期望效用。

前述數(shù)學(xué)模型為SA-Q提供了理論基礎(chǔ)。根據(jù)樣本轉(zhuǎn)移過程，給出平均準則下的差分公式和Q值更新公式：

根據(jù)式、和樣本轉(zhuǎn)移可知，系統(tǒng)在狀態(tài)s下采取等待行動和加工行動轉(zhuǎn)移到下一狀態(tài)s'過程中的累積代價分別如下：

為了平衡Q學(xué)習(xí)的探索和利用，避免算法進入局部最優(yōu)，使用模擬退火的Metropolis接受準則設(shè)置Q學(xué)習(xí)的探索率。學(xué)習(xí)過程中每N步，由Q值表生成當前的貪婪策略，并評估當前貪婪策略的優(yōu)化性能。SA-Q流程如圖1所示，其中，Z為算法截止步數(shù)，ζ是模擬退火的溫度衰減因子。

3 仿真結(jié)果分析

小于等于1；當TI＞1時，即使批處理機一直處在滿批次加工，系統(tǒng)中工件也會不斷積累[10]。在前述數(shù)學(xué)模型的基礎(chǔ)上，首先通過策略迭代算法分析不同緩沖庫容量和流失代價對系統(tǒng)優(yōu)化性能的影響。然后比較兩組工件時，SA-Q和策略迭代算法的優(yōu)化效果。本文所有仿真實驗均在Microsoft Windows7（CPU 3.40GHz，RAM 7.90GB）環(huán)境下，使用MATLAB R2016a平臺編程實現(xiàn)。

不同流失代價下兩組工件的實例設(shè)置如表1所示。

表1 不同流失代價下兩組工件的實例設(shè)置

圖1 SA-Q流程圖

不同流失代價下兩組工件的最優(yōu)平均代價曲線如圖2所示。當klose=0時，隨緩沖庫容量的增大，工件的流失量減小，同時系統(tǒng)中平均持有的工件數(shù)增多，則最優(yōu)平均代價逐漸增大。klose≠0時，工件的流失量減小，流失代價對平均代價的貢獻減小，則最優(yōu)平均代價隨緩沖庫容量的增大而衰減；且流失代價越大，流失代價對平均代價的貢獻減小的越快，則曲線衰減的越快。

不同流失代價下兩組工件的平均處理率曲線如圖3所示。不同流失代價下平均處理率曲線隨緩沖庫容量的增大而增大。在相同緩沖庫容量下，流失代價klose為0時工件平均處理率最小，主要原因是考慮流失代價時系統(tǒng)單位時間加工的工件數(shù)增大。流失代價klose為500和1000時，處理率曲線基本重合，主要原因是在緩沖庫容量較小時，由于緩沖庫中工件存儲量的制約，工件平均處理率不會隨流失代價klose的增大而增大，此時相同緩沖庫容量下的工件流失率基本相同，并且流失代價越大則最優(yōu)平均代價越大（如圖2所示）；在緩沖庫容量較大時，由于工件總到達率的制約，工件平均處理率不會隨流失代價klose的增大而增大。此外，不同流失代價下的平均處理率隨緩沖庫容量的增大趨于相同，主要原因是緩沖庫容量增大，則工件的流失量減小；當工件平均處理率等于工件的到達率時，流失代價對平均代價的貢獻為零。

圖2 不同流失代價時的最優(yōu)平均代價曲線

圖3 不同流失代價時的平均處理率曲線

圖2 和圖3的實驗結(jié)果表明隨著緩沖庫容量的增加，工件的流失率逐漸減小；且當緩沖庫容量B=30時，工件組1和工件組2的平均處理率分別為3.09和1.08，近似等于兩組工件的到達率。對于表1的實驗數(shù)據(jù)選取緩沖庫容量略大于30較合適；這樣不僅可以減少庫存浪費和工件流失，同時也可以保證合適的狀態(tài)空間大小。

在本文不相容工件組的半馬爾科夫決策過程模型中，系統(tǒng)狀態(tài)空間（(B+1)m）隨工件組數(shù)的增大呈指數(shù)增大。當工件組數(shù)較大時，通過SA-Q對系統(tǒng)進行優(yōu)化控制。下面通過實驗比較工件組數(shù)為2時兩種算法的性能。根據(jù)表1的實驗數(shù)據(jù)，表2中選取緩沖庫容量為30，流失代價klose=500，批處理機容量C=6，TI=0.7。當TI減小時，相同批處理機容量和工件處理率計算得到的工件到達率減小，則系統(tǒng)的緩沖庫容量選為30能滿足優(yōu)化的需要。

表2 兩組工件的實例設(shè)置和實驗結(jié)果

兩組工件的實例設(shè)置和實驗結(jié)果如表2所列。表中列出了三種到達率比值，兩種權(quán)重和兩種處理率；不同組工件到達率的實際值由TI和工件處理率計算得到。

兩組工件的實驗結(jié)果如表2所示。表中GAP=（SA-Q/PI）-1用于表示SA-Q次優(yōu)解與策略迭代最優(yōu)解的相對差距。表2中SA-Q獲得的次優(yōu)解與最優(yōu)解的相對差距總體在3%以內(nèi)，實驗結(jié)果說明SA-Q具有較好的優(yōu)化效果。表中，1～6組的實驗結(jié)果明顯大于7～12組，主要原因是由于工件組1的權(quán)重增大，則其平均代價增大。此外，1～6組實驗結(jié)果隨到達率比值的減小而減小，主要原因是工件到達率比值減小，由TI計算得到的工件組1到達率減小，工件組2到達率增大；在前6組實驗數(shù)據(jù)中，工件組1的權(quán)重大，因此平均代價隨到達率比值減小而增大。在7～12組實驗參數(shù)中，平均代價隨到達率比值的減小由微小增大，主要原因是由TI計算得到的工件總到達率隨到達率比值的減小有小幅增加，則平均代價有小幅增大。

在表2的實驗數(shù)據(jù)下，系統(tǒng)的狀態(tài)空間為961，且SA-Q在學(xué)習(xí)50萬步后基本收斂到最優(yōu)解，且耗時在200秒以內(nèi)；其與策略迭代算法的耗時相比沒有太大的優(yōu)勢，但當工件組數(shù)大于2時，系統(tǒng)狀態(tài)空間呈指數(shù)增大，策略迭代算法的耗時將大幅增加，下面通過設(shè)置三組工件和四組工件的實驗來說明SA-Q的優(yōu)化效果。

三組工件的實例設(shè)置和實驗結(jié)果如表3所示。表中列出了四組到達率比值，工件到達率的實際值由TI和工件處理率計算；根據(jù)前述實驗結(jié)果，表3中選取緩沖庫容量為15，流失代價klose=500，批處理機容量C=3，TI=0.4，并且只給出了工件具有相同等待代價權(quán)重的實驗結(jié)果。

三組工件的實驗結(jié)果如表3所示。表中，SA-Q次優(yōu)解與最優(yōu)解的相對差距在1%以內(nèi)。三工件組實驗參數(shù)中TI較小，系統(tǒng)的平均處理率遠大于工件的到達率，則平均代價較小。

表3 三工件組的實例設(shè)置和性能比較

在表3的實驗數(shù)據(jù)下，系統(tǒng)的狀態(tài)空間為4096；SA-Q在學(xué)習(xí)1000萬步后基本收斂到最優(yōu)解，且計算耗時在一個小時內(nèi)，相同問題策略迭代的耗時需要按天計算。在不相容工件組的分批調(diào)度問題中，緩沖庫容量需要大于批處理機的容量；當工件組數(shù)大于3時，策略迭代算法將無法計算這種具有大規(guī)模狀態(tài)空間的問題。

下面給出工件組數(shù)為4的SA-Q優(yōu)化實驗。根據(jù)前述實驗結(jié)果，令B=15，C=3，klose=500，工件等待代價權(quán)重（w1,w2,w3,w4）=（1.5,1.3,1.2,1.0）；并由工件處理率（μ1，μ2，μ3，μ4）=（0.5,0.6,0.7,0.8）和TI（等于0.4），計算得到的工件到達率（λ1，λ2，λ3，λ4）=（0.32,0.16,0.11,0.11）。學(xué)習(xí)過程中，每20萬步由Q值表更新一次策略，并仿真評估其性能。每次評估進行20次獨立實驗，每次運行20萬步，然后估計當前策略下系統(tǒng)的平均性能。

四工件組的總平均處理率曲線如圖4所示，平均處理率隨SA-Q學(xué)習(xí)步數(shù)的增大而增大，最終近似等于工件的總到達率，且各組工件的平均到達率分別為0.321、0.161、0.107和0.107；說明在當前緩沖庫容量下系統(tǒng)的工件流失可以忽略不計。四工件組的平均代價優(yōu)化曲線如圖5所示，SA-Q學(xué)習(xí)初始曲線具有較大波動，隨著學(xué)習(xí)步數(shù)的增加曲線最終收斂；說明SA-Q學(xué)到的次優(yōu)策略有效減少了系統(tǒng)的平均代價。

圖4 四組工件的總平均處理率

4 結(jié)束語

本文研究了不相容工件組在單臺批處理機上的分批加工問題。首先，根據(jù)問題的特點將其建模為半馬爾科夫決策過程；然后在所建模型的基礎(chǔ)上，通過策略迭代算法分析了緩沖庫容量對系統(tǒng)平均性能的影響；并通過比較兩種算法的性能，說明了SA-Q能有效緩解大狀態(tài)空間導(dǎo)致的維數(shù)災(zāi)問題。本文只考慮了工件加工時間為指數(shù)分布的情況，所建模型對加工時間為一般分布的問題同樣適用，如愛爾蘭分布等。另外，也可以擴張到相容工件組的分批加工問題。

圖5 四組工件的SA-Q優(yōu)化曲線

[1] 李文華,柴幸,袁航,楊素芳.平行機上帶有前瞻區(qū)間的不相容工件組在線排序問題[J].運籌學(xué)學(xué)報,2015,19(4):121-126.

[2] J.B.C.Tajan.Control of a Single Batch Processor with Incompatible Job Families and Future Job Arrivals[J].IEEE Transactions on Semiconductor Manufacturing,2011,24(2):208-222.

[3] J. W. Fowler.Optimal batching in a wafer fabrication facility using a multiproduct G/G/c model with batch processing[J].International Journal of Production Research,2002,40(2):275-292.

[4] 劉建軍,陳慶新,毛寧,朱鑫.事件驅(qū)動的并行多機模具熱處理生產(chǎn)調(diào)度[J].計算機集成制造系統(tǒng),2015,21(4):1013-1022.

[5] 王小明,陳慶新,毛寧,劉建軍.隨機環(huán)境下的模具項目交貨期預(yù)測方法[J].計算機集成制造系統(tǒng),2012,18(2):405-414.

[6] S Yao, Z Jiang,N Li.A branch and bound algorithm for minimizing total completion time on a single batch machine with incompatible job families and dynamic arrivals[J].Computers & Operations Research,2012,39(5):939-951.

[7] Xi-Ren Cao.Semi-Markov decision problems and performance sensitivity analysis[J].Automatic Control,2003,48(5):758-769.

[8] Xi-Ren Cao. Stochastic learning and optimization:A sensitivitybased approach[J].Annual Reviews in Control,2009,33(1):11-24.

[9] H Tang, Arai Tamio. Look-ahead control of conveyor-serviced production station by using potential-based online policy iteration[J].International Journal of Control,2009,82(10):1917-1928.

[10] I Duenyas,JJ Neale. Stochastic scheduling of a batch processing machine with incompatible job families[J].Annals of Operations Research,1997,70:191-220.

Stochastic scheduling of incompatible job families on a single batch machine

TAN Qi, WANG Yong-qing, DAI Fei

TP278

：A

1009-0134(2017)06-0063-06

2017-04-10

國家自然科學(xué)基金面上項目（JZ2015GJMS0418）

譚琦（1985 -），男，湖南邵陽人，講師，博士，研究方向為生產(chǎn)優(yōu)化及相關(guān)研究。