求解ｊｏｂｓｈｏｐ調度問題的量子粒子群優化算法

摘要：針對粒子群優化算法搜索空間有限、容易出現早熟現象的缺陷，提出將量子粒子群優化算法用于求解作業車間調度問題。求解時，將每個調度按照一定的規則編碼為一個矩陣，并以此矩陣作為算法中的粒子；然后根據調度目標確定目標函數，并按照量子粒子群優化算法的進化規則在調度空間內搜索最優解。仿真實例結果證明，該算法具有良好的全局收斂性能和快捷的收斂速度，調度效果優于遺傳算法和粒子群優化算法。

關鍵詞：粒子群優化算法；量子粒子群優化算法；作業車間調度

中圖分類號：TP391文獻標志碼：A

文章編號：1001－3695(2008)03－0684－03

作業車間調度問題（JSSP）是實現先進制造和提高生產效益的基礎和關鍵，受到機械工程、計算科學和運籌學的廣泛關注。JSSP具有建模復雜、計算復雜和多約束等特點，屬于組合優化問題，被證明是典型的NPhard問題[1]。JSSP是關于計算機集成制造系統的設計和制造控制中至關重要的環節。然而在很多情況下，即使是解決一個很普通的JSSP也會很艱難，并且僅僅針對某些調度問題才有最佳的調度方案。所以，本文希望找到一個可行的方案來解決這個問題。

目前，將粒子群優化算法用于解決JSSP是國內外正在研究的熱點。PSO算法用于求解JSSP要比其他經典調度算法具有更大的優勢和可行性，與以往經典的調度理論相比，也取得了更好的調度效果。但在實際應用中，PSO算法還是會經常陷入局部極值（出現早熟現象）。針對這些不足，考慮將量子粒子群優化算法應用于JSSP。該算法比PSO算法具有更快的收斂速度，修正了PSO算法容易陷入局部最優解的缺陷，比PSO算法具有更好的全局搜索能力。

1JSSP描述

JSSP研究n個工件在m臺機器上加工。已知各操作步驟的加工時間和各工件在各機器上的加工次序約束，要求確定與工藝約束條件相容的各機器上所有工件的加工開始或完成時間或加工次序，使加工性能指標達到最優。

用m表示機器的數量，n表示需要加工的工件數量。假如用i表示第i個工件，k表示第k個工序，則m(i，k)表示加工第i個工件的第k個工序的機器編號。ti，k表示工序(i，k)的加工時間，mi，k是加工工序(i，k)的機器編號，ki表示第i個工件的最后一道工序。

JSSP可描述如下：

a）每個工件由m道工序組成，每道工序在不同的機器上加工；

b）每道工序必須在指定的機器上加工；

c）按照加工工藝的規定，每道工序必須在它前面的工序加工完畢后再加工；

d）每道工序從開始到結束，不會被另外的工序所中斷；

e）一臺機器在某一時間只能加工一個工件，且每個工件在某一時間只能由一臺機器加工。

可以看出，JSSP是一個典型的線性規劃問題。若用Si，k表示第i個工件的第k個工序的加工開始時間，可以定義如下三個約束條件：

其中：約束(a)表示工序(i，k)必須在工序(i，k-1)之后被加工；約束(b)表示工序的開始加工時間必須是不小于零的；約束(c)表示一個特定的機器在某一時間只能加工一個工件，這樣可以避免兩個工件產生沖突。

調度的目標是使全部工件的加工結束時間最小，即讓全部工件盡可能早地被加工完成。因此，調度的目標函數是max(Si，ki+ti，ki)，那么最小的總完工時間是min(max(Sj，ki+ti，ki))。

2算法簡介

2．1PSO算法

PSO算法是一種基于群體智能方法的演化計算技術，是由Kennedy和Eberhart于1995年提出的[2]，源于對鳥群捕食行為的研究。與遺傳算法（genetic algorithm，GA）類似，兩者都是優化算法，都力圖在自然特性的基礎上模擬個體種群的適應性，且都采用概率變換規則通過搜索空間求解。但在PSO算法中，粒子的變化是通過向同等的粒子學習而不是通過遺傳來重組和變異得到的。近年來，因PSO算法具有個體數目少、計算簡單和魯棒性好等優點，已被成功應用于函數優化、系統辨識、神經網絡訓練、模糊系統控制等領域。

