張 偉

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

0 引言

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

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

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

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

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

流水車間調(diào)度問題通常描述如下：n(w1,w2,…,wn)個產(chǎn)品在m(M1,M2,…,Mm)臺機器上進行生產(chǎn)，每個產(chǎn)品都要進行p道工序的生產(chǎn)，每臺設(shè)備分配不同的工序進行生產(chǎn).第i個產(chǎn)品的第j道工序表示為Rij，第u個產(chǎn)品的第j道工序表示為Ruj，n個產(chǎn)品的p道工序具有一樣的加工路徑，即不同產(chǎn)品的相同工序是在相同的機器上生產(chǎn)，表示為M(Rij)=M(Ruj)，其中i≠u，i，u=1,…,n；j=1,…,p.Rij被分配在設(shè)備Mg(g=1,2,…,m)上進行生產(chǎn)，則其生產(chǎn)時間表示為Tijg.在一般流水車間調(diào)度問題中，一臺設(shè)備被唯一分配一道工序進行生產(chǎn)，生產(chǎn)設(shè)備不能挑選，即p=m.已知每臺設(shè)備上生產(chǎn)產(chǎn)品的的時間，要求明確設(shè)備上生產(chǎn)產(chǎn)品的次序，其目的是獲得多目標函數(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)品訂單的時間預(yù)期，本文考慮以使最大完工時間f1=Cmax、總流程時間f2=Ctotal和總拖期時間f3=Detotal最小的優(yōu)化目標，即f=min(f1,f2,f3).其中：

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

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

(5)

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

(6)

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

(7)

其中：

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

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

2.1 編碼

在流水車間調(diào)度問題中，產(chǎn)品在機器上加工路徑相同，不同工序在不同的機器上進行加工，因而算法選擇采用基于產(chǎn)品的編碼方式，即n個產(chǎn)品排列組合生成染色體，每條染色體中產(chǎn)品的先后次序代表一種調(diào)度信息.例如，7個產(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進行非支配排序是為了獲取種群中支配個體i的非支配數(shù)ni和被個體i支配的支配集Pi.其詳細實施過程如下：

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

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

Frank=Frank∪{i}.

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

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

2.3 擁擠距離

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

(8)

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

2.4 選擇

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

2.5 交叉

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

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

2.6 變異

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

圖2 對換變異Fig.2 Swapping mutation

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

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

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

(9)

(10)

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

(11)

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

2.8 精英保留策略

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

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

3 實例

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

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

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

3.2 結(jié)果輸出

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

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

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

4 結(jié)論

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