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

譚 琦，王永青，戴 飛

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

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

譚 琦，王永青，戴 飛

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

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

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

0 引言

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

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

1 模型的建立

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

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

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

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

C：批處理機容量。

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

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

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

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

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

前述問題的狀態(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，并立即進(jìn)入下一個決策時刻。

下面詳細(xì)介紹半馬爾科夫決策過程模型的建立。首先，定義系統(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)移概率可以分為兩類：采取等待行動時，由下一個到達(dá)的工件類型決定狀態(tài)的轉(zhuǎn)移；采取加工行動時，由于工件的到達(dá)過程相互獨立，則系統(tǒng)狀態(tài)的轉(zhuǎn)移概率由各緩沖庫的狀態(tài)轉(zhuǎn)移概率共同決定。

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

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

2 優(yōu)化算法

在前述半馬爾科夫決策過程模型的基礎(chǔ)上，可通過策略迭代方法對本文問題進(jìn)行優(yōu)化控制。一次迭代過程可以簡單的描述為：在當(dāng)前策略Vk，可通過泊松方程計算性能勢向量并通過方程進(jìn)行策略更新[7,8]。由于策略迭代的每一步迭代都需要計算穩(wěn)態(tài)分布和泊松方程，當(dāng)狀態(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ù)值而對問題進(jìn)行求解，在不需要環(huán)境模型的情況下可以有效評估可用行動的期望效用。

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

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

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

3 仿真結(jié)果分析

小于等于1；當(dāng)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所示。當(dāng)klose=0時，隨緩沖庫容量的增大，工件的流失量減小，同時系統(tǒng)中平均持有的工件數(shù)增多，則最優(yōu)平均代價逐漸增大。klose≠0時，工件的流失量減小，流失代價對平均代價的貢獻(xiàn)減小，則最優(yōu)平均代價隨緩沖庫容量的增大而衰減；且流失代價越大，流失代價對平均代價的貢獻(xiàn)減小的越快，則曲線衰減的越快。

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

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

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

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

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

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

兩組工件的實例設(shè)置和實驗結(jié)果如表2所列。表中列出了三種到達(dá)率比值，兩種權(quán)重和兩種處理率；不同組工件到達(dá)率的實際值由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é)果隨到達(dá)率比值的減小而減小，主要原因是工件到達(dá)率比值減小，由TI計算得到的工件組1到達(dá)率減小，工件組2到達(dá)率增大；在前6組實驗數(shù)據(jù)中，工件組1的權(quán)重大，因此平均代價隨到達(dá)率比值減小而增大。在7～12組實驗參數(shù)中，平均代價隨到達(dá)率比值的減小由微小增大，主要原因是由TI計算得到的工件總到達(dá)率隨到達(dá)率比值的減小有小幅增加，則平均代價有小幅增大。

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

三組工件的實例設(shè)置和實驗結(jié)果如表3所示。表中列出了四組到達(dá)率比值，工件到達(dá)率的實際值由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)的平均處理率遠(yuǎn)大于工件的到達(dá)率，則平均代價較小。

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

在表3的實驗數(shù)據(jù)下，系統(tǒng)的狀態(tài)空間為4096；SA-Q在學(xué)習(xí)1000萬步后基本收斂到最優(yōu)解，且計算耗時在一個小時內(nèi)，相同問題策略迭代的耗時需要按天計算。在不相容工件組的分批調(diào)度問題中，緩沖庫容量需要大于批處理機的容量；當(dāng)工件組數(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），計算得到的工件到達(dá)率（λ1，λ2，λ3，λ4）=（0.32,0.16,0.11,0.11）。學(xué)習(xí)過程中，每20萬步由Q值表更新一次策略，并仿真評估其性能。每次評估進(jìn)行20次獨立實驗，每次運行20萬步，然后估計當(dāng)前策略下系統(tǒng)的平均性能。

四工件組的總平均處理率曲線如圖4所示，平均處理率隨SA-Q學(xué)習(xí)步數(shù)的增大而增大，最終近似等于工件的總到達(dá)率，且各組工件的平均到達(dá)率分別為0.321、0.161、0.107和0.107；說明在當(dāng)前緩沖庫容量下系統(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ù)分布的情況，所建模型對加工時間為一般分布的問題同樣適用，如愛爾蘭分布等。另外，也可以擴(kuò)張到相容工件組的分批加工問題。

圖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)研究。