目前，有關PSO算法的研究大多以帶慣性權重的PSO算法為基礎進行擴展和改進。為此將帶慣性權重的PSO算法稱為標準PSO算法。

根據對粒子收斂行為的分析[4]，要保證算法的收斂性，每個粒子必須收斂于各自的p點，這是由粒子的追隨性和粒子群的聚集性決定的。在整個收斂過程中，在p點處實際上存在某種形式的勢能場吸引著粒子，這正是整個粒子群能保持聚集性的原因。但遺憾的是，在標準PSO算法的粒子群系統中，粒子的搜索空間是一個有限的區域，不能覆蓋整個可行空間。

2．2QPSO算法

受量子物理基本理論的啟發，根據粒子群的基本收斂性質，Sun等人于2004年提出的QPSO算法是對整個PSO算法進化搜索策略的改變，并且進化方程中不需要速度向量，而且進化方程的形式更簡單、參數更少且更容易控制。在量子空間中，粒子在整個可行解空間中進行搜索，因而QPSO算法的全局搜索性能遠遠優于標準PSO算法。

QPSO算法利用波函數ψ(x，t)來描述粒子的狀態，并通過求解薛定諤方程得到粒子在空間某一點出現的概率密度函數，再通過Monte Carlo隨機模擬得到粒子的位置方程為

3基于QPSO算法的作業車間調度

3．1基于GA和PSO算法的作業車間調度分析

L.W.Cai等人在2000年證明了GA特別適用于JSSP，GA使用了簡單的編碼方式和新的交叉、變異操作。Shouichi Matsui等人于2002年提出了一種應用于JSSP的新的遺傳算法。該算法是基于自由參數的GA和并行分布的GA。GA在調度領域中已經得到了比較廣泛的應用和發展，特別是20世紀90年代以來，國內外學者發表了大量應用GA解決調度問題的文章。幾乎每一種調度問題都有人用GA求解，因此可以認為GA的適用性是比較好的。

GA的有效性一般與其相關參數的選擇有關，使用不同的遺傳因子，算法的有效性也有一定差異。使用單一遺傳因子時的有效性比較低，而混合使用這些因子時的算法有效性較高。另外，迭代次數對算法的結果也有一定程度的影響。

基于GA的調度理論雖然很成熟，但大都是在簡化實際調度問題基礎上進行研究的，因此與解決實際調度問題還有相當大的差距。GA有自身的缺陷，它在解決大規模的JSSP時存在著進化速度過慢和過早收斂的局限，并且隨著問題規模的增大，算法有效性呈下降趨勢。

根據PSO算法的基本原理，將其應用于JSSP具有理論上的可行性，實例仿真也證明了PSO算法的有效性。PSO算法在求解JSSP時取得了比GA更好的調度效果。但在實際調度中，PSO算法還是會經常出現陷入局部極值的早熟現象，它并不能從根本上解決早熟收斂問題。

3．2粒子的編碼設計

針對GA和PSO算法的上述缺陷，本文提出將QPSO算法應用于JSSP。QPSO算法中的粒子對應于GA 中的染色體，采用基于操作的編碼方式。因此，對于一個n個工件在m臺機器上加工的JSSP，問題的每一個調度均被編碼成一個由n×m個代表工序的基因所組成的染色體串。該染色體串對應所有工件的所有工序在機器上的一個排列。其中各工件號均出現m次。解碼時先將染色體串轉換為一個有序的操作表；然后基于此操作表以及工藝約束條件對各操作以最早允許的加工時間逐一進行加工，從而產生調度方案。

3．3QPSO算法的流程設計

對于n個工件在m臺機器上加工的調度問題，假設種群的粒子數為s，采用QPSO算法對問題進行求解時，將該問題中的每個調度編碼為一個m×n的矩陣，以此矩陣作為QPSO算法中的粒子進行進化，由此在一個s×m×n的三維空間內搜索最優調度。算法根據種群的規模，按照上述粒子的結構隨機產生一定數目的粒子（個體）組成種群，不同的粒子代表不同的調度，同時初始化pbest、gbest。

如前所述，調度的目標函數是max(Si，ki+ti，ki)。為了使得到的調度滿足第一個約束條件，在目標函數中引入一個懲罰因子PNSH(Si，k-Si，k-1-ti，k-1)。最后，得到的目標函數是

