裴小兵，李依臻

(天津理工大學(xué)管理學(xué)院，天津 300384)

0 引言

在制造系統(tǒng)領(lǐng)域，車(chē)間調(diào)度是一個(gè)重要的研究課題，合理的調(diào)度計(jì)劃可以有效地減少浪費(fèi)，為企業(yè)創(chuàng)造更好的經(jīng)濟(jì)效益。車(chē)間調(diào)度問(wèn)題分為單機(jī)調(diào)度問(wèn)題、流水車(chē)間調(diào)度問(wèn)題和作業(yè)車(chē)間調(diào)度問(wèn)題[1]。在工業(yè)生產(chǎn)領(lǐng)域，流水車(chē)間調(diào)度問(wèn)題(Flow shop Scheduling Problem，F(xiàn)SP)是一個(gè)通用的問(wèn)題模型，同時(shí)也是學(xué)術(shù)領(lǐng)域研究的熱點(diǎn)。流水車(chē)間調(diào)度問(wèn)題包含置換FSP、零等待FSP、阻塞FSP、零空閑FSP和混合FSP。本文研究了零等待流水車(chē)間調(diào)度問(wèn)題(No-wait Flow Shop Scheduling Problem，NWFSP)，且已經(jīng)證明機(jī)器數(shù)大于2時(shí)，NWFSP是一類(lèi)NP-hard問(wèn)題[2]。零等待約束廣泛存在于鋼鐵冶煉、食品加工、生物制藥和化工等生產(chǎn)過(guò)程中，即加工過(guò)程一旦開(kāi)始將不能中斷，直到完成所有加工工序。例如，鋼鐵生產(chǎn)中為防止金屬溫度降低而導(dǎo)致成份破壞，其軋制過(guò)程必須連續(xù)無(wú)間斷地完成;塑料成型過(guò)程中所有工序之間必須不間斷地連續(xù)完成，以防止塑料成份降解退化。

隨著問(wèn)題規(guī)模的擴(kuò)大，通過(guò)分支界定法或混合整數(shù)規(guī)劃法等精確算法求解NWFSP，難以在合理的時(shí)間內(nèi)得到結(jié)果，因此，需要進(jìn)一步研究其他有效算法求解該問(wèn)題。近幾年，已經(jīng)提出各種有效的優(yōu)化算法用于求解復(fù)雜優(yōu)化問(wèn)題，如回溯搜索算法[3]、教與學(xué)算法[4]、猴群算法[5]、鯨魚(yú)優(yōu)化算法[6]等。Laha等[7]提出了基于懲罰的匈牙利算法求解NWFSP，采用基于懲罰的策略產(chǎn)生初始調(diào)度，并運(yùn)用3種插入方法提高初始解的質(zhì)量，實(shí)驗(yàn)結(jié)果表明所提算法的計(jì)算結(jié)果均優(yōu)于現(xiàn)存優(yōu)化算法。Ye等[8]以完工時(shí)間最小化為目標(biāo)，提出了平均撤出時(shí)間啟發(fā)式求解NWFSP，插入過(guò)程采用目標(biāo)值增量法來(lái)降低算法的計(jì)算復(fù)雜度，實(shí)驗(yàn)結(jié)果驗(yàn)證了相同計(jì)算復(fù)雜度情況下，所提啟發(fā)式方法比其他啟發(fā)式方法更優(yōu)。仲維亞等[9]研究了兩階段零等待流水作業(yè)排序問(wèn)題，提出了兩個(gè)近似算法，并通過(guò)數(shù)值分析驗(yàn)證了算法的性能。Ding等[10]結(jié)合禁忌搜索機(jī)制提出了改進(jìn)迭代貪婪算法求解NWFSP，該算法采用基于禁忌表重組策略和變鄰域搜索策略提高解的質(zhì)量，運(yùn)算結(jié)果表明了所提算法比其他啟發(fā)式算法具有更好的性能。針對(duì)NWFSP 的特點(diǎn)，Zhao等[11]提出了具有種群適應(yīng)機(jī)制的基于因子的粒子群優(yōu)化算法，算法采用變鄰域局部搜索機(jī)制提高種群的質(zhì)量，通過(guò)種群適應(yīng)機(jī)制控制種群多樣性，避免算法陷入局部最優(yōu)，最后通過(guò)標(biāo)準(zhǔn)算例對(duì)算法進(jìn)行了測(cè)試，算例求解結(jié)果表明了文中所提算法的優(yōu)越性。宋存利等[12]針對(duì)大規(guī)模NWFSP的特點(diǎn)提出了鄰域迭代搜索算法，并以最小化完工時(shí)間為目標(biāo)，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了所提算法性能的高效性和有效性。Riahi等[13]結(jié)合模擬退火算法提出新型混合蟻群算法求解NWFSP，該算法在增加種群多樣性和改善傳統(tǒng)蟻群算法容易陷入局部最優(yōu)問(wèn)題上有了明顯的提高。李永林等[14]提出一種混合群搜索算法，并根據(jù)NWFSP的特點(diǎn)設(shè)計(jì)了一種完工時(shí)間的簡(jiǎn)化計(jì)算方法和有效的局部搜索策略，有效地平衡了計(jì)算代價(jià)與性能。Engin等[15]結(jié)合遺傳算法的交叉和變異機(jī)制來(lái)避免蟻群算法陷入局部最優(yōu)解的可能，采用全局更新規(guī)則實(shí)現(xiàn)種群進(jìn)化，計(jì)算結(jié)果驗(yàn)證了所提算法相對(duì)于其他算法具有更好的性能。

