基于并行融合機(jī)制的改進(jìn)遺傳算法求解HFSP調(diào)度問(wèn)題

張 源 陶翼飛 王加冕

(昆明理工大學(xué)機(jī)電工程學(xué)院 云南 昆明 650500)

0 引 言

混合流水車間調(diào)度問(wèn)題[1](HFSP)是流水車間[2]調(diào)度問(wèn)題的推廣，其特征是在某些工序中存在并行機(jī)器，其目的是指在一定時(shí)間內(nèi)對(duì)加工工件的排序和加工設(shè)備的分配進(jìn)行優(yōu)化使某些性能指標(biāo)達(dá)到最優(yōu)?？紤]切換時(shí)間的HFSP是指在混合流水車間調(diào)度問(wèn)題的基礎(chǔ)上引入了機(jī)器依次加工不同工件時(shí)的切換準(zhǔn)備時(shí)間[3]，由于加入了工件之間切換時(shí)間的因素[4]，使研究的問(wèn)題與實(shí)際更為接近，成為現(xiàn)階段混合流水車間調(diào)度領(lǐng)域研究的新方向。

引入并行進(jìn)化機(jī)制的遺傳算法[5]是對(duì)傳統(tǒng)遺傳算法[6]的優(yōu)化，可以提高算法的尋優(yōu)質(zhì)量。目前引入并行進(jìn)化機(jī)制的遺傳算法主要運(yùn)用于路徑規(guī)劃[7]問(wèn)題的優(yōu)化，也有學(xué)者將其用于求解車間調(diào)度問(wèn)題。Belkadi等[8]對(duì)混合流水車間調(diào)度問(wèn)題，以最大完工時(shí)間為目標(biāo)，采用并行遺傳算法進(jìn)行求解并與標(biāo)準(zhǔn)遺傳算法的結(jié)果進(jìn)行比較，證明了該算法可以提高求解質(zhì)量。Rubiyah等[9]提出了一種求解作業(yè)車間調(diào)度問(wèn)題的混合并行遺傳算法(PGA)，該算法基于異步群體和自主遷移進(jìn)行迭代更新，通過(guò)對(duì)不同規(guī)模問(wèn)題進(jìn)行仿真實(shí)驗(yàn)，證明了該算法能夠在一定程度上求解出更優(yōu)的完工時(shí)間。在近幾年中的研究中，Luo等[10]針對(duì)動(dòng)態(tài)混合流水車間問(wèn)題，提出一種基于優(yōu)先級(jí)的并行混合遺傳算法進(jìn)行求解，通過(guò)仿真實(shí)驗(yàn)證明了該算法的優(yōu)越性。Zhu等[11]針對(duì)多目標(biāo)混合流水車間問(wèn)題，提出了基于灰熵分析的并行遺傳算法進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明該算法能有效解決多目標(biāo)車間調(diào)度優(yōu)化問(wèn)題。Fu等[12]提出了一種基于特殊交叉變異策略的多種群并行遺傳算法對(duì)作業(yè)車間調(diào)度問(wèn)題進(jìn)行求解，實(shí)驗(yàn)結(jié)果表明該算法能求解出更優(yōu)的解。

文獻(xiàn)研究表明，并行遺傳算法在求解HFSP時(shí)，能夠改善求解質(zhì)量，但由于缺乏關(guān)于遺傳算法的改進(jìn)研究，使得引入并行機(jī)制后的算法仍存在收斂速度慢、易陷入局部極值的缺點(diǎn)，且多數(shù)文獻(xiàn)以完工時(shí)間[13](makespan)為目標(biāo)進(jìn)行優(yōu)化，忽略了對(duì)加工不同工件時(shí)機(jī)器切換時(shí)間的研究。因此，針對(duì)上述問(wèn)題，本文以考慮工件切換時(shí)間的混合流水車間調(diào)度問(wèn)題為研究對(duì)象建立仿真模型，優(yōu)化目標(biāo)為總工位切換時(shí)間(Total Station Switching Time，TSST)，并提出一種基于種群并行融合機(jī)制的改進(jìn)遺傳算法(PIGA)進(jìn)行求解，最終將總工位切換時(shí)間(TSST)作為各算法的性能指標(biāo)進(jìn)行對(duì)比，驗(yàn)證了本文算法的有效性。

1 問(wèn)題描述

