一種改進的和聲搜索算法求解FJSP

徐文星 梁菁菁 高梓森 俞奉伶 盛 沙*

1(北京石油化工學院信息工程學院 北京 102617) 2(北京市密云區(qū)科學技術(shù)委員會 北京 101500)

0 引 言

柔性作業(yè)車間調(diào)度問題(FJSP)是傳統(tǒng)車間調(diào)度的擴展。由于一道工序可以由給定集合中的任何機器處理[1-2]，F(xiàn)JSP增強了生產(chǎn)調(diào)度的靈活性，更加貼近實際生產(chǎn)中的制造環(huán)境[3]。但因為不僅需要對工序加工順序進行排序，還需要給工序分配機器，F(xiàn)JSP比傳統(tǒng)作業(yè)車間調(diào)度問題更復雜，同樣歸為NP-hard類問題[4]。

雖然FJSP的復雜性是眾所周知的，但是為了適應(yīng)當前市場的需要，研究者們還是更多地關(guān)注FJSP。目前，F(xiàn)JSP的求解方法分為兩種，精確算法和近似算法。精確算法的優(yōu)化結(jié)果雖然精確，但在有限的時間里無法有效解決大規(guī)模車間調(diào)度問題。另一種方法是近似算法，目前，隨著智能算法的發(fā)展，應(yīng)用智能算法求解該問題已經(jīng)成為最流行的方法，如：Lu等[5]利用遺傳算法(GA)求解分布式FJSP；Wang等[6]采用一種改進的蟻群優(yōu)化算法(IACO)來優(yōu)化FJSP的最大完工時間；Zarrouk等[7]提出了一種兩級粒子群優(yōu)化算法求解FJSP；Gao等[8]針對具有模糊處理時間的FJSP，提出了一種改進的人工蜂群(IABC)算法；姜天華[9]將混合灰狼優(yōu)化算法(GWO)用于求解FJSP。雖然智能算法在FJSP上進行了大量研究，但仍然沒有一種智能算法能夠求得所有FJSP的最優(yōu)解，所以研究者們還在不斷地探索新的、更有效的方法。

近年來，隨著智能算法的不斷發(fā)展，出現(xiàn)了模擬音樂家演奏出完美和聲過程的和聲搜索算法[10]，該算法具有理論簡單和易實現(xiàn)的特點。為了提高和聲搜索算法的搜索能力，Zou等[11]將和聲搜索算法與遺傳算法融合做出改進，以遺傳突變替換了隨機選擇部分，對和聲記憶庫中的最壞和聲進行小概率遺傳變異操作，既增強了收斂性，又能有效地防止神經(jīng)網(wǎng)絡(luò)陷入局部最優(yōu)，在解決無約束問題上取得了一定成效。隨后，改進的和聲搜索算法被嘗試用于調(diào)度問題。Pan等[12]將和聲搜索算法應(yīng)用于批量流水車間調(diào)度。吳龍成等[13]將改進的和聲搜索算法應(yīng)用于硫化車間調(diào)度。張敬敏等[14]將差分和聲搜索算法應(yīng)用到作業(yè)車間調(diào)度問題。Yuan等[15]將基于集成方法的混合和聲搜索算法應(yīng)用到了FJSP。崔喆[16]在和聲搜索算法中加入差分進化策略，變異過程中對和聲庫中的所有和聲以一定的變異概率進行插入操作，在解決流水車間調(diào)度問題上取得了一定成效。Gao等[17]將離散和聲搜索算法應(yīng)用于多目標FJSP。和聲搜索算法應(yīng)用于車間調(diào)度領(lǐng)域求解問題取得了一定的成效，但仍然存在很多不足。雖然和聲搜索算法具有很強的全局搜索能力，但是局部搜索能力比較弱，后期進化速度大幅減慢，同時應(yīng)用在FJSP問題上操作復雜。結(jié)合前人的研究與改進思想，本文針對不足之處提出一種適用于柔性作業(yè)車間編碼方式的改進和聲搜索算法。采用兩種初始化方式混合應(yīng)用進行初始化，保證了解的多樣性和解的質(zhì)量；基于兩段組合編碼方式，結(jié)合一種新的創(chuàng)作和聲策略來進行和聲更新，避免產(chǎn)生無效解；采用一次創(chuàng)作多個和聲來充分利用和聲庫的有用資源，同時應(yīng)用智能變異算子均衡機器負載，在保證全局搜索效率的同時，加強了局部搜索能力。最后通過實例測試結(jié)果證明了改進和聲搜索算法對于求解單目標FJSP的有效性。

