任務負載競爭下制造資源配置的非合作博弈方法

陳 冰 劉 凱 楊 挺

西北工業大學現代設計與集成制造技術教育部重點實驗室，西安，710072

0 引言

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

為此，在本文中把每臺設備作為決策主體來描述它們在生產過程中的相互競爭關系，在制造過程中，以每臺生產設備的利用率為收益函數，建立制造資源配置的非合作博弈模型，并通過對局中人的模糊聚類實現對模型的求解，進而實現制造資源的優化配置。

1 設備配置過程的形式化描述

本文所研究的是將制造任務加載到具體生產設備的過程，為此，首先進行如下假設：①在同一時間，一臺設備只能完成一個零件一道工序的生產任務；②所有的生產設備有相同的機會競爭加工任務。

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

（1）生產設備E ＝｛Ei，i＝1，2，…，n｝，表示生產線中的n個生產設備。

（2）可用時間Ta＝｛Ta，i，i＝1，2，…，n｝，表示生產設備能夠用于生產的時間。

（3）制造工藝Pr＝｛Pr，ij，i＝1，2，…，m；j＝1，2，…，Ni｝，其中，i 為零件的序號，j 為零件Pi的工序號，Ni為工藝路線所包含的工序數，Pr，ij表示零件Pi的第j道工序。此外，Pi的第j道工序的工時可以表示為Tij。

（4）任務負載L＝｛Li，i＝1，2，…，n｝，表示在制造任務加載到生產設備之后，其所承擔的工序對應工時的總和。

（5）設備利用率U＝｛Ui，i＝1，2，…，n｝，表示生產設備的利用率，等于任務負載與可用時間的比值，即

2 制造資源優化配置非合作博弈數學模型

2.1 博弈論與非合作博弈

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

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

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

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

上式的變量描述如下：

（1）假設有n臺可用設備，局中人為E＝｛E1，E2，…，En｝。

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

（3）Ui為設備局中人的收益函數，即為生產設備的利用率。

3 基于模糊聚類的博弈模型求解方法

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

3.1 博弈局中人的模糊聚類方法

模糊聚類分析應用模糊數學方法進行聚類分析，因此模糊聚類分析可以將各個樣本以不同的隸屬度劃分到各個類別，即將樣本對各個類的隸屬度擴展到區間［0，1］，以數字定量地確定樣品的“親疏關系”，從而將樣品進行分類劃分［10］。

本文采用模糊等價關系的聚類分析，將不同的博弈局中人進行歸屬分類。在聚類分析之前，需要明確局中人之間的關系，可以引申為模糊數學的模糊關系。數學上用“關系”來描述事物之間的聯系，在模糊數學中用集合的形式來表示“關系”。如果不僅僅只有兩種事物，那么每兩種事物將會構成一個模糊關系集合，所有模糊關系的集合構成一個模糊關系矩陣R＝（rij）n×n。模糊關系矩陣可以描述設備局中人策略空間的相似程度，便于歸屬分類，從而簡化博弈模型求解。通常情況下計算得到的模糊矩陣滿足自反性及對稱性，但是不滿足傳遞性。為了能夠對設備局中人進行歸屬分類，需要對模糊矩陣進行合成運算，使模糊矩陣滿足模糊關系矩陣性質。

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

在整個聚類過程中，建立模糊相似矩陣的方法有很多種，常用的有：夾角余弦法、相關系數法、最大最小法、數量積法、算術平均最小法、幾何平均最小法、絕對值指數法、絕對值倒數法、絕對值減法等。根據設備局中人的特點，這里選擇絕對值減法來建立模糊相似矩陣，具體實現步驟如下：

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

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

式中，C為適當選取的系數，使0≤rij≤1。

（3）將標定所得的模糊矩陣R改造成模糊等價矩陣R＊，即使得R滿足模糊關系矩陣的性質。常用平方法求得R的傳遞閉包，依次計算R2，R4，R8，…，R2i，當滿足R＊＝R＊·R＊時，R＊即為R的傳遞閉包矩陣。

（4）對傳遞閉包矩陣R＊，取模糊分類隸屬度λ由大變小，即從1到0，可以把不同的設備局中人進行歸屬分類，形成動態聚類圖，從而減少局中人的策略歸屬空間，簡化博弈模型求解。

3.2 博弈模型納什均衡最優解

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

在博弈過程中，局中人通過競爭與合作，最終會達到利益均衡，那么這個均衡就是博弈論的解。1950年約翰·納什（John Nash）定義了非合作博弈模型及其均衡解。這個均衡理論被稱為納什均衡（Nash Equilibrium）。納什均衡可以用數學的方式描述如下：

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

