差異工件并行批調度問題中遺傳算法研究①

楊 棟

(中國科學技術大學 管理學院,合肥 230026)

生產調度問題,就是在有限資源與時間內,最大效率的完成指定的生產目標.關于生產調度問題的研究一直是現今學界研究的熱點.一些學者對單機批調度問題展開了研究.Uzsoy[1]最先考慮了差異工件單機批調度中最小化最大完工時間Cmax的問題,并且證明其為NP-hard類問題.Lee[2]在Uzsoy[1]的研究基礎上,在單機批調度問題中考慮了工件動態到達約束.Mosheiov和Oron[3]與Cheng等[4]均考慮了其他調度目標,其中Mosheiov和Oron[3]考慮了單機批調度中最小化總流經時間問題,而Cheng等[4]考慮了單機批調度中最小化模糊完工時間問題.劉娟和陳華平[5]提出了一種求解單機批調度問題的改進PSO算法,并驗證了算法的性能.吳愁[6]在單機批調度問題研究中考慮了能耗情況.而并行批調度研究是對單機批調度問題的進一步拓展.一些學者對不同算法在并行批調度問題中的應用進行了研究.Damodaran和Chang[7]提出了一些啟發式算法來求解最小化制造跨度并行批調度問題.然而這些算法的局限之處在于,求解大規模工件問題得到的解的質量要弱于一些智能優化算法.郭乘濤和江志斌[8]提出了一種混合型蟻群算法來解決并行批調度中工件動態到達組批難問題;王慶[9]提出了一個混合粒子蜂群算法,并將其運用于并行批調度問題研究之中.程八一等[10]考慮了最小化聯合成本并行批調度問題,并設計了一種多項式時間近似算法.李國臣等[11]和張震等[12]分別考慮了能耗約束和模具約束并行批調度問題.

本文對遺傳算法在差異工件動態到達約束下并行批調度問題中的應用展開了研究.首先根據問題假設建立了一個混合整數規劃模型.采用BF、ERT-LPT規則對工件進行分批排序.然后設計了新的選擇、交叉、變異操作并結合遺傳算法進行求解.

1 問題描述

本文研究了差異工件的并行批調度問題,該問題的具體特征描述如下:

(1)差異工件集合J={1,2,···,n},其中,工件j所需的加工時間為pj,其尺寸為sj;

(2)批處理機器集合K={1,2,···,m},其中所有批處理機器的容量均為C;

(3)工件加工批次集合B={1,2,···,|B|},差異工件分批次加工,且同一批中工件的總尺寸需不超過C;

(4)工件動態到達,工件j的到達時間為rj,工件在到達時間之前不允許加工;

(5)批的加工時間為批中工件最大的加工時間,批的到達時間為批中最晚到達工件的到達時間;

(6)批的加工無法中斷,工件加工不允許搶占;

(7)優化目標是最小化制造周期,即 makespan.

根據上述描述,本研究差異工件的并行批調度問題的數學模型為:

式(1)表示的是本研究數學模型的優化目標;式(2)表示的是一個工件只能分配到一個批次;式(3)表示的是一個批次只能由一個機器進行加工;式(4)表示的是同一批次所加工工件尺寸的容量約束;式(5)表示在機器k上加工的批b的加工時間;式(6)表示在機器k上加工的批b的到達時間;式(7)、式(8)表示的是系統對批的開始加工時間的約束,即工件加工不允許搶占約束,批中工件全部到達之后才能開始加工;式(9)表示批的數量約束;式(10)、式(11)表示的是模型制造跨度的計算方法;式(12)、式(13)則是對兩個0-1變量的描述.

2 遺傳算法在并行批處理機調度中的應用

自1975年Holland教授提出遺傳算法以來,由于遺傳算法所具有的獨特求解復雜的優化問題的優勢,大量學者對遺傳算法的理論研究方向以及應用研究方向展開了深入研究.本文就是對差異工件并行批調度問題中遺傳算法應用方向展開研究的.

2.1 遺傳算法簡介

遺傳算法是通過模擬生物進化過程求得最優解的方法.遺傳算法一般計算流程如圖1所示.

圖1 遺傳算法計算流程圖

2.2 編碼與分批排序策略

常見用來求解批調度問題的編碼方式有兩種:基于批和基于工件序列.本文采用基于工件序列的編碼方式,即用一組1～n的數字排列代表一個可行解,如表1所示.

表1 基于工件序列的編碼方式

不同的排列中工件的位置不同,根據后面提出的調度策略可以生成不同的調度方案.

分批與排序是批調度中最重要的兩個決策過程,決策的好壞直接影響解的質量.本文考慮采用BF規則進行分批,采用ERT-LPT規則安排批在機器上的加工順序.兩種規則的具體實現步驟如下:

BF規則:

(1)給定一個工件序列;

(2)選擇序列中第一個工件,在所有批中查找能容納該工件且剩余容量最小的批,并將該工件加入到該批中;否則,新建一個批并將該工件加入到新批中;

(3)重復步驟2,直到所有工件完成分批.

ERT-LPT規則:

(1)計算所有批的到達時間、加工時間.批的到達時間為批中最晚到達工件的到達時間,批的加工時間是批中工件最大的加工時間;

(2)將批按到達時間的先后順序排列,若有多個批的到達時間相同,則按照批的加工時間長短順序進一步排列;

(3)選擇當前處于空閑的狀態的機器,將批序列中首個批次安排在該機器上加工;