上述文獻(xiàn)中的算法在解決NWFSP時(shí)均求得了較優(yōu)的結(jié)果，為算法的初始化、局部搜索策略、全局改善機(jī)制以及種群多樣性等方面提供了積極的借鑒意義和理論基礎(chǔ)。遺傳算法(Genetic Algorithm，GA)[16]是目前發(fā)展比較成熟的一種優(yōu)化算法，具有較高的通用性、潛在的并行性和較佳的全局搜索能力等特點(diǎn)，被廣泛應(yīng)用于求解車(chē)間調(diào)度問(wèn)題中。Yu等[17]運(yùn)用遺傳算法解決混合流水車(chē)間調(diào)度問(wèn)題，采用一種新的解碼機(jī)制，從給定的工件排序中改進(jìn)調(diào)度構(gòu)建過(guò)程，然而遺傳操作過(guò)程采用隨機(jī)方式無(wú)法避免交叉和變異過(guò)程中的無(wú)效操作。Deng等[18]提出協(xié)同進(jìn)化量子遺傳算法求解零等待流水車(chē)間調(diào)度問(wèn)題，以方陣表示量子個(gè)體，更容易得到工件排序，但并未降低問(wèn)題復(fù)雜度，對(duì)于大規(guī)模問(wèn)題運(yùn)算時(shí)間會(huì)大大增加。崔琪等[19]提出改進(jìn)混合變鄰域搜索的遺傳算法求解混合流水車(chē)間調(diào)度，但是僅使用反轉(zhuǎn)逆序變異的方式無(wú)法有效地避免算法陷入局部最優(yōu)解。通過(guò)查閱和分析文獻(xiàn)可知，國(guó)內(nèi)缺乏運(yùn)用GA求解NWFSP的研究，且運(yùn)用遺傳算法求解調(diào)度問(wèn)題仍存在較大的改進(jìn)空間。

區(qū)塊、關(guān)鍵塊或優(yōu)勢(shì)塊是近年來(lái)提出的一種新理論，在降低問(wèn)題復(fù)雜性、提高算法求解速度、改善解的質(zhì)量方面優(yōu)勢(shì)明顯。Chang 等[20]依據(jù)二元變量概率模型，結(jié)合概率矩陣和輪盤(pán)賭法挖掘優(yōu)勢(shì)塊，運(yùn)用二元變量概率模型提出了基于塊的分布估計(jì)算法求解FSP。Hsu等[21]則運(yùn)用關(guān)聯(lián)規(guī)則挖掘優(yōu)勢(shì)個(gè)體的基因組合組成優(yōu)勢(shì)塊，大大提高了運(yùn)算效率。

隨著對(duì)GA研究的逐步深入，許多學(xué)者將該算法應(yīng)用求解調(diào)度問(wèn)題中。本研究針對(duì)NWFSP問(wèn)題提出了新型混合改進(jìn)遺傳算法(New Hybrid Improving Genetic Algorithm，NHIGA)。首先，通過(guò)改進(jìn)NEH(Nawaz-Enscore-Ham)算法獲得具有較優(yōu)質(zhì)量和多樣性的初始種群。為加快算法求解效率、降低問(wèn)題復(fù)雜性，采用關(guān)聯(lián)規(guī)則挖掘優(yōu)勢(shì)染色體上的優(yōu)勢(shì)塊，加快算法迭代效率。此外，通過(guò)改進(jìn)交叉和變異過(guò)程進(jìn)一步改善遺傳算法的全局和局部搜索能力。本研究還提出了基于NEH(Nawaz-Enscore-Ham)算法的鄰域搜索機(jī)制，通過(guò)擴(kuò)大搜索范圍，進(jìn)一步提高算法的質(zhì)量。最后，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了本文算法求解NWFSP的有效性和魯棒性。

