任務(wù)負(fù)載競(jìng)爭(zhēng)下制造資源配置的非合作博弈方法

陳 冰 劉 凱 楊 挺

西北工業(yè)大學(xué)現(xiàn)代設(shè)計(jì)與集成制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，西安，710072

0 引言

以汽車(chē)、飛機(jī)、航空發(fā)動(dòng)機(jī)、船舶等為代表的離散制造業(yè)在其零件生產(chǎn)過(guò)程中具有工藝復(fù)雜、品種多、批量小、批次多、難度大、特種工藝多的特點(diǎn)，大多采用在一定時(shí)間內(nèi)，同一條生產(chǎn)線上生產(chǎn)多種不同型號(hào)、不同數(shù)量產(chǎn)品的多品種混流生產(chǎn)的生產(chǎn)組織模式［1］，為此，生產(chǎn)線中設(shè)備大都需要承擔(dān)不同種類(lèi)零件的生產(chǎn)任務(wù)。在生產(chǎn)線中往往以設(shè)備利用率作為對(duì)設(shè)備服役過(guò)程的考核指標(biāo)，每臺(tái)設(shè)備在生產(chǎn)過(guò)程中，都希望有較高的設(shè)備利用率，因此，在生產(chǎn)過(guò)程中不同設(shè)備之間存在對(duì)制造任務(wù)的競(jìng)爭(zhēng)關(guān)系。設(shè)備與任務(wù)之間的關(guān)系就是制造資源的配置問(wèn)題。傳統(tǒng)的資源優(yōu)化配置主要從任務(wù)調(diào)度方面進(jìn)行研究，以車(chē)間或者單元為研究對(duì)象，實(shí)現(xiàn)制造任務(wù)向車(chē)間或者單元的生產(chǎn)設(shè)備分配［2-6］。這樣的資源配置方法忽略了生產(chǎn)設(shè)備之間存在的追求任務(wù)負(fù)載的競(jìng)爭(zhēng)關(guān)系，從而不能保證設(shè)備的利用率獲得最大程度的提高，最終導(dǎo)致資源浪費(fèi)。

為此，在本文中把每臺(tái)設(shè)備作為決策主體來(lái)描述它們?cè)谏a(chǎn)過(guò)程中的相互競(jìng)爭(zhēng)關(guān)系，在制造過(guò)程中，以每臺(tái)生產(chǎn)設(shè)備的利用率為收益函數(shù)，建立制造資源配置的非合作博弈模型，并通過(guò)對(duì)局中人的模糊聚類(lèi)實(shí)現(xiàn)對(duì)模型的求解，進(jìn)而實(shí)現(xiàn)制造資源的優(yōu)化配置。

1 設(shè)備配置過(guò)程的形式化描述

本文所研究的是將制造任務(wù)加載到具體生產(chǎn)設(shè)備的過(guò)程，為此，首先進(jìn)行如下假設(shè)：①在同一時(shí)間，一臺(tái)設(shè)備只能完成一個(gè)零件一道工序的生產(chǎn)任務(wù)；②所有的生產(chǎn)設(shè)備有相同的機(jī)會(huì)競(jìng)爭(zhēng)加工任務(wù)。

設(shè)備配置過(guò)程中涉及的主要元素包括制造工藝、生產(chǎn)設(shè)備等，它們可以形式化描述如下：

（1）生產(chǎn)設(shè)備E ＝｛Ei，i＝1，2，…，n｝，表示生產(chǎn)線中的n個(gè)生產(chǎn)設(shè)備。

（2）可用時(shí)間Ta＝｛Ta，i，i＝1，2，…，n｝，表示生產(chǎn)設(shè)備能夠用于生產(chǎn)的時(shí)間。

（3）制造工藝Pr＝｛Pr，ij，i＝1，2，…，m；j＝1，2，…，Ni｝，其中，i 為零件的序號(hào)，j 為零件Pi的工序號(hào)，Ni為工藝路線所包含的工序數(shù)，Pr，ij表示零件Pi的第j道工序。此外，Pi的第j道工序的工時(shí)可以表示為T(mén)ij。

（4）任務(wù)負(fù)載L＝｛Li，i＝1，2，…，n｝，表示在制造任務(wù)加載到生產(chǎn)設(shè)備之后，其所承擔(dān)的工序?qū)?yīng)工時(shí)的總和。