如前所述，在整個博弈的過程中，博弈的結果不僅受到局中人所選策略的影響，還將受到其他局中人策略的影響，即任何一個局中人的收益都取決于所有局中人的策略組合。在某一次博弈過程中，如果某個局中人的某一種策略對于其他策略總是嚴格優勢或者弱優勢的，那么該局中人會樂于接受這種策略選擇。推廣開來，如果某種策略組合對于其他策略組合是嚴格優勢或者弱優勢的，那么所有的局中人都將樂于接受這種策略組合，因此是穩定的，即達到了Nash均衡。

對于有限個局中人博弈，Nash均衡并不唯一。對于Nash均衡的多重性問題，一般的解決方法是采用均衡精煉的方法。常用的均衡精煉方法主要有帕累托（Pareto）改進與風險占優兩種方法，本文采用的是帕累托改進的方法。即

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

4 算例分析

4.1 非合作博弈模型實例

為了驗證資源優化配置非合作博弈模型的有效性及可行性，以擁有8臺設備，承擔7種不同零件生產任務的生產線為實例進行驗證計算。

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

表1 設備可加工工序集h

4.2 基于模糊聚類的博弈模型解算

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

首先對每個局中人（設備）Ei用每道工序在該設備能夠消耗的工時來表征，即（xi1，xi2，…，xiM），例如設備E1的隸屬度值為

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

采用平方法來求布爾矩陣R的傳遞閉包矩陣：

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

通過對比分析P1與P2的策略空間，把只能由生產設備組P1（P2）加工的工序稱為P1（P2）的固有策略，這些固有策略并不因為生產設備組的博弈過程而改變，也不存在固有設備組之間的競爭。由于固有策略的特殊性，需要對其進行特殊的處理。把P1和P2的固有策略提取出來，其中，P1的固定策略為

P2的固定策略為

通過劃分，博弈模型變為二人博弈。但是存在一個問題，P1及P2的固定策略是由其組員共同承擔的，對于具體設備的配置就需要先對P1及P2的固定策略進行博弈解算，同時可以得到生產設備組P1及P2在其固定策略上的設備利用率，才能使P1、P2間的博弈能夠進行下去。

對P1的固有策略來說，對其進行模糊聚類分析，求得模糊相似矩陣及其傳遞閉包矩陣為

同樣地，對P2的固有策略進行模糊聚類分析，可以求得其模糊相似矩陣以及傳遞閉包矩陣，即

博弈的結果是雙方相互作用的結果，任何一個局中人改變其策略，雙方的收益都會發生變化。需要注意的是，當局中人E1與局中人E4選擇的策略中包含相同的工序時，此時雙方的利用率收益均為零。根據之前假設的條件及博弈模型的約束可以知道，在實際加工過程中，同一個工序不能同時被兩臺生產設備加工，同時生產設備并不區分優勢弱勢，均具有相同的機會申請加工該道工序，因此不能說明發生沖突的工序應該由哪臺設備進行加工，由此雙方局中人的收益均為零。

4.3 Nash均衡的求解

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

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

在完成了對設備組P1和P2的固定策略的策略歸屬之后，把它們對應的策略表示為OP1和OP2，再來對設備組P1和P2進行博弈解算。設備組P1和P2的收益矩陣如表3所示。

表3 P1和P2的收益矩陣

根據收益矩陣采用基于啟發搜索算法［11］其Nash均衡計算過程如圖1所示。此時P1選擇策略P1（OP1Pr，25Pr，51Pr，77），P2選擇策略P2（OP2）。圖1顯示了P1和P2純策略Nash均衡帕累托改進的收斂曲線。

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

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

將P1和P2的策略歸屬到8臺生產設備E1，E2，…，E8上來，我們可以得到8臺設備局中人進行博弈后最終的策略選擇。表4為各局中人E1，E2，…，E8的策略選擇及其收益。

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

5 博弈方法與遺傳優化算法的比較

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

表5 優化結果比較

6 結論

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

［1］王炳剛，饒運清，邵新宇，等.基于多目標遺傳算法的混流加工／裝配系統排序問題研究［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］鄭永前，王陽.基于遺傳算法的加工工藝決策與排序優化［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］潘全科，朱劍英.多工藝路線多資源多目標的作業調度優化［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］侯定丕.博弈論導論［M］.合肥：中國科學技術大學出版社，2004.

［8］鄭丞，金隼，來新民，等.基于非合作博弈的公差分配優化［J］.機械工程學報，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］范周田.模糊矩陣理論與應用［M］.北京：科學出版社，2006.

［10］張弢，紀德云.模糊聚類分析法［J］.沈陽大學學報，2000，12（2）：73－79.Zhang Tao，Ji Deyun.Fuzzy Clustering Analytical Methods［J］.Journal of Shenyang University，2000，12（2）：73－79.

［11］隗立濤，修乃華.基于啟發搜索算法的納什均衡計算［J］.北京交通大學學報，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.