裴小兵，張春花

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

置換流水車間調(diào)度問(wèn)題(permutation flow-shop scheduling problem, PFSP)是廣泛受到研究的一種組合優(yōu)化問(wèn)題，屬于NP-hard問(wèn)題。PFSP的搜索空間中存在諸多局部最優(yōu)解，且問(wèn)題復(fù)雜度越高，越容易局部最優(yōu)化，因此許多學(xué)者針對(duì)PFSP特性不斷對(duì)求解PFSP的算法進(jìn)行優(yōu)化。求解PFSP的算法可分為精確算法和近似算法，精確算法雖能求出最優(yōu)解，但時(shí)間復(fù)雜性較高，隨著問(wèn)題的規(guī)模增大將變得不可行。近似算法對(duì)于較大規(guī)模的問(wèn)題能在可行時(shí)間內(nèi)求出近優(yōu)解，是研究PFSP問(wèn)題的重要方法。近似算法包括遺傳算法[1]、蟻群算法[2]、模擬退火算法[3]等。

遺傳算法(genetic algorithm, GA)通過(guò)選擇、交叉和變異等操作搜索解空間的最優(yōu)解，已經(jīng)成功應(yīng)用于解決旅行商問(wèn)題、車輛路徑問(wèn)題和車間調(diào)度問(wèn)題等不同領(lǐng)域的組合問(wèn)題。但是遺傳算法的局部搜索能力較差，在實(shí)際應(yīng)用中容易產(chǎn)生早熟收斂的問(wèn)題。怎么運(yùn)用遺傳算法既能保留優(yōu)良個(gè)體，又能維持群體的多樣性，一直是遺傳算法中較難解決的問(wèn)題。近年來(lái)針對(duì)PFSP，不少學(xué)者為提高遺傳算法的有效性，將遺傳算法與其他算法相結(jié)合對(duì)該問(wèn)題進(jìn)行求解，取得了不錯(cuò)的效果。Benbouzid等[4]針對(duì)PFSP提出VacGA(introduces vaccination into the field of GAs)，將遺傳算法和免疫算法相結(jié)合，遺傳算法執(zhí)行全局搜索，人工免疫系統(tǒng)執(zhí)行局部搜索，以克服演化過(guò)程中遺傳算法局部搜索能力不足的問(wèn)題。Chen等[5]將遺傳算法與廣義鄰域搜索相結(jié)合，提出一種新型混合遺傳算法求解PFSP。Bessedik等[6]提出一種基于免疫的遺傳算法，這種算法分為兩種形式：1）將接種引入到基于免疫理論的遺傳算法；2）從免疫網(wǎng)絡(luò)理論得到啟發(fā)，并將其運(yùn)用到遺傳算法中。Ganguly等[7]將貪婪局部搜索算子引入到遺傳算法，有效地解決大范圍的排序和調(diào)度離散優(yōu)化問(wèn)題。齊學(xué)梅等[8]為求解PFSP問(wèn)題，將變鄰域搜索算法與遺傳算法相結(jié)合，加快了收斂速度。吳秀麗等[9]將變鄰域搜索算法和遺傳算法相結(jié)合提出了一種變鄰域改進(jìn)遺傳算法求解混合流水車間調(diào)度問(wèn)題，增強(qiáng)了遺傳算法的局部搜索能力。

Chang等[10]針對(duì)置換流水車間調(diào)度問(wèn)題，提出一種基于區(qū)塊的遺傳算法(puzzle-based artificial chromosome genetic algorithm，p-ACGA)，將遺傳算法和蟻群算法相結(jié)合，通過(guò)簡(jiǎn)單遺傳算法的交叉、突變等操作產(chǎn)生精英群體，針對(duì)這些精英群體，利用蟻群算法的信息素濃度對(duì)工件與工件的關(guān)系進(jìn)行統(tǒng)計(jì)分析，進(jìn)而建立信息素相依矩陣并根據(jù)矩陣挖掘區(qū)塊，利用區(qū)塊和非區(qū)塊重組形成人工染色體，然后將其注入到進(jìn)化過(guò)程中。雖然p-ACGA能夠避免局部最優(yōu)問(wèn)題，一定程度上改善了解的質(zhì)量，加快了進(jìn)化速度，但是算法在初始化、信息素分布統(tǒng)計(jì)等方面還存在一些不足。因此本文提出一種改進(jìn)區(qū)塊遺傳算法(puzzlebased improved artificial chromosome genetic algorithm，p-IACGA)。該算法在種群初始化時(shí)引入反向?qū)W習(xí)的思想，并對(duì)其進(jìn)行了改進(jìn)，將其與隨機(jī)機(jī)制相結(jié)合產(chǎn)生初始解，大大提高了初始解的多樣性和質(zhì)量；為進(jìn)一步描述信息素在路徑上的分布情況，算法考慮了信息素在節(jié)點(diǎn)上的分布情況，即工件與所在解序列位置的關(guān)系，并將其與p-ACGA中的統(tǒng)計(jì)分析工件與工件的相鄰關(guān)系相結(jié)合，以全面地描述解的空間分布情況。然后，根據(jù)這兩種關(guān)系建立相依信息素矩陣和位置信息素矩陣，進(jìn)而挖掘區(qū)塊以組合人工染色體。最后，引入染色體重組機(jī)制，進(jìn)一步提高解的質(zhì)量。