1 柔性作業(yè)車間問題

FJSP是n個工件J(Ji,i∈{1,2,…,n})在m臺機器M(Mk,k∈{1,2,…,m})上加工的調(diào)度模型。每個工件由一道或者多道操作工序O(Oij,j∈{1,2,…,ni})組成，ni表示當前工件的總工序數(shù)。每道工序可選擇允許機器集(一臺或多臺不同機器)中任意一臺機器進行加工。FJSP的目的是選擇加工每道工序的機器設(shè)備，并且對所有工序進行排序，達到優(yōu)化目標的最優(yōu)值。此類問題滿足的約束條件有：

(1) 在同一工件中，工序具有優(yōu)先級，前一道工序加工后才可以開始加工下一道。

(2) 不同工件的加工優(yōu)先級相同。不同工件的工序加工優(yōu)先級也是相同的。

(3) 在0時刻，假設(shè)所有機器都是空閑的,并且在機器加工完成到下一道工序沒有開始時進行空載運行。

(4) 同一個工件上的同一道工序只能在一臺機器上加工。同一時刻每臺機器上也只能加工一道工序。

(5) 任何工序一旦開始加工，就不可間斷。

(6) 工件的準備時間以及轉(zhuǎn)移時間都算在加工時間內(nèi)。

本文在求解FJSP時，考慮優(yōu)化調(diào)度系統(tǒng)最大完工時間這一優(yōu)化目標。即在滿足上述所有約束條件后，達到機器最大完工時間值最小化。用MT(k)表示在第k臺機器上的完工時間，則數(shù)學模型表示為：

(1)

如表1所示的3×5 FJSP實例，有3個工件，每個工件對應(yīng)3道工序，每道工序有多臺機可供選擇，在可選擇機器上的加工時間分別給出，“—”表示對應(yīng)該道工序不能在對應(yīng)此臺機器上加工。本文后續(xù)均以這一實例為例對改進和聲搜索算法求解FJSP過程進行說明。

表1 3×5 FJSP實例描述

2 基本和聲搜索算法

和聲搜索就是把音樂家彈奏樂曲的過程轉(zhuǎn)化為數(shù)學表示。首先按照和聲記憶庫大小(Harmony Memory Size, HMS)初始化和聲記憶庫，并且對和聲庫內(nèi)的和聲按照目標解由優(yōu)到差的次序排出最優(yōu)解和最差解，存放解向量的HM矩陣如式(2)所示。然后每次創(chuàng)作一個新和聲進行迭代。創(chuàng)造的新和聲就是產(chǎn)生的一個新的解向量，創(chuàng)造方式由考慮從和聲庫中學習、考慮是否調(diào)整和聲音調(diào)、隨機創(chuàng)作一個新的音調(diào)三部分組成。最后更新和聲庫，將創(chuàng)作的新和聲與和聲記憶庫內(nèi)的最差和聲進行比較，如果新和聲的解優(yōu)于和聲庫內(nèi)的最差解，則將新和聲放入和聲庫內(nèi)，否則保留原和聲庫的和聲。

(2)

3 改進和聲搜索算法求解FJSP

3.1 編碼與解碼

柔性作業(yè)車間要解決的主要問題分為兩部分：(1) 對加工每道工序的機器集里的機器進行選擇；(2) 對工序的加工順序進行排序。故本文采用兩段組合編碼方式對和聲搜索算法進行編碼，將一組和聲分為機器選擇部分(Machine Selection Section， MSS)和工序排序部分(Operational Sequencing Section， OSS)兩段。每段編碼長度為工序數(shù)L，總編碼長度為2L。

(1) 和聲的機器選擇部分編碼：按照工件工序的順序依次選擇機器，這部分每一個音符代表機器在可選機器集中的位置號，如圖1所示，和聲的第一個音符“4”為第一個工件第一道工序所對應(yīng)機器集{M1，M2，M3，M5}中的第四臺機器M5。

圖1 MSS/OSS編碼說明

(2) 和聲的工序排序部分編碼：每個音符代表的都是它的工件數(shù)，相同音符出現(xiàn)的次序就是這個工件的工序數(shù)。第一個音符“2”就表示為第二個工件的第一道工序，即O21。

解碼是編碼的逆過程，是將一組和聲工序排序部分解碼成對應(yīng)機器選擇部分的活動調(diào)度的過程。依據(jù)工序順序?qū)?yīng)的機器編碼選擇每道工序的加工機器和加工時間，按照工序部分編碼確定的順序依次進行解碼，并且采用插入法在不改變已安排工序的情況下，將新工序盡可能地插入對應(yīng)機器上的空閑位置進行加工，縮短在這臺機器上加工的完成時間。