（5）設(shè)備利用率U＝｛Ui，i＝1，2，…，n｝，表示生產(chǎn)設(shè)備的利用率，等于任務(wù)負(fù)載與可用時(shí)間的比值，即

2 制造資源優(yōu)化配置非合作博弈數(shù)學(xué)模型

2.1 博弈論與非合作博弈

博弈論是研究決策問(wèn)題及均衡問(wèn)題的理論。非合作博弈是指所有局中人選擇各自策略以求得自身利益最大化的過(guò)程。規(guī)范型的非合作博弈問(wèn)題包括三個(gè)要素：局中人（player），策略集 （strategy），收益函數(shù)（payoff）［7］。

2.2 制造資源配置的非合作博弈模型

在本文的制造資源配置的非合作博弈過(guò)程中，參與制造的生產(chǎn)設(shè)備映射為博弈模型中的局中人，與生產(chǎn)設(shè)備相關(guān)的制造任務(wù)工序映射為策略集，將生產(chǎn)設(shè)備的利用率作為局中人的收益函數(shù)，通過(guò)求解該模型的Nash均衡［7］，就可完成制造資源的優(yōu)化配置，提高設(shè)備利用率，促進(jìn)設(shè)備之間的負(fù)載均衡，降低設(shè)備運(yùn)行成本，使得任務(wù)負(fù)載和資源配置更趨合理。

針對(duì)上述資源配置模型，引入博弈論，那么制造資源配置的非合作博弈模型可以用如下三元組進(jìn)行描述：

上式的變量描述如下：

（1）假設(shè)有n臺(tái)可用設(shè)備，局中人為E＝｛E1，E2，…，En｝。

（2）Si為局中人Ei的策略集，即設(shè)備可承擔(dān)的可選任務(wù)。生產(chǎn)線中所有設(shè)備局中人的可選任務(wù)集為S｛Si（Pr，i，Ti）｝，i＝1，2，…，n。 假設(shè)局中人Ei的策略集Si包括k個(gè)策略，則Si＝｛（Pr，ij，Tij）｝，i＝1，2，…，n；j＝1，2，…，k。

（3）Ui為設(shè)備局中人的收益函數(shù)，即為生產(chǎn)設(shè)備的利用率。

3 基于模糊聚類(lèi)的博弈模型求解方法

尋找博弈論的解是博弈論的核心內(nèi)容，針對(duì)多個(gè)局中人博弈模型的問(wèn)題，本文引入模糊聚類(lèi)理論對(duì)局中人進(jìn)行聚類(lèi)分析［8-9］，把多個(gè)局中人分為兩組，將多人博弈的模型轉(zhuǎn)化為兩人博弈模型，從而降低博弈求解的難度。

3.1 博弈局中人的模糊聚類(lèi)方法

模糊聚類(lèi)分析應(yīng)用模糊數(shù)學(xué)方法進(jìn)行聚類(lèi)分析，因此模糊聚類(lèi)分析可以將各個(gè)樣本以不同的隸屬度劃分到各個(gè)類(lèi)別，即將樣本對(duì)各個(gè)類(lèi)的隸屬度擴(kuò)展到區(qū)間［0，1］，以數(shù)字定量地確定樣品的“親疏關(guān)系”，從而將樣品進(jìn)行分類(lèi)劃分［10］。

本文采用模糊等價(jià)關(guān)系的聚類(lèi)分析，將不同的博弈局中人進(jìn)行歸屬分類(lèi)。在聚類(lèi)分析之前，需要明確局中人之間的關(guān)系，可以引申為模糊數(shù)學(xué)的模糊關(guān)系。數(shù)學(xué)上用“關(guān)系”來(lái)描述事物之間的聯(lián)系，在模糊數(shù)學(xué)中用集合的形式來(lái)表示“關(guān)系”。如果不僅僅只有兩種事物，那么每?jī)煞N事物將會(huì)構(gòu)成一個(gè)模糊關(guān)系集合，所有模糊關(guān)系的集合構(gòu)成一個(gè)模糊關(guān)系矩陣R＝（rij）n×n。模糊關(guān)系矩陣可以描述設(shè)備局中人策略空間的相似程度，便于歸屬分類(lèi)，從而簡(jiǎn)化博弈模型求解。通常情況下計(jì)算得到的模糊矩陣滿足自反性及對(duì)稱(chēng)性，但是不滿足傳遞性。為了能夠?qū)υO(shè)備局中人進(jìn)行歸屬分類(lèi)，需要對(duì)模糊矩陣進(jìn)行合成運(yùn)算，使模糊矩陣滿足模糊關(guān)系矩陣性質(zhì)。

