顧幸生，丁豪杰

（華東理工大學(xué)信息科學(xué)與工程學(xué)院，上海200237）

調(diào)度是一個決策過程，是在規(guī)定的時間內(nèi)進行有限資源的合理化配置，其目的是優(yōu)化一個或多個目標［1］。而生產(chǎn)調(diào)度則是企業(yè)針對生產(chǎn)過程，進行有效、合理地規(guī)劃，以便正常組織和開展產(chǎn)品的生產(chǎn)、加工或制造。生產(chǎn)調(diào)度問題是企業(yè)資源規(guī)劃（enterprise resource planning，ERP）之后，制造執(zhí)行系統(tǒng)（manufacturing executive system，MES）高效、順利地完成產(chǎn)品制造的核心和關(guān)鍵［2］。根據(jù)系統(tǒng)的復(fù)雜性劃分，柔性作業(yè)車間調(diào)度問題（flexible jobshop scheduling problem，F(xiàn)JSP）是最具代表性的一類調(diào)度問題。它將“在一組設(shè)備上加工完成一件產(chǎn)品”定義為一個作業(yè)（Job），其中參與加工的每臺設(shè)備被定義為機器（Machine）；而一個作業(yè)根據(jù)加工工藝等限制，常被分成幾個連續(xù)且相關(guān)的加工環(huán)節(jié)（單元）依次進行加工，這些加工環(huán)節(jié)被定義為工序（Operation）；工序是生產(chǎn)制造過程中最小的調(diào)度單元，每個工序每次只能被一臺機器加工處理［3］。由于并行機等柔性設(shè)備的引入，柔性作業(yè)車間調(diào)度問題的求解需要同時對工序排序和機器選擇兩個子調(diào)度問題進行求解。

隨著研究的深入，大量元啟發(fā)式算法被用于對FJSP進行求解［4］。在對元啟發(fā)式算法的改進和FJSP求解的研究過程中，Mesghouni等率先使用遺傳算法對FJSP進行了求解［5］；Ong等進一步使用克隆和選擇規(guī)則模擬人類免疫系統(tǒng)對FJSP進行求解［6］；Zribi等將遺傳算法和局部搜索算法相混合對FJSP進行求解［7］；Tay和Ho混合遺傳規(guī)劃算法與調(diào)度分發(fā)規(guī)則求解FJSP［8］；Liouane等通過混合蟻群算法和禁忌搜索算法對FJSP進行求解［9］。21世紀以來，粒子群算法因其簡捷、易于實現(xiàn)且便于與其他算法融合的特點而被國內(nèi)外學(xué)者大量地嘗試用于求解FJSP，并取得了豐富的成果。Girish等人較早發(fā)布了結(jié)合調(diào)度規(guī)則的粒子群算法對FJSP進行求解［10］；近年，Nouiri等使用分布式的粒子群算法針對嵌入式實時生產(chǎn)系統(tǒng)中的柔性作業(yè)車間問題進行了求解，均取得了較好的實用效果［11］。

對生產(chǎn)調(diào)度問題的研究涉及多個調(diào)度指標，其中因最大完工時間指標可以有效表達為其他常規(guī)調(diào)度指標的函數(shù)而最常被作為FJSP的目標進行研究。本文同樣以該調(diào)度指標作為研究FJSP的唯一目標，采用一種字符數(shù)串編碼方式對FJSP進行編碼，同時采用一種基于有效空閑時段插入工序生成活動調(diào)度方案的解碼方法［12］對FJSP問題進行解碼；在對存在矛盾的多個調(diào)度指標間研究后［13］，根據(jù)自定義的博弈規(guī)則，利用了這些指標進行博弈，建立博弈解集對傳統(tǒng)的粒子群算法進行改進，并結(jié)合對關(guān)鍵工序備機進行調(diào)整的調(diào)度策略提出了一種博弈粒子群算法。之后，在對一系列調(diào)度標準問題算例進行測試并與其他改進粒子群算法的對應(yīng)結(jié)果進行了對比分析，表明了該博弈粒子群算法的良好求解性能。

