改進(jìn)的自適應(yīng)NSGA-II求解多目標(biāo)流水車間調(diào)度問題

張 偉

(福建船政交通職業(yè)學(xué)院通用航空產(chǎn)業(yè)學(xué)院，福建福州 350007)

0 引言

針對流水車間調(diào)度問題，調(diào)度問題學(xué)者Johnson[1]起先于1954年發(fā)表行之有效的算法，至此許多學(xué)者紛紛加入研究流水車間調(diào)度問題行列，取得了大量的研究成果.其中多是關(guān)注解決單目標(biāo)問題，即構(gòu)建最大完工時(shí)間最小為優(yōu)化目標(biāo)模型[2,3]，除此之外，還有最小化最大延遲時(shí)間[4]和總流程時(shí)間[5]等，它們是衡量生產(chǎn)經(jīng)濟(jì)效益、關(guān)乎調(diào)度成本的重要指標(biāo).可是面對競爭越來越激烈的產(chǎn)品制造行業(yè)，經(jīng)營者往往要思量兩個(gè)及以上優(yōu)化目標(biāo)，而這些目標(biāo)之間存在矛盾關(guān)系.從而，在流水車間調(diào)度中琢磨其多目標(biāo)問題就顯得越有工程價(jià)值.

宋存利[3]設(shè)計(jì)了一種改進(jìn)貪婪遺傳算法，應(yīng)用逆序解碼和正序解碼、貪婪交叉算子、貪婪變異算子，用于改善最大完成時(shí)間目標(biāo)，使其達(dá)到最小.王宇等[6]構(gòu)思了實(shí)數(shù)編碼、差分進(jìn)化變異、混合采樣的多目標(biāo)差分進(jìn)化算法，用以最小化最大拖期和最大完工時(shí)間.張聞強(qiáng)等[7]提出一種快速多目標(biāo)混合進(jìn)化算法，用以解決雙目標(biāo)的流水車間調(diào)度問題，為使最大完工時(shí)間和總流經(jīng)時(shí)間最小并取得最佳.羅哲[8]設(shè)想了一種混合遺傳算法，通過灰熵并行關(guān)聯(lián)度作為算法適應(yīng)值挑選子代，并建立Pareto外部檔案、使用Pareto排序和擁擠距離計(jì)算，用以在流水車間調(diào)度問題中優(yōu)化最大拖期時(shí)間、總流程時(shí)間和最大完成時(shí)間三個(gè)目標(biāo).

基于以上文獻(xiàn)分析，許多學(xué)者探究的重點(diǎn)是兩個(gè)目標(biāo)的優(yōu)化問題，也有少部分關(guān)注三個(gè)目標(biāo)優(yōu)化問題的鉆研，并且研究成果多數(shù)是通過多目標(biāo)進(jìn)化算法求得.因此，本文按照某企業(yè)流水車間的一條實(shí)際生產(chǎn)線調(diào)度環(huán)境，綜合考慮了最大完工時(shí)間、總拖期時(shí)間和總流程時(shí)間最小三個(gè)目標(biāo)并為此構(gòu)建調(diào)度模型，通過帶有自適應(yīng)參數(shù)調(diào)節(jié)改進(jìn)的NSGA-II算法在調(diào)度解空間找尋Pareto解集，將數(shù)據(jù)進(jìn)行加權(quán)處理挑選出中意的調(diào)度方案，表明該算法在解決多目標(biāo)流水車間調(diào)度問題上是可行的、有效的.

1 流水車間調(diào)度問題描述和數(shù)學(xué)模型構(gòu)建

1.1 流水車間調(diào)度問題描述