根據(jù)非合作博弈模型，基于模糊聚類(lèi)分析對(duì)設(shè)備局中人進(jìn)行聚類(lèi)，完成策略空間的歸屬。模糊聚類(lèi)分析的過(guò)程首先是建立模糊聚類(lèi)分析的樣本，通過(guò)消除樣本的量綱把樣本的隸屬度控制在［0，1］區(qū)間之內(nèi)，最后建立模糊相似矩陣，并對(duì)模糊相似矩陣進(jìn)行合成運(yùn)算，求得其傳遞矩陣，最后根據(jù)傳遞矩陣來(lái)歸屬聚類(lèi)。

在整個(gè)聚類(lèi)過(guò)程中，建立模糊相似矩陣的方法有很多種，常用的有：夾角余弦法、相關(guān)系數(shù)法、最大最小法、數(shù)量積法、算術(shù)平均最小法、幾何平均最小法、絕對(duì)值指數(shù)法、絕對(duì)值倒數(shù)法、絕對(duì)值減法等。根據(jù)設(shè)備局中人的特點(diǎn)，這里選擇絕對(duì)值減法來(lái)建立模糊相似矩陣，具體實(shí)現(xiàn)步驟如下：

（1）模糊聚類(lèi)分析的初始樣本表征的是設(shè)備局中人在其策略空間中描述加工每道可選加工工序的利用率，可以使設(shè)備局中人能夠“理性地”爭(zhēng)取自身利用率最大的工序，避免承擔(dān)自身利用率較低的工序。通過(guò)建立初始樣本，可以使得設(shè)備局中人一開(kāi)始就謀求自身利用率最大化，同時(shí)也便于具有相似策略空間的設(shè)備局中人的聚類(lèi)歸屬。此外，根據(jù)初始樣本的特征，可以把樣本的隸屬度控制在［0，1］區(qū)間內(nèi)，便于構(gòu)建模糊相似矩陣。

（2）由于建立的樣本隸屬度在［0，1］區(qū)間內(nèi)，因此不需要再進(jìn)行標(biāo)準(zhǔn)差變換及極差變換來(lái)消除量綱對(duì)模糊相似矩陣的影響。為此，首先對(duì)每一臺(tái)生產(chǎn)設(shè)備Ei用每道工序在該設(shè)備能夠消耗的工時(shí)來(lái)表征，即（xi1，xi2，…，xiM），其中 M 是所有零件所包含工序數(shù)量的總和，即然后，建立模糊相似矩陣R＝（rij）n×n，其中0≤rij≤1，i，j＝1，2，…，n。這里rij表示對(duì)象Ei與Ej的相似程度，且

式中，C為適當(dāng)選取的系數(shù)，使0≤rij≤1。

（3）將標(biāo)定所得的模糊矩陣R改造成模糊等價(jià)矩陣R＊，即使得R滿足模糊關(guān)系矩陣的性質(zhì)。常用平方法求得R的傳遞閉包，依次計(jì)算R2，R4，R8，…，R2i，當(dāng)滿足R＊＝R＊·R＊時(shí)，R＊即為R的傳遞閉包矩陣。

（4）對(duì)傳遞閉包矩陣R＊，取模糊分類(lèi)隸屬度λ由大變小，即從1到0，可以把不同的設(shè)備局中人進(jìn)行歸屬分類(lèi)，形成動(dòng)態(tài)聚類(lèi)圖，從而減少局中人的策略歸屬空間，簡(jiǎn)化博弈模型求解。

3.2 博弈模型納什均衡最優(yōu)解

對(duì)于局中人Ei的策略si和s′i，當(dāng)且僅當(dāng)ui（si，s－i）＞u（s′i，s′－i）對(duì)于任意s－i∈S－i都成立時(shí)，稱(chēng)前者對(duì)于后者是嚴(yán)格優(yōu)勢(shì)的。如果ui（si，s－i）≥u（s′i，s′－i），且至少有一個(gè)s－i使不等式嚴(yán)格成立時(shí)，則稱(chēng)純策略si為弱優(yōu)勢(shì)。一般地，博弈論中將除了某個(gè)給定的局中人之外的所有局中人標(biāo)記為“－i”。