1 問題建模

1.1 符號定義

為方便對FJSP的數(shù)學(xué)模型進行描述，本文定義了如表1所示的參數(shù)符號體系。

1.2 數(shù)學(xué)模型

優(yōu)化目標：

約束條件：

FJSP的數(shù)學(xué)模型中，作業(yè)內(nèi)部的工序加工次序為滿足特定的約束條件而進行了預(yù)先的排定，因此加工時必須給予保障；但是由于每個作業(yè)間的相互對等和獨立，不同作業(yè)的工序之間優(yōu)先級相等，其加工次序不受約束，只要相應(yīng)的加工機器空閑，即可進行加工，但是已經(jīng)開始進行加工的工序中途不能被取消，也不能被其他作業(yè)的工序搶占。同時，F(xiàn)JSP還遵循以下的假定，所有參數(shù)均為非負整數(shù)；所有作業(yè)（第1道工序）在開始時刻（0時刻）均可被加工；每個作業(yè)由一個或多個排定的連續(xù)工序組成，每個工序至少有一臺機器可以對其進行加工，且加工過程不能間斷執(zhí)行；一旦一個工序被加工完成，包含該工序的作業(yè)即被立刻轉(zhuǎn)入到其下一個工序所分派的機器等待加工，直到該作業(yè)結(jié)束，而中間的存儲環(huán)節(jié)被假定為無窮大，可以存儲所有待加工的作業(yè)。

表1 FJSP相關(guān)參數(shù)符號定義Tab.1 Denotation of parameter character related with FJSP

從機器加工工序的角度（解碼問題的角度）看FJSP的約束式，易知每臺機器在對所分配到的工序進行加工時，只需保證同屬一個作業(yè)的工序是按其內(nèi)部預(yù)排的次序進行加工即可。此外，本文對機器故障等其他不確定因素未予考慮；但即使如此，由上述介紹可知，從組合優(yōu)化角度看，F(xiàn)JSP模型的解（調(diào)度方案）隨著作業(yè)在不同機器上的排布加工可以有多種不同的方案，是NP-hard問題較難求解的一類。如對于一個簡單的10個作業(yè)分配給10臺機器加工的問題，其可能的調(diào)度方案就有（10?。?0個，而這種組合數(shù)可以隨著作業(yè)數(shù)和機器數(shù)的增加呈指數(shù)爆炸形式的增加，基于文獻［1］附錄部分此類問題模型性能的分析，要在規(guī)定時限內(nèi)從這些數(shù)目眾多的方案中尋找出最優(yōu)調(diào)度方案是一件無法完成的任務(wù)，只能求取其近似最優(yōu)解。

2 問題的編碼和解碼

2.1 問題的編碼

博弈粒子群算法在處理FJSP時，使用了一種新的字符數(shù)串編碼方案，該編碼方案采用整數(shù)字符數(shù)串進行編碼，具體的實現(xiàn)過程通過表2所呈現(xiàn)的FJSP例子進行詳細地說明。

表2 簡單的FJSP例子Tab.2 Instance of FJSP

表2中第1列序號為所有工序的順序編號，為方便與計算機內(nèi)部計數(shù)轉(zhuǎn)換，序號編號從“0”開始；第2列是給定的作業(yè)編號；第3列是按每個作業(yè)的內(nèi)部約束對其所含工序的依次編號；最后3列分別列出了能夠加工該工序的機器和對應(yīng)的加工時間，其中，“-”表示該工序不能被對應(yīng)的機器進行加工。

表3示例了如何將表2所呈現(xiàn)的FJSP例子編碼為相應(yīng)的字符數(shù)串，形成FJSP問題基礎(chǔ)信息編碼表。

表3 FJSP問題基礎(chǔ)信息編碼表Tab.3 Basic information encoding table for the intance of FJSP