在考慮切換時(shí)間的HFSP中，假設(shè)共有J個(gè)工序組成，其中至少有一個(gè)工序存在一臺(tái)以上的不相關(guān)并行機(jī)設(shè)備，并且相鄰工序間存在暫存緩沖區(qū)。每個(gè)工件需要依次經(jīng)過(guò)J個(gè)工序進(jìn)行加工，工件在每道工序中只能選擇該工序中的一臺(tái)機(jī)器進(jìn)行加工，工件在不同機(jī)器上加工時(shí)間不同，加工不同工件時(shí)機(jī)器的切換時(shí)間不同，加工相同工件時(shí)機(jī)器不需要切換時(shí)間。已知工件在所有設(shè)備上的加工時(shí)間和各工件之間的切換時(shí)間。為方便描述問(wèn)題，定義參數(shù)如表1所示。

表1 數(shù)學(xué)模型定義參數(shù)

續(xù)表1

假設(shè)所有設(shè)備的切換時(shí)間只與加工工件順序相關(guān)；所有設(shè)備加工第一個(gè)工件時(shí)不需要切換準(zhǔn)備時(shí)間；同一時(shí)間每臺(tái)設(shè)備只能加工一個(gè)工件；不同工序間有無(wú)限暫存區(qū)；問(wèn)題優(yōu)化目標(biāo)是求解最小化總工位切換時(shí)間，即：

minCmax

(1)

考慮切換時(shí)間的混合流水車間調(diào)度問(wèn)題的數(shù)學(xué)模型存在的約束條件及計(jì)算公式如下：

(2)

(3)

Si1,i2>0i1≠i2

(4)

(5)

(6)

式(2)為總工序切換時(shí)間計(jì)算公式及目標(biāo)函數(shù)；式(3)為各個(gè)工序中所有機(jī)器的總切換時(shí)間；式(4)說(shuō)明，任意兩個(gè)不同工件之間的切換時(shí)間必須大于0；式(5)說(shuō)明同一時(shí)間，每臺(tái)機(jī)器只能加工一個(gè)工件；式(6)表示如果在工序j的機(jī)器k上依次加工工件i1和工件i2，那么工件i2在工序j機(jī)器k上的完工時(shí)間應(yīng)大于等于工件i1在工序j的機(jī)器k上的完工時(shí)間、工件i1和工件i2的切換時(shí)間、工件i2在工序j的機(jī)器k上的加工時(shí)間三者之和。

2 并行融合機(jī)制的改進(jìn)遺傳算法求解

遺傳算法(Genetic algorithm，GA)在HFSP中應(yīng)用較為廣泛，但是標(biāo)準(zhǔn)遺傳算法由于在個(gè)體選擇和交叉變異概率方面的局限性，使算法全局搜索能力降低且出現(xiàn)早熟現(xiàn)象。因此本文結(jié)合并行融合拆分機(jī)制、精英保留策略[14]和自適應(yīng)遺傳因子[15]對(duì)遺傳算法進(jìn)行改進(jìn)，建立了基于并行融合機(jī)制的改進(jìn)遺傳算法，該算法有效克服了傳統(tǒng)遺傳算法易陷入局部極值的缺點(diǎn)。

2.1 編碼和解碼

編碼采用基于工件編號(hào)的實(shí)數(shù)編碼，即染色體中的各元素值代表對(duì)應(yīng)的工件編號(hào)。解碼的目的是確定工件的加工順序和各工序設(shè)備的分配情況，其中染色體中的元素值序列代表工件進(jìn)入混合流水車間的初始加工順序，后續(xù)階段加工工件的排序按前階段工件完工時(shí)間的先后順序進(jìn)行加工。工件在各工序并行設(shè)備的分配根據(jù)先到先服務(wù)法則[16](First In First Seved，F(xiàn)IFS)進(jìn)行安排，即優(yōu)先安排最早進(jìn)入暫存區(qū)隊(duì)列等候的工件進(jìn)行加工。

2.2 種群初始化及適應(yīng)度函數(shù)

初始種群產(chǎn)生的方法為：在均勻分布(Uniform Distribution)中隨機(jī)產(chǎn)生I個(gè)不重復(fù)的數(shù)字來(lái)建立初始種群，種群中的每個(gè)染色體由一個(gè)一維矩陣組成，染色體長(zhǎng)度表示加工工件的個(gè)數(shù)。

本文優(yōu)化的目標(biāo)是最小化總工序的切換時(shí)間，但在遺傳算法迭代過(guò)程中保留的是適應(yīng)度值最大的個(gè)體，應(yīng)取目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)，由于切換時(shí)間以秒為單位計(jì)算，目標(biāo)函數(shù)計(jì)算結(jié)果較大，所以為方便觀察比較，在目標(biāo)函數(shù)倒數(shù)的基礎(chǔ)上再放大100倍，即第g代的第n條染色體的適應(yīng)度函數(shù)為：

fg,n=100/Cg,n

(7)