在博弈過(guò)程中，局中人通過(guò)競(jìng)爭(zhēng)與合作，最終會(huì)達(dá)到利益均衡，那么這個(gè)均衡就是博弈論的解。1950年約翰·納什（John Nash）定義了非合作博弈模型及其均衡解。這個(gè)均衡理論被稱(chēng)為納什均衡（Nash Equilibrium）。納什均衡可以用數(shù)學(xué)的方式描述如下：

納什均衡實(shí)際上是一組所有局中人策略的組合，它使得每個(gè)局中人的策略都是對(duì)其他局中人策略的最優(yōu)反應(yīng)，即任何一個(gè)局中人單獨(dú)偏離納什均衡，其自身收益不會(huì)因此而變大；相反，如果存在這么一種均衡不是納什均衡，即不是所有參與者的最優(yōu)策略組合，至少會(huì)有一個(gè)局中人會(huì)改變自己的策略來(lái)謀求更好的收益，那么這種均衡不具有“自我約束力”，就不能達(dá)到一種穩(wěn)定而且持久的平衡。

如前所述，在整個(gè)博弈的過(guò)程中，博弈的結(jié)果不僅受到局中人所選策略的影響，還將受到其他局中人策略的影響，即任何一個(gè)局中人的收益都取決于所有局中人的策略組合。在某一次博弈過(guò)程中，如果某個(gè)局中人的某一種策略對(duì)于其他策略總是嚴(yán)格優(yōu)勢(shì)或者弱優(yōu)勢(shì)的，那么該局中人會(huì)樂(lè)于接受這種策略選擇。推廣開(kāi)來(lái)，如果某種策略組合對(duì)于其他策略組合是嚴(yán)格優(yōu)勢(shì)或者弱優(yōu)勢(shì)的，那么所有的局中人都將樂(lè)于接受這種策略組合，因此是穩(wěn)定的，即達(dá)到了Nash均衡。

對(duì)于有限個(gè)局中人博弈，Nash均衡并不唯一。對(duì)于Nash均衡的多重性問(wèn)題，一般的解決方法是采用均衡精煉的方法。常用的均衡精煉方法主要有帕累托（Pareto）改進(jìn)與風(fēng)險(xiǎn)占優(yōu)兩種方法，本文采用的是帕累托改進(jìn)的方法。即

考慮博弈G＝（N，Si，Ui），對(duì)于任意給定的兩種策略組合s∈Si，如果：①｛i∈N：ui）＞ui（s）｝≠ ?，② 對(duì)于任意一個(gè)i∈N，都有ui）≥ui（s），則稱(chēng)為s 的一個(gè)帕累托改進(jìn)。對(duì)于策略組合而言，如果不存在其他策略組合為其帕累托改進(jìn)，那么稱(chēng)策略組合為帕累托最優(yōu)。

4 算例分析

4.1 非合作博弈模型實(shí)例

為了驗(yàn)證資源優(yōu)化配置非合作博弈模型的有效性及可行性，以擁有8臺(tái)設(shè)備，承擔(dān)7種不同零件生產(chǎn)任務(wù)的生產(chǎn)線為實(shí)例進(jìn)行驗(yàn)證計(jì)算。

表1中給出了設(shè)備可承擔(dān)的工序集合。從表中可以看出設(shè)備E2可以承擔(dān)的工序集合可以表示 為 ｛Pr，11，Pr，15，Pr，24，Pr，33，Pr，41，Pr，45，Pr，47，Pr，56，Pr，62，Pr，71，Pr，73｝，此外，每道工序在對(duì)應(yīng)設(shè)備上的工時(shí)在圓括號(hào)中給出。例如工序Pr，11在E2上的工時(shí)為7.2h。表1中給出的工序集合就是生產(chǎn)設(shè)備的博弈策略空間，其策略只能從該策略空間中選擇，通過(guò)預(yù)測(cè)他人的策略選擇來(lái)確定自己的策略，以謀求自身利益最大化，顯然，Nash均衡解也必定落在這個(gè)工序集合之內(nèi)。

表1 設(shè)備可加工工序集h

4.2 基于模糊聚類(lèi)的博弈模型解算