1 問(wèn)題描述

NWFSP可以定義如下:在m臺(tái)機(jī)器M={M1，M2，…，Mm}上按順序加工n個(gè)工件J={J1，J2，…，Jn}，工件的加工路徑均相同。Pj，i表示工件Jj在機(jī)器Mi上的加工時(shí)間，j∈{1，2，…，n}，i∈{1，2，…，m}，工件的加工時(shí)間已知。問(wèn)題的約束條件如下:機(jī)器在同一時(shí)間只能加工一個(gè)零件，且該時(shí)間一個(gè)工件只能在一臺(tái)機(jī)器上加工;工件從開(kāi)始加工到完成，加工過(guò)程中無(wú)任何等待時(shí)間。調(diào)度的目的是找到工件最佳的加工順序，本研究以最小化完工時(shí)間Cmax為目標(biāo)，則目標(biāo)函數(shù)如式(1)所示。

假設(shè)一個(gè)可行調(diào)度序列π={π1，π2，…，πj，…，πn}，由于零等待條件的約束，相鄰兩工件πj和πj+1在第一臺(tái)機(jī)器上加工時(shí)存在開(kāi)工時(shí)間差Ej，j+1，Ej，j+1的計(jì)算公式如下[22]:

因此，可行調(diào)度π的完工時(shí)間Cmax的計(jì)算公式如下:

同時(shí)，NWFSP問(wèn)題還需滿足下列條件[23]:

式(4)表示決策變量;式(5)和式(6)確保了在一個(gè)調(diào)度序列中，所有工件僅出現(xiàn)一次;式(7)表示第一個(gè)工件在第一臺(tái)機(jī)器上的完工時(shí)間，確保了第一臺(tái)機(jī)器的開(kāi)工時(shí)間為零;式(8)為每一臺(tái)機(jī)器上相鄰兩工件之間的關(guān)系，確保一臺(tái)機(jī)器在同一時(shí)刻不能同時(shí)加工多個(gè)零件;式(9)表示同一工件相鄰工序之間完工時(shí)間的關(guān)系，確保問(wèn)題滿足零等待約束條件;式(10)保證了所有工序的完工時(shí)間均大于零。

2 新型混合改進(jìn)遺傳算法求解NWFSP

考慮到GA 算法的優(yōu)點(diǎn)，本研究結(jié)合NWFSP自身特點(diǎn)，提出了新型混合改進(jìn)遺傳算法(NHIGA)，其流程圖如圖1所示。圖中:ΔNS表示鄰域搜索計(jì)數(shù)器;NS表示鄰域搜索范圍臨界值;ΔBM表示優(yōu)勢(shì)塊挖掘計(jì)數(shù)器;BM 表示優(yōu)勢(shì)塊挖掘臨界值。NHIGA主要分為6個(gè)部分:①初始化種群;②基于關(guān)聯(lián)規(guī)則的優(yōu)勢(shì)塊挖掘;③人工染色體組合;④遺傳操作;⑤鄰域搜索機(jī)制;⑥優(yōu)勢(shì)染色體保留機(jī)制。各部分的具體操作如下文所述。

2.1 初始化種群

本研究以加工工件的編號(hào)作為染色體的基因，一個(gè)完整的染色體由所有工件的排序組成，工件的個(gè)數(shù)n即為染色體長(zhǎng)度。通過(guò)種群初始化構(gòu)造具有較高質(zhì)量的初始染色體種群，達(dá)到改善算法求解效率的目的。

NEH 算法[24]是最常用的初始化方法，本研究根據(jù)NEH 算法的思想，結(jié)合NWFSP的特點(diǎn)，提出了改進(jìn)NEH 啟發(fā)式算法產(chǎn)生初始化種群。首先，根據(jù)NEH 算法生成一條染色體;然后，在該條染色體的基礎(chǔ)上實(shí)施破壞性重組;從所得鄰域中選擇最優(yōu)染色體替換初始染色體。重復(fù)上述過(guò)程，直到獲得NP(種群數(shù)量)個(gè)初始個(gè)體。具體操作如下:

步驟1計(jì)算每一個(gè)工件從機(jī)器1到機(jī)器m的加工總時(shí)間Tj，并將Tj按降序進(jìn)行排列，構(gòu)成工件序列T。Tj計(jì)算公式如下:

步驟2選擇T中的前兩個(gè)工件，并計(jì)算兩個(gè)工件組成的兩個(gè)排序的總完工時(shí)間，保留完工時(shí)間最小的排序。

步驟3按照降序選取T中的一個(gè)工件，并依次插入到當(dāng)前序列的所有可能位置，每插入一個(gè)位置計(jì)算該位置形成的序列的完工時(shí)間，最終將總完工時(shí)間最小的序列作為下一個(gè)工件插入的基礎(chǔ)。

步驟4重復(fù)步驟3，直到所有工件都完成插入，形成完整序列π。

步驟5隨機(jī)選擇π中k個(gè)工件實(shí)施破壞重組操作，并對(duì)k個(gè)工件按Tj的降序進(jìn)行排列形成T'。將π中未被選中的工件組成新的排列π'。

步驟6選擇T'中第一個(gè)工件，將其插入π'中所有可能的位置，并計(jì)算對(duì)應(yīng)的完工時(shí)間Cmax，保留Cmax值最小的序列作為T(mén)'中下一個(gè)工件插入的基礎(chǔ)序列，重復(fù)該步驟直到T'中的工件全部插入到π'中，得到第二條初始染色體。

步驟7重復(fù)步驟5和步驟6，直到形成完整的初始種群NP。

2.2 基于關(guān)聯(lián)規(guī)則的優(yōu)勢(shì)塊挖掘

優(yōu)勢(shì)染色體之間的基因結(jié)構(gòu)是具有一定規(guī)律的，通過(guò)尋找這種規(guī)律，將其組合成優(yōu)勢(shì)塊可以大幅降低問(wèn)題復(fù)雜度、提高算法求解效率、改善求解質(zhì)量。本研究基于關(guān)聯(lián)規(guī)則挖掘優(yōu)勢(shì)染色體上的優(yōu)勢(shì)基因塊組成優(yōu)勢(shì)塊，以提高算法的求解效率，改善算法的整體性能。

2.2.1 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則[25]是數(shù)據(jù)挖掘中一種常用的方法，可有效改善數(shù)據(jù)結(jié)構(gòu)，提高算法求解性能。本研究通過(guò)關(guān)聯(lián)規(guī)則分析染色體的結(jié)構(gòu)，發(fā)現(xiàn)基因之間的相關(guān)性，尋找優(yōu)勢(shì)基因組成優(yōu)勢(shì)塊，通過(guò)將優(yōu)勢(shì)塊直接注入人工染色體來(lái)降低問(wèn)題的復(fù)雜度。

A與B之間關(guān)聯(lián)規(guī)則的表達(dá)存在支持度和信心水平[26]兩個(gè)重要的參考指標(biāo)。支持度表示A與B同時(shí)出現(xiàn)在數(shù)據(jù)記錄中的頻率;信心水平表示A與B之間的關(guān)聯(lián)強(qiáng)度。關(guān)聯(lián)強(qiáng)度的評(píng)判指標(biāo)增益值表示關(guān)聯(lián)度的強(qiáng)弱，若增益值大于1，則表示強(qiáng)關(guān)聯(lián)。對(duì)應(yīng)計(jì)算公式如下:

上述公式中，A→B表示若A發(fā)生，則B也發(fā)生;N為染色體總數(shù);sup(A∪B)表示各染色體上同時(shí)出現(xiàn)基因集A和基因集B的總次數(shù);sup(A)表示基因集A出現(xiàn)在各個(gè)個(gè)體中的總次數(shù);s(A→B)為A和B之間關(guān)聯(lián)支持度的強(qiáng)弱;c(A→B)為A和B之間關(guān)聯(lián)信心水平;lift表示評(píng)價(jià)指標(biāo)增益值，其作用是判定A與B之間是否具有強(qiáng)關(guān)聯(lián)性。此外，為保證關(guān)聯(lián)法則的有效性，需設(shè)置最小支持度和最小信心水平，當(dāng)所挖掘個(gè)體之間的關(guān)聯(lián)評(píng)價(jià)指標(biāo)滿足設(shè)立的最小臨界值時(shí)，則視為有效關(guān)聯(lián)，并進(jìn)行保留。

2.2.2 挖掘優(yōu)勢(shì)塊

