曾艾婧，劉永姜，孟小玲，溫海駿，邵延君

（中北大學，太原 030051）

0 引言

武器裝備對于戰(zhàn)爭來說尤為重要，一個國家的軍事和社會發(fā)展水平均可以通過武器的發(fā)展和管理來反映［1］。而武器裝備使用一定期限后，就會造成一些零部件的嚴重損傷，導致武器裝備的性能指標有所降低，許多裝備都將到壽或被替代，那么就需要對戰(zhàn)后武器裝備進行回收再制造處理［2］。車間調(diào)度是對戰(zhàn)后武器裝備回收再制造的重要一步，對戰(zhàn)損的武器裝備進行高效的車間調(diào)度不僅可以提高生產(chǎn)設備的利用率，而且可以大大縮短裝備的交貨期，甚至會影響到軍事裝備的發(fā)展和戰(zhàn)斗力的提高等重大軍事和經(jīng)濟問題［3］。因此，研究戰(zhàn)后武器裝備車間調(diào)度問題具有重要的現(xiàn)實意義。

GA 方法被認為是解決JSP 問題最有效的進化算法之一，目前許多國內(nèi)外學者已對使用遺傳算法進行車間調(diào)度有了一定的研究。M.Kamrul Hasan［4］等人在研究車間調(diào)度問題時，對傳統(tǒng)的遺傳算法進行改善，通過設置一些優(yōu)先規(guī)則，來減少更換裝備的時間間隙，提高了算法的性能。鞠錄巖［5-6］等人基于非支配排序遺傳算法，提出了一種改進非劣前沿分級的方法，并采用了精英保留策略，該方法不但繼承了遺傳算法全局搜索能力還防止了提早陷入局部最優(yōu)。葉婉秋［7］等人針對不確定的生產(chǎn)環(huán)境，提出了遺傳算法與RL 結合的車間調(diào)度算法，該算法采用了自適應交叉而獲得較優(yōu)的交叉率，使得算法性能有所提高。曹慶奎［8-9］等人提出一種模擬退火與遺傳算法相結合的算法來解決車間調(diào)度問題，該算法利用遺傳算法收斂較快的優(yōu)點克服了模擬退火算法收斂較慢的問題，進而提高了算法的性能。在現(xiàn)有的文獻中，通過尋求遺傳算法最優(yōu)的參數(shù)組合，來改善戰(zhàn)后武器裝備車間調(diào)度的研究還不夠全面，需要進一步的探討。

基于此，本文采用響應面法（Response surface method，RSM）來尋求遺傳算法的最優(yōu)參數(shù)組合。選取遺傳算法中交叉率、變異率、個體數(shù)目、迭代次數(shù)這4 個關鍵參數(shù)，根據(jù)中心復合實驗設計得到實驗方案，利用MATLAB 仿真軟件對每種方案進行仿真，得出每種方案下的最小完成工時，在此基礎上進行響應面分析，建立這4 個關鍵參數(shù)對遺傳算法車間調(diào)度的響應函數(shù)，并考慮參數(shù)之間的交互作用對仿真結果的影響，以尋求使得調(diào)度達到最小完成工時的最優(yōu)參數(shù)組合。

1 問題描述與模型建立

1.1 問題描述

對戰(zhàn)損的武器裝備進行再制造維修車間調(diào)度的問題可描述為：n 臺戰(zhàn)后武器裝備需在m 臺機器上進行再制造維修，每個裝備都不只有一道工序，各工序的加工順序是設定好的，同一工序能在幾臺不同的機器上加工且不同機器上的加工時間也不相同。通過給每個工序安排合適的加工機器，并確定每臺機器上對應工序的加工順序，使得戰(zhàn)后武器裝備再制造維修時間最短。為了方便建立模型和求解，該問題還應滿足以下約束：1）每個回收裝備都擁有相同的優(yōu)先級；2）各裝備所有工序間的先后順序已知；3）同一裝備的待加工工序必須是在它前面的工序加工完后才能開始加工；4）每臺機器上同一時間有且只能加工一道工序；5）每道工序一旦開始加工就不能中途暫停；6）各機器上相鄰的兩個加工工序之間切換時間為零。

