求解車間調(diào)度問題的自適應(yīng)混合粒子群算法-計算機學(xué)報

求解車間調(diào)度問題的自適應(yīng)混合粒子群算法基金項目：基金項目：國家自然科學(xué)基金重大項目基金(60496320,60496321)，國家自然科學(xué)基金資助項目（60773097，60873148），新世紀優(yōu)秀人才支持計劃項目基金、吉林省科技發(fā)展計劃項目基金(20060532,20080107)，吉林省青年科研基金項目（20080107，20080617），東北師范大學(xué)自然科學(xué)青年基金（20081003）張長勝孫吉貴歐陽丹彤張永剛（吉林大學(xué)計算機學(xué)院，符號計算與知識工程教育部重點實驗室，長春，130012，中國）摘要：針對最小完工時間的流水車間作業(yè)調(diào)度問題，提出了一種自適應(yīng)混合粒子群進化算法-AHPSO，將遺傳操作有效的結(jié)合到粒子群算法中。定義了粒子相似度及粒子能量，粒子相似度閾值隨迭代次數(shù)動態(tài)自適應(yīng)變化，而粒子能量閾值與群體進化程度及其自身進化速度相關(guān)。此外，針對算法運行后期進化速度慢的缺點，提出了一種基于鄰域的隨機貪心策略進一步提高算法的性能。最后將此算法在不同規(guī)模的實例上進行了測試，并與其他幾種最近提出的具有代表性的算法進行了比較，實驗結(jié)果表明，無論是在求解質(zhì)量還是穩(wěn)定性方面都優(yōu)于其他幾種算法，并且能夠有效求解大規(guī)模車間作業(yè)問題關(guān)鍵詞：粒子群算法；車間調(diào)度；粒子相似度；粒子能量；貪心策略1．引言調(diào)度問題是很多實際流水線生產(chǎn)調(diào)度問題的簡化模型，因此其研究具有極高的理論價值和實踐價值。本文研究的置換流水車間作業(yè)調(diào)度問題是在滿足工件約束和機器約束條件下，使得最小完工時間盡可能小。工件約束指每個工件在每臺機器上恰好加工一次,每個工件在每個機器上的加工順序相同；機器約束指每臺機器在任何時刻至多加工一個工件,每臺機器加工的各工件的順序相同.該問題一般可以描述為:個待加工的作業(yè),需要在臺機器上加工M,每個作業(yè)包含道工序,其中代表作業(yè)在機器上的加工時間為,,的工序。作業(yè)的完工時間為其最后一個工序完成時間即。求解目標是求得一個可行調(diào)度,使得加工完所有作業(yè)所花的時間盡可能少.該問題可用如下的數(shù)學(xué)模型表示: 其中表示工序的完工時間。此問題已被證明是NP難度問題[1]，因此，精確方法[2]在合理的時間內(nèi)只能求解小規(guī)模問題，其求解時間隨著問題規(guī)模成指數(shù)倍增長。而啟發(fā)式算法能夠在可接受的時間內(nèi)，使用較少的存儲空間求得問題近似最優(yōu)解或最優(yōu)解，主要分為構(gòu)造啟發(fā)式[3]和元啟發(fā)式兩種[4]：構(gòu)造啟發(fā)式方法雖可以在較短時間內(nèi)獲得調(diào)度問題的解，但其在構(gòu)造調(diào)度的過程中依賴根據(jù)問題局部信息設(shè)計的調(diào)度規(guī)則,所獲得的調(diào)度一般為局部最優(yōu)解；元啟發(fā)式方法，是基于仿生學(xué)機理的調(diào)度算法能夠在可行時間內(nèi)以較大概率獲得該類問題的最優(yōu)解或近似最優(yōu)解，成為求解各種車間調(diào)度問題的有效算法，正受到研究者的廣泛關(guān)注。粒子群算法（PSO）是受鳥群覓食啟發(fā)提出的一種進化計算方法，其收斂速度快、易于實現(xiàn)，被成功應(yīng)用在多個領(lǐng)域中[5]。目前，應(yīng)用PSO算法求解調(diào)度問題的研究還很少，實驗表明，在求解調(diào)度問題時，它們較GA算法更為有效。但已提出的算法都存在早熟收斂，易陷入局部最優(yōu)、進化后期算法收斂速度明顯下降等缺點[6,7]。主要由于進化過程中粒子能量不斷下降，導(dǎo)致粒子進化停滯不前，群體多樣性過低造成的。為了克服這些不足，本文提出了一種混合元啟發(fā)式算法-AHPSO，將PSO算法與GA算法[8]結(jié)合在一起，利用遺傳操作不斷引入新的信息指導(dǎo)群體的進化。定義了粒子相似度及粒子能量，粒子相似度閾值隨迭代次數(shù)動態(tài)自適應(yīng)變化，而粒子能量閾值與群體進化程度及其自身進化速度相關(guān)。使用排序策略保持群體的多樣性，當相鄰的兩個粒子的相似度大于其當前的相似度閾值時，對其中的一個粒子執(zhí)行變異操作。設(shè)計了一種基于遍歷矩陣的快速計算最小完工時間方法。此外，針對進化后期進化速度慢得缺點，提出了一種基于鄰域的隨機貪心策略進一步提高算法的性能。最后，分析了算法的復(fù)雜度及收斂性，并通過實驗對比證明了算法的有效性。2 AHPSO算法為了使用PSO算法求解調(diào)度問題，Rameshkumar提出了一種置換離散粒子群算法[7]，粒子在更新過程中只交換相應(yīng)位置的元素，而不引入新元素。受其啟發(fā)，我們將置換的思想引入到所提出的算法中。對于一個含有個作業(yè)的流水調(diào)度問題，粒子的位置及速度均被表示為一個滿足“alldifferent”約束[9]的維向量，即所有作業(yè)的一個全排列，然后結(jié)合GA算法中的交叉及變異操作不斷更新粒子的位置及速度。2.1 算法進化模型在PSO算法中，每個粒子的行為主要受其當前動量項、個體認知部分及群體認知部分的影響。因此，傳統(tǒng)的粒子速度公式可通過將粒子的當前速度與其個體最優(yōu)解及當前的群體最優(yōu)解分別進行交叉來取代，粒子的位置更新也相應(yīng)的變?yōu)閷⒘Ｗ赢斍拔恢门c當前速度交叉求得。粒子速度及位置更新公式可表示如下： （2.1） （2.2）其中符號表示交叉操作。由上面的公式可以看出，每個粒子追隨其當前個體最優(yōu)解及全局最優(yōu)解運動。與傳統(tǒng)的PSO算法一樣，它具有快速收斂，計算簡單等優(yōu)點。但是，進化過程中粒子的速度會迅速逼近零，即粒子的當前速度和其當前位置相同，使算法易于陷入局部最優(yōu)解，如實驗部分的AHPSO-S-A算法所示。為此，本文引入了粒子能量及粒子能量閾值的概念。粒子能量閾值隨著迭代次數(shù)粒子的進化速度動態(tài)自適應(yīng)調(diào)整，使算法在進化初期具有較強的全局搜索能力，在后期則側(cè)重局部精化能力。定義1：給定粒子Pi，其當前位置和速度分別為Xi、Vi，當前的個體最優(yōu)位置和群體最優(yōu)位置分別為Pibest、Pgbest。此粒子的當前所具有能量可計算如下： ，其中。粒子能量用于刻畫粒子的搜索能力，與粒子當前狀態(tài)及群體當前最優(yōu)位置相關(guān)。易見。定義2：設(shè)當前迭代次數(shù)為currGen，最大迭代次數(shù)MAXGEN。eIni與eFin分別代表粒子能量的上界及下界，則對于給定的粒子Pi，其能量閾值定義如下： 其中，e為預(yù)先指定的常量，用于控制粒子能量閾值的變化趨勢。粒子能量閾值與群體進化程度及粒子進化速度相關(guān)?？梢钥闯?，算法運行過程中粒子能量不斷變化，當粒子能量小于它當前的能量閾值時，對其當前速度及位置執(zhí)行變異操作如公式（2.3-2.4）所示，以此引入新的信息增加粒子能量，擴大其能夠到達的搜索范圍。 （2.3） （2.4）以上模型在迭代過程中群體多樣性會不斷減少，全局搜索能力不斷下降，影響群體的進化質(zhì)量，如實驗中AHPSO-S算法所示。由此，我們定義了粒子相似度及粒子相似度閾值，采用排序策略保持群體的多樣性。粒子相似度用于度量兩個粒子的相近程度，根據(jù)相鄰兩個粒子的個體最優(yōu)位置的距離定義。定義3：給定粒子Pi、Pj，它們的相似度計算如下：其中，dim表示待加工的作業(yè)數(shù)量。定義4：設(shè)最大迭代次數(shù)MAXGEN，粒子相似度閾值的取值范圍為[sIni，sFin]，則當?shù)螖?shù)為currGen時粒子相似度閾值定義如下：其中s為一常量，用于控制粒子相似度閾值每次變化的幅度。粒子相似度閾值設(shè)定當前群體中粒子之間距離的下界，它隨迭代次數(shù)動態(tài)自適應(yīng)變化。在算法運行的初始階段，粒子相似度閾值取值較大，使得粒子在搜索空間中分布均勻，擴大搜索范圍；隨著群體的不斷進化，相似度閾值不斷減小，使得粒子之間能夠逐漸聚合到當前的全局最優(yōu)位置，加強搜索最優(yōu)位置的鄰域，進一步提高最優(yōu)解的精度。為了保持群體的多樣性，在進化過程中，根據(jù)適應(yīng)度值對群體中的所有粒子進行排序，當兩個相鄰的粒子的相似度小于當前的粒子相似度閾值時，對較差粒子的歷史最優(yōu)解執(zhí)行變異操作，如公式（2.5）所示。 （2.5）通過變異操作能夠在群體中重新引入新的有用信息，指導(dǎo)粒子搜索那些未曾搜索過的區(qū)域，進一步抑制算法的早熟收斂。2.2 適應(yīng)度計算為了提高算法的速度，我們設(shè)計了一種基于遍歷矩陣的快速計算粒子適應(yīng)度的方法。對于給定的個待加工作業(yè),每個作業(yè)包含道工序，我們將調(diào)度的加工時間矩陣定義為 其中，表示作業(yè)在第臺處理機上的加工時間，,。算法中粒子的適應(yīng)度值由最小完工時間表示，根據(jù)以上定義，通過對問題數(shù)學(xué)模型的分析，給定的調(diào)度對應(yīng)的最小完工時間，可通過按照如下公式遍歷矩陣求得。遍歷完成后，新計算出的的值就是調(diào)度的最小完工時間。2.3 算法描述及分析在我們的AHPSO算法中，群體的初始化采用隨機的方式，即在搜索空間中隨機的產(chǎn)生粒子的初始位置和初始速度，將每個粒子的歷史最優(yōu)位置設(shè)置為其當前位置，并計算每個粒子當前位置所代表調(diào)度的最小完工時間，將其作為粒子的適應(yīng)度值。根據(jù)算法的進化模型，AHPSO算法可描述如下：收斂通常是指一個系統(tǒng)或過程達到一個穩(wěn)定狀態(tài)，對基于群體的優(yōu)化算法來說，算法的收斂可以根據(jù)群體的行為來定義[10]。給定待求解的調(diào)度問題，其搜索空間，為算法在時間或在群體的第次進化中求得的最優(yōu)位置。為中的一個固定位置，收斂的定義可記為 也就是說，如果由算法求得的不在變化，那么就說處于收斂狀態(tài)。如果為搜索空間的全局最佳位置，則算法獲得了全局最優(yōu)收斂，否則算法陷入局部最優(yōu)位置。定理1：AHPSO算法是收斂的。證明：將群體中的每個粒子的當前位置視為一個狀態(tài)，則所有的粒子當前位置的集合可視為一種狀態(tài)分布。這種狀態(tài)分布會隨算法的運行而改變。由于AHPSO算法的運行具有隨機性，其基本操作只與當前狀態(tài)有關(guān)，是無后效性的，因此可以把群體內(nèi)的個體視為一個具有不同狀態(tài)的隨機變量的概率分布。首先證明由公式（2.1-2.2）構(gòu)成的迭代過程是收斂的。設(shè)群體規(guī)模為m，問題規(guī)模為群體的狀態(tài)記為(p1,p2,…,pm)，最佳調(diào)度為p*。所有的群體狀態(tài)構(gòu)成一個的行向量，其中，這個行向量的每個元素由排在一起的m個粒子的當前位置構(gòu)成。可表示為假設(shè)經(jīng)過若干代進化后，達到種群最優(yōu)狀態(tài)p*，不妨設(shè)其排在狀態(tài)行向量的第一個分兩處，即根據(jù)粒子的速度及位置更新公式可知，此時，處在最優(yōu)位置粒子的速度及歷史最優(yōu)位置均為p*，在下一次迭代中求得的粒子當前位置不變。狀態(tài)狀態(tài)轉(zhuǎn)移矩陣可寫為：其中為隨機矩陣，其每一行至少有一個正的元素，為N-1維行向量。顯然為可約隨機矩陣，且、不是零矩陣，根據(jù)可約隨機矩陣的性質(zhì)有： 其中。因為可看作是一個狀態(tài)分布，所以應(yīng)有，于是，即算法收斂到了p*。 當算法中粒子能量小于其當前的能量閾值或粒子的相似度大于當前相似度閾值時，雖然引入了變異操作，但并沒有改變當前已經(jīng)得到的歷史全局最優(yōu)位置，而且在以后的進化中，只有當?shù)玫降奈恢糜捎诖俗顑?yōu)位置時才會被取代，即全局最優(yōu)位置總是朝著更好的位置進化。所以，根據(jù)定義6，AHPSO算法是收斂的。定理2：AHPSO算法求得的解是一個合法調(diào)度。證明：算法中使用的交叉及變異操作可參看文獻[8]，每種操作都滿足“alldifferent”約束，都是一個合法調(diào)度，即AHPSO算法的搜索空間是由所有合法調(diào)度構(gòu)成的。所以由AHPSO算法求得的解必然合法。定理3：AHPSO算法的空間復(fù)雜度為O((4n+2m+2)·d)，群體每次進化的最壞漸進時間復(fù)雜度為O(mnd2)。其中n為群體規(guī)模，d表示作業(yè)數(shù)量，m為處理機個數(shù)。證明：在AHPSO算法運行過程中需要存儲每個粒子的當前位置、個體最佳位置、上一次迭代的個體最佳位置及速度，令群體規(guī)模為n，則它所消耗存儲空間為O(4n·d)；在求解粒子適應(yīng)度時還需要存儲處理時間矩陣，所消耗的空間為O(2md)；每次執(zhí)行交叉及變異等操作時還需要一個存儲新位置或速度的空間，此外還需要存儲一個全局最優(yōu)調(diào)度；所以HPGA算法的空間復(fù)雜度為O((4n+2m+2)·d)。算法運行時，執(zhí)行一次交叉操作消耗的時間最多為O(2d-1),變異操作最多為O(d)，所以在HPGA算法的一次迭代過程中，由交叉或變異引起的最壞時間復(fù)雜度為O(2n(2d-1))；計算個體能量時，需要訪問每個粒子，由此引起的時間復(fù)雜度為O(2n·d)；計算相似度及相似度閾值所消耗的時間也為O(2n·d)，求解每個粒子適應(yīng)度時需要求得及遍歷與之相應(yīng)的時間矩陣，其時間復(fù)雜度O(2md)。由于在一次迭代中需要計算所有粒子的適應(yīng)度，那么需要消耗的時間就變?yōu)闉镺(2mnd)，并且最壞情況下，在一次迭代中每個粒子都需要更新其個體最優(yōu)位置及當前位置和速度時，那么此時所消耗的時間為就便為O(4mnd2)。當問題規(guī)模逐漸增大即m·n的值趨于無窮大時，所以HPGA算法的最壞時間漸進復(fù)雜度為O(mnd2)。2.4 算法改進實驗中發(fā)現(xiàn)，進化后期算法收斂速度明顯下降，當接近最優(yōu)解時，易于停止進化。為此AHPSO算法中引入一種基于鄰域的貪心隨機搜索策略在每次迭代過程中更新粒子的個體最優(yōu)解，進一步提高解的質(zhì)量，此時將算法記作-G-AHPSO。定義7：給定一個含有n個作業(yè)的調(diào)度問題，它的任意一個有效調(diào)度可看作是n維空間中的一個點。通過隨機選擇一個作業(yè)，將其插入到任意其他位置，可求得一個新的有效調(diào)度，即n維空間中一個新的點。所有以此方式求得的點就構(gòu)成了作業(yè)的鄰域。根據(jù)以上定義，提出了一種基于鄰域的貪心隨機搜索策略，可描述如下：3 實驗結(jié)果文獻[8]對各種基本的遺傳操作及它們對GA算法求解FSP問題的性能的影響進行了分析。實驗中本文選擇第二種形式的兩點交叉操作，并分別測試了六種變異操作對算法的影響。這六種變異操作分別是近鄰變異（M1）、隨機交換變異（M2）、移位變異（M3）、置換變異（M4）、逆轉(zhuǎn)變異（M5）、逆轉(zhuǎn)/置換變異（M6）。此外，還測試了粒子能量及粒子相似度策略對算法性能的影響。最后在不同規(guī)模的Tailliard數(shù)據(jù)集[11]上對AHPSO及G-AHPSO算法進行了測試，并與最近提出的求解調(diào)度問題的GA算法[8]、SPSOA算法[7]進行了比較。為了方便，試驗中AHPSO和G-AHPSO算法的參數(shù)設(shè)置相同，MAXGEN=1000，popNum=60，s=1.40，e=1.35，eIni=0.45，eFin=0.10，sIni=0.85，sFin=0.05。為說明算法每次求得的最優(yōu)解與已知最優(yōu)解的差距，我們定義了算法所求得的最優(yōu)解的平均偏離度（AverageRelativedeviation）即算法每次運行得到的最優(yōu)解與已知最優(yōu)解的差的均值。計算如下：其中T為針對某個問題算法的運行次數(shù)，它是算法求得的最優(yōu)解偏離已知最優(yōu)解平均程度的指標，能夠反映出算法的平均求解質(zhì)量。本文試驗中每個測試問題上各算法運行次數(shù)都為10，即T=10。3.1 粒子能量及粒子相似度策略對算法性能的影響 為了測試它們在AHPSO算法中的作用，我們比較了采用移位變異操作的AHPSO算法、AHSPO-S算法及AHPSO算法在不同規(guī)模問題上的求解結(jié)果。AHPSO-S-A算法是去除粒子能量及粒子相似度策略即迭代模型只由公式（2.1）-（2.2）構(gòu)成的算法；AHPSO-S算法是去除粒子相似度策略即迭代模型由公式（2.1）-（2.4）構(gòu)成的算法。表-1為在每個問題上各算法10次運行中求得的最好解、最優(yōu)解均值、最差解及平均偏離度的比較結(jié)果。各算法在不同規(guī)模問題上的群體平均適應(yīng)度進化曲線如圖-1所示。圖-1不同規(guī)模問題上AHPSO、AHPSO-S和AHPSO-S-A算法的群體平均進化曲線可以看出AHPSO算法的平均求解質(zhì)量最佳，求得的最優(yōu)解及平均偏離度都是最小的。AHPSO-S的求解質(zhì)量也明顯高于AHPSO-S-A算法。也就是說粒子能量及粒子相似度策略能夠極大的提高算法的性能。從圖-1中明顯看出AHPSO-S-A算法雖然收斂速度快，但容易陷入局部最優(yōu)解，其求解質(zhì)量最差。此外，對于小規(guī)模問題由于其解空間小，粒子能夠搜索到的區(qū)域幾乎涵蓋整個解空間，此時，粒子相似度策略對算法性能影響不大，如圖-1(a)所示，隨著問題規(guī)模增加，其求解空間也變得相對復(fù)雜，此時排序策略能夠指導(dǎo)粒子朝著最有希望獲得更好解的區(qū)域搜索，進一步提高算法的性能，如圖-1(b-d)所示。3.2 局部搜索策略對算法性能的影響為了測試局部搜索策略對算法性能的影響，我們在每個測試集上采用不同變異操作的AHPSO及G-AHPSO算法分別運行10次，所求得的最優(yōu)解，最優(yōu)解均值及最差解，如表-2和表-3所示。 從表中可以看出，無論是從所得到的最優(yōu)解、最優(yōu)解均值還是最差解方面，使用變異操作M3時AHPSO算法的性能最佳，在10次運行中除問題ta020外，求得的最小完工時間都優(yōu)于使用其它幾種變異操作時算法求得的解。對于G-AHPSO算法來說，除變異操作M1外，使用其它幾種變異操作對算法的性能影響不是很大，這主要是由于使用這幾種變異操作時，算法的全局搜索能力相差不大，而在算法運行后期，解的質(zhì)量的精化又主要依賴于貪心隨機搜索策略。從表-1、表-2的對比中可以看出，無論使用哪種變異操作，G-AHPSO算法求得的最優(yōu)解、最優(yōu)解均值和最差解都要明顯好于AHPSO算法求得的解。此外，我們還比較了這兩種算法的收斂速度，如圖-1，它顯示了對于不同規(guī)模的問題，采用不同變異操作時最小完工時間隨迭代次數(shù)的進化曲線。其中虛線表示AHPSO算法的收斂曲線，實線是G-AHPSO算法的收斂曲線。顯然，G-AHPSO算法隨迭代次數(shù)收斂的快些，而且收斂點的值也小于AHPSO算法。對于不同的問題，變異操作對算法的收斂速度的影響也稍有不同。圖-2不同規(guī)模問題上采用各種變異操作時AHPSO和GAHPSO算法的群體適應(yīng)度進化曲線AHPSO算法與G-AHPSO算法在各問題上所求得解的平均偏離度，如表-4所示，括號內(nèi)為G-AHPSO算法的平均偏離度。 可以看出，無論是使用哪種變異操作G-AHPSO算法求得解的平均偏離度都明顯小于AHPSO算法求解的平均偏離度。也就是說，G-AHPSO算法每次求得高質(zhì)量解的概率遠遠大于AHPSO算法。 從上面的實驗分析對比中，可以得出，無論是從求得的解質(zhì)量、收斂速度還是平均偏離度方面，G-AHPSO算法都明顯優(yōu)于AHPSO算法。但是，由于G-AHPSO算法在群體進化中，每個粒子都要執(zhí)行貪心隨機搜索過程，所以每次群體進化所消耗的時間也高于AHPSO算法。在所有測試問題上AHPSO算法與G-AHPSO算法進化一次所消耗的時間對比如圖2所示。圖-3采用變異操作M3時AHPSO和G-AHPSO算法求解各問題的時間對比此外，由于貪心隨機搜索過程主要依賴于插入操作求解鄰域內(nèi)的點，所以在計算這些點的適應(yīng)度時可以通過使用文獻[12]中基于插入的加速算法可以進一步提高G-AHPSO算法的速度，但仍會略慢于AHPSO算法。在實際應(yīng)用中是否采用貪心搜索策略，需要在求解質(zhì)量與求解速度之間進行權(quán)衡。3.3 與其他算法的比較最后，為了進一步說明本文提出算法的有效性，將它們與最近提出的GA算法[8]及SPSOA算法[7]進行了比較，所得結(jié)果如表-5所示。表示都是使用各變異操作每個算法運行10次得到的最好結(jié)果，可以看出在所有的測試集上無論G-AHPSO算法還是AHPSO算法所求得的最優(yōu)解、最優(yōu)解均值及最差解都明顯小于其他兩種算法，而且G-AHPSO算法能夠求得問題ta070的最優(yōu)解5322，也就是說在此問題上G-AHPSO具有全局收斂性。4 結(jié)語本文工作主要體現(xiàn)在以下幾個方面：一、提出了一種求解流水調(diào)度問題的自適應(yīng)混合粒子群算法，將遺傳操作結(jié)合到算法中；二、定義了粒子能量及隨進化程度自適應(yīng)調(diào)整的粒子能量閾值，采用變異操作保持粒子的搜索能力；三、引入了粒子相似度及相似度閾值，并采用排序策略保持群體的多樣性，抑制算法的早熟收斂；四、通過使用遍歷矩陣方式快速計算一個調(diào)度的最小完工時間；五、證明了算法的收斂性，分析了算法空間復(fù)雜度及迭代一次的漸進時間復(fù)雜度。最后定義了衡量算法性能指標-平均偏離度，將該算法在8個不同規(guī)模的問題上進行了測試，并與當前國際文獻中最近提出的兩種著名算法進行了比較，結(jié)果表明無論是求得的解得質(zhì)量還是算法的穩(wěn)定性均明顯好于這兩種算法，加入隨機貪心搜索策略后效果更佳明顯。下一步工作主要集中在測試其他交叉策略對算法的影響，找出交叉操作與變異操作的最佳組合，以及使用本文提出的算法解決其他組合優(yōu)化問題。參考文獻[1] GareyM,JohnsonD,SethyR.Thecomplexityofflowshopandjobshopscheduling[J].MathematicsofOperationsResearch,1976,1(2):117-129.[2] JorgeM.S.ValenteandR.A.F.S.Alves,Anexactapproachtoearly/tardyschedulingwithreleasedates[J].Computers&OperationsResearch,2005,32(11):2905~2917.[3] GangadharanR,RajendranC.Heuristicalgorithmsforschedulinginno-waitflowshop[J].InternationalJournalofProductionEconomics1993,32:285–90.[4] AldowaisanT,AllahverdiA.Newheuristicsforno-waitflowshopstominimizemakespan[J].ComputersandOperationsResearch2003,30(12):19–31.[5] QingyunYang,JiguiSun,JuyangZhang,ChunjieWang:AHybridDiscreteParticleSwarmAlgorithmforOpen-ShopProblems[C].Proceedingsofthe6thInternationalConferenceonSimulatedEvolutionAndLearning(SEAL2006),Hefei,[6] K.Rameshkumar,R.K.Suresh,andK.M.Mohanasundaram:DiscreteParticleSwarmOptimization(DPSO)AlgorithmforPermutationFlowshopSchedulingtoMinimizeMakspan[C].In:Proc.ICNC2005,LNCS3612,(2005)572-581[7] ZhigangLian,XingshengGuandBinJiao,Asimilarparticleswarmoptimizationalgorithmforpermutationflowshopschedulingtominimizemakespan[J],AppliedMathematicsandComputation,

