基于灰數(shù)描述的不確定工時作業(yè)車間E/T調(diào)度優(yōu)化*

陳開院,熊禾根

(武漢科技大學a.冶金裝備及其控制教育部重點實驗室;b.機械傳動與制造工程湖北省重點實驗室,武漢 430000)

0 引言

工件的加工工時由于設計的經(jīng)驗性、加工設備的實時狀態(tài)、操作工人的實時狀態(tài)等原因,使得實際操作時的加工工時具有波動性和不確定性。因此生產(chǎn)調(diào)度方案在實際生產(chǎn)運作中不可避免會產(chǎn)生偏離,在面向訂單的制造系統(tǒng)中,這種偏離可能體現(xiàn)得更為嚴重,進而影響訂單的按期交貨。另一方面,在進行交貨期制定時,除了按確定時間點設定交貨期的方式,另一種常用的方式是給訂單設定一個合理的交貨時間窗,在給定時間窗內(nèi)交貨,既不影響客戶的生產(chǎn),也不至于增加庫存的成本。

針對工件加工工時不確定的調(diào)度問題,現(xiàn)有研究主要使用概率分布、區(qū)間數(shù)和三角模糊數(shù)來建立相應的調(diào)度模型。張潔等[1]采用埃爾朗分布模擬加工時間,設計一種基于交貨期偏差容忍度的滾動調(diào)度策略;楊宏安等[2]通過區(qū)間可能度比較法分析工件完工時間區(qū)間與交貨期窗口的各種關系進行求解;LI等[3]提出一種基于概率和偏好比的區(qū)間排名方法,用于精確的區(qū)間計算;彭運芳等[4]用三角模糊數(shù)進行建模,利用均值去模糊化結合改進遺傳算法對調(diào)度問題提供解決方案;劉琦等[5]基于模糊規(guī)劃理論,采用“中間值最大隸屬度”的算法對調(diào)度問題進行求解。對于提前/拖期調(diào)度問題(earliness/tardiness,E/T),WODECK等[6]考慮單機調(diào)度中的E/T調(diào)度問題,提出一種用序列塊代表搜索集合的Tabu搜索算法求解。

模糊數(shù)方法在處理工時不確定的調(diào)度問題方面取得了顯著成效。然而,在數(shù)據(jù)處理過程中,去模糊化方法對權重和隸屬度的選擇非常敏感。為克服這一問題,研究中引入了灰色理論,該理論使用區(qū)間灰數(shù)來描述加工工時的不確定性,并利用灰數(shù)的白化權函數(shù)描述區(qū)間內(nèi)每個數(shù)的取值概率。通過白化權函數(shù)將區(qū)間灰數(shù)轉化為確定值,從而建立相應的灰色理論調(diào)度模型。

基于前人的已有研究,對具有工時不確定性和交貨期窗口的作業(yè)車間E/T調(diào)度問題(job shop earliness and tardiness scheduling problem with uncertain processing-times and due-wind-ows,JSSP/ET_UPD)進行研究,基于灰色理論建立了問題的數(shù)學規(guī)劃模型,提出了遺傳算法與局部搜索結合的求解算法。在目標函數(shù)中考慮工件提前和拖期懲罰,以該函數(shù)值最小使工件盡可能在交貨期窗口內(nèi)完成,同時為保證機器資源的充分利用,還將機器空閑的成本包含在目標函數(shù)中。

1 問題描述

1.1 JSSP/ET_UPD問題描述

所提出的JSSP/ET_UPD問題可描述如下:有n個工件需要在m臺機器上加工,每個工件含有若干道加工工序,工件的工藝路線預先指定;各工序在指定的機器上加工,加工工時為非確定值。每個工件均設定有一個交貨期窗口[Ei,Ti],若工件在設定的交貨期窗口內(nèi)按完工,則沒有懲罰;否則,若工件提前或者拖期完工,將產(chǎn)生相應的懲罰。此外,若機器在加工過程中出現(xiàn)空閑,也將產(chǎn)生相應的懲罰。問題的目標是尋找一個優(yōu)化的調(diào)度方案,使完成所有工件的總成本(懲罰)最小。該問題其他一些基本假設為:

(1)所有工件零時刻可開始加工;

(2)所有機器零時刻可用,不考慮機器故障和維護;

(3)所有工件等權重,且相互獨立,不存在約束關系;

(4)同一時刻,一臺機器只能加工一個工件;

(5)同一時刻,一個工件只能被一臺機器加工;

(6)工件的加工路徑中機器不可重入;

(7)一道工序一旦開工,在其加工過程中不允許被中斷和被搶占。

1.2 不確定工時的灰數(shù)描述

(1)

根據(jù)期望值法去模糊數(shù)化,將其轉為確定加工時間,表示為:

(2)

由于該方法在對不確定工時轉為確定值進行算法求解時,難以考慮到加工時間的所有分布信息,因此提出一種工時的灰數(shù)描述方法?；覕?shù)是灰色理論的基本單元,通常把只知道大概范圍而不知道確切值的數(shù)稱為灰數(shù),灰數(shù)常記作“?”。與模糊理論不同,灰色理論著重研究的是外延明確而內(nèi)涵不明確的問題。對于工時不確定性而言,顯然,其外延(即工件的工時)是明確的,但內(nèi)涵(即工時的確切取值)是不明確的。因此,采用灰數(shù)對不確定工時進行描述是合理的。

基于不確定工時的三角模糊數(shù)表示,灰色理論下的加工時間可表示為區(qū)間灰數(shù)?∈[pmin,pmax],對應的白化權函數(shù)表達式為:

(3)

(4)

之后通過灰色模擬[8]產(chǎn)生服從F分布的實際時間加工時間,在[0,1]之間通過均勻分布產(chǎn)生隨機變量μ,再求得F-1(p)的值,即為灰色理論下模擬出的實際加工時間?p。

(5)

?p=F-1(p)

(6)

1.3 基于灰數(shù)描述的JSSP/ET_UPD問題模型

為方便描述及數(shù)學模型的建立,定義相關符號以及相關決策變量,如表1所示。

表1 相關符號及其含義

工件若未在交貨期窗口完成交貨,提前或者拖期完成都會造成一定的成本損失,機器處于空載狀態(tài)時也會造成不必要的損失。因此綜合考慮拖期/提前成本以及機器空閑成本,將目標函數(shù)定義為:

min?Z=?G+?M

(7)

式中:?G為工件的提前/拖期成本,?M為機器空閑成本,均由灰數(shù)表示;其表達式為:

式中:CE為提前懲罰,CT為拖期懲罰,CM為機器空閑懲罰。并根據(jù)相關定義,給出如下約束條件:

?cij≤?si(j+1)

(8)