表3中的每個字段的編碼位寬，即采用多少字符對該字段信息進行描述應(yīng)視具體問題的規(guī)模而定。針對本例，“索引”、“作業(yè)碼”和“工序碼”字段均選擇了用2位字符表述該字段的信息；而“備選機器及加工時間編碼”字段則選擇了5位字符寬度，其中前2位表示機器號，后3位表示加工相應(yīng)工序的處理時間，對于無法加工的情況則以全‘0’補位。

為配合算法程序使用此編碼方案進行求解，編碼方案設(shè)置了一個數(shù)組項數(shù)與工序數(shù)目相同的字符串數(shù)組，以對每種不斷變化更新的調(diào)度情形進行存儲。每次迭代時，一組更新了的工序排序次序碼被按照當前工序的順序，重新賦給每個待加工的工序；同時，根據(jù)每個工序所分派的備選機器號，對應(yīng)的作業(yè)、工序和機器信息碼被賦給相應(yīng)的工序，最終形成一個新的調(diào)度解，即一個新的可行調(diào)度方案。表4所示的是第1步迭代時，針對已經(jīng)分配好加工機器的原始工序排序，利用一組經(jīng)算法更新后的次序碼，生成一種新的可行調(diào)度方案的信息數(shù)據(jù)，表中第一列是問題當前工序的順序（與當前數(shù)組索引號一致），第二列是一組更新后的工序排序次序碼（與更新后數(shù)組索引號一致），最后一列則是為每個工序分配好機器后的作業(yè)、工序和機器信息碼（機器號和相應(yīng)加工時間編碼的拼接）。算法迭代時，字符串數(shù)組根據(jù)次序碼對當前工序排序進行調(diào)整，并存儲其相應(yīng)的作業(yè)、工序和機器信息碼到更新后的各數(shù)組單元，即使用次序碼作為更新后數(shù)組的索引，將對應(yīng)的作業(yè)、工序和機器信息碼存入相應(yīng)的數(shù)組單元。上述具體的實現(xiàn)過程如圖1所示，對于每個作業(yè)、工序和機器信息碼而言，第1～2位表示作業(yè)號，第3～4位表示該作業(yè)下的工序號，第5～6位表示選中處理該工序的加工機器號，而最后3位表示使用該機器加工該工序的處理時間。

表4 一種待更新編碼情況下的信息數(shù)據(jù)Tab.4 Information data waiting to be updated

圖1 算法迭代中字符數(shù)串編碼更新過程Fig.1 Updatingprocessofthecharacter-number string encoding in iteration

2.2 問題的解碼

算法求解過程中，需要不斷地對新生成的解進行適應(yīng)度值的評估，因此需要將其解碼成為一個可行的調(diào)度方案。根據(jù)文獻［1］中的介紹，調(diào)度可以分為無延遲調(diào)度、活動調(diào)度和半活動調(diào)度，且最優(yōu)的調(diào)度解一定位于活動調(diào)度當中。因此，本文使用文獻［12］所介紹的一種常用的解碼思路，針對所設(shè)計的編碼，將生成的新碼（新的調(diào)度解），根據(jù)依次得到的作業(yè)、工序和機器信息碼所包含的每個工序的調(diào)度信息，將對應(yīng)的工序插入到被指派機器上的空閑時段內(nèi)，最終解碼成為一個活動調(diào)度方案進行相關(guān)調(diào)度指標的考察。

具體解碼時，考察每個工序所分派的機器上已安排的待加工工序情況：如果其上待加工工序間存在符合約束條件的、足夠的空閑時段，則將工序盡可能早的安排到此空閑時段內(nèi)等待加工；否則，就在滿足約束條件的情況下，將工序盡量早地安排在該機器上待加工工序隊列的隊尾。

3 改進的博弈粒子群算法

3.1 傳統(tǒng)粒子群算法

傳統(tǒng)的粒子群算法（particle swarm optimization algorithm，PSO）由Kennedy在考察鳥群協(xié)同覓食等行為之后，于1995年提出，算法最終總結(jié)了如下的速度、位移迭代公式［14］。

