求解置換流水車間調(diào)度問題的一種混合算法

劉祝智

【摘 要】置換流水車間調(diào)度問題是一類經(jīng)典的組合優(yōu)化問題，智能優(yōu)化算法是求解該問題的首要方法。遺傳算法和分布估計算法在PFSP問題上均存在著一定的缺陷，即無法平衡局部搜索和全局搜索。為了克服它們的缺陷，本文將分布估計算法與遺傳算法結(jié)合，并引入模糊邏輯控制來調(diào)節(jié)兩種算法的參與率，最后用基準算例的測試結(jié)果證實了本文所設(shè)計的混合算法是有效的。

【關(guān)鍵詞】置換流水車間調(diào)度；分布估計算法；遺傳算法；模糊邏輯控制

0.前言

置換流水車間調(diào)度問題（PFSP）是對經(jīng)典的流水車間調(diào)度問題進行簡化后得到的一類子問題，最早在石化工業(yè)中得到應(yīng)用，隨后擴展到制造系統(tǒng)、生產(chǎn)線組裝和信息設(shè)備服務(wù)上[1]。該問題一般可以描述為，n個待加工工件需要在m臺機器上進行加工。問題的目標是求出這n個工件在每臺機器上的加工順序，從而使得某個調(diào)度指標達到最優(yōu)，最常用的指標為工件的總完工時間（makespan）最短。

PFSP最早由Johnson于1954年進行研究[2]，具有NP難性質(zhì)[3]。求解方法主要有數(shù)學(xué)規(guī)劃，啟發(fā)式方法和基于人工智能的元啟發(fā)式算法[4]。數(shù)學(xué)規(guī)劃等適用于小規(guī)模問題，啟發(fā)式方法計算便捷，卻又無法保證解的質(zhì)量。隨著計算智能的發(fā)展，基于人工智能的元啟發(fā)式優(yōu)化算法成為研究的重點。

遺傳算法（GA）是研究與應(yīng)用得最為廣泛的智能優(yōu)化算法，利用遺傳算法求解PFSP問題的研究也有很多。遺傳算法具有操作簡單、容易實現(xiàn)的優(yōu)點，且求解時不受約束條件限制。然而，遺傳算法通常存在著過早收斂，容易陷入局部最優(yōu)的現(xiàn)象。導(dǎo)致這一現(xiàn)象的原因在于遺傳算法的交叉、變異操作具有一定的隨機性，在求解PFSP問題的過程中往往會破壞構(gòu)造塊，產(chǎn)生所謂的連鎖問題。為了克服遺傳算法的缺陷，研究人員提出了一種不進行遺傳操作的分布估計算法[5]（EDA）。EDA是一種運用統(tǒng)計學(xué)習(xí)的新型優(yōu)化算法。相比GA，EDA在全局搜索上有較大的優(yōu)勢，而局部搜索能力不足，同樣會導(dǎo)致局部最優(yōu)[6][7]。以混合優(yōu)化為思路，本文將設(shè)計一種EDA與GA結(jié)合的混合算法來求解PFSP問題，混合算法通過EDA的概率模型和GA的交叉變異操作兩種方式來生成個體，并引入模糊控制理論[8]來自適應(yīng)調(diào)節(jié)兩種算法生成個體的比例。

1.置換流水車間調(diào)度問題

PFSP問題通常假設(shè)：

（1）n臺工件在m臺機器上加工。

（2）每個工件以相同的順序在m臺機器上加工。

（3）每個工件在每臺機器上的加工時間是預(yù)先確定的。

（4）每臺機器只能同時加工一個工件。

2.混合算法設(shè)計

2.1種群初始化

初始種群含有PS個個體，利用經(jīng)典的啟發(fā)式方法NEH[9]算法產(chǎn)生1個個體，其余PS-1個個體采用隨機初始化的方法生成。

2.2選擇

根據(jù)PFSP問題所給的加工時間表計算出種群中所有個體的總完工時間Cmax，顯然Cmax越小，個體的質(zhì)量就越好，據(jù)此可將評價個體好壞的適應(yīng)度函數(shù)設(shè)為1/Cmax。本文選擇的是輪盤賭法，加工時間越小，適應(yīng)度值越高，個體被選擇的概率也就越大

2.3概率模型

2.4局部搜索

對概率模型采樣即可得到新一代的個體，對個體進行局部搜索可以提高EDA的性能[11]，本文將對較好的個體進行局部搜索，分別有如下三種搜索方法：