對該問題進行建模，建模所引入的符號如下：

i：裝備號，i=1，2，3，…，n

j：工序號，j=1，2，3，…，n

k：機器號，k=1，2，3，…，n

tik：裝備i 在機器k 上的加工時間

Cik：裝備i 在機器k 上的完工時間

本文采用的是6 臺武器裝備，每臺裝備6 道工序，將其安排在10 臺機器上進行再制造維修的車間調(diào)度問題。該車間調(diào)度問題描述如表1、表2 所示。

1.2 模型建立

對于戰(zhàn)后武器裝備車間調(diào)度問題的求解就是要獲取一種調(diào)度方法，使得對其再制造維修的總作業(yè)時間最短。戰(zhàn)后武器裝備再制造車間調(diào)度的模型如下：

表1 加工工序可選機器

表2 工序加工時間

模型中式（1）表示把調(diào)度的總作業(yè)時間最短作為優(yōu)化目標；式（2）為同一裝備在機器上的加工順序的約束關系；式（3）表示同一機器上各個裝備加工順序的約束關系，A 為充分大的正數(shù)；式（4）表示裝備的完工時間為最后一臺機器上的完工時間；式（5）為非負約束；式（6）和式（7）為機器順序約束和裝備順序約束系數(shù)。

1.3 算法設計

1.3.1 染色體

1.3.2 適應度函數(shù)

將全部回收裝備的總完成時間作為染色體的適應度值，其函數(shù)為：

1.3.3 選擇操作

對染色體進行選擇時是采用輪盤賭法，根據(jù)染色體的適應度值進行選擇，染色體被選中的概率是適應度值的倒數(shù)。

1.3.4 交叉操作

基于兩層編碼進行交叉操作時，只對染色體的前半部分進行交叉。交叉后，由于工序發(fā)生了改變，所以要用交叉后缺少的工序來替換交叉后多余的工序，最后按交叉前工序所對應的加工機器來調(diào)整后半部分的染色體。

1.3.5 變異操作

變異操作是將一個隨機選取的個體以一定的概率進行變異，最后把變異前個體對于的加工機器序號對換，從而產(chǎn)生新的個體。

2 實驗設計及結果

響應面法（RSM）［11］是一種將統(tǒng)計和數(shù)學建模結合起來，進行預測的優(yōu)化方法。響應面法具有實驗次數(shù)少、周期短，求得預測回歸模型精度高等優(yōu)勢［12］。它的基本思想是通過中心復合設計實驗得到合理的實驗方案，并通過仿真得到實驗結果，根據(jù)響應變量與響應值之間的擬合關系，得出預測回歸模型，最后通過因素之間的交互作用來尋求最優(yōu)參數(shù)組合［13］。

本文通過對遺傳算法中的關鍵參數(shù)進行優(yōu)化，從而得到更好的調(diào)度方法，使完工時間最小，即選擇的優(yōu)化參數(shù)有：A（交叉率）、B（變異率）、C（個體數(shù)目）、D（迭代次數(shù)），響應值為M（最小完工時間）。為了可以得到理想的回歸模型，本文將采用四因素三水平的中心復合設計實驗方案。根據(jù)文獻［14-15］，確定了4 個優(yōu)化參數(shù)的取值范圍，表3 為遺傳算法關鍵參數(shù)水平編碼表。

表3 遺傳算法關鍵參數(shù)水平編碼表

