王 博，陸寶春

（南京理工大學(xué) 機(jī)械工程學(xué)院，江蘇 南京 210094）

1 引言

長久以來，如何利用生產(chǎn)調(diào)度優(yōu)化技術(shù)提高制造系統(tǒng)生產(chǎn)率、縮短產(chǎn)品加工周期一直是生產(chǎn)制造與管理領(lǐng)域的核心問題。作為傳統(tǒng)作業(yè)車間調(diào)度問題的延伸，柔性作業(yè)車間調(diào)度問題（Flexible Job Shop Scheduling Problem，F(xiàn)JSP）打破了加工設(shè)備唯一性的約束，允許工序在可用設(shè)備集中的任一臺(tái)上加工，更加符合車間生產(chǎn)實(shí)際的同時(shí)也增加了該問題的求解難度[1]。近年來，蟻群算法[2]、免疫算法[3]、禁忌搜索算法[4]以及粒子群算法[5]等智能啟發(fā)式算法越來越多的被用于求解FJSP，并取得較好的效果。

遺傳算法（Genetic Algorithm）由于其穩(wěn)定的計(jì)算性能和突出的全局搜索能力被廣泛用于求解FJSP。但局部尋優(yōu)能力差，易過早收斂的缺點(diǎn)使傳統(tǒng)遺傳算法在求解該問題時(shí)準(zhǔn)確性不高。因此，學(xué)者們不斷地致力于改進(jìn)傳統(tǒng)遺傳算法使其快速準(zhǔn)確地獲得最優(yōu)解。文獻(xiàn)[6]設(shè)計(jì)了一種非支配排序遺傳算法用于提高求解FSJP的尋優(yōu)能力；文獻(xiàn)[7]結(jié)合遺傳算法與瓶頸移動(dòng)法解決柔性車間調(diào)度問題；文獻(xiàn)[8]在免疫算法的基礎(chǔ)上融入遺傳算子提出了一種遺傳免疫算法。

定點(diǎn)擾動(dòng)-遺傳算法（FPD-GA）為了避免算法早熟并增強(qiáng)局部搜索能力，一方面用復(fù)合選擇策略代替比例選擇算子，保證優(yōu)良個(gè)體遺傳的同時(shí)降低劣勢個(gè)體淘汰率，維持了種群的多樣性；另一方面定量分析種群收斂程度[9]，并融合模擬退火算法和免疫算法，設(shè)計(jì)定點(diǎn)擾動(dòng)機(jī)制，避免算法陷入局部最優(yōu)。最后通過實(shí)例驗(yàn)證改進(jìn)算法的可行性。

2 FJSP數(shù)學(xué)模型建立

車間調(diào)度問題可描述為：離散制造車間共有m臺(tái)機(jī)器｛W1，W2，…，WM｝，需完成n個(gè)工件｛J1，J2，…，Jn｝的 p 道工序，每道工序Oij的加工設(shè)備不唯一，并且相同工序在不同設(shè)備上的加工時(shí)間不相同。優(yōu)化調(diào)度的目標(biāo)是為每道工序安排最合適的設(shè)備，并在工序不干涉的前提下規(guī)定各臺(tái)設(shè)備的工件加工次序，使整個(gè)制造系統(tǒng)達(dá)到最佳狀態(tài)。同時(shí)，加工過程中應(yīng)滿足以下約束條件：

（1）在某一時(shí)刻，工件Ji的某道工序Oij只能在指定的機(jī)器Wk上加工，并且加工時(shí)間tijk已知。

（2）不同工件的工序相互獨(dú)立，同一工件的各道工序按規(guī)定的工藝流程依次進(jìn)行。

（3）在t=0時(shí)刻所有設(shè)備可以被使用，所有工件可以被加工。

針對(duì)實(shí)際生產(chǎn)需要，選擇以下目標(biāo)為制造系統(tǒng)的性能指標(biāo)，并構(gòu)建多目標(biāo)適應(yīng)度函數(shù)：

（1）最小化工件最大完工時(shí)間。設(shè)Di為工件Ji的完工時(shí)間，其目標(biāo)函數(shù)可表示為：f1=Min｛Max｛Di，i=1，2，…，n｝｝

（2）最小化設(shè)備最大負(fù)荷。設(shè)Lk為機(jī)器Wk的生產(chǎn)負(fù)荷，采用設(shè)備的工作時(shí)間表述其生產(chǎn)負(fù)荷，該目標(biāo)函數(shù)可表示為：

（3）最大化設(shè)備使用率。最大化設(shè)備使用率在于使設(shè)備負(fù)荷均衡化，采用所有設(shè)備中最大與最小工作時(shí)間的差表述機(jī)床負(fù)荷均衡化：f3=Min（Max（Lk）-Min（Lk））

