一類具有成組可重入特征單機調(diào)度的改進分布估計算法

袁帥鵬, 李鐵克, 王柏琳, 張文新, 張卓倫, 余娜娜

(1.北京科技大學 經(jīng)濟管理學院,北京 100083; 2.鋼鐵生產(chǎn)制造執(zhí)行系統(tǒng)技術教育部工程研究中心,北京 100083)

0 引言

本文研究了一類具有成組可重入特征的單機調(diào)度問題,該問題源于鋼鐵企業(yè)寬厚板生產(chǎn)過程中熱軋工序的生產(chǎn)管理需求。熱軋是寬厚板生產(chǎn)過程中極其關鍵的一道工序,其工藝流程如圖1所示,來自連鑄車間的板坯需按照設定的軋制節(jié)奏進入軋機進行軋制,隨后進入下游工序加工。與其他常規(guī)加工過程不同,板坯的軋制過程具有以下特點:①由于軋制工藝的要求,板坯需依次進行粗軋、精軋兩個階段的軋制,且階段間需要一定的等待時間,以防止軋制過程中發(fā)生不可控的形變;②不同板坯兩個軋制階段的加工時間和等待時間均不相同,為了提高軋機利用率,充分利用粗軋和精軋間的等待時間,企業(yè)通常會設計調(diào)度策略安排兩塊板坯作為一組進行軋制,即如果相鄰板坯滿足成組軋制的條件,會在第一塊板坯完成粗軋后,安排第二塊板坯進入軋機進行粗軋;待第二塊板坯粗軋完成且達到第一塊板坯規(guī)定的等待時間后,第一塊板坯重新進入軋機完成精軋操作,隨后第二塊板坯再次進入軋機執(zhí)行精軋操作。若相鄰板坯不滿足成組軋制的條件,則無法進行成組軋制,只能逐一加工。

圖1 寬厚軋制工藝流程

若將板坯視為工件,整個軋制過程可視為一類特殊的單機調(diào)度問題,且存在以下調(diào)度特征:①工件需分階段重復進入同一臺機器加工,加工過程具有可重入性;②不同階段間存在固定的等待時間,工件在等待期間可暫時釋放機器,達到規(guī)定等待時間后必須馬上進入機器;③對于相鄰加工的兩個工件,如果滿足成組加工的條件,可以安排其成組加工。綜上,該問題可抽象為一類具有可重入和成組加工特征(本文將其定義為成組可重入特征)的單機調(diào)度問題,通過確定工件間的調(diào)度順序、以及相鄰工件是否成組加工兩個子問題,以實現(xiàn)系統(tǒng)生產(chǎn)效率的最大化。

可重入調(diào)度在半導體制造、鋼鐵生產(chǎn)等工業(yè)領域具有廣泛應用,已有不少學者對該問題進行了研究。FRIHAT等[1]從皮革工業(yè)中提煉出一類可重入混合流水車間調(diào)度問題,以最大完工時間和拖期成本為目標,分別構建了混合整數(shù)線性規(guī)劃模型和約束規(guī)劃模型;XU等[2]研究了一類可重入置換流水車間調(diào)度問題,以最大完工時間為目標建立了數(shù)學模型,并提出一種文化基因算法;朱艷艷等[3]研究了具有不確定加工時間的可重入調(diào)度問題,以最小化提前懲罰和拖期懲罰為目標構建了混合整數(shù)線性規(guī)劃模型,提出一種變鄰域化學反應優(yōu)化算法;王凱等[4]研究了不確定服務時間的可重入手術系統(tǒng)調(diào)度問題,采用三角模糊函數(shù)來表征各項服務的持續(xù)時長,并以最小化術后恢復平均完成時間為目標,構建了混合整數(shù)線性規(guī)劃模型,提出一種改進的遺傳算法;姚遠遠等[5]針對可重入混合流水車間調(diào)度問題,提出一種改進的多目標灰狼優(yōu)化算法來優(yōu)化完工時間和拖期時間。以上文獻主要針對流水車間展開,針對考慮階段間等待過程的單機可重入調(diào)度問題,尚未發(fā)現(xiàn)相關成果。