3.2 和聲記憶庫初始化

同其他智能算法類似，和聲搜索算法的和聲記憶庫初始化也直接影響和聲搜索的最終解。對于和聲記憶庫的初始化要達到兩個要求：(1) 要保持和聲記憶庫的多樣性，擴大搜索范圍，提高搜索到全局最優(yōu)解的概率；(2) 要保證和聲記憶庫初始化的解的質(zhì)量，解的質(zhì)量影響著收斂速率。為了更好地達到以上兩點要求，本文對和聲記憶庫中和聲的機器選擇部分和工序排序部分采用不同的初始化方式，具體方案如下：

(1) 和聲的工序排序部分則采用隨機生成方式，這樣能使解的分布更廣，達到擴大解的搜索范圍的目的。

(2) 和聲的工序排序部分則采用優(yōu)先對關(guān)鍵工序進行機器選擇的全局初始化方式[18]，全面考慮到關(guān)鍵工序?qū)C器負荷和工件加工時間產(chǎn)生的重要影響，提高初始解的質(zhì)量。

3.3 創(chuàng)作新和聲

基本的和聲算法在每次迭代時，只創(chuàng)造一個新和聲，沒有最大可能地利用和聲庫里積累下來的信息，因此本文提出改進策略，在每次迭代時同時產(chǎn)生多個新和聲，然后用多個新和聲進行迭代，以此提高搜索速度。在創(chuàng)作新和聲的機器選擇部分和工序排序部分時結(jié)合了FJSP的特征采用了有效的創(chuàng)作方式[19]，創(chuàng)作步驟如下。

(1) 新和聲的機器選擇部分：生成新和聲機器選擇部分的策略是當rand1

圖2 創(chuàng)作MSS示例

(2) 新和聲的工序排序部分：按照傳統(tǒng)的和聲搜索去創(chuàng)作新和聲的工序排序部分可能會生成非法解，故結(jié)合FJSP特性對生成策略做了調(diào)整，加入了一個轉(zhuǎn)化矩陣，將生成新和聲工序排序部分分為兩個模塊。第一模塊是生成轉(zhuǎn)換矩陣，首先將n個工件號置亂，對每一個工件進行判斷，當rand1

圖3 創(chuàng)作OSS示例

3.4 和聲智能變異

為了提高算法的搜索能力，本文在生成的多個新和聲中進行智能變異操作，并且在變異操作過程中結(jié)合FJSP的特點考慮到平衡機器負載，增加搜索到最優(yōu)和聲的概率，提高搜索最優(yōu)和聲速率，可以更有效求解FJSP。智能變異操作的步驟：(1) 當rand3

圖4 和聲智能變異示例

3.5 更新和聲庫

對每一步迭代產(chǎn)生的多個新和聲進行目標函數(shù)評價，將創(chuàng)作的新和聲解與和聲記憶庫中保留下來的和聲解進行比較。即對HMS+NHM(NHM為每次產(chǎn)生新和聲的數(shù)量)個和聲按照解從優(yōu)到差的順序排序，選出前HMS個和聲作為和聲記憶庫繼續(xù)進行迭代更新。

3.6 算法流程

改進和聲搜索算法的總體流程如下。

Step1初始化算法參數(shù)。初始化實驗案例數(shù)據(jù)、和聲記憶庫大小HMS、考慮在和聲記憶庫中取值的概率HMCR、考慮是否調(diào)整和聲音調(diào)PAR、每次產(chǎn)生新和聲的數(shù)量NHM、智能變異概率PIM、和迭代次數(shù)NI。

Step2初始化和聲記憶庫。采用兩段組合的編碼方式初始化HM，評估和聲記憶庫中的每一個和聲，找到最優(yōu)和聲和最差和聲。

Step3創(chuàng)作新和聲。對NHM個和聲進行新和聲的機器選擇部分和新和聲的工序排序部分的創(chuàng)作。

Step4和聲智能變異。利用PIM創(chuàng)作的新和聲中需要進行智能變異的和聲進行智能變異操作。

Step5更新和聲記憶庫。評估創(chuàng)作的新和聲，用優(yōu)于和聲記憶庫中和聲的新和聲替換和聲記憶庫中的和聲，更新和聲庫的最優(yōu)和聲和最差和聲。

Step6重復Step 3、Step 4和Step 5直到迭代次數(shù)等于NI，停止創(chuàng)作和更新。