依據(jù)中心復合實驗設計原理，當選取4 個優(yōu)化參數(shù)時，需要進行30 組實驗。所有實驗方案均通過MATLAB 進行戰(zhàn)后武器裝備車間調(diào)度模擬，將30組最小完工時間作為實驗結果。下頁表4 為具體的實驗方案與實驗結果，其中將每組參數(shù)進行MATLAB 仿真時，每次仿真工序的排列順序并不完全相同，所以本文提到的最小完工時間實則是將每組參數(shù)各仿真10 次后，所求得的平均最小完工時間。

3 實驗結果分析與優(yōu)化

3.1 響應預測模型的建立及顯著性分析

根據(jù)上述實驗結果，借助Design-Expert 數(shù)據(jù)分析軟件對這幾個關鍵因素進行回歸擬合分析，并剔除不顯著的變量，建立的最小完工時間（W）回歸模型如下：

為評價模型的擬合程度，采用方差分析進行分析，方差表中的P 值為顯著性水平，用來說明該實驗因素對優(yōu)化目標的影響水平。對上式進行方差分析，分析結果見表5。

從表5 看出，整體模型的F 值為10.09，P＜0.000 1，表明該模型有較高的擬合度。模型的失擬項反應了模型預測值與實驗測量值不擬合的概率，該模型失擬項P=0.187 7＞0.05，說明失擬項不顯著，表明方程擬合良好。圖1 為W 模型的殘差正態(tài)概率圖，由于每一個點都遵循一個直線模式，沒有違規(guī)跡象，這意味著實際值較高程度地符合了預測值，進一步說明了該回歸模型具有較高的可行性。

圖1 W 殘差正態(tài)概率圖

另一方面，根據(jù)表3 可知，在該模型中，B（變異率）、C（個體數(shù)目）、D（迭代次數(shù)）對最小完成工時影響特別顯著；AC、AD、BD 對最小完成工時影響較為顯著；A（交叉率）、AB、BC、CD（P＞0.1）對最小完成工時不顯著。同時，該模型中各影響因素的均方值反映了其對響應值得影響程度。均方越大，對響應值的影響越大［16］，則由表5 可得，影響最小完成工時（W）的4 個關鍵因素的主次順序為：B＞D＞C＞A。

3.2 參數(shù)的交互作用分析

通過對回歸預測模型進行方程分析，得出不同因素對響應值的影響程度，而響應面圖能反應不同因素之間的交互作用。基于預測模型，得出具有顯著性交互作用項AC、AD、BD，因此，對這3 個一級交互作用進行具體分析。

圖2 交叉率與迭代次數(shù)交互作用響應面圖

圖2 為變異率與個體數(shù)目處于零水平時，交叉率與迭代次數(shù)交互作用響應面圖。由圖2 可得，當?shù)螖?shù)達到50 次時，交叉率從0.4 增加到0.99，最小完工時間縮短幅度最大為3 min 左右；當變異率為0.4 時，迭代次數(shù)從50 次增加到200 次，最小完工時間縮短幅度最大為6 左右，可見這兩個因素對最小完工時間的影響并不同步，迭代次數(shù)的影響更為顯著，由于迭代次數(shù)的增加，最小完工時間明顯縮短，當?shù)螖?shù)達到125 次時，尋找到了最優(yōu)解，算法也已經(jīng)收斂，而當?shù)螖?shù)處于125～200次時，曲面趨于平滑，說明迭代次數(shù)的改變對最小完工時間的影響很小。

表4 實驗方案設計與結

表5 最短加工時間回歸模型方差分析

圖3 為變異率與迭代次數(shù)處于零水平時，交叉率與個體數(shù)目交互作用響應面圖。圖3 直觀地給出了最小完工時間隨交叉率和個體數(shù)目變化的規(guī)律，由圖3 可看出，隨著個體數(shù)目的增加，最小完工時間的變化幅度大于隨交叉率變化的變化幅度，因此，個體數(shù)目的影響更為顯著。個體數(shù)目影響顯著是因為隨個體數(shù)目的不斷增大，算法搜索到最優(yōu)值的概率也會增大，即全局搜索能力增強，而且，在對最優(yōu)解進行搜索時，最優(yōu)解可以在較少的代數(shù)中被找到，那么尋找到最小加工時間也會縮短。