1 置換流水車間生產(chǎn)調(diào)度問(wèn)題描述

PFSP生產(chǎn)調(diào)度問(wèn)題可以描述為：有 n 個(gè)作業(yè)以相同的順序在 m 臺(tái)機(jī)器上加工。同時(shí)，要滿足的約束條件包括：1)操作是獨(dú)立的，可以在零時(shí)間開始；2)每臺(tái)機(jī)器在同一時(shí)間最多加工一個(gè)工件；3)每一個(gè)工件在同一時(shí)間只能在一臺(tái)機(jī)器上加工。用 P ( i,j) 表 示工件 i 在 機(jī)器 j 上的處理時(shí)間，用(π1,π2,···,πn) 表示工件序列，用 C ( πi,j) 表示完成時(shí)間的計(jì)算，即

2 求解置換流水車間調(diào)度問(wèn)題的改進(jìn)區(qū)塊遺傳算法

p-IACGA主要分為5部分：產(chǎn)生初始解、挖掘區(qū)塊、構(gòu)建人工染色體、染色體重組和保留優(yōu)勢(shì)解。p-IACGA流程如圖1所示，因?yàn)槿旧w攜帶的較優(yōu)信息是逐代積累的，所以為了挖掘出較優(yōu)人工染色體，每執(zhí)行 n(給定的一個(gè)數(shù))代遺傳算法后挖掘一次區(qū)塊，這樣每一輪執(zhí)行的總代數(shù)是 n + 1。解并對(duì)每條初始解求出它的反向解；然后，將兩種群混合在一起形成規(guī)模為2 N 的種群，計(jì)算每個(gè)解的適應(yīng)度，并按照適應(yīng)度大小對(duì)解降序排列；最后，選擇前 N 條適應(yīng)度較大的解作為進(jìn)化的初始種群。

圖 1 p-IACGA流程Fig. 1 Flow chart of p-IACGA

圖 2 改進(jìn)反向?qū)W習(xí)法Fig. 2 Improved opposition-based learning

2.1 改進(jìn)反向?qū)W習(xí)法初始化種群

1)反向?qū)W習(xí)法

通過(guò)同時(shí)評(píng)估這兩個(gè)解可以獲得更好的結(jié)果。

2)應(yīng)用改進(jìn)反向?qū)W習(xí)法進(jìn)行種群初始化

初始化過(guò)程采用隨機(jī)機(jī)制和改進(jìn)反向?qū)W習(xí)機(jī)制相結(jié)合的方式，以兼顧初始解的多樣性和質(zhì)量。本研究對(duì)反向?qū)W習(xí)法作了改進(jìn)以減少優(yōu)秀解的丟失，基本思路就是將所有原始解和所有反向解混合在一起形成混合群體，然后從混合群體中選出適應(yīng)度較高的解，如圖2所示。首先利用隨機(jī)方式產(chǎn)生 N(N 為給定的初始種群規(guī)模)條初始

2.2 挖掘區(qū)塊

在遺傳算法中，進(jìn)化若干代后，大部分染色體都會(huì)攜帶與較優(yōu)解相似的一些信息，這些信息具有相似性并且這些相似性在大規(guī)模的種群中具有一定的可靠性[12]。在p-IACGA中，使用蟻群優(yōu)化算法(ant colony optimization，ACO)中的螞蟻信息素濃度來(lái)識(shí)別染色體中較好的相似序列并通過(guò)區(qū)塊的方式將它們挖掘出來(lái)。

1)建立信息素矩陣