式中：n∈{1,2,…,N}，N為每代的染色體數(shù)目；Cg,n為第g代的第n條染色體的總切換時(shí)間。

2.3 并行融合拆分機(jī)制

由于隨機(jī)生成的初始種群增加了算法尋優(yōu)過(guò)程中的不確定因素，使得算法的最優(yōu)解質(zhì)量和收斂速度等方面的結(jié)果并不理想。因此本文在遺傳算法的迭代進(jìn)化中引入一種基于多種群的并行融合拆分機(jī)制，該機(jī)制是指對(duì)遺傳算法進(jìn)行并行設(shè)計(jì)，同時(shí)在并行計(jì)算中加入了種群個(gè)體間的融合拆分策略，通過(guò)對(duì)多個(gè)種群的分布式并行處理，不僅提高了算法的求解速度和運(yùn)行效率，而且由于增加了種群規(guī)模和個(gè)體間的融合拆分，使得種群個(gè)體的多樣性得以維持和豐富，增加了算法的求解空間，降低了陷入局部極值的可能性，提高了求解質(zhì)量。

如圖1所示，并行融合拆分機(jī)制是指將m個(gè)種群個(gè)體進(jìn)行融合，融合后按某種規(guī)律重新差分為m個(gè)種群的過(guò)程。其中：bmn為種群m的第n個(gè)染色體；am×n為種群融合后的第m×n個(gè)染色體，且fa1≥fa2≥…≥fam×n；Bm為融合拆分后的第m個(gè)種群。并行融合拆分機(jī)制的具體操作為：

(1) 若滿足合并條件，將m個(gè)種群的個(gè)體進(jìn)行融合，融合后通過(guò)仿真輸出所有個(gè)體的適應(yīng)度值并保留最優(yōu)個(gè)體。

(2) 將融合后的種群個(gè)體按適應(yīng)度值大小進(jìn)行降序排列，并根據(jù)排列順序重新編號(hào)，其中a1、am×n分別為融合種群的最優(yōu)和最差個(gè)體。

(3) 將融合種群個(gè)體的序號(hào)按公差為m的等差數(shù)列重新拆分為m個(gè)種群，并用最優(yōu)個(gè)體替換各種群中的最差個(gè)體，如拆分后種群B1的最差個(gè)體為a1+m(n+1)，則將融合種群的最優(yōu)個(gè)體a1與該個(gè)體進(jìn)行替換，其余種群同理進(jìn)行保優(yōu)操作。

(4) 保留拆分后的各種群，進(jìn)行遺傳操作。

圖1 并行融合拆分機(jī)制示意圖

2.4 基于精英保留策略的個(gè)體選擇機(jī)制

在傳統(tǒng)的遺傳算法中，選擇操作采用輪盤賭[17]的方式，用適應(yīng)度值對(duì)每代染色體進(jìn)行評(píng)價(jià)，適應(yīng)度值大的染色體被選中的概率也高，但該方法并不代表適應(yīng)度值低的染色體不會(huì)被選中，若適應(yīng)度值低的染色體被選中進(jìn)入子代,則會(huì)對(duì)最終尋優(yōu)結(jié)果的質(zhì)量產(chǎn)生影響。因此本文采用精英保留策略的方法進(jìn)行個(gè)體選擇,該策略是指在種群進(jìn)化過(guò)程中選擇適應(yīng)度值較高的個(gè)體進(jìn)行復(fù)制，替換較差個(gè)體進(jìn)行后續(xù)遺傳操作，并且將適應(yīng)度最好的精英個(gè)體直接保留到下一代的過(guò)程。通過(guò)對(duì)優(yōu)良個(gè)體進(jìn)行保留復(fù)制,增強(qiáng)其繁衍能力，保證種群精英個(gè)體的基因序列不被破壞，提高算法的收斂速度和尋優(yōu)解質(zhì)量。具體操作為：

(1) 將種群中的染色體按適應(yīng)度值大小降序排列。

(2) 排列后將前50%的染色體進(jìn)行復(fù)制并替換后50%的染色體組成待配種群，并將最優(yōu)個(gè)體保留到子代中。

(3) 保留選擇后的待配種群，進(jìn)行后續(xù)的交叉變異操作。

2.5 改進(jìn)自適應(yīng)遺傳因子設(shè)計(jì)

在遺傳算法求解不同規(guī)模的調(diào)度問(wèn)題時(shí)，很難確定最佳的交叉變異概率值，使算法過(guò)早收斂無(wú)法求解出全局最優(yōu)解。而自適應(yīng)交叉變異因子可以根據(jù)某些條件自行調(diào)整交叉變異概率，以達(dá)到或接近其最佳值,從而能較好地改善尋優(yōu)解質(zhì)量。因此本文采用基于進(jìn)化代數(shù)和適應(yīng)度值變化的自適應(yīng)遺傳因子替換固定的交叉變異概率。