A×max(Si，ki+ti，ki)+B×ikPNSH(Si，k-Si，k-1-ti，k-1)

其中A和B是權重。以此作為目標函數，評價種群中的所有粒子，從中找到最佳粒子，并判斷是否需要更新粒子的pbest和gbest。然后按照QPSO算法的進化方程更新每一個粒子的位置向量，以此產生新的粒子。如此反復直到滿足算法的終止條件。算法的終止條件是當目標函數的值小于一個給定值時或限定算法的迭代次數作為終止條件。

基于QPSO算法的JSSP的流程描述如下：

a)初始化種群，根據調度規則設定各粒子的隨機位置，并初始化Pi和Pg；

b)根據當前迭代次數動態調整收縮擴張系數，從而實現算法搜索空間由全局逐步過渡到局部；

c)計算每一粒子的適應度值，并確定是否更新Pi和Pg；

d)按種群的進化方程生成新的粒子；

e)判斷是否滿足算法的終止條件，若滿足則轉到f)，否則轉到b)；

f)輸出最佳調度，算法結束。

4實例仿真

以某加工車間的工件加工為例，要在10臺機器上加工10個工件，機器加工的工藝流程（工序集）矩陣m(i，k)及對應于工序集的機器加工工件的時間矩陣ti，k為

分別用GA、PSO和QPSO算法來求解此調度問題，進而比較這些算法在求解大規模JSSP時的性能。綜合考慮算法和調度的效率，經多次仿真測試，設GA的交叉概率Pc=0.9，變異概率Pm=0.4；PSO算法的加速常數c1=c2=1.85，慣性權重ω從0.8到0.4線性減小；QPSO算法的收縮擴張系數β從1.0到0.5線性減小。GA、PSO和QPSO算法的種群規模均為30，迭代次數均為600；三種算法均分別運行50次。三種算法得到的最小完工時間、平均最小完工時間和平均運行時間如表1所示；三種算法分別運行50次后得到的平均收斂曲線如圖1所示。

從表1可以看出，QPSO算法的最小完工時間、平均最小完工時間和50次平均運行時間三個指標均優于GA和PSO算法，證明了QPSO算法在求解JSSP時的有效性，并且計算速度更快，同時取得了比GA和PSO算法更好的調度效果。從圖1可以看出，QPSO算法的收斂速度更快，全局收斂能力更強，由此證明了QPSO算法在收斂性能及解決JSSP上的優越性。

5結束語

本文在討論典型JSSP的基礎上，提出了將一種目前最新的群體智能優化算法QPSO用于解決JSSP。QPSO算法相比GA、PSO算法計算更簡單、收斂速度更快，并可以防止算法早熟，有利于發現更優解，從而具有更好的全局收斂性能。其搜索成功率遠遠高于其他算法，這對于求解大規模的JSSP是十分有利的。仿真實例將QPSO算法應用于求解復雜的JSSP，調度結果顯示了它具有良好的調度效果，證明了其有效性。

參考文獻：

［1］王凌.車間調度及其遺傳算法[M]. 北京：清華大學出版社，2003.

[2]KENNEDY J， EBERHART R C.Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks.Piscataway: IEEE Press，1995:19421948.

[3]SHI Y，EBERHART R C.A modified particle swarm optimizer[C]//Proc of IEEE International Conference on Evolutionary Computation.Piscataway:IEEE Press，1998:69－73.

[4]CLERC M. The swarm and queen:towards a deterministic and adaptive particle swarm optimization[C]//Proc of CEC.Piscataway:IEEE Press， 1999:19511957.

[5]SUN Jun，FENG Bin，XU Wenbo.Particle swarm optimization with particles having quantum behavior[C]//Proc of Congress on Evolutionary Computation.2004:325－331.

[6]曾建潮，介婧，崔志華. 微粒群算法[M].北京：科學出版社，2004.

[7]SUN Jun，XU Wenbo，FENG Bin.A global search strategy of quantumbehaved particle swarm optimization[C]// Proc of IEEE Conference on Cybernetics and Intelligent Systems.2004:111116.

[8]CLERC M，KENNEDY J.The particle swarm:explosion，stability， and convergence in a multidimensional complex space[J].IEEE Journal of Evolutionary Computation，2002，6(1):5873.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”