從表1可知，博弈局中人N＝8，即為｛E1，E2，E3，E4，E5，E6，E7，E8｝，構(gòu)成8 人的多人博弈模型。這種多人博弈模型中Nash均衡的求解是非常困難的。為此，本文引入模糊聚類(lèi)算法來(lái)對(duì)局中人進(jìn)行聚類(lèi)分析，以減少局中人的個(gè)數(shù)，這樣可以大大降低博弈模型的求解難度。

首先對(duì)每個(gè)局中人（設(shè)備）Ei用每道工序在該設(shè)備能夠消耗的工時(shí)來(lái)表征，即（xi1，xi2，…，xiM），例如設(shè)備E1的隸屬度值為

同樣對(duì)其他設(shè)備進(jìn)行表征，并采用絕對(duì)值減法，｜C｜＝0.02，求得模糊相似矩陣為

采用平方法來(lái)求布爾矩陣R的傳遞閉包矩陣：

由于R4＝R8，因此矩陣R的傳遞閉包矩陣t（R）＝R4。當(dāng)λ＝0.7時(shí)，把8個(gè)局中人（設(shè)備）分為兩組，即P1＝｛E1，E4，E5，E7｝，P2＝｛E2，E3，E6，E8｝。經(jīng)過(guò)歸屬后，P1、P2的策略空間分別為

通過(guò)對(duì)比分析P1與P2的策略空間，把只能由生產(chǎn)設(shè)備組P1（P2）加工的工序稱(chēng)為P1（P2）的固有策略，這些固有策略并不因?yàn)樯a(chǎn)設(shè)備組的博弈過(guò)程而改變，也不存在固有設(shè)備組之間的競(jìng)爭(zhēng)。由于固有策略的特殊性，需要對(duì)其進(jìn)行特殊的處理。把P1和P2的固有策略提取出來(lái)，其中，P1的固定策略為

P2的固定策略為

通過(guò)劃分，博弈模型變?yōu)槎瞬┺?。但是存在一個(gè)問(wèn)題，P1及P2的固定策略是由其組員共同承擔(dān)的，對(duì)于具體設(shè)備的配置就需要先對(duì)P1及P2的固定策略進(jìn)行博弈解算，同時(shí)可以得到生產(chǎn)設(shè)備組P1及P2在其固定策略上的設(shè)備利用率，才能使P1、P2間的博弈能夠進(jìn)行下去。

對(duì)P1的固有策略來(lái)說(shuō)，對(duì)其進(jìn)行模糊聚類(lèi)分析，求得模糊相似矩陣及其傳遞閉包矩陣為

同樣地，對(duì)P2的固有策略進(jìn)行模糊聚類(lèi)分析，可以求得其模糊相似矩陣以及傳遞閉包矩陣，即

博弈的結(jié)果是雙方相互作用的結(jié)果，任何一個(gè)局中人改變其策略，雙方的收益都會(huì)發(fā)生變化。需要注意的是，當(dāng)局中人E1與局中人E4選擇的策略中包含相同的工序時(shí)，此時(shí)雙方的利用率收益均為零。根據(jù)之前假設(shè)的條件及博弈模型的約束可以知道，在實(shí)際加工過(guò)程中，同一個(gè)工序不能同時(shí)被兩臺(tái)生產(chǎn)設(shè)備加工，同時(shí)生產(chǎn)設(shè)備并不區(qū)分優(yōu)勢(shì)弱勢(shì)，均具有相同的機(jī)會(huì)申請(qǐng)加工該道工序，因此不能說(shuō)明發(fā)生沖突的工序應(yīng)該由哪臺(tái)設(shè)備進(jìn)行加工，由此雙方局中人的收益均為零。

4.3 Nash均衡的求解

用相同的方法繼續(xù)對(duì)設(shè)備組P1和P2的固定策略劃分為不同的子博弈模型，計(jì)算其利用率收益并對(duì)加工工序進(jìn)行策略歸屬，可以得到設(shè)備局中人的策略空間歸屬。表2列出了設(shè)備組P1和P2固定策略經(jīng)過(guò)博弈后，各設(shè)備局中人的策略空間。

表2 設(shè)備局中人在固定策略下的策略歸屬

在完成了對(duì)設(shè)備組P1和P2的固定策略的策略歸屬之后，把它們對(duì)應(yīng)的策略表示為OP1和OP2，再來(lái)對(duì)設(shè)備組P1和P2進(jìn)行博弈解算。設(shè)備組P1和P2的收益矩陣如表3所示。