插入：選擇一個工件并隨機插入到某一位置。

交換：隨機選擇兩個工件并交換其所在位置。

倒置：隨機選擇兩個工件，將這兩個工件之間的序列反轉(zhuǎn)。

2.5交叉算子

本文采用的交叉算子為次序保留交叉。例如，親代個體為{2，3，5，1，4，9，8，6，7，10}和{1，2，4，5，6，7，8，3，9，10}，在交叉過程中保留的片段為{4，9，8，6}，則生成的子代個體為{1，2，5，7，4，9，8，6，3，10}和{2，3，4，5，6，1，8， 7，9，10}，圖示如下：

2.6變異算子

本文選取的變異算子為移碼變異，例如，變異前的個體為{6，8，9，10，7，4，3，1，2，5}，選擇7，8這兩個位點進行變異，變異后個體為{6， 9，10，7，8，4，3，1，2，5}，如下圖所示：

2.7模糊邏輯控制

混合優(yōu)化策略中，不同算法的比例是影響算法性能的關(guān)鍵，傳統(tǒng)的算法比例混合方法主要包括固定比例和動態(tài)比例兩種。使用固定比例時，比例值將在整個算法搜索過程中保持不變。這種方法需要進行試驗來確定合適的比例值，其缺點在于為尋找到最佳比例值所需進行的試驗多，耗時久。而動態(tài)比例調(diào)節(jié)則只需預(yù)先確定一個比例的初始值，而在運行過程中會根據(jù)搜索情況調(diào)節(jié)比例。調(diào)節(jié)方式又可以分為兩種：一種是應(yīng)用傳統(tǒng)的啟發(fā)式規(guī)則控制算法生成個體的比例，這些規(guī)則可以用確定的數(shù)學(xué)公式表示；而另一種是用人工智能技術(shù)自適應(yīng)調(diào)整生成個體的比例，最常見的是將模糊邏輯應(yīng)用于比例調(diào)節(jié)，能根據(jù)算法性能的變化來實現(xiàn)比例控制[12]。為了使混合算法具有優(yōu)良的適應(yīng)性，本文采用模糊邏輯控制來進行比例調(diào)節(jié)：在EDA表現(xiàn)良好時提高EDA生成個體的比例發(fā)揮其全局搜索的優(yōu)勢，在EDA求得解的質(zhì)量下降時提高GA生成個體的比例，以避免出現(xiàn)局部最優(yōu)。

3.EDA-GA混合算法

通過以上設(shè)計，EDA-GA混合算法的步驟如下：

3.1種群和概率模型的初始化

產(chǎn)生初始種群，迭代次數(shù)t=1，概率模型P中pij=1/n

3.2對種群個體進行評價并選擇出優(yōu)勢個體

以輪盤賭法選擇出用以更新EDA概率模型的優(yōu)勢個體和待進行交叉變異操作的父代個體。

3.3更新概率模型并對概率模型取樣生成個體

對優(yōu)勢個體進行統(tǒng)計學(xué)習(xí)完成概率模型的更新，然后對概率模型抽樣產(chǎn)生PS個個體，局部搜索后，把最好的rate（t）*PS個個體加入到下一代種群，rate（t）為當前EDA所生成個體的比例。

3.4交叉操作和變異操作

對父代分別進行交叉操作和變異操作，共產(chǎn)生（1-rate（t））*PS個個體，將這些個體加入到下一代種群中。

3.5模糊邏輯控制調(diào)節(jié)比例

新一代種群生成后，將種群平均完工時間與上一代進行比較，得到模糊輸入量，根據(jù)模糊判斷規(guī)則確定下一次迭代時EDA所生成個體的比例rate（t+1）。

3.6終止條件判斷

若滿足終止條件，輸出此時得到的最優(yōu)解；否則，t=t+1，進入步驟2）。

4.實驗結(jié)果

4.1參數(shù)設(shè)置

將EDA-GA混合算法的參數(shù)設(shè)為種群大小PS=200，迭代次數(shù)iteration_times=300，優(yōu)勢個體所占比例為superior_rate=0.2，GA變異比例mutation_rate=0.1，EDA初始生成個體的比例rate=1，概率模型學(xué)習(xí)速率α=0.2。

4.2結(jié)果分析