流水車間調(diào)度問題通常描述如下：n(w1,w2,…,wn)個(gè)產(chǎn)品在m(M1,M2,…,Mm)臺(tái)機(jī)器上進(jìn)行生產(chǎn)，每個(gè)產(chǎn)品都要進(jìn)行p道工序的生產(chǎn)，每臺(tái)設(shè)備分配不同的工序進(jìn)行生產(chǎn).第i個(gè)產(chǎn)品的第j道工序表示為Rij，第u個(gè)產(chǎn)品的第j道工序表示為Ruj，n個(gè)產(chǎn)品的p道工序具有一樣的加工路徑，即不同產(chǎn)品的相同工序是在相同的機(jī)器上生產(chǎn)，表示為M(Rij)=M(Ruj)，其中i≠u，i，u=1,…,n；j=1,…,p.Rij被分配在設(shè)備Mg(g=1,2,…,m)上進(jìn)行生產(chǎn)，則其生產(chǎn)時(shí)間表示為Tijg.在一般流水車間調(diào)度問題中，一臺(tái)設(shè)備被唯一分配一道工序進(jìn)行生產(chǎn)，生產(chǎn)設(shè)備不能挑選，即p=m.已知每臺(tái)設(shè)備上生產(chǎn)產(chǎn)品的的時(shí)間，要求明確設(shè)備上生產(chǎn)產(chǎn)品的次序，其目的是獲得多目標(biāo)函數(shù)的Pareto前沿.而且流水車間調(diào)度問題又符合普遍性的約束要求與設(shè)想[9].

1.2 數(shù)學(xué)模型構(gòu)建

Cw11=Tw11

(1)

Cw1g=Cw1g-1+Tw1g;g=2,...,m

(2)

Cwi1=Cwi-11+Twi1;i=2,...,n

(3)

Cwig=max(Cwi-1g;Cwig-1)+Twig;i=2,...,n;g=2,...,m

(4)

鑒于流水車間的生產(chǎn)效率最大、資源配置合理和庫存最小以及符合用戶對產(chǎn)品訂單的時(shí)間預(yù)期，本文考慮以使最大完工時(shí)間f1=Cmax、總流程時(shí)間f2=Ctotal和總拖期時(shí)間f3=Detotal最小的優(yōu)化目標(biāo)，即f=min(f1,f2,f3).其中：

(1)最大完工時(shí)間相應(yīng)的目標(biāo)函數(shù)Cmax：

Cmax=max(Cwim|i∈1,2,...,n)

(5)

(2)總流程時(shí)間相應(yīng)的目標(biāo)函數(shù)Ctotal：

(6)

(3)總拖期時(shí)間相應(yīng)的目標(biāo)函數(shù)Detotal：

(7)

其中：

2 自適應(yīng)參數(shù)的NSGA-II算法設(shè)計(jì)

關(guān)于多目標(biāo)優(yōu)化問題的求解，呈現(xiàn)出許多多目標(biāo)優(yōu)化算法，有模擬退火算法、粒子群優(yōu)化算法、遺傳算法等.模擬退火算法采取冷卻表進(jìn)行探尋，模擬物理學(xué)中金屬的平緩冷卻過程規(guī)律，通常選取變權(quán)重措施開展目標(biāo)函數(shù)加權(quán)組合，其實(shí)現(xiàn)過程慢且收斂能力尚待加強(qiáng).粒子群優(yōu)化算法采取類似于蜜蜂采蜜、螞蟻覓食、鳥群捕食等行為的原理，經(jīng)由粒子在探尋空間追隨最佳粒子進(jìn)行探尋，如果該粒子趕上粒子群目前的最佳粒子，出現(xiàn)種群多樣性會(huì)丟失、早熟問題，同時(shí)如果粒子群的目前最佳值和一個(gè)粒子的目前位置與該粒子的目前最佳值一致，致使算法無法收斂.多目標(biāo)遺傳算法(MOGA)在Pareto支配等級(jí)基礎(chǔ)上可以獲取分布勻稱的適應(yīng)度，其采用適應(yīng)度共享方法可以實(shí)現(xiàn)在選擇壓力適合的條件下維系整個(gè)種群的適應(yīng)度為常數(shù)，然而由Pareto支配關(guān)系確定等級(jí)的方法可能使選擇壓力較大而導(dǎo)致非成熟收斂，如果一樣的目標(biāo)函數(shù)值對應(yīng)于多個(gè)不同的非支配解，MOGA不易找出多個(gè)解.Pareto小生境遺傳算法通過非支配關(guān)系進(jìn)行聯(lián)賽選擇，且通過小生境技術(shù)來共享適應(yīng)值維系種群多樣性，其可以得到不差的Pareto前沿，缺點(diǎn)是比較集大小的揀選與小生境半徑揀選沒有一個(gè)一致的規(guī)范.而帶精英策略的快速非支配排序遺傳算法(NSGA-II)[10]選擇一種快速非支配排序方法，使計(jì)算復(fù)雜度減少；利用擁擠距離和擁擠比較算子獲取勻稱的Pareto前沿，用于維系種群多樣性；提出卓越解保存準(zhǔn)則，將父代中卓越解保存，從而優(yōu)化越恰當(dāng).本文通過NSGA-II算法來處理第1方面提出的多目標(biāo)流水車間調(diào)度問題，采用自適應(yīng)參數(shù)與NSGA-II算法結(jié)合以達(dá)到動(dòng)態(tài)調(diào)節(jié)交叉、變異算子的目的，確保不丟失最佳解.