本研究使用相依信息素矩陣和位置信息素矩陣來(lái)記錄螞蟻經(jīng)過(guò)的路徑信息，其中位置信息素矩陣記錄每個(gè)節(jié)點(diǎn)(工件在解序列中的位置)的信息素濃度信息，相依信息素矩陣記錄兩節(jié)點(diǎn)間的路徑(兩工件間的相鄰關(guān)系)的信息素濃度信息。矩陣建立過(guò)程如下：

從第 n 代中選擇一條最優(yōu)染色體進(jìn)行矩陣初始化。圖3為初始相依信息素矩陣生成過(guò)程，兩個(gè)工件間的初始信息素表示為 τ0(見式(1))。同樣的方法生成初始位置信息素矩陣如圖4。

式中 L 表示完工時(shí)間。

圖 3 初始相依信息素矩陣Fig. 3 Initially dependent pheromone matrix

圖 4 初始位置信息素矩陣Fig. 4 The initial position pheromone matrix

由遺傳算法產(chǎn)生的最新一代的前30%適應(yīng)度較高的染色體更新信息素矩陣，更新過(guò)程如圖5，更新公式如式(2)：

圖 5 更新相依信息素矩陣Fig. 5 Update dependent pheromone matrix

同理，得到更新的位置信息素矩陣如圖6。更新公式如式(3)：

圖 6 更新的位置信息素矩陣Fig. 6 Updated positional information matrix

2)構(gòu)建區(qū)塊

區(qū)塊是簡(jiǎn)短的染色體片段，本研究通過(guò)學(xué)習(xí)鏈接關(guān)系[13]構(gòu)建區(qū)塊。首先確定區(qū)塊的最小長(zhǎng)度，然后隨機(jī)選擇起始位置，最后為各位置選擇工序。在區(qū)塊最小長(zhǎng)度內(nèi)，起始位置采用位置信息素矩陣中的信息選擇工序，如圖7，假設(shè)選擇工件 J1放 入起始位置 S1。其他位置采用位置信息素矩陣和相依信息素矩陣的合并信息，以輪盤賭選擇法(roulette wheel section，RWS)[13]對(duì)工序進(jìn)行篩選，已經(jīng)入選的工件不再進(jìn)行篩選，如圖8，假設(shè) C P2最大，選擇工件 J2放入位置 S2。

圖 7 起始位置工序挑選Fig. 7 Starting position process selection

圖 8 區(qū)塊最小長(zhǎng)度內(nèi)其他位置工件選擇Fig. 8 Workpiece selection at other positions within the block's minimum length

當(dāng)出現(xiàn)兩個(gè)或多個(gè)較大值時(shí)隨機(jī)選擇。位置信息素濃度概率計(jì)算公式為

式中：i 表示工件號(hào)；j 表 示 i 所連接的上一個(gè)工件號(hào)； m 表示染色體上的工件的位置；n 表示染色體長(zhǎng)度； P′表示工件 i 與 位置 m 在位置矩陣的概

im率； Pij表 示相依矩陣中工件 j 相 連于工件 i 之后的概率； C Pi表 示工件 i 的 合并概率； W′與 W 分別表示位置矩陣與相依矩陣的權(quán)重值，權(quán)重值會(huì)隨著進(jìn)化代數(shù)的增加不斷改變[14]。

對(duì)最小長(zhǎng)度外的位置進(jìn)行工序選擇時(shí)設(shè)立合并概率最小閾值[15]，作為篩選條件。當(dāng)工件的合并概率大于最小閾值時(shí)，選擇該工件，否則停止選擇工件，本區(qū)塊完成挖掘，如圖9所示。因?yàn)楫?dāng)區(qū)塊包含的工件越多總體概率越低，組合錯(cuò)誤的概率越大，區(qū)塊閾值將會(huì)保證區(qū)塊的質(zhì)量，同時(shí)也將會(huì)導(dǎo)致挖掘出的區(qū)塊長(zhǎng)度也有所不同。挖掘的區(qū)塊均存放在區(qū)塊資料庫(kù)中。

3)區(qū)塊競(jìng)爭(zhēng)

區(qū)塊競(jìng)爭(zhēng)[16]就是去除有重復(fù)信息的區(qū)塊。將區(qū)塊資料庫(kù)中的區(qū)塊的工序與位置進(jìn)行比對(duì)，如果區(qū)塊之間出現(xiàn)重復(fù)的工序或涵蓋的位置重復(fù)，則通過(guò)比較平均概率的方式進(jìn)行選擇，平均概率較大者保留至區(qū)塊資料庫(kù)，較小者則刪除，舉例如圖10。平均概率的計(jì)算公式為表示區(qū)塊的長(zhǎng)度；表示第 i 條區(qū)塊的第 l 個(gè)工件的位置概率； C PBil表示第 i 個(gè)區(qū)塊的第 l 個(gè)工件的合并概率。