已有的算法研究中，多目標(biāo)適應(yīng)度函數(shù)的設(shè)計(jì)策略主要有加權(quán)策略、目標(biāo)設(shè)計(jì)策略和非劣解等級(jí)優(yōu)先策略?？紤]到兼顧各個(gè)性能指標(biāo)的同時(shí)盡可能的減小計(jì)算量，采用加權(quán)策略在可行域中尋找最優(yōu)解，并用以上三個(gè)目標(biāo)函數(shù)構(gòu)建多目標(biāo)適應(yīng)度函數(shù)：

F=ω1f1+ω2f2+ω3f3

3 FPD-GA求解FJSP

3.1 FJSP中遺傳算子設(shè)計(jì)

3.1.1 編碼與解碼

對(duì)于柔性車間調(diào)度問題，染色體編碼在反映出工件加工順序的同時(shí)，還要體現(xiàn)各道工序所在的加工設(shè)備，基于工序或操作的單一編碼形式很難實(shí)現(xiàn)該問題的求解。因此采用雙倍染色體編碼形式，即一對(duì)相互關(guān)聯(lián)染色體對(duì)應(yīng)一個(gè)調(diào)度解，其中第一條染色體采用基于工序的編碼，用于確定所有工件各道工序的加工次序，另一條染色體為基于分配機(jī)器的編碼，用于為工序染色體分配加工設(shè)備。通過工序和機(jī)器染色體共同表達(dá)柔性車間的調(diào)度解。一個(gè)（3×5）調(diào)度問題編碼方式，如圖1所示。

圖1 雙倍染色體編碼Fig.1 Form of Double Chromosome Encoding

針對(duì)上述的編碼方式，在解碼時(shí)首先將雙倍染色體解碼為機(jī)器矩陣和加工時(shí)間矩陣，然后按照工序染色體序列，安排每道工序到對(duì)應(yīng)機(jī)器染色體指定機(jī)床的最佳加工時(shí)刻，最終得到調(diào)度解。

3.1.2 交叉算子

交叉操作是通過隨機(jī)交換兩個(gè)個(gè)體的部分基因，從而形成具有更優(yōu)秀基因組合的新個(gè)體的過程。由于編碼的特殊性，為了避免非法解的出現(xiàn)，采用基于染色體對(duì)的多父代交叉操作。具體實(shí)施步驟：（1）將所有工件劃分為兩個(gè)互補(bǔ)的非空子集G1和G2，并在種群中隨機(jī)選取三個(gè)父代個(gè)體 P1、P2、P3；（2）對(duì) P1進(jìn)行順序操作，去除 P1中所有屬于G1的基因信息并用0代替，得到新染色體對(duì)，同理，去除P2中所有屬于G2的基因信息，得到新染色體對(duì)；（3） 對(duì) P3進(jìn)行順序操作，用P3中屬于G1的基因信息按次序替換中的0基因位，得到子代個(gè)體C1；同理得到子代個(gè)體C2。

3.1.3 變異算子

為了保證變異操作后解的可行性，將該操作分為工序染色體變異和機(jī)器染色體變異兩部分。對(duì)工序染色體采取插入式變異：隨機(jī)生成兩個(gè)不同的整數(shù)S1和S2，將第S1位的基因插入到第S2位的基因前，得到新的工序染色體；對(duì)于機(jī)器染色體：遍歷整條染色體，查詢每一個(gè)基因位的取值是否包含在對(duì)應(yīng)工序的可用機(jī)器集內(nèi)，如不包含，則在該可用機(jī)器集內(nèi)隨機(jī)抽取一臺(tái)機(jī)器編號(hào)替換當(dāng)前基因，由此得到可行的機(jī)器染色體。

3.2 遺傳算法的改進(jìn)

在求解柔性制造車間調(diào)度問題時(shí)，采用傳統(tǒng)遺傳算法通常會(huì)出現(xiàn)局部搜索效率低，過早陷入局部收斂等問題。分析出現(xiàn)問題的原因有兩個(gè)：（1）比例算子使個(gè)別優(yōu)勢個(gè)體大量遺傳，導(dǎo)致種群多樣性急劇下降；（2）進(jìn)化后期的種群個(gè)體趨于相似，交叉與變異操作不容易破壞父代個(gè)體性狀，算法難以跳出局部最優(yōu)。

針對(duì)上述分析原因，F(xiàn)PD-GA通過改進(jìn)選擇操作、設(shè)計(jì)定點(diǎn)擾動(dòng)策略兩個(gè)方面改進(jìn)傳統(tǒng)遺傳算法。

3.2.1 復(fù)合選擇策略