式中：w、c1和c2分別表示慣性系數(shù)、個體認知系數(shù)和社會認知系數(shù)，w是維持迭代進行的基本參數(shù)；vcur和xcur表示當前的速度值和位移值；vnext和xnext表示下一步的速度值和位移值；p*表示個體經(jīng)歷過的最好位置；g*表示當前代中所有個體所經(jīng)歷過的最好位置中最優(yōu)的一個位置，即，全局最優(yōu)位置；r1和r2為一組(0，1)內(nèi)的隨機數(shù)，用以維系元啟發(fā)式算法的隨機性。其中，每個工序分量的xnext值被用作所有工序排定次序時的比較依據(jù)。

3.2 博弈粒子群算法

當要使最大完工時間（Cmax）指標最小時，需要令每臺加工機器的負載（Lk）盡可能的飽滿和平衡，因每臺機器對各工序的加工性能（處理時間）不同，這種安排不可能將每個工序都安排在使其加工時間最小的機器之上，根據(jù)總機器負載（Ltotal）的定義，這將令該指標值增加；同理，要使總機器負載指標值最小，則需要將各個工序都盡量安排在使其加工時間最小的機器之上，這種安排常常會造成工序被集中分派給某些加工性能強的機器，即對大多數(shù)工序有較短的加工處理時間的機器（如表2中的機器2），造成這些機器的負載增加，從而令整個調(diào)度方案的最大完工時間增加；而要使最大負載機器負載（Lmax）指標減小，必然要以增加其他加工機器上的負載為代價，即將當前最大負載機器上的某些工序重新合理地分派給其它的加工機器處理，通常情況下，最大負載機器多是加工性能較強的機器，向其它機器分派這些工序同樣會造成其被處理的時間增加，從而引起總機器負載指標值的增加。

因此，當同時考慮優(yōu)化最大完工時間、總機器負載和個體最大機器負載三個指標時，必然會產(chǎn)生需要調(diào)和的矛盾，本文充分利用這些矛盾，為每個粒子構(gòu)建了個體博弈解集，同時為整個群構(gòu)建了一個群體博弈解集，然后分別隨機使用個體博弈解集和群體博弈解集中的一個解代替?zhèn)鹘y(tǒng)粒子群公式（1）、（2）中的p*和g*參與迭代運算。在每個粒子完成各分量的迭代計算之后，針對產(chǎn)生的新解再與原有個體博弈解集中的解進行逐個地博弈，根據(jù)博弈的結(jié)果，更新和維護每個粒子的個體博弈解集；同時根據(jù)進一步博弈的結(jié)果維護群體博弈解集。此時，傳統(tǒng)的粒子群公式變?yōu)?/p>

式中：prep表示隨機地從粒子的個體博弈解集中選出的一個博弈解；而grep表示隨機地從群體博弈解集中選出的一個博弈解。

博弈即一些個人、對、組或者其他組織，面對一堆的環(huán)境條件，在一定的規(guī)則下，同時或先后，一次或多次，從各自允許選擇的行為或策略中進行選擇并加以實施，從而獲得各自結(jié)果的過程［13］。經(jīng)過對上述算法改進策略的分析，易知本算法能夠成功的關(guān)鍵是利用博弈規(guī)則生成有效的個體博弈解集和群體博弈解集，因此博弈規(guī)則的設(shè)計和訂立直接影響著本算法的最終求解效能。

3.3 博弈規(guī)則

本文制定的博弈規(guī)則如下：