2006,175(1):773-785[8] A.C.Nearchou,Theeffectofvariousoperatorsonthegeneticsearchforlargeschedulingproblems[J],Int.J.Product.Economy.2004,88:191–203[9] J.-L.Lauriere,Alanguageandaprogramforstatingandsolvingcombinatorialproblems[J].ArtificialIntelligence.1978, 10(1):29-127[10] F.vandenBergh.AnAnalysisofParticleSwarmOptimizers,PhDthesis.DepartmentofComputerScience,UniversityofPretoria,Pretoria,[11] E.Taillard.Someefficientheuristicmethodsfortheflowshopsequencingproblem[J].EuropeanJournalofOperationalResearch,

1990,47(1):65-74.[12] Quan-KePan,M.FatihTasgetirenandYun-ChiaLiang.Adiscreteparticleswarmoptimizationalgorithmfortheno-waitflowshopschedulingproblem[J].Computers&OperationsResearch,2008,35(9):2807-2839Aself-adaptivehybridparticleswarmoptimizationalgorithmforflowshopschedulingproblemChangshengZhang,JiguiSun,DantongOuyang,YonggangZhang(KeyLaboratoryofSymbolComputationandKnowledgeEngineeringoftheMinistryofEducation,Changchun130012,China)Abstract:Ahybridself-adaptivealgorithmisproposedtosolvetheflowshopschedulingproblemwiththeobjectiveofminimizingmakespan,whichcombinedtheparticleswarmoptimizationalgorithmandgeneticoperatorstogether.Theparticlesimilarityandparticleenergyaredefined.Thethresholdofparticlesimilaritydynamicallychangeswithiterationsandtheparticleenergydependsontheswarmevolvingdegreeandtheparticle’sevolvingspeed.Inordertoimprovetheproposedalgorithmperformancefurther,aneighborhoodbasedrandomgreedysearchstrategyinintroducedtoovercometheshortcomingofevolvingslowlyinthelaterrunningphase.Finally,theproposedalgorithmistestedondifferentscalebenchmarksandcomparedwiththerecentlyproposedefficientalgorithms.TheresultshowsthatthesolutionqualityandthestabilityoftheHPGAbothprecedetheothertwoalgorithms.Itcanbeusedtosolvelargescaleflowshopschedulingproblem.Keywords:particleswarmoptimization；flowshopscheduling；particlesimilarity；particleenergy;greedystrategy作者簡介：張長勝：男（1980-），吉林大學(xué)博士研究生，研究方向為智能信息處理孫吉貴：男（1962-2008），吉林大學(xué)教授，博士生導(dǎo)師，研究方向為自動推理，約束程序歐陽丹彤：女（1968-），吉林大學(xué)教授，博士生導(dǎo)師，研究方向為基于模型的診斷張永剛：男（1975-），吉林大學(xué)博士，講師，研究方向為約束程序第一作者相片：聯(lián)系人：歐陽丹彤，電話email:zcs820@