Step7輸出最優(yōu)和聲和最優(yōu)和聲解，即最佳機器選擇與工序排序的操作和最小的最大完工時間。

4 仿真實驗與分析

4.1 性能分析實驗

4.1.1和聲記憶庫初始化方式

以Brandimarte[20]提出的MK02實例為例，以最大完工時間最小值為目標函數(shù)值研究不同初始化方式對改進和聲搜索算法性能的影響，隨機全局混合初始化和隨機初始化實驗設(shè)置如下：HMS=100，HMCR=0.97，PAR=0.01，PIM=0.8，NI=500 000，COT=1(運行1次)。圖5給出了不同初始化方式產(chǎn)生的初始值以及收斂情況。

圖5 不同初始化方式對比結(jié)果

可以看出兩種初始化方式求解MK02實例時，全局隨機混合初始化方式產(chǎn)生的初始解的最優(yōu)解要優(yōu)于隨機初始化方式所得解，并保證了初始解的質(zhì)量。另外全局隨機混合初始化方式求得的解的多樣性也要優(yōu)于隨機初始化方式所得，因此后續(xù)收斂速度更快，即提高了搜索全局最優(yōu)解的概率和收斂速度。這體現(xiàn)出了采用全局隨機混合初始化方式求解FJSP的優(yōu)越性。

4.1.2一次創(chuàng)作多個新和聲

以Brandimarte[20]提出的MK04實例為例，以最大完工時間最小值為目標函數(shù)值研究一次創(chuàng)作多個和聲對改進和聲搜索算法性能的影響。由于更新機制不同，為保證生成新和聲的總數(shù)相同，設(shè)置了不同的迭代次數(shù)。一次創(chuàng)作單個新和聲實驗設(shè)置如下：HMS=100，HMCR=0.97，PAR=0.01，PIM=0.8，NI=500 000，COT=1。參考文獻[21]并且通過實驗驗證，一次創(chuàng)作的多個新和聲的數(shù)量為和聲記憶庫大小的一半時能夠取得良好的算法性能，故一次創(chuàng)作多個新和聲實驗設(shè)置如下：HMS=100，HMCR=0.97，PAR=0.01，PIM=0.8，NI=10 000，NHM=50，COT=1。圖6對比了不同單次新和聲創(chuàng)作數(shù)量下的收斂情況。

圖6 不同單次新和聲創(chuàng)作數(shù)量的對比結(jié)果

可以看出求解MK04實例時，在初始方式相同的情況下，以最大完工時間最小為目標，一次創(chuàng)作多個新和聲在搜索到最優(yōu)解時生成的總和聲數(shù)要少于一次創(chuàng)作單個新和聲搜索到最優(yōu)解時生成的總和聲數(shù)。體現(xiàn)出一次創(chuàng)作多個新和聲的求解效率高于一次創(chuàng)作單個新和聲的求解效率，能夠充分利用和聲庫中的優(yōu)良資源，以更快的收斂速度更有效地求解FJSP。

4.1.3加入智能變異的改進和聲搜索算法

為了研究加入智能變異前后對改進和聲搜索算法性能的影響，本文針對Cmax和AVCmax兩個指標對文獻[20]中的10個Brandimarte標準算例進行實驗,并與文獻[15]提出的HHM和文獻[17]中提出的同類算法作對比。Cmax為案例求解COT次后取到的最大完工時間的最優(yōu)值；AVCmax為案例運行COT次所得最優(yōu)最大完工時間的平均值。加入智能變異前(改進前HS)實驗設(shè)置如下：HMS=100，HMCR=0.97，PAR=0.01，NI=10 000，NHM=50，COT=10。加入智能變異后(改進HS)其他設(shè)置不變，增加參數(shù)PIM=0.8。表2給出了實驗的對比結(jié)果。由表2可以看出，對于AVCmax指標，改進HS在10組標準算例中的結(jié)果全部不弱于改進前HS，其中7組結(jié)果更優(yōu)。對于Cmax指標，加入改進HS在10組標準算例中求得的最優(yōu)解全部不弱于改進前HS，其中4組結(jié)果更優(yōu)。體現(xiàn)出加入智能變異后的改進HS增加了搜索到最優(yōu)和聲的概率。同時對比同類算法，對比文獻[17]，Cmax指標有8組不弱于文獻[17]，其中4組優(yōu)于文獻[17]。針對Cmax指標對比文獻[15]的實驗結(jié)果，改進HS有3組稍弱于文獻[15]，其余均能達到相同水平。但是，文獻[15]提出的HHM采用連續(xù)和聲向量轉(zhuǎn)化為離散和聲向量的編碼轉(zhuǎn)換技術(shù)與基于關(guān)鍵路徑的局部搜索技術(shù)，應(yīng)用在FJSP問題上操作復雜，而本文提出的改進HS則簡單易操作。通過實驗結(jié)果與分析表明，改進HS用于求解FJSP實現(xiàn)簡單且結(jié)果較優(yōu)。