圖 9 區(qū)塊最小長(zhǎng)度外的工件選擇Fig. 9 Selection of workpieces outside the block minimum length

圖 10 區(qū)塊競(jìng)爭(zhēng)Fig. 10 Block competition

2.3 組合染色體

本研究利用新建區(qū)塊資料庫(kù)中的區(qū)塊和非區(qū)塊資料庫(kù)中的工件組合出較優(yōu)染色體。先將區(qū)塊資料庫(kù)中的所有區(qū)塊復(fù)制到確定長(zhǎng)度的空白染色體對(duì)應(yīng)位置，對(duì)于尚未放入工序的空位置依照其位置順序(由左到右)，利用RWS方法根據(jù)合并概率從剩余的工件中選擇合適工件放入其中。例如圖11區(qū)塊資料庫(kù)中有2個(gè)區(qū)塊，非區(qū)塊資料庫(kù)有2個(gè)工件，合并概率 C P6大 于 C P5， 選擇 J6放至位置5，剩下 J5放至位置9。

2.4 染色體重組

為了進(jìn)一步提高算法搜索到最優(yōu)解的機(jī)會(huì)，對(duì)每一代染色體進(jìn)行重組。首先隨機(jī)選擇 N 個(gè)切點(diǎn)，將一條完整的染色體分割成 N +1 個(gè)片段，再?gòu)倪@些片段中選擇出長(zhǎng)度最長(zhǎng)的片段進(jìn)行重組。以工件數(shù)為10切點(diǎn)數(shù)為2為例，如圖12，切割完成后的段數(shù)為 3 段，分別為{5，2}、{2，6，10，9，1，7}及{7，4，3，8}，選擇長(zhǎng)度較長(zhǎng)的片段進(jìn)行重組，過(guò)程如圖13所示。

圖 12 切割人工染色體Fig. 12 Cutting an artificial chromosome

圖 13 人工染色體重組Fig. 13 Artificial chromosome reorganization

2.5 留存優(yōu)勢(shì)解

將重組后的GA最新子代 μi和人工染色體Ci放入選擇池，使用二元競(jìng)賽法[17]選擇出優(yōu)秀染色體作為子代進(jìn)入下一代進(jìn)化。首先，從選擇池中隨機(jī)選擇兩條染色體，比較適應(yīng)度，選擇適應(yīng)度較大的染色體放入染色體庫(kù)，適應(yīng)度較小的染色體放回選擇池繼續(xù)篩選，反復(fù)執(zhí)行上述步驟，直到染色體庫(kù)中染色體的數(shù)量滿足設(shè)定的群體大小，如圖14。

圖 14 留存優(yōu)勢(shì)解Fig. 14 Retention of advantage solution

3 實(shí)驗(yàn)結(jié)果分析

為了評(píng)估所提出的算法的性能，本研究將通過(guò)對(duì)不同實(shí)例進(jìn)行測(cè)試，使用誤差率(ER)作為對(duì)比指標(biāo)，與其他算法進(jìn)行比較。誤差率是指測(cè)試中算法所得最優(yōu)解與實(shí)例已知最優(yōu)解的差值占實(shí)例已知最優(yōu)解的比例，ER計(jì)算公式為

式中： Ui是 實(shí)例的已知最優(yōu)解； Cmax是測(cè)試算法的最優(yōu)解。

本文所提算法由C++語(yǔ)言編寫，程序的運(yùn)行環(huán)境為：處理器Intel(R) Core(TM) i5-4005U CPU @3.40 GHz，內(nèi)存為4.0 GB的計(jì)算機(jī)。在本文中，選擇了29個(gè)調(diào)度問(wèn)題進(jìn)行比較，其中21個(gè)Reeves實(shí)例和8個(gè)Taillard實(shí)例，每個(gè)實(shí)例獨(dú)立運(yùn)行30次，并求出ER的平均值。為了達(dá)到性能評(píng)價(jià)的目的，在 SGA[18]、ACGA[19]、p-ACGA[10]、BBEDA[18]、LMBBEA[20]、p-IACGA 的參數(shù)設(shè)置上選擇了最佳的、相同的參數(shù)配置以保證了算法的可比性。