附錄資料：不需要的可以自行刪除動力車間崗位責任制主任崗位責任制1、在公司領(lǐng)導(dǎo)下負責車間的行政、生產(chǎn)、人事管理等全面工作；是車間職業(yè)健康、安全、環(huán)保、消防工作第一責任人。2、負責對本車間人員工作的檢查、監(jiān)督和考核，根據(jù)工作業(yè)績完成員工月度及年終等績效考核。3、建立健全車間的管理制度與工作程序，堅持按制度和程序辦事，明確責任分工。并且以身作則，帶頭執(zhí)行，使車間管理科學(xué)化、規(guī)范化4、每月召開一次車間管理人員、班組長會議，總結(jié)上月工作，布置本月任務(wù)。每周召開一次車間生產(chǎn)例會。5、加強車間內(nèi)部管理，組織好業(yè)務(wù)學(xué)習、培訓(xùn)職工考評及崗位練兵工作；6、負責本車間安全培訓(xùn)和安全管理，認真貫徹執(zhí)行安全生產(chǎn)管理制度，保障車間生產(chǎn)安全7、加強車間內(nèi)部建設(shè)，對職工思想工作做好動態(tài)管理，抓好職工隊伍建設(shè)；副主任崗位責任制1、在車間主任領(lǐng)導(dǎo)下，負責組織生產(chǎn)、工藝和設(shè)備管理，同時受生產(chǎn)副總經(jīng)理的領(lǐng)導(dǎo)，在指定的工作范圍內(nèi)對安全生產(chǎn)負責；2、貫徹工藝管理制度，組織制定、修訂崗位管理技術(shù)標準及管理制度，并檢查貫徹執(zhí)行情況。3、負責編制生產(chǎn)、檢修、技措技改、安措和質(zhì)量工作計劃，并監(jiān)督執(zhí)行。4、負責貫徹安全生產(chǎn)制度，組織工藝事故的調(diào)查、分析和處理，并制定落實防范措施。5、發(fā)動好職工的合理化建議討論，并組織好論證與實施；6、加強車間崗位練兵制的實施與業(yè)務(wù)培訓(xùn)，不斷提高職工素質(zhì)、崗位技能、提高業(yè)務(wù)水平；7、協(xié)助車間主任做好職工的政治、思想工作；抓好職工隊伍的建設(shè)8、協(xié)助主任工作，在主任外出時代行其責工藝技術(shù)員崗位責任制1、在車間主任和副主任的領(lǐng)導(dǎo)下，協(xié)助做好車間的工藝技術(shù)管理工作。2、編寫車間各種工藝試車方案、規(guī)程，制訂和修訂崗位操作規(guī)程和工藝指標，并檢查貫徹執(zhí)行情況。3、編制車間年、季、月原輔材料消耗、降耗節(jié)能和技措技改計劃。4、每日研究生產(chǎn)操作記錄，分析判斷生產(chǎn)中的薄弱環(huán)節(jié)，提出對策不斷挖掘生產(chǎn)潛力，實現(xiàn)安全、高產(chǎn)、優(yōu)質(zhì)、低耗。5、根據(jù)職能部門規(guī)定，建立健全各類工藝臺帳。6、對生產(chǎn)中出現(xiàn)異常狀況要及時分析和處理，參加工藝事故分析，提出防范措施7、制定職工業(yè)務(wù)培訓(xùn)計劃，做好業(yè)務(wù)技術(shù)培訓(xùn)和考核。8、負責本車間各崗位各種數(shù)據(jù)記錄報表的審查，并對其負責。9、努力鉆研業(yè)務(wù)技術(shù)，不斷進行知識更新。掌握國內(nèi)外先進生產(chǎn)技術(shù)，參與組織實施技術(shù)革新活動10、定期對生產(chǎn)系統(tǒng)的安全隱患進行排查、治理，對排查出來的安全隱患，要落實整改措施設(shè)備技術(shù)員崗位責任制1、在車間主任和副主任的領(lǐng)導(dǎo)下，做好本車間的設(shè)備管理工作2、負責編制本車間各類設(shè)備檢修規(guī)程，維護保養(yǎng)制度3、協(xié)調(diào)檢修車間做好車間的設(shè)備檢修工作4、建立健全車間各類設(shè)備管理臺帳，做到有計劃的更換和檢修，保證安全穩(wěn)定長周期運行。5、每日對車間主要設(shè)備進行一次巡檢，做好記錄，及時發(fā)現(xiàn)和解決問題。6、定期對設(shè)備的安全隱患進行排查、治理，對排查出來的安全隱患，要落實整改措施7、編制車間設(shè)備的大、小修計劃、備品備件計劃；8、努力鉆研業(yè)務(wù)技術(shù)，不斷進行知識更新。掌握國內(nèi)外先進生產(chǎn)技術(shù)，參與組織實施技術(shù)革新活動安全員崗位責任制1、在車間主任和副主任的領(lǐng)導(dǎo)下，負責車間日常安全管理工作，貫徹上級有關(guān)安全生產(chǎn)的指示和規(guī)定，并監(jiān)督檢查執(zhí)行情況。在業(yè)務(wù)上受公司按環(huán)部領(lǐng)導(dǎo)，有權(quán)直接向按安環(huán)部反映情況，匯報安全方面的工作。2、做好員工的環(huán)境保護、職業(yè)衛(wèi)生、安全生產(chǎn)、消防知識、安全技術(shù)教育工作、負責新入廠人員的車間級安全教育，指導(dǎo)并督促檢查班組(崗位)的安全教育。3、每日深入現(xiàn)場檢查安全生產(chǎn)情況，發(fā)現(xiàn)違章作業(yè)者，要及時糾正或制止。遇有重大險情，應(yīng)立即報告車間處理。4、負責車間事故的管理，參與事故分析和處理，查明責任，積極提出防范措施，建立事故臺帳。5、協(xié)助車間技術(shù)人員編制安全技術(shù)措施計劃并檢查執(zhí)行情況，負責勞動保護用品、消防器材的管理，對存在的不安全因素督促有關(guān)人員及時處理。6、建立健全車間安全管理臺帳，負責安全資料的管理。7、負責制定、修訂車間級事故應(yīng)急預(yù)案，制定演練計劃、方案，并定期組織演練。8、總結(jié)和推廣安全管理工作的先進經(jīng)驗。綜合管理員崗位責任制1、在車間主任（副主任）的領(lǐng)導(dǎo)下，貫徹執(zhí)行公司各項規(guī)章制度。2、負責本單位職工考勤的匯總和職工探親假報批工作。3、負責本單位辦公用品的計劃編制、領(lǐng)取、保管及發(fā)放工作。