當(dāng)染色體適應(yīng)度值趨于早熟或多數(shù)個(gè)體集中于局部最優(yōu)時(shí)，為跳出局部極值并延續(xù)優(yōu)良個(gè)體的基因結(jié)構(gòu),應(yīng)適當(dāng)降低交叉概率增加變異概率，以達(dá)到快速尋找最優(yōu)解的目的；當(dāng)染色體適應(yīng)度差距較大或種群個(gè)體在解空間中分散分布時(shí)，為利于優(yōu)良個(gè)體的生存并保持染色體之間的差異性，應(yīng)適當(dāng)增加交叉概率減小變異概率[18]，以幫助種群在尋找完最優(yōu)解后快速收斂。綜上所述,本文改進(jìn)自適應(yīng)交叉變異概率計(jì)算公式如下：

(8)

(9)

式中：Pc為交叉概率；Pcmax、Pcmin分別表示交叉概率的最大值和最小值；Pm為變異概率；Pmmax、Pmmin分別表示變異概率的最大值和最小值；favg為當(dāng)前種群個(gè)體平均適應(yīng)度值；fg,n為第g代第n個(gè)個(gè)體的適應(yīng)度值；fmax為當(dāng)前種群中最大的適應(yīng)度值；fmin為當(dāng)前種群中最小的適應(yīng)度值；g為當(dāng)前迭代次數(shù)；G為總的迭代次數(shù)。

在改進(jìn)自適應(yīng)遺傳因子中，交叉算子為相鄰個(gè)體間的PMX交叉，即隨機(jī)選擇兩個(gè)交叉點(diǎn)，交換染色體之間的片段，交換后的染色體采用部分映射進(jìn)行修復(fù)。變異算子為兩點(diǎn)變異法，即在染色體中隨機(jī)選擇兩個(gè)位置的基因進(jìn)行互換。

2.6 并行融合機(jī)制改進(jìn)遺傳算法步驟及流程

本文在上述改進(jìn)自適應(yīng)遺傳算法的基礎(chǔ)上引入并行融合拆分機(jī)制構(gòu)建最終的改進(jìn)遺傳算法。算法總流程如圖2所示，具體步驟如下：

Step1隨機(jī)生成m個(gè)指定規(guī)模數(shù)量的種群作為改進(jìn)遺傳算法的初始子種群。

Step2分別通過(guò)計(jì)算機(jī)仿真輸出m個(gè)種群中對(duì)應(yīng)個(gè)體的適應(yīng)度值。

Step3基于精英保留策略對(duì)各種群中的優(yōu)良個(gè)體進(jìn)行選擇操作。

Step4基于改進(jìn)自適應(yīng)遺傳算法進(jìn)行種群個(gè)體的交叉變異操作。

Step5是否滿足終止條件，若滿足輸出優(yōu)化結(jié)果；若不滿足轉(zhuǎn)Step 6。

Step6是否滿足合并條件，若滿足轉(zhuǎn)Step 7；若不滿足轉(zhuǎn)Step 2。

Step7將m個(gè)種群的個(gè)體進(jìn)行融合，并按適應(yīng)度值降序排列。排列后序號(hào)按公差為m的等差數(shù)列重新拆分為m個(gè)種群，并轉(zhuǎn)Step 2。

圖2 引入并行融合機(jī)制的改進(jìn)遺傳算法流程

3 仿真實(shí)驗(yàn)

本文進(jìn)行的仿真實(shí)驗(yàn)的混合流水車間實(shí)例[19]為某鋼鐵廠生產(chǎn)企業(yè)加工12個(gè)工件，加工過(guò)程由煉鋼、精煉、連鋼、軋制四道工序組成，四道工序的并行機(jī)數(shù)量分別為3、3、2、2。仿真模型在Plant Simulation軟件中建立，如圖3所示。

圖3 混合流水車間仿真優(yōu)化模型

混合流水車間仿真模型由控制參數(shù)、程序仿真和數(shù)據(jù)統(tǒng)計(jì)三個(gè)模塊組成，其中程序仿真模塊中用Simtalk語(yǔ)言編寫算法和模型調(diào)度程序。數(shù)據(jù)統(tǒng)計(jì)模塊將工件之間的切換時(shí)間、工件在各機(jī)器上的加工時(shí)間、算法求解結(jié)果等數(shù)據(jù)進(jìn)行記錄?？刂茀?shù)模塊為仿真運(yùn)行過(guò)程中需要調(diào)用的參數(shù)，并顯示當(dāng)前種群的實(shí)時(shí)數(shù)據(jù)。各工件之間的切換時(shí)間服從X(min)～U[1,10]均勻分布如表2所示。