以 SGA、ACGA、p-ACGA、BBEDA、LMBBEA和p-IACGA計(jì)算Taillard實(shí)例，結(jié)果如表1所示。從表 1可以看出，ta005、ta010、ta020、ta030、ta070和 ta080這6個(gè)實(shí)例中的ER值均為0，即找到了6個(gè)與實(shí)例已知解相同的解，多于其他算法所能找到的個(gè)數(shù)。盡管在 ta050實(shí)例中，BBEDA和LMBBEA的 ER值為0.85，p-IACGA的ER值為0.97，前兩者的結(jié)果優(yōu)于p-IACGA，但是p-IACGA的平均值ER為0.32%，均低于其他算法，表明p-IACGA的整體求解問(wèn)題的性能優(yōu)于其他算法。同理，用這些算法計(jì)算Reeves實(shí)例，結(jié)果如表2。通過(guò)對(duì)Reeves的21個(gè)實(shí)例測(cè)試，發(fā)現(xiàn)p-IACGA在Rec0 1 、 R e c0 3 、 R e c0 9 、 R e c1 1 和 R e c35實(shí)例中ER的值為0，找到了5個(gè)與實(shí)例已知解相同的解，多于其他算法，且p-IACGA的平均誤差率為0.46，均小于其他算法，充分表明p-IACGA求解PFSP的優(yōu)良性能。

表 1 Taillard實(shí)例測(cè)試結(jié)果比較Table 1 Comparison of Taillard instance test results

表 2 Reeves實(shí)例測(cè)試結(jié)果比較Table 2 Comparison of Reeves instance test results

續(xù)表 2

為了更直觀地比較算法性能，圖15給出了關(guān)于p-ACGA和p-IACGA兩個(gè)算法測(cè)試部分Taillard實(shí)例的收斂圖。從圖15中可以看出，在相同的最大迭代次數(shù)下，p-IACGA的收斂速度比p-ACGA更快。在進(jìn)化初期，算法通過(guò)優(yōu)化初始方法提高初始解的質(zhì)量，保證進(jìn)化過(guò)程中解的質(zhì)量；采用節(jié)點(diǎn)信息濃度和路徑信息度相結(jié)合的方式生成矩陣，提高了區(qū)塊質(zhì)量。在進(jìn)化的后期，應(yīng)用二元競(jìng)賽法來(lái)尋找具有更優(yōu)適應(yīng)值的解，加快了進(jìn)化速度。

圖 15 算例收斂圖Fig. 15 Instance convergence diagram

通過(guò)實(shí)驗(yàn)數(shù)據(jù)分析，對(duì)于求解PFSP，本文提出的p-IACGA相較于SGA、ACGA、p-ACGA、BBEDA、LMBBEA和p-IACGA具有較優(yōu)的求解性能。

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

本文針對(duì)置換流水車間調(diào)度問(wèn)題，通過(guò)對(duì)p-ACGA改進(jìn)，提出了p-IACGA。該算法初始化采用隨機(jī)機(jī)制和改進(jìn)反向?qū)W習(xí)機(jī)制相結(jié)合的方式，提高了初始種群的多樣性和質(zhì)量。進(jìn)一步考慮了工件與所在解序列的位置關(guān)系，對(duì)節(jié)點(diǎn)信息素濃度進(jìn)行了分析，通過(guò)位置信息素矩陣和相依信息素矩陣挖掘區(qū)塊加快了收斂速度，提高了最終解的質(zhì)量。該算法保留了傳統(tǒng)GA的交叉、變異等操作，通過(guò)若干代的GA進(jìn)化過(guò)程產(chǎn)生精英群體，不斷更新區(qū)塊，提高了人工染色體的質(zhì)量和更新速度。實(shí)驗(yàn)中，通過(guò)Taillard和Reeves實(shí)例進(jìn)行測(cè)試，以誤差率作為比較指標(biāo)，將結(jié)果與其他算法比較，驗(yàn)證了p-IACGA的有效性。

未來(lái)研究方向可以將所提出的p-IACGA應(yīng)用于其他組合優(yōu)化問(wèn)題，如旅行商問(wèn)題、車輛路徑問(wèn)題等。也可以通過(guò)改進(jìn)該算法對(duì)PFSP的最小化流程時(shí)間、最小化延遲時(shí)間等其他一個(gè)或多個(gè)目標(biāo)進(jìn)行研究。