4、負責本單位文件、信函、報刊的接收、登記、傳遞、發(fā)放及保管、歸檔管理工作。

5、負責辦理本單位員工調(diào)轉(zhuǎn)、離、退休等工作的報批手續(xù)及新員工的接收工作。

6、負責辦理本單位職工的轉(zhuǎn)正、定級、工資晉升等報批手續(xù)及工資領(lǐng)發(fā)工作。

7、負責辦理經(jīng)本單位領(lǐng)導(dǎo)同意的職工所需的各種證明、介紹信等手續(xù)。

8、負責建立個人考勤臺帳。負責外來電話的記錄，各種會議的通知及有關(guān)會議的記錄、整理工作。

9、積極完成領(lǐng)導(dǎo)交辦的其它工作。班長崗位責任制１、在車間主任（副主任）領(lǐng)導(dǎo)下，負責組織班組的生產(chǎn)和工藝管理，在值班期間受調(diào)度室的領(lǐng)導(dǎo)，對本崗位所屬設(shè)備的安全、經(jīng)濟、文明運行負責，領(lǐng)導(dǎo)全班完成各項生產(chǎn)任務(wù)。２、主持班前和班后會，根據(jù)上級指示和調(diào)度安排，布置當班的工作和注意事項。３、嚴格執(zhí)行崗位操作規(guī)程，控制好各項工藝指標４、對本班組的安全、生產(chǎn)、勞動紀律、現(xiàn)場管理負責。５、及時總結(jié)本班組的生產(chǎn)、操作管理經(jīng)驗８、負責本班的日常檢查、整改工作。９、實事求是，認真細致地填寫崗位各項記錄，并予以保管，對其它崗位的所有記錄要經(jīng)常檢查其填寫情況。10、對違章指揮和命令有權(quán)拒絕執(zhí)行，并迅速越級上報11、負責崗位的設(shè)備、專用工器具、消防和防護器材保管工作。12、負責本班員工的日常工作考核，制定本班員工考核辦法，每月將員工考核情況上報車間。一三、關(guān)心班組職工生活，圍繞以生產(chǎn)為中心搞好班組建設(shè)，增創(chuàng)先進文明生產(chǎn)班組。嚴格執(zhí)行崗位安全生產(chǎn)責任制，指揮協(xié)調(diào)本班生產(chǎn)。司爐崗位責任制1、司爐是當班本臺鍋爐運行的負責人，并服從調(diào)度的統(tǒng)一調(diào)度管理，對所管設(shè)備的安全、經(jīng)濟運行負全部責任。2、負責所管設(shè)備的起動停止，切換操作，認真監(jiān)視設(shè)備儀表，及時進行運行調(diào)整，確保各項運行參數(shù)的正常，對運行日志，記錄及其真實性負責。3、司爐指揮副司爐搞好設(shè)備巡回檢查和定期工作，搞好設(shè)備的維護，對所管設(shè)備按規(guī)定認真檢查，發(fā)現(xiàn)異常及時匯報班長。4、對出現(xiàn)的設(shè)備異?；虬l(fā)生事故時，應(yīng)沉著、冷靜準確判斷并組織人員按規(guī)程有關(guān)規(guī)定處理，并及時報告班長、調(diào)度，對危及設(shè)備及人身安全的命令有權(quán)拒絕執(zhí)行，但必須向有關(guān)領(lǐng)導(dǎo)匯報。5、如因公或其它原因須暫時離崗，經(jīng)班長許可并向副司爐交待好工作，否則不得脫離工作崗位，班長不在時，代理班長職務(wù)，指揮全班生產(chǎn)。6、交接班前要按專責分工，搞好交接班的一切檢查或準備工作。7、負責專責范圍內(nèi)的設(shè)備和場地的整潔，搞好文明生產(chǎn)。8、協(xié)助班長及時完成車間交給的各項臨時任務(wù)。副司爐崗位責任制１、在司爐的直接領(lǐng)導(dǎo)下，協(xié)助司爐搞好所管設(shè)備的安全經(jīng)濟運行，司爐需離崗時，可受委托代行司爐職責。２、在司爐或班長的指導(dǎo)和監(jiān)護下，對所管設(shè)備進行啟動、停止、切換等重大操作和進行定期工作。３、運行中如發(fā)現(xiàn)其它異常運行時，應(yīng)及時匯報司爐，并配合司爐搞好各種事故處理，獨立處理事故時，要及時、準確，事后要立即將處理的全過程報告司爐或班長。４、認真執(zhí)行各項規(guī)章制度，搞好勞動紀律、值班紀律。5、協(xié)助司爐搞好交接班工作，完成分工負責的接班、交班前的檢查和準備工作，并將情況匯報主操。6、對所管設(shè)備按規(guī)定認真檢查，發(fā)現(xiàn)異常及時匯報司爐或班長。7、副司爐離開崗位時，需經(jīng)司爐、班長同意。鍋爐除渣、除灰工崗位責任制１、在班長、司爐的領(lǐng)導(dǎo)和指揮下，完成本崗的工作任務(wù)及各項臨時工作。２、在司爐、副司爐的指導(dǎo)下，搞好鍋爐的灰渣排放、外運。３、負責氣力輸灰系統(tǒng)與除塵器的正常運行和定期巡檢。發(fā)現(xiàn)異常及時匯報班長、司爐或副司爐，并做好記錄。4、負責放灰管、放渣管的檢查，確保放灰管暢通，發(fā)現(xiàn)堵管應(yīng)及時排除。如因故不能排除，應(yīng)向司爐、班長報告。５、負責除塵器及周圍環(huán)境的清理，確保運行正常。6、根據(jù)排渣溫度及時調(diào)節(jié)冷渣器冷卻水量。７、做好交接班前的檢查和準備工作，嚴格執(zhí)行交接班制度。８、要確保除塵器系統(tǒng)的正常運行，不經(jīng)批準，不得隨便停運。汽輪機主操崗位責任制1、汽輪機主操是當班汽輪機、除氧器、給水泵、熱力管網(wǎng)系統(tǒng)安全運行的負責人，并服從調(diào)度的統(tǒng)一調(diào)度管理，對所管設(shè)備的安全、經(jīng)濟運行負全部責任。2、負責所管設(shè)備的起動、停止及切換操作，認真監(jiān)視設(shè)備儀表，及時進行運行調(diào)整，確保各項運行參數(shù)的正常，對運行日志，記錄及其真實性負責。3、汽輪機主操指揮副司機搞好設(shè)備巡回檢查和定期工作，搞好設(shè)備的維護保養(yǎng)，對所管設(shè)備按規(guī)定認真檢查，發(fā)現(xiàn)異常及時匯報班長。4、對出現(xiàn)的設(shè)備異常或發(fā)生事故時，應(yīng)沉著、冷靜準確判斷并組織人員按規(guī)程有關(guān)規(guī)定處理，并及時報告班長、調(diào)度，對危及設(shè)備及人身安全的命令有權(quán)拒絕執(zhí)行，但必須向有關(guān)領(lǐng)導(dǎo)匯報。5、如因公或其它原因須暫時離崗，經(jīng)班長許可并向副操交待好工作，否則不得脫離工作崗位。理班長職務(wù)，指揮全班生產(chǎn)。6、交接班前要按專責分工，搞好交接班的一切檢查或準備工作。7、負責專責范圍內(nèi)的設(shè)備和場地的整潔，搞好文明生產(chǎn)。8、協(xié)助班長及時完成車間交給的各項臨時任務(wù)。汽輪機副操崗位責任制１、在主操的直接領(lǐng)導(dǎo)下，協(xié)助主操搞好所管轄設(shè)備的安全經(jīng)濟運行，主操需離崗時，可受委托代行主操職責。２、在主操或班長的指導(dǎo)和監(jiān)護下，對所管設(shè)備進行啟動、停止、切換等重大操作和進行定期工作。３、運行中如發(fā)現(xiàn)其它異常運行時，應(yīng)及時匯報司機，并配合主操搞好各種事故處理，獨立處理事故時，要及時、準確，事后要立即將處理的全過程報告主操或班長。４、認真執(zhí)行各項規(guī)章制度，搞好勞動紀律、值班紀律。5、協(xié)助主操搞好交接班工作，完成分工負責的接班、交班前的檢查和準備工作，并將情況匯報主操。6、對所管設(shè)備按規(guī)定時間及線路認真檢查，發(fā)現(xiàn)異常及時匯報主操或班長。7、副操離開崗位時，需經(jīng)主操、班長同意。除鹽水（循環(huán)水）主操崗位責任制

在班長的領(lǐng)導(dǎo)下工作，在技術(shù)和業(yè)務(wù)上接受技術(shù)員的檢查和指導(dǎo)，聽從調(diào)度的指揮。對所管設(shè)備的安全、經(jīng)濟運行負全部責任。負責所管設(shè)備的起動、停止及切換操作，認真監(jiān)視設(shè)備儀表，及時進行運行調(diào)整，確保各項運行參數(shù)的正常，對運行日志，記錄及其真實性負責對出現(xiàn)的設(shè)備異?；虬l(fā)生事故時，應(yīng)沉著、冷靜準確判斷并組織人員按規(guī)程有關(guān)規(guī)定處理，并及時報告班長、調(diào)度，對危及設(shè)備及人身安全的命令有權(quán)拒絕執(zhí)行，但必須向有關(guān)領(lǐng)導(dǎo)匯報。嚴格控制工藝指標、水質(zhì)指標，精心操作，確保生產(chǎn)穩(wěn)