另一方面,具有成組加工特征的調(diào)度問題同樣是國內(nèi)外學者關注的焦點:COSTA等[6]研究了一類流水車間環(huán)境下的成組調(diào)度問題,構建了問題的調(diào)度模型,提出一種基于并行優(yōu)化的自適應遺傳算法;LIN和YING[7]提出一種基于LKH規(guī)則和0-1整數(shù)規(guī)劃模型的兩階段元啟發(fā)式算法,通過數(shù)據(jù)實驗證實了算法的有效性;袁帥鵬等[8]考慮了一類帶有階段間運輸?shù)膬呻A段流水車間成組調(diào)度問題,結合問題特征提出一種協(xié)同進化迭代貪婪算法。上述文獻為進一步研究提供了較好的基礎,但已有成果均假定同組內(nèi)的工件需連續(xù)加工,且工件加工過程不允許中斷,這與本文的成組可重入調(diào)度特征具有較大差別。

綜上,盡管可重入調(diào)度和成組調(diào)度方面均已存在較多的研究成果,但已有成果與本文所研究的具有成組可重入特征的調(diào)度問題存在實質(zhì)性不同。實際上,此類具有成組可重入特征的調(diào)度問題不僅存在于鋼鐵企業(yè)的軋制車間,在其他離散制造行業(yè)也同樣存在,因此對該調(diào)度問題展開研究具有重要意義。

1 問題描述與建模

1.1 問題描述

具有成組可重入特征的單機調(diào)度問題描述如下:(1)n個工件J={Ji|i=1,2,…,n}需重復進入同一臺機器依次執(zhí)行兩個階段的加工,加工過程具有可重入特征,記兩個階段的加工時間分別為pi1和pi2;(2)每個工件兩個加工階段間均存在等待時間wi,等待期間工件可暫時釋放機器,但到達等待時間后必須立刻進入機器完成第二階段的加工;(3)由于階段間存在必要的等待時間,為提高設備利用率,如果相鄰的兩個工件滿足成組加工的條件,則允許兩者成組加工,若不滿足成組加工的條件,只能逐一加工,本文將其定義為非成組加工。圖2給出了成組加工和非成組加工的示意圖,顯然工件進行成組加工能夠充分利用設備的空閑時間,進而縮短制造期。對于先后加工的工件Ji和Jj,進行成組加工的充分條件為:wi≥pj1且pi2≤wj。

圖2 成組加工和非成組加工調(diào)度示意圖

根據(jù)三元組表示法,該調(diào)度問題可表示為1|rcrc,wj,group|Cmax,其中1表示單機環(huán)境,rcrc表示可重入特征,wj表示階段間等待時間限制,group表示成組特征,Cmax表示目標函數(shù)。

1.2 數(shù)學模型

為方便描述,表1給出了模型中涉及的符號變量及含義。

表1 符號變量含義

數(shù)學模型如下:

(14)

式(1)為目標函數(shù),表示最小化Cmax;約束(2)和(3)表示工件的序列關系約束;約束(4)表示虛擬工件必須被安排在調(diào)度序列的首位;約束(5)和(6)分別表示兩個工件只有在滿足成組加工條件、且存在緊鄰關系的前提下才有可能執(zhí)行成組加工;約束(7)表示對于任一工件,成組加工的次數(shù)至多為1;約束(8)和(9)分別為各工件第一階段、第二階段的完工時間約束;約束(10)表示相鄰加工的兩個工件未成組加工時的時序關系;約束(11)和(12)限制了相鄰加工的兩個工件執(zhí)行成組加工時的時序關系:后續(xù)工件第一階段的開工時間不小于緊前工件第一階段的完工時間,且第二階段的開工時間不小于緊前工件第二階段的完工時間;約束(13)和(14)分別表示0-1決策變量和連續(xù)變量的取值范圍。

2 問題性質(zhì)分析

本節(jié)將對問題的復雜性進行分析,同時給出了問題最優(yōu)解存在的一些性質(zhì)特征,這些性質(zhì)特征將為后續(xù)算法的設計提供有效支撐。為方便下文描述,首先給出以下定義。

定義1對于問題1|rcrc,wj,group|Cmax的任一調(diào)度實例,如果存在工件與其他工件都不滿足成組加工的條件,則將該工件記為無成組特征工件;反之,如果存在其他工件能與其進行成組加工,則將該工件定義為有成組特征工件。

定理1問題1|rcrc,wj,group|Cmax具有強NP難特性。