圖3 交叉率與個體數(shù)目交互作用響應圖

圖4 為交叉率與迭代次數(shù)處于零水平時，變異率與個體數(shù)目交互作用響應圖。由圖4 可清晰地看出，當變異率為0.1 時，個體數(shù)目從40 增大到100，最小完工時間縮短幅度最大為2 min 左右；當個體數(shù)目為40 時，變異率從0.000 1 增加到0.1，最小完工時間縮短幅度最大為4 左右，可見變異率為主要影響因素。最小完工時間隨變異率的增大而縮短，這是因為變異率較小時新個體的出現(xiàn)少，這就很難尋找到最小完工時間，當變異率到達0.1 左右時，得到了最小完工時間。

圖4 變異率與個體數(shù)目交互作用響應圖

3.3 最優(yōu)參數(shù)模擬驗證

采用Design-Expert 軟件中的優(yōu)化功能Numer ical 對遺傳算法車間調(diào)度的關鍵參數(shù)進行優(yōu)化，設計優(yōu)化條件為調(diào)度完工時間最小。當算法的性能達到最好，即調(diào)度完工時間最小時，各關鍵參數(shù)的取值為：交叉率（A）為0.99，變異率（B）為0.1，迭代次數(shù)（C）為131 次，個體數(shù)目（D）為77 個，此時的最小完工時間W=43.881 9 min。將優(yōu)化結果進行模擬仿真，得到的最短完工時間為45 min，相對誤差為2.5%，說明該回歸模型的預測精度是較高的，即采用響應面法對遺傳算法車間調(diào)度進行優(yōu)化分析是可行的，具有實用價值。

將優(yōu)化前后的結果進行對比可得：運用響應面法對遺傳算法關鍵參數(shù)進行優(yōu)化后，戰(zhàn)后武器裝備調(diào)度的最小完工時間明顯縮短。表6 為算法優(yōu)化前后性能的對比，由表6 可以看出，優(yōu)化后車間調(diào)度的效率比優(yōu)化前提高了13.46 %。圖5 與圖6 分別為優(yōu)化前后的算法迭代過程圖與加工順序甘特圖。

表6 算法優(yōu)化前后對比

圖5 優(yōu)化前算法迭代過程圖與加工順序甘特圖

圖6 優(yōu)化后算法迭代過程圖與加工順序甘特圖

4 結論

本文針對戰(zhàn)后武器裝備再制造遺傳算法車間調(diào)度基于響應面分析法對交叉率、變異率、個體數(shù)目、迭代次數(shù)4 個關鍵參數(shù)進行優(yōu)化研究，并分析了它們之間的交互作用對最小完工時間（W）的影響，最后建立相應的回歸預測模型。主要結論如下：

1）通過方差分析以及響應面圖得出了在遺傳算法車間調(diào)度中，對最小完工時間的影響顯著性從大到小依次為變異率、個體數(shù)目、迭代次數(shù)、交叉率。而且優(yōu)化變量之間存在著交互作用，交叉率與迭代次數(shù)的交互作用，交叉率與個體數(shù)目的交互作用以及變異率與個體數(shù)目的交互作用的影響比較顯著。

2）基于響應面分析獲得考慮交互作用下的最優(yōu)參數(shù)組合為：交叉率=0.99，變異率=0.1，個體數(shù)目=77 個，迭代次數(shù)=131 次。

3）本文以戰(zhàn)后武器裝備為背景，對戰(zhàn)后損傷的武器裝備進行遺傳算法車間調(diào)度，并利用響應面分析法對遺傳算法關鍵參數(shù)進行優(yōu)化，最終得到最優(yōu)參數(shù)組合，此研究對于更多戰(zhàn)后武器裝備車間調(diào)度優(yōu)化具有參考作用。