2.1 編碼

在流水車間調(diào)度問題中，產(chǎn)品在機(jī)器上加工路徑相同，不同工序在不同的機(jī)器上進(jìn)行加工，因而算法選擇采用基于產(chǎn)品的編碼方式，即n個(gè)產(chǎn)品排列組合生成染色體，每條染色體中產(chǎn)品的先后次序代表一種調(diào)度信息.例如，7個(gè)產(chǎn)品在流水生產(chǎn)線上制造加工，假設(shè)一組產(chǎn)品的排列是w7、w1、w2、w3、w4、w6、w5，就體現(xiàn)一種調(diào)度策略W=7，1，2，3，4，6，5.

2.2 Pareto排序

對種群I進(jìn)行非支配排序是為了獲取種群中支配個(gè)體i的非支配數(shù)ni和被個(gè)體i支配的支配集Pi.其詳細(xì)實(shí)施過程如下：

國企面臨的另一重大沖擊來自鄉(xiāng)鎮(zhèn)企業(yè)。當(dāng)時(shí)，鄉(xiāng)鎮(zhèn)企業(yè)在江蘇南部和山東的膠東半島迅速發(fā)展起來，鄉(xiāng)鎮(zhèn)企業(yè)因?yàn)闄C(jī)制靈活在競爭中明顯優(yōu)于國有企業(yè)，并出現(xiàn)了“星期天工程師”現(xiàn)象：國有企業(yè)的技術(shù)人員，星期天到附近鄉(xiāng)鎮(zhèn)企業(yè)“走穴”，進(jìn)行技術(shù)支持。

(1)對比種群中的兩個(gè)個(gè)體i與j，當(dāng)i好于j時(shí)，Pi=Pi∪{j}；當(dāng)i差于j時(shí)，ni=ni+1；如果ni=0，則

Frank=Frank∪{i}.

(2)Pt是目前集合Frank中的每個(gè)個(gè)體t所支配的個(gè)體集合，針對Pt中保存的每個(gè)個(gè)體q，執(zhí)行nq=nq-1步驟，若nq=0，則R=R∪{q}.

(3)非劣等級(jí)rank=1，即Frank=F1是第一非劣等級(jí)的個(gè)體集合，循環(huán)執(zhí)行rank=rank+1，R=Frank步驟，直至種群中全部個(gè)體被非劣排序?yàn)橹?

2.3 擁擠距離

為了維護(hù)種群多樣性，算法定義擁擠距離來確保Pareto解集可以約束到一個(gè)分散勻稱的Pareto前沿.其計(jì)算公式為：

(8)

其中：d(k)distance是第k個(gè)個(gè)體的擁擠距離，f(k+1).e、f(k-1).e分別是第(k+1)、(k-1)個(gè)個(gè)體第e個(gè)目標(biāo)分量的函數(shù)值，femax、femin分別是第e個(gè)目標(biāo)分量的函數(shù)值最大值與最小值.

2.4 選擇

選擇使種群演變朝向Pareto最佳解的方位逼近，以確保Pareto前沿勻稱分散.算法采用二元聯(lián)賽選擇，其原理為隨便遴選兩個(gè)個(gè)體i與j進(jìn)行比較，選擇最優(yōu)的個(gè)體進(jìn)入下一代種群，鑒別個(gè)體i好于j的標(biāo)準(zhǔn)如下：非劣等級(jí)rankj>ranki；或ranki=rankj，而擁擠距離d(i)distance>d(j)distance.

2.5 交叉