定理2對于問題的1|rcrc,wj,group|Cmax任一實例,如果存在無成組特征工件,那么至少存在一個最優(yōu)調(diào)度方案,其中無成組特征工件是連續(xù)加工的,且這些工件加工順序的變化不會影響Cmax值。

定理3對于任一實例,如果兩個工件Ji和Jj滿足成組加工的條件,則Ji和Jj進行成組加工比非成組加工情況下Cmax值的減少量sij至多為min(wi+pi2,pj1+wj) 。

定理4對于任一實例,至少存在一個最優(yōu)調(diào)度,相鄰工件是否成組加工滿足貪婪規(guī)則,貪婪規(guī)則定義為:從給定調(diào)度序列的第1個位置開始,如果當前位置加工的工件與緊后工件滿足成組加工的條件,可直接將其與緊后工件進行成組加工,無需考慮緊后工件及后續(xù)調(diào)度序列的情況。

3 改進的分布估計算法

分布估計算法(Estimation of Distribution Algorithm, EDA)利用概率模型的統(tǒng)計學習取代原有交叉與變異操作,能夠有效挖掘出優(yōu)勢基因區(qū)塊特征,進而產(chǎn)生優(yōu)秀新個體,已被證實在解決調(diào)度類組合優(yōu)化問題方面具有很強的優(yōu)勢[9,10]。本文提出了一種改進的分布估計算法(Improved Estimation of Distribution Algorithm, IEDA),算法實施過程如下。

3.1 編碼解碼策略

為提升算法的搜索效率,IEDA采用置換序列的方式進行編碼,以此確定工件間的加工順序,記為X;然后通過圖3所示的貪婪規(guī)則確定相鄰工件是否進行成組加工,其中Y為輔助向量,Y(i)=1表示X中處于位置i的工件與后續(xù)工件進行成組加工,Y(i)=0則表示兩者不進行成組加工。

圖3 基于貪婪規(guī)則的解碼策略

3.2 初始種群構造

為保證種群的質(zhì)量和多樣性,一個有效的做法是結合問題特征設計啟發(fā)式規(guī)則構造若干高質(zhì)量的人工解,并將其注入初始種群[11]。對于本文問題,我們提出如下啟發(fā)式規(guī)則來構造人工解:首先將待調(diào)度工件按照是否存在成組特征分為兩個子集N1和N2,對于N1中的工件,計算兩兩工件間進行成組加工Cmax時值的減少量sij,得到減少量矩陣S,若不能成組加工則記sij=0;然后按照sij值由大到小的順序依次選擇所對應的工件進行加工,同時將被選擇的工件從N1中刪除,重復上述操作直至N1為空。對于集合N2中的工件,采用隨機方式進行排序。

在構造初始種群時,首先利用上述啟發(fā)式規(guī)則產(chǎn)生第一條染色體,然后采用隨機方式生成剩余染色體。需要說明的是,由于N2中工件的調(diào)度序列不會對Cmax值造成影響,因此在構造初始種群時,N2中的工件序列不會參與后續(xù)的優(yōu)化操作。

3.3 概率模型設置

概率模型是EDA算法的核心。對于調(diào)度類的組合優(yōu)化問題,工件間的前后順序和工件在某一基因位上出現(xiàn)的頻率是決定染色體優(yōu)劣的兩個主要因素。JARBOUI等[12]設計了一種帶有工件區(qū)塊結構特征的概率模型來指導種群進化,即首先按照適應值大小從當前種群中挑選出給定容量Q的優(yōu)勢染色體集,然后按照式(15)生成子代個體:

(15)