優(yōu)勢(shì)塊是染色體上優(yōu)勢(shì)基因之間的結(jié)構(gòu)組合，在降低算法復(fù)雜度上具有明顯的效果。本研究采用關(guān)聯(lián)規(guī)則挖掘優(yōu)勢(shì)染色體中的優(yōu)勢(shì)塊，尋找優(yōu)勢(shì)基因結(jié)構(gòu)組合成優(yōu)勢(shì)塊。首先，將各代群體中的染色體依據(jù)適應(yīng)度值從小到大的順序進(jìn)行排序，選擇前k條染色體，將所選染色體上的工件加工順序轉(zhuǎn)換為工件加工記錄資料。以工件5和機(jī)器5為例，如圖2所示為染色體轉(zhuǎn)化過(guò)程。

設(shè)立最小支持度水平(support)臨界值和優(yōu)勢(shì)塊長(zhǎng)度，找出所得到的工件加工數(shù)據(jù)集中大于臨界值的工件及對(duì)應(yīng)機(jī)器。具體操作步驟如下:

步驟1選擇工件加工數(shù)據(jù)集中大于臨界值的基因放入頻繁項(xiàng)目集F中。

步驟2將頻繁項(xiàng)目集F中的基因組合成優(yōu)勢(shì)塊放入候選項(xiàng)目集C中。

步驟3觀察候選項(xiàng)目集C，將所有大于臨界值的優(yōu)勢(shì)基因進(jìn)行組合，形成新的頻繁項(xiàng)目集H'。

步驟4重復(fù)上述步驟，直到將所有優(yōu)勢(shì)基因組合存入暫存資料庫(kù)。

如圖3所示為優(yōu)勢(shì)基因塊的構(gòu)建過(guò)程。

2.2.3 優(yōu)勢(shì)塊篩選

由于依據(jù)關(guān)聯(lián)規(guī)則挖掘產(chǎn)生的優(yōu)勢(shì)塊之間存在工件或機(jī)器的重疊，需要通過(guò)比較優(yōu)勢(shì)塊暫存器中的優(yōu)勢(shì)塊進(jìn)行篩選，通過(guò)優(yōu)勢(shì)塊之間的競(jìng)爭(zhēng)，最終形成具有高度競(jìng)爭(zhēng)優(yōu)勢(shì)的優(yōu)勢(shì)塊。具體操作如下:首先，對(duì)比暫存器中優(yōu)勢(shì)塊的工件與機(jī)器，若各優(yōu)勢(shì)塊之間出現(xiàn)重復(fù)的工件或機(jī)器，則計(jì)算優(yōu)勢(shì)塊的增益值[27]，增益值大于1且數(shù)值較大的優(yōu)勢(shì)塊具有更強(qiáng)的關(guān)聯(lián)度，對(duì)其進(jìn)行保留，不滿足要求的則刪除。優(yōu)勢(shì)塊的篩選過(guò)程如圖4所示，經(jīng)過(guò)競(jìng)爭(zhēng)留存下來(lái)的優(yōu)勢(shì)塊將用于組合人工染色體。

2.3 人工染色體組合

人工染色體組合可以獲得具有高度競(jìng)爭(zhēng)優(yōu)勢(shì)的染色體種群。本研究利用關(guān)聯(lián)規(guī)則挖掘和篩選出來(lái)的優(yōu)勢(shì)塊組合人工染色體，具體操作步驟如下:將優(yōu)勢(shì)基因塊直接復(fù)制到人工染色體上的對(duì)應(yīng)位置;然后，將尚未分配的非優(yōu)勢(shì)塊上的基因以隨機(jī)的方式插入人工染色體的空白位置，直到所有基因均插入到人工染色體中，形成完整的人工染色體。如圖5所示為人工染色體組合方式。

2.4 遺傳操作

2.4.1 交叉算子

在GA中，通過(guò)兩個(gè)原有染色體之間的交叉，可能會(huì)得到更優(yōu)異的染色體，從而實(shí)現(xiàn)種群的進(jìn)化。求解FSP的GA 大多數(shù)交叉算子均采用基于位置的交叉或兩點(diǎn)交叉機(jī)制。本文根據(jù)NWFSP的特點(diǎn)，設(shè)計(jì)了3種不同的交叉機(jī)制，分別為單段交叉、雙段交叉和三段交叉，以提高算法求解質(zhì)量，實(shí)現(xiàn)種群進(jìn)化。首先，隨機(jī)選擇交叉?zhèn)€體父代1和父代2，并選取兩個(gè)父代上相同位置的基因段，被選擇的基因段直接復(fù)制到子代;然后，父代1上的剩余基因依據(jù)父代2上基因出現(xiàn)的順序重新組合，父代2上的剩余基因依據(jù)父代1上基因出現(xiàn)的順序重新組合;最后，將重組后的基因段依序插入到對(duì)應(yīng)的子代中。圖6展示了3種交叉方式的交叉過(guò)程。