max{sij,?si′j′≥min{ ?cij,?ci′j′}

(9)

mij≠mij′

(10)

?cij=?sij+?pij

(11)

約束(8)對應工件指定的工藝路線要求,約束(9)表示同一時刻一臺機器只能加工一個工件,約束(10)表示機器不可重入;約束(11)保證工序能夠連續(xù)加工,既不被中斷也不被搶占;約束(8)和約束(11)保證工件在同一時刻只能被一臺機器加工。

2 算法設計

遺傳算法作為一種元啟發(fā)式算法,是一種群體智能搜索算法,有著很強的大范圍搜索能力,但在局部深入搜索能力方面有所欠缺。因此,為改善遺傳算法求解問題的性能,將遺傳算法與局部搜索相結合,設計了求解JSSP/ET_UPD問題的混合遺傳算法,算法流程圖如圖1所示。求解過程中先通過遺傳算法進行全局搜索,滯留現(xiàn)象到一定程度時,調(diào)用局部搜索對當前最優(yōu)解進行優(yōu)化,并根據(jù)滯留代數(shù)對局部搜索的鄰域大小和搜索次數(shù)進行動態(tài)調(diào)整,具體如圖2所示。

圖1 算法流程圖 圖2 動態(tài)局部搜索策略

2.1 遺傳算法設計

遺傳算法方面,各算子及控制參數(shù)具體設計為:

(1)編碼與解碼。采用基于符號的編碼方式,每一條染色體包含所有工件的加工工序。以3×3 Job Shop問題舉例,一條隨機生成的染色體為[3,1,2,2,1,3,1,3,2],用工件序號表示基因。解碼過程中,根據(jù)工件號在染色體中重復出現(xiàn)的次數(shù)找到對應工件的加工工序,并將其置入對應機器上加工,直至所有工件加工完成,解碼過程結束。

(2)選擇操作。利用輪盤賭策略,該策略會根據(jù)每個個體的適應度來確定其被選中的概率,適應度越高的個體被選中的概率就越大。為了確保種群有更好的進化方向,采用精英保留策略[9],將適應度最好的個體直接保留到下一代。

(3)交叉與變異操作。采用基于POX算子[10]的交叉方式;為保證種群多樣性,避免陷入局部最優(yōu),采用翻轉變異[11]。

(4)確定交叉變異概率。區(qū)別于文獻[5]基于種群適應度的動態(tài)交叉概率,針對種群中的每個個體分別設置交叉概率(Pc)和變異概率(Pm),并根據(jù)其適應度值進行動態(tài)調(diào)整,賦予適應度差的個體更高的交叉和變異概率,對于適應度較好的個體則賦予較小的概率,以保證有益基因個體能夠傳承至下一代。具體步驟為:

步驟1:給定交叉、變異概率的Pc,Pm基準值;

步驟2:計算種群中個體l的適應度,將其記作Zl;

步驟3:個體l的動態(tài)交叉概率Pc(l)及變異概率Pm(l)表示為:

式中:S為種群規(guī)模。

2.2 局部搜索部分

設z為滯留代數(shù),當遺傳算法求解過程中滯留代數(shù)z>5,則調(diào)用局部搜索嘗試對最優(yōu)個體進行尋優(yōu);若z>10,則對局部搜索的參數(shù)進行動態(tài)調(diào)整。

根據(jù)文獻[12],調(diào)度方案的優(yōu)劣與工件的不確定程度有關,因此在局部搜索的鄰域設計中,選擇不確定程度不一致的多道工序設計為鄰域,將鄰域里不確定程度不同的多道工序重新排序。通過改變局部序列調(diào)整整體調(diào)度方案,嘗試找出更好的調(diào)度方案。具體步驟為:

步驟1:獲取當前最優(yōu)個體,通過其對應的模糊調(diào)度模型或灰色理論模型,將不確定的加工時間轉化為確定值。利用該值表示工序加工時間的不確定程度,通過該值的大小,將最優(yōu)個體中的所有工序均勻劃分為工序加工時間不確定程度不同的兩個集合;

步驟2:從步驟1中生成的集合分別選擇等量的工序置為鄰域,通過對鄰域內(nèi)已選中工序的加工順序進行局部調(diào)整,來改變最優(yōu)個體對應的整體調(diào)度方案及其適應度值,然后保持鄰域不變,對鄰域內(nèi)的工序局部調(diào)整20次,得到該鄰域下的20個鄰域解。將本次生成的鄰域加入禁忌表,以及20個鄰域解中的最優(yōu)解記錄在集合G中;

步驟3:對步驟2重復t次,選擇未在禁忌表中的鄰域結構,利用該鄰域再次對初始最優(yōu)個體進行鄰域搜索,獲取搜索結果。最終得到t個鄰域結構和t個鄰域結構下所對應的最優(yōu)解,記錄在集合G中。獲取集合G;

步驟4:將G中的最優(yōu)個體g與初始最優(yōu)個體進行適應度值比較,若適應度值優(yōu)于初始最優(yōu)個體,則將g置為當前最優(yōu)個體,進行下一次算法迭代;否則不變,直接進入下一次迭代。

假設最優(yōu)個體包含的總工序數(shù)量為q,則該算法中局部搜索策略如圖2所示。當滯留代數(shù)z<10時,該算法可能處于初始階段,滯留現(xiàn)象出現(xiàn)時能夠更容易找出更優(yōu)解,同時考慮到求解計算量,因此給予較大的鄰域空間對和較少的鄰域生成次數(shù)進行搜索;當滯留代數(shù)z>10時,該算法可能處于中后期的迭代過程中,此時最優(yōu)解已經(jīng)獲得了一個較好的排序方案,難以找到更優(yōu)解,采用較小的基因片段,增加鄰域生成次數(shù),增加搜索次數(shù),以找出更優(yōu)解。

3 算例仿真

3.1 實驗設計

(1)算例選擇。為便于實驗結果的分析比較,仿真算例選自于相關文獻。所選算例包括兩種規(guī)模:6工件6機器(6×6)和10工件10機器(10×10),各4個算例。算例來源如表2所示,具體數(shù)據(jù)見對應文獻。

表2 算例來源

表3和表4給出算例Case1每個工件的加工信息及其工件的交貨期窗口。

表3 6×6算例Case1工件加工信息

表4 6×6算例Case1工件交貨期

(2)實驗方案。仿真調(diào)度包含3個實驗,具體為:

①實驗1:基本遺傳算法[5]與混合遺傳算法性能對比實驗。針對表中所列案例,工時不確定性用三角模糊數(shù)描述,采用基本遺傳算法與本文提出的混合遺傳算法進行仿真調(diào)度。每個算例均在兩種算法下進行20次獨立的仿真調(diào)度,對每次仿真調(diào)度所獲得的最優(yōu)解進行統(tǒng)計分析,以比較兩種算法的求解性能。

②實驗2:不確定工時三角模糊數(shù)描述與灰數(shù)描述模型下性能對比實驗。針對表中所列案例,工時不確定性分別用三角模糊數(shù)和灰數(shù)描述,采用本文提出的混合遺傳算法進行仿真調(diào)度。每個算例均在兩種描述模型下進行20次獨立的仿真調(diào)度,并對每次仿真調(diào)度所獲得的最優(yōu)解進行統(tǒng)計分析,以比較兩種描述模型下的求解性能。

③實驗3:不確定工時三角模糊數(shù)描述與灰數(shù)描述模型下調(diào)度方案穩(wěn)定性對比實驗。針對實驗2的40次仿真調(diào)度所得到每一個最優(yōu)解,分別采用對應的描述模型(三角模糊數(shù)或灰數(shù))進行20次工時隨機抽樣,并按最優(yōu)解染色體進行解碼,可獲得每個最優(yōu)解在每次隨機抽樣工時下的總成本。對每個最優(yōu)解20次抽樣總成本的均值進行統(tǒng)計分析,以比較兩種描述模型下的調(diào)度方案的穩(wěn)定性。

(3)實驗參數(shù)實驗環(huán)境及參數(shù)設置。運行環(huán)境:Windows 10操作系統(tǒng),內(nèi)存8 G,CPU 2.8 GHz;采用python編程;參數(shù)設置如表5所示。

表5 參數(shù)設置

3.2 實驗結果及分析

(1)實驗1結果及分析。為了驗證算法的有效性,進行了20次仿真實驗,其中6×6和10×10的算例的最優(yōu)值進化曲線如圖3所示。實線為混合遺傳算法的進化曲線,虛線為文獻[5]提出的遺傳算法進化曲線,這些曲線在20次仿真結果中變化趨勢基本相同。

(a) Case1 (b) Case2

通過對算法的最優(yōu)值進化曲線進行分析,可以得出結論:在解決小規(guī)模問題時,混合遺傳算法通常在50代左右就能夠收斂并獲得最優(yōu)解,相比基本遺傳算法,混合遺傳算法具有更好的收斂能力;在大規(guī)模問題中,雖然混合遺傳算法的收斂速度略慢于基本遺傳算法,但其能夠獲得更好的最優(yōu)解。

為了更準確地評估混合遺傳算法的優(yōu)化效果,采用以下評估準則:假設使用基本遺傳算法得到的仿真結果的平均值為b,混合遺傳算法后得到的平均值為h,則可以通過以下公式計算出相對百分比偏差RPD1為:

通過相對百分比偏差RPD1的值可知,混合遺傳算法在大規(guī)模的案例中,對于最優(yōu)值的優(yōu)化程度更為明顯,其相對百分比偏差基本大于10%。

(2)實驗2結果及分析。結合灰色理論,采用區(qū)間灰數(shù)對不確定工時進行描述,建立相應的灰色理論調(diào)度模型。其仿真結果如表6所示,并將其仿真結果繪制成圖4的小提琴圖,以顯示其仿真結果的分布情況。

(a) Case1 (b) Case2

表6 算法測試及模型測試結果

與算法評估準則相同,假設灰色理論下得到的仿真結果的均值為r,則相對百分比偏差RPD2:

利用該值進行比較,灰數(shù)模型在不同數(shù)據(jù)規(guī)模上的優(yōu)化效果不一,但總體而言,在數(shù)據(jù)規(guī)模較大的案例中,能夠獲得更好的優(yōu)化效果的可能性更大,最大的相對百分比偏差能夠達到10%以上。

結合表6算法測試及模型測試結果中的相對百分比偏差與圖4的小提琴圖分布情況可以發(fā)現(xiàn),基于灰色理論的建模方法,其仿真結果表現(xiàn)為分布較為集中,相比三角模糊數(shù)模型,其方差表現(xiàn)也更為優(yōu)異?？傮w而言,在處理大規(guī)模和大數(shù)據(jù)問題時,灰色理論表現(xiàn)出更為顯著的優(yōu)化效果,且具有更高的穩(wěn)定性。

通過對表6的數(shù)據(jù)和圖4的小提琴圖進行分析,發(fā)現(xiàn)算例Case1的仿真結果優(yōu)化程度也較為明顯,因此本研究以算例Case1為例,分別用模糊數(shù)模型和灰色理論調(diào)度模型,結合表3、表4的原始數(shù)據(jù)進行算例仿真,得到對應調(diào)度甘特圖如圖5所示。

(a) 模糊數(shù)模型最優(yōu)結果甘特圖

分析甘特圖可以發(fā)現(xiàn),與模糊數(shù)模型相比,灰數(shù)模型所得到的甘特圖在工件最大完工時間和機器的空載時間方面都有所改善,從而降低目標函數(shù)值,總成本也能因此減小。

(3)實驗3結果及分析。實驗結果如表7所示,根據(jù)方差分析,灰色理論下描述的不確定加工時間作業(yè)車間調(diào)度模型穩(wěn)定性和適應性明顯更高。灰色理論建立的模型可以彌補模糊數(shù)模型在計算過程中無法考慮實際加工時間分布的限制。該模型將加工時間區(qū)間內(nèi)所有可能取值的概率表述在模型中,并通過白化權函數(shù)將區(qū)間灰數(shù)轉化為確定值,實現(xiàn)對優(yōu)化求解的支持。

表7 模型穩(wěn)定性測試結果

在實際生產(chǎn)過程中,由于各種不確定因素導致加工時間出現(xiàn)波動,使得調(diào)度方案出現(xiàn)偏差。而灰色理論模型能夠更全面地利用已知信息,盡可能地利用先前已有的加工時間分布情況,因此在面對加工時間波動時,具有更強的穩(wěn)定性和更好的適應性。

結論:使用三角模糊數(shù)轉為灰數(shù),并通過三角模糊數(shù)構建白化權函數(shù),能夠更全面地考慮到數(shù)據(jù)的不確定性,從而在調(diào)度問題中獲得更加穩(wěn)定的決策結果。相比于三角模糊數(shù)用均值轉換為確定值的方法,這種方法可以更充分地利用數(shù)據(jù)的特征,提高決策的精度和可靠性,從而獲得更優(yōu)的調(diào)度結果。

4 結束語

對單一的遺傳算法的穩(wěn)定性和精度進行改進,將局部搜索融入遺傳算法,測試改進前后算法的求解質(zhì)量和收斂速度。分析用模糊數(shù)描述的不確定加工時間的作業(yè)車間模型,通過灰色理論對不確定加工時間的調(diào)度問題重新建模仿真,分別對兩種模型進行仿真測試。仿真結果表明,灰色理論能夠有效地應用于不確定加工工時的調(diào)度問題中,相對于三角模糊數(shù)模型,灰色模型能夠考慮到更多已知信息,提高調(diào)度決策地和適應性穩(wěn)定性。