其中δij表示當前優(yōu)勢染色體集中工件Ji被安排在位置j上的概率,ηij表示工件Ji在位置j及其之前出現(xiàn)的次數(shù),其值反映了工件前后作業(yè)順序?qū)φ{(diào)度序列的影響;μi′ij表示工件Ji在位置j且Ji′作為其緊前工件上出現(xiàn)的次數(shù),其值反映了工件塊結構的相似性;Qj表示在位置j及其之前尚未參與調(diào)度的工件集。該模型較好的反映了工件間調(diào)度序列以及基因塊的相似性,但并不完全適用本文問題,原因如下:①該模型僅考慮了優(yōu)勢染色體中具有相同基因位的優(yōu)勢區(qū)塊,這會嚴格限制生成后代種群的多樣性,且對于本文問題,優(yōu)勢區(qū)塊并不一定必須處于相同的基因位置;②采用乘法運算作為ηij和μi′ij兩個因素的綜合影響率時,容易導致算法在進化過程中丟失有效信息。為了克服以上缺點,對上述概率模型進行了改進,得到式(16)的概率模型:

(16)

其中δij,ηij和Oj與式(15)相同,λi′i表示優(yōu)勢染色體集中Ji作為Ji′的緊后工件出現(xiàn)的次數(shù),Ji′表示位置j-1處被選中的工件,特別地,當j-1時,我們將λi′i的值定義為0,λi′i值反映了優(yōu)勢染色體集中相似區(qū)塊的重要性。此外,該概率模型采用加法運算作為ηij和λi′i兩個因素的綜合影響率。

在構造子代個體時,對于每一個位置j,根據(jù)式(16)的概率模型從當前個體尚未調(diào)度的工件集中選取工件,進而得到完整的個體。每得到一個新的子代個體,將其與當前種群中最差的個體進行對比,如果優(yōu)于當前種群最差的個體,則替換之,重復上述過程M次,直至生成M個新的個體。

3.4 局部搜索策略

為提升IEDA的局部搜索能力,本節(jié)設計了一種基于最大化減少量的重構策略對每條染色體進行深度搜索:對于任一染色體,首先從子集N1對應的調(diào)度序列中隨機選取并移除1個工件,記為Ji;然后根據(jù)定理3計算Ji與調(diào)度序列中其他工件進行成組加工時的最大減少量,并選取能與Ji成組加工且能得到最大減少量的工件,記為Jj,按照最大減少量的配置關系將Ji重新插在工件Jj緊前或緊后的位置,即如果最大減少量是由Ji和Jj成組加工得到,則將Ji插入Jj的緊前位置,如果是由Ji和Jj成組加工得到,則插入緊后的位置,進而得到一條新的染色體;最后判斷新染色體是否優(yōu)于當前染色體,如果優(yōu)于則替換之。

3.5 算法步驟

本文設計IEDA的實施步驟如下:

步驟1基于啟發(fā)式規(guī)則構造容量為p_size的初始種群;

步驟2采用解碼策略計算種群內(nèi)所有個體的適應值,并按適應值由高到低排序;

步驟3從當前種群中選取前Q條高質(zhì)量的染色體,形成優(yōu)勢染色體集;

步驟4更新概率模型,并基于概率模型生成M個新個體以更新當前種群;

步驟5使用局部搜索策略對當前種群內(nèi)的個體進行深度搜索;

步驟6統(tǒng)計算法的運行時間,判斷是否達到最大運行時間限制,若未達到,轉(zhuǎn)至步驟2;否則,輸出當前最優(yōu)解及其目標值。

4 問題最優(yōu)解下界分析

本節(jié)通過理論分析給出了問題最優(yōu)解的兩個下界。首先,由于機器在同一時刻能且僅能加工1個工件,因此對于任一問題實例,其Cmax至少大于所有工件需要占用機器的時間,因此我們可得到問題的第一個下界:

(17)

其中,N1表示具有成組特征的工件集,N2表示無成組特征的工件集。

另外,任一調(diào)度方案的Cmax值至少大于所有工件Cmax值的上限與最大減少量的差值,因此可得到問題最優(yōu)解的第二個下界:

(18)

5 仿真實驗

5.1 實驗設計

檢驗IEDA算法的有效性,本節(jié)將 IEDA與其他三種元啟發(fā)式算法進行對比。實驗采用離散均勻分布的方式隨機生成實驗數(shù)據(jù),其中工件規(guī)模n={40,60,80,100,150};各工件兩個階段的加工時間和階段間等待時間均為介于a和b之間的離散均勻分布,其中a的取值范圍為[5,50β1],β1∈{0.5,1};b的取值范圍為[a+1,?a(1+β2)」],β2∈{0.5,1}。對于每種工件規(guī)模n、時間參數(shù)β1和β2的組合,隨機生成10組測試算例,共有200組測試算例。采用相對偏差率(Percentage Relative Difference, PRD)作為算法性能評價指標,PRD計算公式為:

PRD=(Cmax(A)-ref)/ref

(19)

其中,Cmax(A)表示當前算例算法A得到的Cmax值,ref為當前測試算例的參考值,計算方式為兩個下界較大的值,即ref=max(LB1,LB2)。

5.2 算法參數(shù)設置

IEDA中的關鍵參數(shù)包括種群規(guī)模p_size,優(yōu)勢群體集容量Q,每次迭代新個體的生成數(shù)量M,本文使用田口實驗設計方法探討了這些參數(shù)對算法性能的影響,結果表明,當p_size=30,Q=10,M=10時,IEDA具有最好的求解性能,因此采用該參數(shù)設置執(zhí)行后續(xù)實驗。

5.3 實驗結果

由于沒有可直接應用于本文問題的相關求解算法,我們選取了三種針對單機調(diào)度問題提出元啟發(fā)式算法,分別為JARBOUI等[12]中的EDA算法(記為EDA_1)、SALAMA和SRINIVAS[13]中的嵌套變鄰域搜索的模擬退火算法(Simulation Annealing, SA)和WANG等[14]中的離散人工蜂群算法(Discrete Artificial Bee Colony,DABC),三種算法均采用原文推薦的參數(shù)設置。針對200組測試算例,將四種對比算法的最大運行時間均設置為n秒,計算每組實驗下10組算例的PRD均值和最大值,結果如表2所示。

表2 四種算法PRD均值(Mean)、最大值(Max)統(tǒng)計結果

由表2可以看出,對于20組測試實驗,IEDA算法的PRD均值全部低于其他三種對比算法,且其總體PRD均值僅為3.16%,明顯低于EDA_1、SA和DABC,這說明針對本文問題,IEDA算法的求解質(zhì)量要優(yōu)于其他三種算法。此外,20組實驗IEDA算法求得的PRD最大值也全部低于其他三種算法,表明IEDA在獲得較優(yōu)解的同時,求解性能也相對穩(wěn)定。與EDA_1相比,所有測試算例下IEDA算法的總體PRD均值降低了15.28%,PRD最大值降低了17.58%,這證實了IEDA中對概率模型的改進是有效的。此外,20組測實驗四種算法求得的PRD最大值僅為 9.19%,非常接近于本文提出的下界值LBmax,這說明本文給出的兩個問題最優(yōu)解下界能夠較好的評估算法的性能。

為進一步檢驗四種算法在收斂速度方面的差異性,以n=100的樣本數(shù)據(jù)為例,隨機選取一次實驗結果,繪制了四種算法的收斂曲線,結果如圖4所示。由該收斂曲線可以直觀看出,IEDA具有更好的收斂性。此外,為檢驗四種算法在不同時間參數(shù)配置下求解性能的差異性,根據(jù)實驗結果匯總了β1和β2取不同值時四種算法PRD均值的差異性,并對其進行95%的置信區(qū)間分析,結果如圖5所示。由圖5可以看出,對于不同的時間參數(shù)配置,IEDA算法均能獲得較低的PRD均值,這進一步證實了IEDA的有效性。

圖4 四種算法收斂曲線對比

圖5 不同時間參數(shù)PRD均值95%置信區(qū)間

綜上,可得出結論,針對本文問題,IEDA算法的求解質(zhì)量要優(yōu)于其他三種對比算法。

6 結語

本文研究了一類具有成組可重入特征的單機調(diào)度問題,該問題具有較為廣泛的工業(yè)應用背景,但尚未發(fā)現(xiàn)相關研究成果。針對此調(diào)度問題,首先構建了混合整數(shù)線性規(guī)劃模型,然后證明了問題的復雜性和最優(yōu)解存在的性質(zhì)特征,隨后提出一種改進的分布估計算法,并給出了問題最優(yōu)解的兩個下界。最后通過數(shù)據(jù)實驗證實了所提算法的有效性。研究成果能夠為鋼鐵生產(chǎn)等制造企業(yè)解決相應調(diào)度問題提供有效的理論支撐。本文只研究了兩個工件進行成組加工的情形,實際工業(yè)生產(chǎn)中存在三個甚至多個工件進行成組加工的情況,下一步將進一步研究多個工件成組加工的調(diào)度問題,并對問題的性質(zhì)特征進行分析,進而設計更為高效的求解算法。