2.4.2 變異算子

交叉操作改善了算法的全局搜索能力，提高了種群的整體質(zhì)量，但較優(yōu)個(gè)體過(guò)度集中容易導(dǎo)致算法陷入局部最優(yōu)，因此在交叉操作的基礎(chǔ)上執(zhí)行變異操作，通過(guò)增強(qiáng)染色體基因突變能力，提高算法的局部搜索性能。變異操作用于全局尋優(yōu)過(guò)程，當(dāng)個(gè)體趨于最優(yōu)解時(shí)，有利的變異可以提高種群的質(zhì)量。為了使變異過(guò)程具有方向性和目的性，本研究結(jié)合種群分割的概念[28]，提出了基于種群分割思想的變異操作機(jī)制，通過(guò)執(zhí)行有效的種群分割，得到染色體質(zhì)量不同的兩個(gè)子種群，分割后的兩個(gè)染色體子種群分別賦予不同的變異概率，以保證染色體變異的有效性。

(1)水平集定義 設(shè)第G代變異染色體種群包含個(gè)體集合為POP={AC1，AC2，…，ACn}，染色體規(guī)模為n，適應(yīng)度函數(shù)為Cmax(i)，稱(chēng)集合:

(2)種群分割定義 將所得染色體中種群集合POP，按照適應(yīng)度值的升序進(jìn)行排列，根據(jù)水平集的概念，將大于或等于的最小位置作為種群分割點(diǎn)，把種群分割成兩部分，大于等于的部分記為Uac，小于的部分記為L(zhǎng)ac。

種群分割可以有效避免變異的無(wú)效性，提高算法局部尋優(yōu)能力。較優(yōu)的染色體子種群進(jìn)行小概率變異，變異概率為Pm1;次優(yōu)的染色體子種群進(jìn)行較大概率的變異，變異概率為Pm2。本研究采用兩種變異機(jī)制，首先隨機(jī)產(chǎn)生兩個(gè)變異點(diǎn)，然后分別采用兩點(diǎn)交換和反轉(zhuǎn)逆序的兩種變異機(jī)制擴(kuò)大搜索空間，以便能產(chǎn)生更好的擾動(dòng)，避免算法陷入局部最優(yōu)解。圖7為變異操作示意圖。

2.5 鄰域搜索機(jī)制

鄰域搜索的關(guān)鍵問(wèn)題是如何設(shè)計(jì)最優(yōu)解的鄰域。本研究根據(jù)NWFSP問(wèn)題的特點(diǎn)，運(yùn)用NEH算法的思想，提出了基于NEH 算法的鄰域搜索機(jī)制。具體操作步驟如下:

步驟1隨機(jī)選擇染色體上L個(gè)基因位點(diǎn)，識(shí)別出兩個(gè)連續(xù)基因位點(diǎn)之間最長(zhǎng)的片段記為L(zhǎng)1，剩余染色體上其他基因位置不變，并記為。

步驟2計(jì)算L1上各工件在機(jī)器加工過(guò)程的總時(shí)間，并按工件加工完成時(shí)間的非增順序進(jìn)行排列，得到L2。

步驟3依據(jù)NEH 算法規(guī)則，將L2上的工件依序插入到染色體的切段位置，并計(jì)算適應(yīng)度值，將適應(yīng)度值最優(yōu)的個(gè)體作為下一工件插入的基準(zhǔn)。

步驟4當(dāng)L2上所有工件插入完成后，將適應(yīng)度值最優(yōu)個(gè)體作為鄰域搜索的結(jié)果，即為鄰域搜索解。

如圖8所示為鄰域搜索的過(guò)程示意圖。

2.6 優(yōu)勢(shì)染色體保留機(jī)制

將鄰域搜索所產(chǎn)生的子代染色體與此代的原始染色體進(jìn)行比較篩選，本文采用二元競(jìng)賽法[29]選擇新的種群進(jìn)入下一代的進(jìn)化過(guò)程。二元競(jìng)賽法的操作過(guò)程如下:首先，將新的子代染色體與原始染色體放入同一個(gè)選擇池中;然后，從選擇池中隨機(jī)選擇兩條染色體，比較各自對(duì)應(yīng)的適應(yīng)度值，適應(yīng)度值小的染色體將被選作新的種群，適應(yīng)度值大的將被放回選擇池繼續(xù)進(jìn)行篩選;反復(fù)執(zhí)行上述步驟，直到所選染色體滿足種群大小，新的種群將進(jìn)入算法的下一次迭代過(guò)程。

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