(4)重復步驟(3),直到所有批調度完成,最后計算makespan.

2.3 面向并行機批調度問題的遺傳算法

遺傳算法是基于種群的進化算法,通過染色體的選擇、交叉、變異操作生成新一代種群,然后在整個解空間迭代優化尋找最優解.Damodaran等[13]提出了一種遺傳算法求解單機批調度問題.本文在此基礎上,考慮新的選擇、交叉、變異算子結合遺傳算法對并行批處理機調度問題進行求解.

(1)選擇

選擇操作是首先尋找適應度較高的個體作為母本,適應度用來評價個體的優劣程度.根據前文提出的BF、ERT-LPT規則可以計算出個體的makespan值.本文中選定以下公式作為適應度函數:

選取指數函數作為適應度函數,是因為在公式中采用指數函數可以提高算法的收斂速度[14].

然后基于比例選擇的方式挑選優勢個體,其中優勢個體選擇概率為:

其中,pop為當代種群.顯然,個體適應度越大,被選擇的幾率越大.

(2)交叉

交叉操作是遺傳算法中生成子代種群最有效、最直接的方法.好的交叉策略能夠提高算法的搜索能力,節省運算時間.常見的交叉操作有單點交叉、雙點交叉.本文通過利用一組隨機浮點數組實現一種新的交叉方式,具體如圖2所示.

圖2 交叉操作

圖2中,我們先挑選工件規模為8的兩個個體作為母本,分別是:個體1[7,5,3,2,1,8,4,6]、個體2[3,2,7,8,1,6,4,5].然后隨機生成一組浮點數組[0.1,0.8,0.4,0.6,0.2,0.7,0.3,0.9].我們設交叉概率pc=0.5,對于個體1來說,當pj＞pc時,子代保留個體1的基因特征,其余位置上的工件我們根據個體2中這些工件的相對位置來決定相應的次序.如此我們可以得到這樣一個子代個體,它的2、4、6、8號位置上的工件和個體1一致,為 5、2、8、6;它的 1、3、5、7號位置上的工件和個體2一致,為3、7、1、4.最后,得到一個子代個體[3,5,7,2,1,8,4,6].

(3)變異

生物在遺傳過程中,難免會發生變異.遺傳算法中同樣引入了這種思想.對于新生成的個體,設變異概率為pm,當隨機數rand＜pm時,我們隨機交換個體中兩個位置的工件,以此作為變異操作.

綜上所述,本文將以上3種遺傳操作嵌入到遺傳算法中,并結合上文提出的啟發式算法來對并行批處理機調度問題求解,算法框架如表2所示.

表2 算法框架

3 仿真實驗設計與分析

3.1 仿真實驗設計

本文根據吳愁[6]提出的方法生成隨機算例.算例規模從5個角度進行劃分:工件數量、工件尺寸、加工時間、到達時間和機器數量.我們考慮了規模分別為10、20、30、40、50、60、70、80、90、100 的差異工件算例,工件尺寸從[1,10]隨機生成,加工時間從離散均勻隨機分布[8,15]中產生,機器數量設置為2,工件的到達從[0,R]中生成,其中實驗中機器容量均設為20.算例規模如表3所示.

表3 算例規模

為了比較算法的性能,我們將提出的算法和粒子群算法(PSO)作了實驗對比,同時對于每個算例,首先使用BFLPT-ERTLPT(以下簡稱BFLPT)啟發式算法進行了求解,BFLPT的實驗結果也納入到實驗對比當中.每個算例運行5次取平均值.所有算法都由Matlab實現,實驗環境為4 G RAM,2.3 GHz的Windows7電腦.

3.2 實驗結果分析

實驗結果如表4所示,遺傳算法GA與粒子群算法PSO結果中均包含解的質量與運算時間.而由于BFLPT算法的運算時間很短暫,不具有對比性,所以并沒有在結果表中列出.表4中第7列與第8列分別表示的是遺傳算法與PSO以及BFLPT算法解的質量對比,其計算方式為:

表4 結果比較

從表4中我們可以看出遺傳算法GA的運行時間大多數情況都小于粒子群算法PSO的運行時間.圖3是表4中第2列、第4列與第6列結果對比折線圖.從圖3中我們可以清晰的觀察到遺傳算法GA與其他兩種算法解的質量之間的對比情況.圖4是表4中第7列與第8列結果改進柱狀圖.從圖4中我們可以清晰的觀察到遺傳算法GA與其他兩種算法解的質量改進程度.如圖3與圖4所示,隨著工件規模的逐漸增大,遺傳算法GA較之其他兩種算法的優勢變得十分明顯.

圖3 不同工件規模下解的質量

圖4 不同工件規模下解的質量改進

4 結論與展望

本文研究了遺傳算法在考慮差異工件的并行批處理機調度中的應用問題.首先提出了一個數學規劃模型,并采用BF規則對工件進行分批,采用ERT-LPT規則將批分配在機器上加工.我們提出了一種基于隨機浮點數組的交叉操作,并將其嵌入到遺傳算法進行求解.實驗結果表明,我們提出的算法不論是在解的質量上還是運行時間上,相比PSO算法都具有很大的優勢,尤其是在大規模工件算例中優勢會更加明顯.

未來的研究可以考慮更復雜的生產加工模型,例如多階段流水車間、柔性車間等;也可以研究其他的一些優化目標,例如最大延時時間、延遲工件數等.