PFSP問題的基準算例有很多，其中Car和Rec類算例運行時間段短，計算快捷，因此選用這兩種算例來驗證本文所設(shè)計混合算法的有效性。每個算例用matlab獨立運行10次，并與GA，EDA的結(jié)果進行比較。測試結(jié)果如表3所示。其中，BRE=×100、ARE=×100為每種算法求得的最優(yōu)解C與三種算法測試所得的最好解C*的相對偏差百分比的最小值和平均值。

從表3的實驗結(jié)果可以看出，對測試問題Car1～Car8和Rec01～Rec37，本文設(shè)計的EDA-GA混合算法ARE與BRE均優(yōu)于EDA和GA，說明GA的引入使得EDA的優(yōu)化性能有了很大的改進。對于Rec39、Rec41，混合算法BRE不如GA，說明優(yōu)化性能稍弱于GA，但相比EDA解的質(zhì)量有顯著提高。因此總體而言，EDA-GA混合算法的性能是要強于GA和EDA。

5.結(jié)論

針對EDA和GA各自在全局搜索和局部搜索的不同側(cè)重，本文設(shè)計了一種EDA-GA混合算法對以最小化總完工時間為優(yōu)化目標的PFSP問題進行了求解。在混合算法中， EDA和GA各自生成一定比例的個體進行混合，在兩種算法比例的調(diào)節(jié)上使用了模糊邏輯控制的方法，其中模糊輸入量為每一代種群個體總加工時間的平均值的變化，而模糊輸出量為EDA在下一次迭代中所生成個體的比例。由此，混合算法綜合了EDA和GA的優(yōu)點，運用Car和Rec類進行算例仿真，實驗結(jié)果證明上述EDA-GA混合算法是有效的。 [科]

【參考文獻】

[1]Pan Q-K，Suganhan PN，Tasgetiren MF，Chua TJ.A discrete artificial bee colony algorithm for thelot-streaming flow shop scheduling problem. Information Sciences，2011，181（12）：2455-68.

[2]JohnsonS M.Optimal two-and three-stage production schedules with setup times included[J].Naval research logistics quarterly，1954，1（1）：61-68.

[3]Zhang Y，Li X.Estimation of distribution algorithm for permutation flow shops with total flow time minimization[J].Computers & Industrial Engineering，2011，60（4）：706-718.

[4]周馳，高亮，高海兵.基于 PSO 的置換流水車間調(diào)度算法[J].電子學(xué)報，2006，34（11）：2008-2011.

[5]LarranagaP，LozanoJA.Estimationofdistributionalgorithms：Anewtoolforevolutionary

computation[M].Springer，2002.

[6]葉寶林，高慧敏，王筱萍，等.基于分布估計算法的二階段置換流水車間調(diào)度算法[J].計算機應(yīng)用研究，2011，28（10）：3702-3706.

[7]ChenSH，ChenMC，Chang P C，et al.Guidelines for developing effective estimation of distribution algorithms in solving single machine scheduling problems[J].Expert Systems with Applications，2010，37（9）：6441-6451.

[8]Chan F T S，Prakash A，Mishra N.Priority-based scheduling in flexible system using AISwithFLCapproach[J].International Journal of Production Research，2013，51（16）：4880-4895.

[9]Nawaz M，Enscore Jr E E，Ham I.A heuristic algorithm for the m-machine，n-job flow-shop sequencing problem[J].Omega，1983，11（1）：91-95.

[10]王圣堯，王凌，許燁，等.求解混合流水車間調(diào)度問題的分布估計算法[J].自動化學(xué)報，2012，38（3）：437-443.

[11]Wang S，Wang L，Liu M，et al.An effective estimation of distribution algorithm for solving the distributedpermutationflow-shopscheduling problem [J]. International Journal of Production Economics，2013，145（1）：387-396.

[12]何宏，錢鋒.遺傳算法參數(shù)自適應(yīng)控制的新方法[J].華東理工大學(xué)學(xué)報：自然科學(xué)版，2006，32（5）：601-606.

[13]Kim K W，Gen M，Yamazaki G.Hybrid genetic algorithm with fuzzy logic for resource-constrained project scheduling[J].Applied Soft Computing， 2003，2（3）：174-188.

[14]Kim KW，YunYS，YoonJM，et al.Hybrid genetic algorithm with adaptive abilities for resource-constrained multipleproject scheduling[J].ComputersinIndustry，2005，56（2）：143-160.