表2 工件切換時(shí)間

仿真模型在Plant Simulation軟件中運(yùn)行，PIGA將各初始子種群分配到對(duì)應(yīng)的處理器并行運(yùn)算，每個(gè)處理器完成獨(dú)立的串行遺傳算法。設(shè)置并行融合機(jī)制的種群數(shù)m為2，滿足合并條件的迭代次數(shù)為100，交叉概率的極值為[0.6,0.9]，變異概率的極值為[0.05,0.15]。各算法的最大迭代次數(shù)Gmax為300，每代種群個(gè)體數(shù)量N為50。

4 結(jié)果分析

分別將標(biāo)準(zhǔn)遺傳算法(GA)、自適應(yīng)遺傳算法(Adaptive Genetic Algorithm，AGA)和基于種群并行融合機(jī)制的改進(jìn)遺傳算法(PIGA)在仿真模型中各運(yùn)行10次進(jìn)行比較。表3為對(duì)比結(jié)果，表中給出了各算法求解的最小值(Min)、平均值(Avg)、最大值(Max)、平均耗時(shí)(CPU)和平均收斂代數(shù)(Avg-FI)。

表3 各算法性能指標(biāo)對(duì)比結(jié)果

如表3所示，由尋優(yōu)解質(zhì)量可得，PIGA求解的最小值、平均值和最大值均優(yōu)于其他兩種算法，且最優(yōu)解的極差僅為2，具有較好的穩(wěn)定性和尋優(yōu)能力。由運(yùn)行時(shí)間可得，由于PIGA中引入了并行融合拆分機(jī)制，增加了種群數(shù)量，使該算法的實(shí)現(xiàn)過(guò)程更復(fù)雜，但PIGA中各子種群是在多個(gè)處理器中分布式運(yùn)行，因此雖然算法的復(fù)雜性得到了提升，但運(yùn)行時(shí)間與自適應(yīng)遺傳算法基本一致，且求解質(zhì)量也得到了改善，表明了該算法在復(fù)雜程度更高的情況下，能用相同的時(shí)間求解出更優(yōu)的解，具有較好的運(yùn)算效率。由收斂代數(shù)可得，PIGA的平均收斂代數(shù)明顯小于其他兩種算法，表明該算法在迭代搜索中能快速收斂到最優(yōu)解，具有較好的收斂性。綜上所述，在迭代次數(shù)相同的情況下，PIGA具有更優(yōu)的全局搜索能力、運(yùn)行效率和收斂速度，從而驗(yàn)證了該算法的有效性和優(yōu)越性。

圖4和圖5為各算法的迭代曲線和最優(yōu)解甘特圖。在迭代曲線中,GA和AGA分別在175和165代發(fā)生尋優(yōu)停滯現(xiàn)象，陷入局部極小值。而PIGA在113代就收斂到最優(yōu)解116，有效避免算法趨于早熟。在甘特圖中工件加工時(shí)間的條形圖下方顯示了該工件的切換準(zhǔn)備時(shí)間，由于各設(shè)備加工首個(gè)工件時(shí)不需要切換準(zhǔn)備時(shí)間,因此在甘特圖中各工位第一個(gè)加工時(shí)間的條形圖下方?jīng)]有顯示切換準(zhǔn)備時(shí)間。從圖5中可得工件的完工時(shí)間為343 min，雖然加工時(shí)間較長(zhǎng)，但優(yōu)化目標(biāo)是總工位切換時(shí)間，所以該結(jié)果反映的是工位切換準(zhǔn)備時(shí)間最少的情況，即各設(shè)備加工時(shí)間下方的切換時(shí)間條形圖最短。

圖4 改進(jìn)前后GA迭代曲線

圖5 最優(yōu)解甘特圖

5 結(jié) 語(yǔ)

本文在傳統(tǒng)遺傳算法的基礎(chǔ)上引入并行融合拆分機(jī)制、精英保留策略和自適應(yīng)遺傳因子，提出一種基于種群并行融合機(jī)制的改進(jìn)遺傳算法，并以總工位切換時(shí)間為目標(biāo)對(duì)混合流水車間調(diào)度問(wèn)題進(jìn)行求解。通過(guò)仿真結(jié)果的對(duì)比分析，驗(yàn)證了本文算法的有效性，為并行遺傳算法的改進(jìn)研究和應(yīng)用提供了一定的參考價(jià)值。