3.1 實(shí)驗(yàn)設(shè)置

選擇Carlier[30]、Reeves[16]和Taillard[31]的基準(zhǔn)算例進(jìn)行實(shí)驗(yàn)驗(yàn)證。算法程序在MATLAB 2016b進(jìn)行編寫(xiě)，運(yùn)行環(huán)境為Windows10(64位)操作系統(tǒng)，處理器為Intel(R)Core(TM)i5-4200M CPU@2.50GHz 2.50GHz，內(nèi)存為8 G 的環(huán)境下運(yùn)行。為了證明本文所提算法的有效性，并能直觀地看出與其他算法比較所得結(jié)果的優(yōu)越性，所有算法運(yùn)行結(jié)果均通過(guò)平均相對(duì)百分比偏差(ARPD)進(jìn)行評(píng)估。ARPD的計(jì)算公式如下:

式中Ck表示對(duì)給定問(wèn)題進(jìn)行第k次實(shí)驗(yàn)時(shí)算法所得到的解，Copt表示當(dāng)前所求問(wèn)題的最優(yōu)解。顯然，ARPD的值越小，則算法的性能越好。此外，實(shí)驗(yàn)過(guò)程還記錄了算法運(yùn)行結(jié)果的標(biāo)準(zhǔn)偏差(SD)，以此來(lái)分析算法的魯棒性。SD的計(jì)算公式如下:

本文所提算法運(yùn)行過(guò)程中的相關(guān)參數(shù)設(shè)置如表1所示，每個(gè)算例運(yùn)行10次，選取最優(yōu)結(jié)果作為輸出解，設(shè)置算法的運(yùn)行時(shí)間為(n2/2×10)ms。

表1 參數(shù)表

3.2 算法比較

為證明本文所提NHIGA 的求解性能，將本文算法與文獻(xiàn)[10]中的禁忌搜索機(jī)制改進(jìn)迭代貪婪(Tabu-Mechanism Improved Iterated Greedy，TMIIG)算法、文獻(xiàn)[32]中的基于概率性的教與學(xué)機(jī)制的元啟發(fā)式(meta-heuristic based on Probabilistic Teaching-Learning Mechanism，mPTLM)算法和文獻(xiàn)[33]中的離散水波優(yōu)化(Discrete Water Wave Optimization，DWWO)算法進(jìn)行了對(duì)比。為闡明本文所提算法的有效性，分別從計(jì)算結(jié)果的精度、離散程度和收斂性進(jìn)行了分析比較。實(shí)驗(yàn)過(guò)程設(shè)置了相同的運(yùn)行環(huán)境和運(yùn)行時(shí)間，以保證比較結(jié)果的精確性和可靠性。

表2顯示了Carlier算例的運(yùn)行結(jié)果。如表2所示，NHIGA 求得的ARPD的平均值為0，相對(duì)TWMIIG 和mPTLM 算法所求得的0.003 與0.001，NHIGA的計(jì)算精度更高。同時(shí)，DWWO算法求得的ARPD平均值與NHIGA所求值相等，在小規(guī)模問(wèn)題上兩者的求解精確性均較優(yōu)。標(biāo)準(zhǔn)偏差SD值反映了算法運(yùn)行的穩(wěn)定性，其值越小，算法的穩(wěn)定性更好。由表2可知，NHIGA求得的SD平均值為0，均低于其他3種算法所求結(jié)果。綜上分析，本文所提算法在求解小規(guī)模問(wèn)題上具有較好的求解精度和較高的穩(wěn)定性。

表2 Carlier基準(zhǔn)算例測(cè)試結(jié)果比較

如表3所示為算法求解Reeves算例運(yùn)行結(jié)果。從表格中可以看出，在工件規(guī)模數(shù)n=20時(shí)，NHIGA與其他算法求解結(jié)果基本一致，但其他較大規(guī)模的問(wèn)題，NHIGA 的求解質(zhì)量?jī)?yōu)于其他3種算法的求解質(zhì)量。從總體上看，NHIGA 所求ARPD 的平均值為0.06，明顯優(yōu)于TWMIIG、mPTLM 和DWWO 三種算法求得的0.11、0.08、0.07，這表明NHIGA算法在求解較大規(guī)模的NWFSP問(wèn)題時(shí)，其算法計(jì)算精度依然更優(yōu)。從NHIGA 所求的標(biāo)準(zhǔn)偏差SD的平均值也可以看出，通過(guò)NHIGA求得的結(jié)果離散程度較小，表明NHIGA的穩(wěn)定性能更優(yōu)。

表3 Reeves基準(zhǔn)算例測(cè)試結(jié)果比較