交叉是種群演變進(jìn)化的核心算子，它可以擴(kuò)大算法搜索新空間的可能性，但也得考慮演變的約束性問題.交叉算子總是期盼能獲取一些有效的新個(gè)體樣式，卻又能較大程度地保護(hù)代表卓越基因的卓越樣式.本文選用部分匹配交叉，其整體探尋成效較優(yōu)，不輕易陷進(jìn)局部最優(yōu)，確保經(jīng)過遺傳最佳樣式能夠最大程度地得到保留.如圖1所示，依據(jù)I中兩個(gè)父代個(gè)體g1、g2動(dòng)態(tài)獲取的兩個(gè)交叉點(diǎn)以得到一個(gè)匹配段，比如3、5是選定的位置；由選定的位置之間所構(gòu)成的匹配段確定部分映射關(guān)系為4-6、2-5、7-2，將兩個(gè)交叉點(diǎn)之間的染色體部分交換，得到如II中g(shù)1，、g2，；根據(jù)匹配段交叉點(diǎn)之間基因映射關(guān)系，將g1，、g2，交換區(qū)域之外的一樣的基因一一交換，從而獲得III中子代個(gè)體h1、h2.

圖1 部分匹配交叉Fig.1 Partial matching crossover

2.6 變異

變異實(shí)現(xiàn)種群演變收斂進(jìn)程中防止陷入局部最優(yōu)功能，可以增加種群的多樣性.本文選用對換操作變異，通過動(dòng)態(tài)方式在一個(gè)個(gè)體上生成兩個(gè)變異位置，將這兩個(gè)變異位置相應(yīng)的染色體編碼互換.比如2、6是變異的位置，圖2所示為其操作過程.

圖2 對換變異Fig.2 Swapping mutation

2.7 自適應(yīng)參數(shù)調(diào)整策略

采用基于進(jìn)化階段的自適應(yīng)方法作為個(gè)體交叉率與變異率的調(diào)整方法[11].第一，要明確劃分進(jìn)化階段，在同一進(jìn)化階段中進(jìn)行個(gè)體交叉率與變異率設(shè)置，在不同進(jìn)化階段中設(shè)置交叉率和變異與基于進(jìn)化階段的自適應(yīng)方法一樣.當(dāng)進(jìn)化代數(shù)增加時(shí)，不同階段個(gè)體交叉率與變異率呈線性下降走向，直至它在數(shù)值上與下一階段的初始交叉率與變異率相等為止.第二，為了確保在進(jìn)化后期個(gè)體也還有一定的幾率參與進(jìn)化，該方法中的交叉率與變異率會(huì)伴隨進(jìn)化代數(shù)的增加逼近一個(gè)趨近于0但不等于0的值.自適應(yīng)交叉率與變異率的模型的兩個(gè)部分如下：

(1)當(dāng)非支配解個(gè)數(shù)小于10時(shí)，個(gè)體交叉率與變異率的模型為：

(9)

(10)

(2)當(dāng)非支配解的個(gè)數(shù)不小于10時(shí)，該情況下的個(gè)體交叉率模型不變，而變異率的模型為：

(11)

其中：Pc是個(gè)體的交叉率，Pm是個(gè)體的變異率，N是算法的最大迭代次數(shù)，L是個(gè)體的編碼長度.N1=αN，N2=(1-α)N.β是進(jìn)化后期階段交叉率與變異率的調(diào)節(jié)參數(shù)，β∈(0,1].0～N1為算法的進(jìn)化初期階段，N1～N2為算法的進(jìn)化中期階段，N2～N為算法的進(jìn)化后期階段.

2.8 精英保留策略

為了防止父種群中卓越的個(gè)體流失，而直接將其放到子種群中，算法引入精英保留策略，使種群演變收斂得到保證.算法執(zhí)行的過程是：首先生成復(fù)合種群G，它是由父代種群P與子代種群Q組合形成；然后將快速非支配排序和擁擠距離計(jì)算應(yīng)用到復(fù)合種群G中；最后選取卓越的個(gè)體形成新一代種群H，這個(gè)過程在復(fù)合種群G中進(jìn)行.算法的詳細(xì)過程如圖3所示.

圖3 改進(jìn)的自適應(yīng)NSGA-II流程Fig.3 Improved adaptive NSGA-II process