傳統(tǒng)遺傳算法采用的比例選擇操作能夠使種群快速地逼近最優(yōu)解，但也淘汰掉了可能包含優(yōu)良基因片段的劣勢個(gè)體，使種群過早的陷入收斂狀態(tài)。為了避免這一現(xiàn)象的發(fā)生，F(xiàn)PD-GA采用精英保留和輪盤賭的復(fù)合選擇策略，在保證優(yōu)良個(gè)體遺傳的同時(shí)降低劣勢個(gè)體淘汰率，維持了種群的多樣性，其步驟：（1）計(jì)算個(gè)體x的適應(yīng)度值Fi和種群整體適應(yīng)度平均值；（2）當(dāng) Fi＜時(shí)，該個(gè)體x被保留；當(dāng)Fi≥時(shí)，以一定概率p接受x，其中p=1/e（Fi-ˉF）；（3）以輪盤賭的方式抽取大于平均適應(yīng)度的個(gè)體，補(bǔ)充種群達(dá)到要求的種群規(guī)模。

3.2.2 定點(diǎn)擾動(dòng)策略

算法進(jìn)化后期，優(yōu)勢個(gè)體大量集中于最優(yōu)解附近，種群進(jìn)入收斂狀態(tài)，但此時(shí)無法判斷種群是否收斂于全局最優(yōu)解，為了避免種群早熟收斂，提出定點(diǎn)擾動(dòng)策略。

定點(diǎn)擾動(dòng)策略的設(shè)計(jì)以模擬退火算法思想為基礎(chǔ)，借鑒了免疫算法的疫苗接種機(jī)制。當(dāng)種群處于收斂狀態(tài)時(shí)，強(qiáng)制改變種群中優(yōu)勢個(gè)體的基因片段，不同于模擬退火算法的隨機(jī)擾動(dòng)，該策略通過計(jì)算優(yōu)勢群體等位基因的相似度，改變指定基因位上的基因，并選擇性地保留擾動(dòng)后的個(gè)體，驅(qū)使群體向最優(yōu)解進(jìn)化。但過于頻繁地定點(diǎn)擾動(dòng)會(huì)干擾正常的進(jìn)化趨勢，不利于算法快速尋優(yōu)，因此，在對(duì)GA收斂狀態(tài)多次分析的基礎(chǔ)上，F(xiàn)PD-GA引入種群收斂度指標(biāo)（其中為小于群體平均適應(yīng)度值的個(gè)體的適應(yīng)度平均值，F(xiàn)min為當(dāng)代種群的最小適應(yīng)度值），用于判斷種群是否進(jìn)入收斂狀態(tài)，并選擇性地觸發(fā)定點(diǎn)擾動(dòng)機(jī)制。

具體步驟：（1）計(jì)算種群收斂度指標(biāo)Δ，當(dāng)Δ小于收斂系數(shù)ε時(shí)，觸發(fā)定點(diǎn)擾動(dòng)機(jī)制；（2）對(duì)所有個(gè)體的適應(yīng)度值從小到大排序，抽取適應(yīng)度值前20%的個(gè)體組成精英群體Q；（3）計(jì)算Q中工序染色體第i個(gè)基因位上等位基因的相似度ηi，即ηi=nmax/nQ（i=1，2，…，np）。其中nmax—染色體第i位上出現(xiàn)頻率最高基因的頻數(shù)；nQ—Q中工序染色體總數(shù)；np—工序染色體基因數(shù)；（4）對(duì)ηi從小到大排序，設(shè)定前r個(gè)基因位為擾動(dòng)基因位，對(duì)工序染色體擾動(dòng)基因位上的基因進(jìn)行位置互換，對(duì)機(jī)器染色體擾動(dòng)基因位上的基因進(jìn)行單點(diǎn)變異；（5）對(duì)擾動(dòng)后的個(gè)體，計(jì)算適應(yīng)度值，若≤Fi，則用擾動(dòng)后的個(gè)體代替原個(gè)體，若＞Fi，以概率 Pt接受擾動(dòng)后的個(gè)體。其中

圖2 FPD-GA流程圖Fig．2 Flow Diagram of FPD-GA

FPD-GA流程圖，如圖2所示。FPD-GA的主要實(shí)現(xiàn)步驟如下：

（1）設(shè)定參數(shù)。設(shè)定種群規(guī)模N，迭代最大次數(shù)T，交叉概率Pc，變異概率 Pm，擾動(dòng)系數(shù) r，收斂系數(shù) ε，適應(yīng)度函數(shù)權(quán)重 ω1、ω2、ω3；

（2）初始化種群。隨機(jī)產(chǎn)生由工序染色體和機(jī)器染色體組成的種群個(gè)體，并設(shè)迭代次數(shù)t=0；

（3）適應(yīng)度值評(píng)價(jià)。計(jì)算每個(gè)個(gè)體的適應(yīng)度值Fi，并獲得最小適應(yīng)度值Fmin和適應(yīng)度平均值Fˉ；