圖9和圖10 展示了NHIGA 算法求解算例Rec35和Rec41時(shí)與其他3種算法的收斂曲線對(duì)比圖。圖9和圖10表明NHIGA 的收斂速率和求解精確度均優(yōu)于其他3種算法。圖11與圖12展示了4種算法在求解算例Rec35和Rec41時(shí)所得數(shù)據(jù)的箱型圖，箱型圖可以直接反應(yīng)測(cè)試數(shù)據(jù)的離散程度，進(jìn)而可以判斷算法的穩(wěn)定性。圖11與圖12進(jìn)一步驗(yàn)證了NHIGA 在求解NWFSP 問(wèn)題時(shí)，相比TWMIIG、mPTLM 算法和DWWO 算法具有較好的穩(wěn)定性。

為進(jìn)一步證明NHIGA算法在求解大規(guī)模問(wèn)題時(shí)的優(yōu)越性，本文測(cè)試了Taillard算例。如表4所示，對(duì)于大規(guī)模問(wèn)題的求解，NHIGA 算法與其他3種算法相比，其計(jì)算精度依然更高。在求解算例Ta100、算例Ta110和算例Ta120時(shí)，NHIGA 求得的ARPD值均小于其他3種算法得到的ARPD值，這表明NHIGA 在求解大規(guī)模問(wèn)題時(shí)仍然具有較好的求解性能。此外，SD值也反映了NHIGA 算法在求解大規(guī)模問(wèn)題中的穩(wěn)定性。

實(shí)驗(yàn)過(guò)程還展示了算法求解算例Ta55和算例Ta90的收斂曲線對(duì)比圖，如圖13和圖14所示。收斂圖證明了NHIGA 算法收斂速度更快，尋優(yōu)能力更強(qiáng)，能夠求得更優(yōu)的結(jié)果。圖15和圖16顯示了求解算例Ta55和算例Ta90時(shí)所得數(shù)據(jù)結(jié)果的箱型圖，該圖進(jìn)一步說(shuō)明了本文所提算法在求解較大規(guī)模的問(wèn)題時(shí)仍然具有較好的穩(wěn)定性。由于所有算法的運(yùn)行環(huán)境是相同的，由此可以說(shuō)明NHIGA 比其他算法的求解性能更優(yōu)。

表4 Taillard基準(zhǔn)算例測(cè)試結(jié)果比較

4 結(jié)束語(yǔ)

本文以最小化完工時(shí)間為優(yōu)化目標(biāo)，根據(jù)零等待流水車(chē)間調(diào)度問(wèn)題的特點(diǎn)，提出了新型混合改進(jìn)遺傳算法。初始化過(guò)程采用改進(jìn)NEH 算法形成具有較高質(zhì)量的初始種群;在算法計(jì)算過(guò)程中設(shè)計(jì)了基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘方法，尋找優(yōu)勢(shì)染色體上的優(yōu)勢(shì)基因，并將優(yōu)勢(shì)基因組成優(yōu)勢(shì)塊，借助優(yōu)勢(shì)塊實(shí)現(xiàn)基因重組，從而達(dá)到降低問(wèn)題復(fù)雜度、加快算法求解效率的目的;算法交叉過(guò)程設(shè)計(jì)了3種交叉方式，有效地提高了算法的交叉性能，從而引導(dǎo)個(gè)體向優(yōu)勢(shì)個(gè)體發(fā)展;為提高種群多樣性，避免變異的無(wú)效性，結(jié)合種群分割思想提出了基于眾群分割的變異操作，將分割后兩個(gè)不同質(zhì)量的子種群賦予不同的變異概率;此外，根據(jù)NWFSP的特點(diǎn)提出了基于NEH 的鄰域搜索機(jī)制，以提升算法的局部搜索能力，進(jìn)一步提高種群質(zhì)量和多樣性。采用標(biāo)準(zhǔn)算例對(duì)算法有效性進(jìn)行了驗(yàn)證，通過(guò)分析計(jì)算結(jié)果的精度、離散程度和收斂性，表明了本文算法求解NWFSP的可行性和有效性。但是，本研究未對(duì)參數(shù)的選擇進(jìn)行理論說(shuō)明，這是下一步需要進(jìn)行深入研究的地方。同時(shí)，NWFSP還存在其他更接近生產(chǎn)實(shí)際的約束問(wèn)題，下一步將對(duì)問(wèn)題進(jìn)行深入挖掘，研究更加符合生產(chǎn)實(shí)際的具有多種約束機(jī)制的NWFSP模型。