3 實(shí)例

3.1 基礎(chǔ)數(shù)據(jù)

某企業(yè)有一條流水線采用8臺(tái)設(shè)備生產(chǎn)7件產(chǎn)品.鑒于流水車間的生產(chǎn)效率最大、資源配置合理和庫存最小以及符合用戶對產(chǎn)品訂單的時(shí)間預(yù)期，需要考慮以使最大完工時(shí)間、總流程時(shí)間和總拖期時(shí)間最小的優(yōu)化目標(biāo)，從而使產(chǎn)品產(chǎn)能生產(chǎn)最大化，提升經(jīng)濟(jì)收益.已知每個(gè)產(chǎn)品的交貨期如表1所示，每個(gè)產(chǎn)品每道工序的生產(chǎn)時(shí)間如表2所示.運(yùn)用MATLAB R2016a來編寫算法的函數(shù)文件、腳本文件，并通過仿真優(yōu)化獲取幾組較好的產(chǎn)品生產(chǎn)排序.

算法的有關(guān)系數(shù)設(shè)置：種群規(guī)模取400，進(jìn)化代數(shù)取150，α取0.37，β取0.4.

3.2 結(jié)果輸出

運(yùn)行算法程序，輸出獲得如圖4、5、6所示的每個(gè)目標(biāo)函數(shù)的最佳解及其特性追蹤，如圖7所示的Pareto非支配解集.如表3所示為每個(gè)Pareto非劣解的3個(gè)目標(biāo)函數(shù)值及其相應(yīng)的生產(chǎn)排序.

圖4 迭代150次最大完工時(shí)間的最佳解及其特性追蹤Fig.4 The optimal solution and characteristic tracking of the makespan of 150 iterations圖5 迭代150次總拖期時(shí)間的最佳解及其特性追蹤Fig.5 The optimal solution and characteristic tracking of the total tardiness of 150 iterations

圖6 迭代150次總流程時(shí)間的最佳解及其特性追蹤Fig.6 The optimal solution and characteristic tracking of the total flow time of 150 iterations圖7 Pareto非支配解集Fig.7 Pareto nondominant solution set

表3 Pareto非支配解集Tab.3 Pareto nondominant solution set

3.3 結(jié)果分析

由圖4、5、6能夠得出，3個(gè)目標(biāo)函數(shù)的均值靠近最佳解，算法趨向收斂.依據(jù)圖7、表3能夠得出：序號(hào)為2的解的總拖期時(shí)間和總流程時(shí)間對比其余12組解都大很多，但由于其最大完工時(shí)間最小，所以每次迭代都能探尋到該解；序號(hào)6和7的解的最大完工時(shí)間都較小，但其總流程時(shí)間都較大；剩下10組解的3個(gè)目標(biāo)函數(shù)值都較好，且布局比較勻稱.運(yùn)用Pareto非劣解集于流水車間調(diào)度中，生產(chǎn)者可以考慮實(shí)際加工條件下目標(biāo)的主次之分，確定從優(yōu)化所得的結(jié)果中遴選滿意的調(diào)度方案，達(dá)到符合實(shí)際的生產(chǎn)供給目的.比如，對于該企業(yè)的流水線，考慮當(dāng)前最重要的是最小化產(chǎn)品的總拖期時(shí)間，所以對3個(gè)目標(biāo)分別給予0.1、0.7和0.2的權(quán)重，將3個(gè)目標(biāo)進(jìn)行歸一化處理，獲取最好調(diào)度方案是w3,w2,w6,w1,w4,w5,w7.

4 結(jié)論

本文按照流水車間調(diào)度問題的理論與特征，創(chuàng)建以最小化最大完工時(shí)間、總拖期時(shí)間與總流程時(shí)間為優(yōu)化目標(biāo)的調(diào)度模型，同時(shí)結(jié)合某企業(yè)的流水線具體調(diào)度情況，使用帶自適應(yīng)參數(shù)的改進(jìn)NSGA-II算法求解該模型，獲取了比較中意的調(diào)度方案，表明NSGA-II算法在解決多目標(biāo)流水車間調(diào)度問題上是可行的、有效的，并且為企業(yè)提供生產(chǎn)調(diào)度排序舉措?yún)⒖?