（1）博弈成功規(guī)則：依次取出個體博弈解集中的一個解與當前的新解進行博弈，當新解對應(yīng)的調(diào)度方案中至少有1個指標優(yōu)于正與之博弈的個體博弈解集中的某個解的對應(yīng)指標，且另2個指標均不劣于正與之博弈的解的對應(yīng)指標，則用當前的新解替換正與之博弈的個體博弈解集中的解；同時觸發(fā)下一級的博弈，即使用當前的新解繼續(xù)與群體博弈解集中的所有解進行逐個博弈，同樣，當新解對應(yīng)的調(diào)度方案中至少有1個指標優(yōu)于當前正與之博弈的群體博弈解集中的某個解的對應(yīng)指標，且另2個指標均不劣于當前與之博弈的解的對應(yīng)指標，則用新解繼續(xù)替換群體博弈解集中正與之博弈的解。

（2）博弈相持規(guī)則：不論在哪一級博弈中，當新解中至少1個指標優(yōu)于當前正與之博弈的解的對應(yīng)指標，而又未達替換正與之博弈的解的條件時，將當前的新解加入到正與之博弈的解所在的解集中。即，當前新解若處于與個體博弈解集中的所有解進行逐個博弈的階段，則僅增添至個體博弈解集中；若處于與群體博弈解集中的所有解進行逐個博弈的階段，則僅增添入群體博弈解集中，而此時，個體博弈解集中的某個解應(yīng)已被當前新解所替代。

（3）博弈失敗規(guī)則：不論在哪一級的博弈中，當新解中所有的指標均不優(yōu)于正與之博弈的解的所有對應(yīng)指標，則放棄該新解，停止博弈，各博弈解集維持不變。

特別需要說明的是，算法開始運行時，當每個粒子被用隨機位置完成初始化后，此粒子所對應(yīng)的解即為每個粒子個體博弈解集中的初始解，并直接與群體博弈解集中所有的解進行逐個博弈，以維護群體博弈解集；而群體博弈解集中的初始解，則默認為第一個被隨機位置初始化的粒子所對應(yīng)的解。

3.4 算法流程

新的改進算法在本文中被命名為博弈粒子群算法（Gaming PSO）。為方便算法流程的闡述，假設(shè)粒子編號為pno，種群規(guī)模數(shù)為N，迭代計數(shù)為r，算法的總迭代次數(shù)為R，算法流程如圖2所示。

圖2 博弈粒子群算法流程Fig.2 Flow of gaming PSO algorithm

4 關(guān)鍵工序確定及對其加工機器的再分派

圖2所示的算法流程中表明，針對FJSP中的工序排序子問題，主要由改進的粒子群算法迭代公式（3）和式（4）來完成；而針對機器選擇子問題，博弈粒子群算法則引入了重新安排關(guān)鍵工序機器的方法來實現(xiàn)，其中關(guān)鍵工序的確定可以根據(jù)其定義來實現(xiàn)。

4.1 關(guān)鍵工序的定義

關(guān)鍵工序是確定關(guān)鍵路徑的核心要素，關(guān)鍵路徑法由Kelly和Walker共同研究提出。該方法為有效解決資源分配與平衡等問題提供了指導(dǎo)思路，在眾多學(xué)科領(lǐng)域發(fā)揮了重要作用。具體在求解FJSP過程中，考察每一個可行的調(diào)度方案（調(diào)度解），那些不能提前也不能推遲的工序被稱為關(guān)鍵工序，而由關(guān)鍵工序組成的每一條完工路徑都是關(guān)鍵路徑。

4.2 關(guān)鍵工序的確定

依據(jù)關(guān)鍵路徑法中關(guān)鍵工序的定義，關(guān)鍵工序的確定就是考察當前正向安排的調(diào)度解中的所有工序，以正向調(diào)度安排的最大完工時間作為基準進行逆向調(diào)度安排，即將正向調(diào)度安排中的每個工序盡可能的延后加工。對比兩種調(diào)度安排，找出那些在兩種調(diào)度安排下，即不能提前也不能推遲的工序，從而確定出當前的關(guān)鍵工序。由關(guān)鍵工序確定的過程，可以看出關(guān)鍵工序是隨調(diào)度解的不同而動態(tài)變化的。圖3展示了某種調(diào)度情況下如何確定關(guān)鍵工序的過程示意。