表3 P1和P2的收益矩陣

根據(jù)收益矩陣采用基于啟發(fā)搜索算法［11］其N(xiāo)ash均衡計(jì)算過(guò)程如圖1所示。此時(shí)P1選擇策略P1（OP1Pr，25Pr，51Pr，77），P2選擇策略P2（OP2）。圖1顯示了P1和P2純策略Nash均衡帕累托改進(jìn)的收斂曲線。

圖1 P1和P2純策略Nash均衡帕累托改進(jìn)的收斂曲線

為了便于分析問(wèn)題，把P1和P2的其他純策略Nash均衡做了隱藏處理。由圖1可以看出，博弈雙方由于不知道對(duì)方會(huì)選擇什么樣的策略，因此一開(kāi)始均以12.5%的概率來(lái)選擇8組純策略進(jìn)行組合作為本方策略選擇，即以混合策略的形式來(lái)選擇策略。隨著博弈活動(dòng)的進(jìn)行，P1發(fā)現(xiàn)如果選擇策略，P2發(fā)現(xiàn)如果選擇策略，那么他們的利用率收益都會(huì)變大。但是由表3可以看出，如果雙方采取的策略組為的話，此時(shí)并不穩(wěn)定，即只要雙方任何一個(gè)人改變其策略，都會(huì)找到更好的收益。策略組并不是它們的Nash均衡點(diǎn)，是不具有任何的“自我強(qiáng)制性”的。博弈活動(dòng)繼續(xù)深入進(jìn)行，此時(shí)局中人P1知道，P2在這次博弈的活動(dòng)中會(huì)一直選擇策略，如果自己不改變策略將會(huì)得到較小的收益，因此P1最后放棄了本來(lái)能夠得到更好收益的策略，轉(zhuǎn)向采取了收益較差的策略，最終達(dá)到了Nash均衡。由表2及表3可以看出，博弈的結(jié)果是局中人雙方相互作用的結(jié)果，是雙方進(jìn)行競(jìng)爭(zhēng)而產(chǎn)生的結(jié)果，競(jìng)爭(zhēng)的結(jié)果不可能達(dá)到雙方都是嚴(yán)格優(yōu)勢(shì)的均衡解，但是一定是嚴(yán)格弱優(yōu)勢(shì)的均衡解。

將P1和P2的策略歸屬到8臺(tái)生產(chǎn)設(shè)備E1，E2，…，E8上來(lái)，我們可以得到8臺(tái)設(shè)備局中人進(jìn)行博弈后最終的策略選擇。表4為各局中人E1，E2，…，E8的策略選擇及其收益。

表4 局中人策略選擇及收益

5 博弈方法與遺傳優(yōu)化算法的比較

為了驗(yàn)證博弈模型及解算結(jié)果的正確性及有效性，將本文提出的博弈算法與常用的遺傳優(yōu)化算法（genetic algorithm，GA）、禁忌搜索（tabu search，TS）和粒子群算法（particle swarm optimization，PSO）進(jìn)行比較分析。遺傳算法一般由選擇、交叉、變異三種進(jìn)化算子組成。對(duì)于選擇算子，采用輪盤(pán)賭的方法進(jìn)行；對(duì)于交叉算子，采用單點(diǎn)交叉的方法；對(duì)于變異算子，與傳統(tǒng)的變異算子相同，有所區(qū)別的是變異的規(guī)則或者說(shuō)變異的范圍要進(jìn)行控制。由于加工任務(wù)由一系列的加工工序組成，當(dāng)發(fā)生變異時(shí)，則在具有相同加工能力的設(shè)備間發(fā)生變異。由此，在本文的實(shí)例中以種群規(guī)模為50，交叉概率為80%，變異概率為5%條件下進(jìn)行遺傳運(yùn)算，在最大迭代次數(shù)為2000時(shí)進(jìn)化終止。對(duì)于禁忌搜素算法采用禁忌長(zhǎng)度為10、候選集長(zhǎng)度為15，最大迭代次數(shù)為200作為搜索參數(shù)。粒子群算法的參數(shù)設(shè)置為：粒子維數(shù)（即設(shè)備數(shù)）D＝8，粒子規(guī)模（即粒子數(shù)）Xnum＝16，加速系數(shù)c1＝2.2，c2＝1.6。將博弈方法與遺傳算法、禁忌搜算、粒子群算法的優(yōu)化結(jié)果在表5中進(jìn)行比較，可以看出博弈方法在優(yōu)化效果上優(yōu)于遺傳算法。