表2 加入智能變異前后及同類算法實驗結(jié)果對比

4.2 算法對比

為了進一步驗證本文提出改進和聲搜索算法的有效性，針對Cmax和AVCmax兩個指標對文獻[20]中的10個Brandimarte標準算例進行實驗。同時將算法與文獻[9]提出的HGWO、文獻[18]提出的改進GA、文獻[22]中提出BBO和文獻[23]中提出的PSO作比較。與其他算法具有可比較和可接受的計算效率時，實驗設(shè)置如下：HMS=100，HMCR=0.97，PAR=0.01，NI=10 000，NHM=50，COT=10，PIM=0.8。改進HS與文獻[9，18，22-23]中算法對比實驗結(jié)果如表3所示，加粗標記的數(shù)據(jù)表示以下對比實驗中實驗結(jié)果最優(yōu)解，10組實驗中9組Cmax指標取得了最優(yōu)解，證明了改進和聲搜索算法在不同算法中的優(yōu)越性。對于AVCmax指標，改進HS在10組標準算例中的值均不高于文獻[9]，其中9組更低，證明了本文算法求解FJSP的穩(wěn)定性高。

表3 改進HS與其他算法在基準算例上的對比結(jié)果

4.3 工程案例測試

為了進一步驗證改進和聲搜索算法的實用性和有效性，本文針對以下兩個工程實例進行實驗求解。

案例一數(shù)據(jù)來源于文獻[24]中的數(shù)據(jù)，是某航空發(fā)動機公司加工過程提出的FJSP實例，共有6個工件，10臺機器可供選擇加工，每個工件有6道加工工序。利用提出的改進和聲搜索算法對實例進行求解，以Cmax、AVCmax、MAXCmax為計算指標與其他算法進行比較，MAXCmax為案例求解COT次得到的最大完工時間的最差值。改進和聲搜索算法參數(shù)設(shè)置如下：HMS=100，HMCR=0.97，PAR=0.01，PIM=0.8，NI=10 000，NHM=50，COT=10。根據(jù)表4計算結(jié)果所示，改進和聲搜索算法求解這三項指標的結(jié)果均優(yōu)于其他算法，證明改進和聲搜索算法能夠更有效地解決FJSP。

表4 案例一對比結(jié)果統(tǒng)計

案例二數(shù)據(jù)來源于文獻[25-26]中的數(shù)據(jù)，是某工廠柔性作業(yè)車間調(diào)度實例，共有6個工件、8臺機器、26道加工工序。利用提出的改進和聲搜索算法對實例進行求解，以Cmax和AVCmax為計算指標。改進和聲搜索算法參數(shù)設(shè)置如下：HMS=100，HMCR=0.97，PAR=0.01，PIM=0.8，NI=10 000，NHM=50，COT=10。得到的計算結(jié)果如表5所示，可見改進和聲搜索算法求得這兩項指標的結(jié)果優(yōu)于其他兩個文獻中求得的結(jié)果，提高了計算精度。

表5 案例二對比結(jié)果統(tǒng)計

5 結(jié) 語

本文針對FJSP求解難的特點，提出一種改進的和聲搜索算法，通過了案例測試與分析，得出以下結(jié)論：

(1) 初始化方面，采用兩段組合編碼序列作為和聲音調(diào)，在離散域構(gòu)建操作順序與機器選擇的關(guān)系。以全局初始化和隨機初始化混合的初始化方式，同時提升了初始解的精度和多樣性，從而增加了搜索全局最優(yōu)解的概率和收斂速度。

(2) 搜索過程方面，采用一次創(chuàng)新多個和聲的搜索方式，設(shè)計了針對柔性作業(yè)車間調(diào)度問題的創(chuàng)作和聲策略，保證了解的可行性。同時引入了智能變異算子，平衡了機器負載，在保證全局搜索的前提下，提高了局部搜索能力。

(3) 通過基準案例和工程實例測試的對比實驗結(jié)果表明，本文算法求解FJSP是有效的，可以在實際生產(chǎn)中起到一定的指導作用。但是在面臨機器數(shù)量多的大規(guī)模FJSP時，解的效率還有待提高。在未來研究中，還需要做更深入的優(yōu)化研究，進一步提升算法的求解性能。