圖3 確定關(guān)鍵工序Fig.3 Illustration of finding out critical operations

由圖3可知，作業(yè)1的2個工序在進行逆向安排后，較之前的正向安排均出現(xiàn)了推遲，故是非關(guān)鍵工序；而作業(yè)2的3個工序無論如何安排其開始時間和結(jié)束時間都沒有變化，因此是關(guān)鍵工序。

4.3 針對關(guān)鍵工序的機器再分派

關(guān)鍵工序一旦確定完成后，則按照數(shù)組的次序，找到第1個關(guān)鍵工序，然后在其備選加工機器集中隨機的選出一臺機器重新分派給該關(guān)鍵工序，對于新生成的解進行重新解碼，并在評估得到的調(diào)度方案中的各個指標值后與博弈解集中的解進行逐個地博弈。當完成第1個關(guān)鍵工序的機器再分派嘗試后，繼續(xù)對第2個、第3個直至最后一個關(guān)鍵工序進行相同地備機再分派嘗試，并且在此過程中將得到的新解不斷地與博弈解集中的解進行博弈，以維護和更新各博弈解集。

5 標準算例測試與比對分析

Brandimarte等設(shè)計了一組FJSP算例［15］，包含10個代表性的FJSP問題，分別命名為Mk01～Mk10，成為目前研究FJSP問題的標準問題算例之一。本文用博弈粒子群算法，以最小化最大完工時間為優(yōu)化目標，對Brandimarte算例進行了20次獨立測試，將多次測試所求得最大完工時間的最小值、最大值和平均值列于表5中；同時，為了體現(xiàn)博弈規(guī)則的作用，表5中還列出了不使用博弈規(guī)則，即僅使用傳統(tǒng)的粒子群算法（Tradition PSO）配合對關(guān)鍵工序的機器再分派規(guī)則對Brandimarte算例進行20次獨立測試的結(jié)果情況。為便于與其他一些改進粒子群算法的相應(yīng)結(jié)果進行了對比，表5列出了3種代表性的改進粒子群算法求解Brandimarte算例所得的最優(yōu)結(jié)果。

粒子群算法參數(shù)的選擇主要根據(jù)Clerc的研究結(jié)果選定［16］，w=0.689 343，c1=c2=1.42 694。同時，為體現(xiàn)算法的高效和快捷性，測試各算例時的粒子群規(guī)模（N）依據(jù)具體問題規(guī)模而單獨設(shè)定，列于表格的最后一列；測試中，算法的總迭代次數(shù)均設(shè)為R=100。

表5中的第一跨列（1～3列）介紹了Brandimarte算例的基本特征信息，包括算例名稱、規(guī)模和包含的工序總數(shù)；第二列給出了Girish等人于2009年發(fā)布于“文獻［10］”的結(jié)合了調(diào)度規(guī)則的粒子群算法測試該組算例所得到的最小最大完工時間值；第三列列出了Nouiri等人于2018年發(fā)布于“文獻［11］”的使用多智能體技術(shù)進行協(xié)同的改進粒子群算法對該組算例測試的相應(yīng)結(jié)果值；第四列列出了本文作者于近期發(fā)布于“文獻［17］”的基于解碼再搜索的改進粒子群算法測試該組算例所得到的結(jié)果值；第五跨列（7-9列）給出了結(jié)合對關(guān)鍵工序備機再分派調(diào)度策略而改進的傳統(tǒng)粒子群算法對各Brandimarte算例進行20次獨立測試所得的最大完工時間值情況，包括多次測試得到的最小值、最大值和平均值；第六跨列（10-12列）給出了使用博弈粒子群算法對各Brandimarte算例進行20次獨立測試的結(jié)果情況，包括多次測試得到的最小值、最大值和平均值；跨列的最后一列（第12列）給出了測試每個具體Brandimarte算例時，傳統(tǒng)粒子群算法和博弈粒子群算法所采用的粒子群規(guī)模，同時用“*”上標表明所有對比算法中的最優(yōu)解。

