面向柔性作業(yè)車(chē)間調(diào)度問(wèn)題的改進(jìn)博弈粒子群算法

顧幸生，丁豪杰

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

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

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

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

1 問(wèn)題建模

1.1 符號(hào)定義

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

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

優(yōu)化目標(biāo)：

約束條件：

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

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

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

2 問(wèn)題的編碼和解碼

2.1 問(wèn)題的編碼

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

表2 簡(jiǎn)單的FJSP例子Tab.2 Instance of FJSP

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

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

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

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

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

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

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

2.2 問(wèn)題的解碼

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

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

3 改進(jìn)的博弈粒子群算法

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

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

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

3.2 博弈粒子群算法

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

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

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

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

3.3 博弈規(guī)則

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

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

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

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

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

3.4 算法流程

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

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

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

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

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

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

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

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

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

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

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

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

5 標(biāo)準(zhǔn)算例測(cè)試與比對(duì)分析

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

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

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

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

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

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

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

6 結(jié)論

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

作者貢獻(xiàn)聲明：

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

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