（4）檢查算法終止條件。如果t≥T，輸出最優(yōu)解Fmin，否則執(zhí)行步驟（5）；

（5）選擇操作。執(zhí)行復(fù)合選擇操作，得到新的種群；

（6）交叉操作。對(duì)滿足交叉概率的種群個(gè)體進(jìn)行多父代交叉操作；

（7）評(píng)價(jià)種群收斂程度。計(jì)算當(dāng)前種群收斂度Δ，當(dāng)Δ＜ε時(shí)，轉(zhuǎn)入步驟（9），否則執(zhí)行步驟（8）；

（8）變異操作。以設(shè)定的變異概率對(duì)選中個(gè)體進(jìn)行變異，返回步驟（3）；

（9）定點(diǎn)擾動(dòng)操作。按照定點(diǎn)擾動(dòng)策略對(duì)精英群體執(zhí)行定點(diǎn)擾動(dòng)。

（10）令 t=t+1，返回步驟（3）；

4 實(shí)例驗(yàn)證與結(jié)果分析

為了驗(yàn)證改進(jìn)算法的有效性，以某液壓油缸零部件生產(chǎn)車間A小組生產(chǎn)計(jì)劃為實(shí)例，測試改進(jìn)算法。該實(shí)例中共有9個(gè)工件，每個(gè)工件有4道工序（車、銑、鉆、鏜），共有12臺(tái)設(shè)備，其中M1、M2、M3、M4、M5、M6 可用于車，M4、M5、M6、M7、M8 可用于銑，M4、M5、M9、M10 可用于鉆，M5、M6、M11，M12 可用于鏜。工序加工時(shí)間表，如表1所示。

表1 工序加工時(shí)間表Tab.1 Schedule of Procedure

設(shè)種群規(guī)模N=60，迭代次數(shù)t=1000，交叉概率Pc=0．8，變異概率Pm=0．05，擾動(dòng)系數(shù)r=8，收斂系數(shù)ε=0．9，適應(yīng)度函數(shù)權(quán)重ω1=0．4，ω2=0．3，ω3=0．3。利用 MATLAB 對(duì)實(shí)例進(jìn)行仿真計(jì)算，并得到最佳調(diào)度方案。傳統(tǒng)遺傳算法（SGA）和FPD-GA收斂曲線，如圖3、圖4所示。SGA、自適應(yīng)遺傳算法（AGA）和FPD-GA的實(shí)例計(jì)算結(jié)果比較，如表2所示。采用FPD-GA計(jì)算實(shí)例的最佳調(diào)度優(yōu)解，如圖5所示。

圖3 傳統(tǒng)GA收斂曲線Fig．3 Convergence Curve of Traditional GA

圖4 FPD-GA收斂曲線Fig．4 Convergence Curve of FPD-GA

通過對(duì)比圖3圖4可以看出：傳統(tǒng)遺傳算法在進(jìn)化初期迅速進(jìn)入收斂狀態(tài)，優(yōu)勢個(gè)體大量遺傳，平均適應(yīng)度值變化平緩且不斷趨近最小適應(yīng)值，種群一直保持收斂狀態(tài)；而FPD-GA在復(fù)合選擇策略的影響下平均適應(yīng)度值波動(dòng)式減小，當(dāng)進(jìn)入收斂狀態(tài)后觸發(fā)定點(diǎn)擾動(dòng)機(jī)制，使種群跳出局部最優(yōu)值，不斷朝全局最優(yōu)值進(jìn)化。通過表2數(shù)值對(duì)比，采用FPD-GA對(duì)實(shí)例求解，與其他算法相比，適應(yīng)度函數(shù)分別減小了7.4%、3.7%，各項(xiàng)指標(biāo)也明顯優(yōu)于SGA和AGA的計(jì)算結(jié)果，驗(yàn)證了FPD-GA的有效性。

表2 算法仿真計(jì)算結(jié)果對(duì)比Tab.2 Comparison of Simulation Results

圖5 最佳調(diào)度方案Fig.5 Optimal Scheduling Scheme

5 結(jié)論

在應(yīng)用遺傳算法的基礎(chǔ)上引入復(fù)合選擇操作，并設(shè)計(jì)定點(diǎn)擾動(dòng)策略，提出了一種融合遺傳算法—FPD-GA。FPD-GA繼承了遺傳算法全局搜索能力突出的優(yōu)勢，同時(shí)克服了局部尋優(yōu)能力差的缺陷，能快速地?cái)[脫局部收斂的狀態(tài)，向全局最優(yōu)解的方向進(jìn)化。通過生產(chǎn)實(shí)例驗(yàn)證，該方法在解的質(zhì)量上有較大提升和改善，是一種高效求解FJSP的方法。