表5 各對比算法針對Brandimarte算例測試所得的最小最大完工時間值的情況Tab.5 Comparison of results on Brandimarte benchmarks with different algorithms

表5中所選的對比算法均是傳統(tǒng)粒子算法與其他某種算法進行融合改進后的粒子群算法，而本文的博弈粒子群算法在設(shè)計上僅是對傳統(tǒng)粒子群算法架構(gòu)的微調(diào)，但考察其對Brandimarte算例的測試結(jié)果中的最優(yōu)解（最小值），其中有9個最優(yōu)解不弱于文獻［10］中的最優(yōu)解，而同樣有9個結(jié)果不弱于文獻［17］中的最優(yōu)解，有6個結(jié)果值不弱于文獻［11］中的最優(yōu)解，表明算法具有較好的求解性能。同時為了進一步考察算法的執(zhí)行效率，表6列出了在N=100時，文獻［17］的算法和博弈粒子群算法執(zhí)行單次迭代的耗時對比。文獻［17］已經(jīng)對其提出的算法收斂度、復(fù)雜度及求解性能等進行了詳細說明，通過對比表6所列的兩種算法單次迭代耗時數(shù)據(jù)，博弈粒子群算法的求解性能較文獻［17］中的算法性能提升了近3～5倍，結(jié)合表5數(shù)據(jù)知博弈粒子群算法的耗時更少但最優(yōu)解的精度更高，故其算法性能更優(yōu)。

此外，通過對比表5中傳統(tǒng)粒子群算法的結(jié)果和博弈粒子群算法的結(jié)果可知，傳統(tǒng)粒子群算法的穩(wěn)定性較差（最大值與最小值的差），且求得最小的最大完工時間值遜于其它算法的結(jié)果值。而當使用博弈規(guī)則對算法改進之后，博弈粒子群算法中的各粒子進行搜索時，在與由這些指標博弈所形成的解集中的解進行信息交流后，間接增加了粒子搜索路徑的曲折性，同時這些指標間的矛盾又可以幫助粒子在搜索中獲得跳出局優(yōu)的“張力”，以維持粒子的繼續(xù)探索。由于粒子不易陷入到局部極值中，其每一次搜索都是一次對解空間有效地探索，這使得算法的搜索更具效率。因此就結(jié)果數(shù)據(jù)看，博弈粒子群算法不僅在求解精度上得到了提高，在搜索的穩(wěn)定性上也得到了極大的改進。

表6 兩種改進粒子群算法的單次迭代耗時對比（N=100）Tab.6 Comparison of duration of iteration with the algorithm from culture[17]and Gaming PSO(N=100)

6 結(jié)論

本文提出的博弈粒子群算法充分利用了問題各性能指標之間的矛盾，通過形成博弈解集對傳統(tǒng)的粒子群算法的信息交流機制進行改良，最終在對研究的單目標調(diào)度問題求解過程中取得了更顯著的效果。由于問題各性能指標的滿足都需要在規(guī)定時間內(nèi)分配到所需的有限資源（矛盾點），因此對矛盾博弈的過程間接為所設(shè)定的目標尋優(yōu)提供了有效的探索方向和驅(qū)離局部極值點的動力。博弈粒子群算法利用了這種隱性特性，結(jié)合對關(guān)鍵工序備機再分派規(guī)則對問題求解，不僅提升了算法的求解速度，也增加了算法的求解精度，而通過用其測試結(jié)果與其他算法相應(yīng)結(jié)果進行對比，進一步表明博弈粒子群算法對單目標FJSP問題求解具有良好的求解性能。

作者貢獻聲明：

顧幸生：算法的前期規(guī)劃和實現(xiàn)過程中的修正以及論文的統(tǒng)稿工作。

丁豪杰：算法的設(shè)計與編程實現(xiàn)，算例測試和結(jié)果比較及論文的撰寫和修正工作。