表5 優(yōu)化結(jié)果比較

6 結(jié)論

針對(duì)制造資源的優(yōu)化配置問(wèn)題，引入博弈論描述設(shè)備之間在任務(wù)負(fù)載上的自由競(jìng)爭(zhēng)關(guān)系。以設(shè)備最大利用率為收益函數(shù)，構(gòu)建了基于非合作博弈論的資源優(yōu)化配置數(shù)學(xué)模型，并根據(jù)模糊數(shù)學(xué)的模糊聚類(lèi)分析理論提出了求解博弈模型Nash均衡的算法。最后通過(guò)實(shí)例并與遺傳算法、禁忌搜算、粒子群算法進(jìn)行比較，驗(yàn)證了本文提出的非合作博弈資源優(yōu)化配置模型及求解方法的有效性和正確性。

［1］王炳剛，饒運(yùn)清，邵新宇，等.基于多目標(biāo)遺傳算法的混流加工／裝配系統(tǒng)排序問(wèn)題研究［J］.中國(guó)機(jī)械工程，2009，20（12）：1434－1438.Wang Binggang，Rao Yunqing，Shao Xinyu，et al.A MOGA－based Algorithm for Sequencing a Mixed－model Fabrication／Assembly System［J］.China Mechanical Engineering，2009，20（12）：1434－1438.

［2］鄭永前，王陽(yáng).基于遺傳算法的加工工藝決策與排序優(yōu)化［J］.中國(guó)機(jī)械工程，2012，23（1）：59－65.Zheng Yongqian，Wang Yang.Optimization of Process Selection and Sequencing Based on Genetic Algorithm［J］.China Mechanical Engineering，2012，23（1）：59－65.

［3］Ma G H，Zhang Y F，Nee A Y C.A Simulated Annealing－based Optimization Algorithm for Process Planning［J］.International Journal of Production Research，2000，38（2）：2671－2687.

［4］潘全科，朱劍英.多工藝路線多資源多目標(biāo)的作業(yè)調(diào)度優(yōu)化［J］.中國(guó)機(jī)械工程，2005，16（20）：1821－1826.Pan Quanke，Zhu Jianying.An Optimization Method for a Multi－objective Job－shop Scheduling Problem under Multi－resource Constraints［J］.China Mechanical Engineering，2005，16（20）：1821－1826.

［5］Wong T N，Leung C W，Mak K L，et al.Dynamic Shop Floor Scheduling in Multi－agent Manufacturing Systems［J］.Expert Systems with Applications，2006，31（3）：486－494.

［6］Li W D.A Simulated Annealing－based Optimization Approach for Integrated Process Planning and Scheduling［J］.International Journal of Computer Integrated Manufacturing，2007，20（1）：80－95.

［7］侯定丕.博弈論導(dǎo)論［M］.合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2004.

［8］鄭丞，金隼，來(lái)新民，等.基于非合作博弈的公差分配優(yōu)化［J］.機(jī)械工程學(xué)報(bào)，2009，45（10）：159－165.Zheng Cheng，Jin Sun，Lai Xinmin，et al.Tolerance Allocation Optimization Based on Non－cooperative Game Analysis［J］.Journal of Mechanical Engineering，2009，45（10）：159－165.

［9］范周田.模糊矩陣?yán)碚撆c應(yīng)用［M］.北京：科學(xué)出版社，2006.

［10］張弢，紀(jì)德云.模糊聚類(lèi)分析法［J］.沈陽(yáng)大學(xué)學(xué)報(bào)，2000，12（2）：73－79.Zhang Tao，Ji Deyun.Fuzzy Clustering Analytical Methods［J］.Journal of Shenyang University，2000，12（2）：73－79.

［11］隗立濤，修乃華.基于啟發(fā)搜索算法的納什均衡計(jì)算［J］.北京交通大學(xué)學(xué)報(bào)，2007，31（3）：58－62.Wei Litao，Xiu Naihua，Computing Nash Equilibria Based on Heuristic Search Methods［J］.Journal of Beijing Jiaotong University，2007，31（3）：58－62.