基于非合作博弈的制造網(wǎng)絡(luò)資源調(diào)度研究*

郝洪艷 孔凡新

(南京工程學(xué)院材料工程學(xué)院，江蘇 南京 211167)

在制造網(wǎng)絡(luò)環(huán)境下，不同制造任務(wù)之間的利益沖突(包括成本、時間、質(zhì)量等)及自由競爭已成為影響網(wǎng)絡(luò)資源調(diào)度優(yōu)化的關(guān)鍵問題，不同制造任務(wù)都追求自身利益最大化，從而催生了制造網(wǎng)絡(luò)模式下網(wǎng)絡(luò)資源調(diào)度的新模式[1-2]。傳統(tǒng)的網(wǎng)絡(luò)資源調(diào)度以網(wǎng)絡(luò)資源為主體，在綜合考慮各制造任務(wù)需求因素(完成時間、加工成本等)的基礎(chǔ)上，執(zhí)行調(diào)度策略，最終實(shí)現(xiàn)總體目標(biāo)最優(yōu)[3-9]。此類方法忽視了各制造任務(wù)之間所存在的利益沖突，其優(yōu)化結(jié)果具有局限性。因此，研究新的網(wǎng)絡(luò)資源調(diào)度策略和模型以達(dá)到各制造任務(wù)之間的利益均衡，已成為當(dāng)前研究的熱點(diǎn)之一。

本文采用博弈論理論[10-11]，研究一種基于非合作博弈模型的網(wǎng)絡(luò)資源調(diào)度模型，將不同的制造任務(wù)映射為博弈模型的局中人，同時將可選的網(wǎng)絡(luò)資源對應(yīng)的制造任務(wù)的子任務(wù)映射到可行方案集，以各制造任務(wù)的完工總時間和執(zhí)行總成本組合成多目標(biāo)綜合指標(biāo)作為收益函數(shù)。基于非合作博弈模型納什(Nash)均衡點(diǎn)和多層編碼遺傳算法對模型進(jìn)行求解，并進(jìn)行仿真計(jì)算與分析。

1 制造網(wǎng)絡(luò)資源調(diào)度問題的描述

制造網(wǎng)絡(luò)資源調(diào)度就是將制造任務(wù)映射到多管理域的制造網(wǎng)絡(luò)資源上，調(diào)度者根據(jù)總體執(zhí)行時間(吞吐量)和制造資源利用成本選擇資源完成調(diào)度任務(wù)，從而滿足用戶的需求[12]。

圖1所示為制造網(wǎng)絡(luò)資源調(diào)度過程，用戶采用統(tǒng)一的Web頁面，由資源管理器完成資源調(diào)度過程。當(dāng)用戶在Web頁面上提交網(wǎng)絡(luò)制造任務(wù)時，多個任務(wù)將自動進(jìn)入網(wǎng)絡(luò)任務(wù)管理機(jī)構(gòu)維護(hù)的任務(wù)隊(duì)列中，資源管理器根據(jù)資源實(shí)時監(jiān)控器監(jiān)測多個制造資源的動態(tài)負(fù)載情況，調(diào)用資源調(diào)度器。資源調(diào)度器根據(jù)網(wǎng)絡(luò)資源調(diào)度策略從任務(wù)隊(duì)列中選擇合適的任務(wù)分配到適合的資源上執(zhí)行，任務(wù)完工后由資源提交給任務(wù)回收器。此時，檢查是否有未完成的任務(wù)，如果有，就重復(fù)上述調(diào)度過程，如果沒有就將調(diào)度結(jié)果反饋回給用戶。

在制造網(wǎng)絡(luò)平臺上，假定有n個網(wǎng)絡(luò)資源節(jié)點(diǎn)，用戶提交m個待完成制造任務(wù)，每個制造任務(wù)又包含若干個子任務(wù)，完成同一子任務(wù)的網(wǎng)絡(luò)資源節(jié)點(diǎn)有多個，則制造網(wǎng)絡(luò)資源調(diào)度問題可描述為：

(1)存在m個任務(wù)和n個資源節(jié)點(diǎn)(不同地理位置)。

(2)每個任務(wù)包含若干個不同的子任務(wù)(或操作)。

(3)一個網(wǎng)絡(luò)資源至少能夠完成一種子任務(wù)。

(4)在特定時間，每個子任務(wù)需要一個網(wǎng)絡(luò)資源完成。

(5)同一任務(wù)的各個子任務(wù)在同一時刻不能同時執(zhí)行。

(6)每個制造任務(wù)之間無先后約束關(guān)系，機(jī)會均等。

(7)任務(wù)在網(wǎng)絡(luò)資源之間運(yùn)輸時間不能忽略。

基于上述分析，競爭驅(qū)動下的網(wǎng)絡(luò)資源調(diào)度目標(biāo)就是尋求在滿足約束條件下，使得所有制造任務(wù)均能達(dá)到完工時間和總執(zhí)行成本組合目標(biāo)值最小的利益均衡調(diào)度結(jié)果。

2 基于非合作博弈的網(wǎng)絡(luò)資源調(diào)度模型

基于非合作博弈的網(wǎng)絡(luò)資源調(diào)度模型可描述為如下三元組：

G=(T,Si,Zi)

(1)

式中：T={T1,T2,…,Tm}，為局中人集，由m個制造任務(wù)構(gòu)成，任務(wù)Ti包含Ji個制造子任務(wù)，第k個子任務(wù)記為Xi,k，則，Ti={Xi,1,Xi,2,…,Xi,Ji}；Si為局中人Ti的策略集，令G={g1,g2,…,gn}為可選網(wǎng)絡(luò)資源的集合，gj(j=1, …,n)表示網(wǎng)絡(luò)資源，則，Si?G，G≡S=S1S2…Sm；Zi為局中人Ti的收益函數(shù)。

(2)

式中：tji為任務(wù)Ti已完成子任務(wù)時間;tgi為網(wǎng)絡(luò)資源gj上已加工時間。

(3)

式中：ci為任務(wù)Ti完工需要花費(fèi)的總成本；c1,i為任務(wù)Ti的加工成本；c2,i為任務(wù)Ti的運(yùn)輸成本；c3,i為任務(wù)Ti的拖后罰款與超前完工成本。

必須對任務(wù)Ti的完工時間及完工需要花費(fèi)的總成本的取值進(jìn)行歸一化處理，再根據(jù)用戶偏好度對完工時間和總成本取不同權(quán)重構(gòu)建收益函數(shù)(即，目標(biāo)函數(shù))為：

Zi(si)=w1tei+w2ci/5

(4)

式中：si∈Si,w1和w2是權(quán)重系數(shù)，且w1+w2=1。

依據(jù)同一任務(wù)的各個子任務(wù)在同一時刻不能同時執(zhí)行，得約束條件為：

(5)

(6)

式中：i，x=0, 1, …,m-1；k=0, 1, …,Ji-1；y=0, 1, …,Jx-1。

基于非合作博弈模型，網(wǎng)絡(luò)資源調(diào)度問題可以轉(zhuǎn)化為Nash均衡點(diǎn)求解。當(dāng)每個制造任務(wù)單獨(dú)改變策略時，都不能獲得更好的收益，此時便達(dá)到納什均衡，即滿足:

(7)

3 基于多層編碼遺傳算法的模型求解

基于上述非合作博弈數(shù)學(xué)模型，本文采用多層編碼遺傳算法對Nash均衡點(diǎn)進(jìn)行求解。算法流程如圖2所示。

3.1 編碼設(shè)計(jì)

對制造任務(wù)和網(wǎng)絡(luò)資源采用整數(shù)編碼的雙層編碼方式，每個染色體個體代表一個可行解，表示任務(wù)的完成順序及對應(yīng)制造網(wǎng)絡(luò)資源，其編碼為:

BT=[BT(1),BT(2),…,BT(i),…,BT(N)]

(8)

BS=[BS(1),BS(2),…,BS(i),…,BS(N)]

(9)

式中：N為編碼長度，等于子任務(wù)的總數(shù)量；BT為任務(wù)編碼，如果BT(i)=t，且t在染色體中第j次出現(xiàn)，則表示任務(wù)編號i執(zhí)行任務(wù)t的第j個子任務(wù)；BS代表資源編碼,與任務(wù)對應(yīng)，假定BS(i)=g(g∈(1,2,…,n))，則表示任務(wù)t的第j個子任務(wù)的候選資源編號為g。

假定有3個任務(wù)，任務(wù)1有2個子任務(wù), 任務(wù)2有1個子任務(wù), 任務(wù)3有2個子任務(wù), 則總子任務(wù)為5個, 那么編碼長度N=5。如，BT=[3,1,2,3,1]就是一個合法子任務(wù)編碼，完成順序?yàn)椋喝蝿?wù)3(任務(wù)3的第1個子任務(wù))→任務(wù)1(任務(wù)1的第1個子任務(wù))→任務(wù)2→任務(wù)3(任務(wù)3的第2個子任務(wù))→任務(wù)1(任務(wù)1的第2個子任務(wù))。

與BT=[3,1,2,3,1]編碼相對應(yīng)，假定任務(wù)3的子任務(wù)1可以在[4,2]資源上完成,任務(wù)1的子任務(wù)1可以在[2,3]資源上完成, 任務(wù)2的子任務(wù)1可以在[1]資源上完成, 任務(wù)3的子任務(wù)2可以在[2,4,3] 資源上完成，任務(wù)1的子任務(wù)2可以在[1,2]資源上完成，那么BS=[2,3,1,4,2]就是一個合法的資源編碼，資源完成上述任務(wù)的順序?yàn)椋嘿Y源2→資源3→資源1→資源4→資源2。

3.2 適應(yīng)度函數(shù)設(shè)計(jì)

為實(shí)現(xiàn)基于非合作博弈的網(wǎng)絡(luò)資源調(diào)度目標(biāo)，使得每個制造任務(wù)的組合目標(biāo)值均最優(yōu)，從而達(dá)到彼此之間的利益均衡。考慮到制造任務(wù)競爭性要求，設(shè)計(jì)適應(yīng)度函數(shù)為：

(10)

3.3 遺傳算法進(jìn)化操作設(shè)計(jì)

(1)選擇操作

采用輪盤賭方法[13]對適應(yīng)度最優(yōu)個體進(jìn)行選擇。設(shè)種群規(guī)模為Q，個體q的適應(yīng)度為Fq，則個體q被選中遺傳到下一代群體的概率為：

(11)

式中：Pq表示個體q在每次選擇中被選中的概率。

(2)交叉操作

本文采用兩點(diǎn)交叉方案。由于是雙層編碼，在交叉時隨機(jī)選擇一層進(jìn)行交叉。例如，隨機(jī)產(chǎn)生交叉位置為2和4。

父個體 [2,1,1,2,1,2] [1,2,1,2,2,1]

子個體 [2,2,1,2,1,2] [1,1,1,2,2,1]

修補(bǔ)→ [2,2,1,2,1,1] [2,1,1,2,2,1]

修補(bǔ)方法：交叉后，取交叉片段的補(bǔ)集重新隨機(jī)排列到非交叉片段。

(3)變異操作

由于采用雙層編碼，在變異時第一層采用兩點(diǎn)互易進(jìn)行變異，第二層采用單點(diǎn)進(jìn)行變異。

染色體兩點(diǎn)變異為：

[2,1,1,2,1,2]→[2,2,1,1,1,2]

染色體單點(diǎn)變異為：

[1,2,2,1,2,3]→[1,3,2,1,2,3]

4 實(shí)例分析

采用表1～4中的有關(guān)參數(shù)構(gòu)建基于非合作博弈的網(wǎng)絡(luò)資源調(diào)度模型，收益函數(shù)中的權(quán)值均取0.5。利用遺傳算法對模型進(jìn)行求解，算法中的種群規(guī)模Q取200，交叉概率取0.8，變異概率取0.05，最大迭代次數(shù)限定為500次。迭代計(jì)算結(jié)果如圖3所示。由圖3設(shè)定終止閾值ξ為20，可得在第469代時模型達(dá)到Nash均衡。此時，對應(yīng)的甘特圖如圖4所示，圖中，k-l的k表示制造任務(wù)編號，l表示該制造任務(wù)的子任務(wù)編號，縱坐標(biāo)表示完成子任務(wù)的資源，橫坐標(biāo)表示子任務(wù)執(zhí)行時間與順序。由圖4可以看出，當(dāng)達(dá)到Nash均衡時，8×8個子任務(wù)對應(yīng)的網(wǎng)絡(luò)資源為{{1,3,9,6,8,3,2,5}、{1,7,8,2,9,2,3,10}、{2,9,2,8,8,7,2,1}、{4,3,7,9,2,5,5,7}、{1,5,1,2,2,2,2,10}、{5,6,2,1,8,1,4,7}、{2,1,6,8,4,9,5,5}、{4,5,3,6,4,10,5,8}}，執(zhí)行順序也可由對應(yīng)的橫坐標(biāo)讀出。對應(yīng)的完工時間、總成本和組合收益如表5所示。

對比圖5(Nash均衡前，第450代調(diào)度結(jié)果)與圖4，并不是每個任務(wù)的組合效益均提高(效益值降低)，而是更趨向均衡，這與Nash均衡思想一致，表明了所提模型的正確性和求解算法的有效性。

表1 制造任務(wù)與可選資源信息表

任務(wù)編號子任務(wù)編號12345678T1{1，2，4}{3，5}{9，10}{5，6}{7，8}{3，5}{2}{5，6}[6，6，7][2，2][3，2][3，4][3，2][1，2][1][1，2]T2{1，4}{6，7}{5，8}{1，2}{9，10}{1，2，4}{3，4}{10}[3，4][2，3][2，1][5，3][3，4][1，2，3][1，2][2]T3{1，2}{9，10}{2，4}{7，8}{8，9}{7}{2，4}{1，2}[5，3][3，4][2，3][5，4][2，3][3][1，2][2，3]T4{2，4}{3，5}{7，8}{9}{2，4}{2，3，5}{5，8}{7，9}[6，7][2，1][3，4][1][6，7][1，2，1][3，4][1，1]T5{1，2，4}{5，7}{1，2}{2，4}{2，4}{1，2}{2，4}{10}[3，3，2][7，8][3，5][1，2][2，3][3，5][1，2][1]T6{3，5}{4，6}{2}{1，2}{7，8}{1，2，4}{4}{7，8}[1，2][2，3][3][4，3][4，5][3，3，4][9][1，2]T7{2，4}{1，3}{6}{5，8}{4，5}{9，10}{5}{5，6}[4，6][1，2][1][1，2][4，6][5，6][3][2，3]T8{1，2，4}{5，6}{3，6}{6，8}{2，4}{9，10}{5}{8}[2，4，3][8，7][2，3][2，1][6，7][4，5][4][3]

表2 制造任務(wù)交貨期及成本相關(guān)信息

任務(wù)編號tdi/hcvi/(元/h)bi/(元)cbi/(元/h)T11501102T2301102T3321202T4381102T5331202T6341102T7321102T8401202

表3 網(wǎng)絡(luò)資源單位加工成本表

資源編號g1g2g3g4g5g6g7g8g9g10cpi1224153123

表4 網(wǎng)絡(luò)資源節(jié)點(diǎn)之間的運(yùn)輸時間與運(yùn)輸成本表

資源節(jié)點(diǎn)g1g2g3g4g5g6g7g8g9g10tyicyityicyityicyityicyityicyityicyityicyityicyityicyityicyig1--514142534252415251g2----3241625163434143g3------31335261223221g4--------314372616252g5----------5241522131g6------------42716272g7--------------423122g8----------------3263g9------------------42g10--------------------

表5 第450代(Nash均衡前)及469代(Nash均衡點(diǎn))時各調(diào)度結(jié)果

任務(wù)編號完工時間/h超前時間/h庫存成本/元拖后時間/h拖期罰款/元總成本/元組合收益450代469代450代469代450代469代450代469代450代469代450代469代450代469代T15957919391930000636535835T2565500002625626010710538738T347460000151450489492329322T45454000016164242114114384384T5363500003226246662246237T6565600002222545413013741417T744430000121134328888308308T86260000022206460157153467453

5 結(jié)語

本文在考慮制造任務(wù)之間自由競爭性需求的基礎(chǔ)上，對關(guān)聯(lián)于各制造任務(wù)的網(wǎng)絡(luò)資源調(diào)度問題進(jìn)行了研究，分析了制造網(wǎng)絡(luò)下網(wǎng)絡(luò)資源調(diào)度的新模式。以滿足每個制造任務(wù)的加工完成時間和加工成本組合目標(biāo)值最優(yōu)為調(diào)度目標(biāo)，基于博弈論思想構(gòu)建了適應(yīng)各目標(biāo)條件的網(wǎng)絡(luò)資源調(diào)度非合作博弈模型，將網(wǎng)絡(luò)資源調(diào)度問題轉(zhuǎn)化為尋求該博弈模型的納什均衡點(diǎn)問題，并設(shè)計(jì)了多層編碼遺傳算法對模型進(jìn)行求解。應(yīng)用具體算例對所提出的非合作博弈模型進(jìn)行了驗(yàn)證。分析結(jié)果表明，基于博弈理論構(gòu)建的網(wǎng)絡(luò)資源調(diào)度模型及采用遺傳算法的求解方法，能夠較好地解決非合作博弈網(wǎng)絡(luò)資源調(diào)度問題。研究結(jié)果可以為制造網(wǎng)絡(luò)資源調(diào)度提供新方法，從而提高網(wǎng)絡(luò)資源調(diào)度的綜合效益。

[1]Jiang Pingyu, Zhou Guanghui, Zhao Gang, et al.E-2-M ES: an e-service-driven networked manufacturing platform for extended enterprises[J].International Journal of Computer Integrated Manufacturing, 2007, 20(2/3): 127-142.

[2] Zhou Guanghui, Jiang Pingyu, Q George, et al.A game-theory approach for job scheduling in networked manufacturing[J].International Journal of Advanced Manufacturing Technology, 2009, 41: 972-985.

[3] Tong Yifei, Li Dongbo, He Yong, et al.A QoS-based resource economic scheduling in manufacturing grid[J].Mechanika, 2012, 18(4): 484-491.

[4] Hu Hesuan, Li Zhiwu.Modeling and scheduling for manufacturing grid workflows using timed Petri nets[J].International Journal of Advanced Manufacturing Technology, 2009, 42: 553-568.

[5]周永利.基于效益驅(qū)動的制造網(wǎng)絡(luò)資源管理和調(diào)度問題研究[D].長沙：國防科學(xué)技術(shù)大學(xué)，2007.

[6] Tao Fei, Hu Yefa, Zhao Dongming, et al.Study of failure detection and recovery in manufacturing grid resource service scheduling[J].International Journal of Production Research, 2010, 48(1): 69-94.

[7]劉海霞，李仁旺，李學(xué)，等.基于遺傳模擬退火算法的制造網(wǎng)絡(luò)資源調(diào)度策略[J].計(jì)算機(jī)工程與應(yīng)用，2008，44(6): 234-237.

[8]宋書強(qiáng)，葉春明.基于量子粒子群算法的制造網(wǎng)絡(luò)資源調(diào)度問題研究[J].制造業(yè)自動化，2008，30(10):40-43.

[9]劉麗蘭，俞濤，施戰(zhàn)備.制造網(wǎng)絡(luò)中基于服務(wù)質(zhì)量的資源調(diào)度研究[J].計(jì)算機(jī)集成制造系統(tǒng)，2005，11(4): 475-480.

[10]葉林，劉人境.網(wǎng)絡(luò)化制造環(huán)境下任務(wù)調(diào)度的非合作博弈模型及實(shí)現(xiàn)[J].中國機(jī)械工程,2006,17(8): 819- 822.

[11]周光輝，王蕊，江平宇，等.作業(yè)車間調(diào)度的非合作博弈模型與混合自適應(yīng)遺傳算法[J].西安交通大學(xué)學(xué)報(bào),2010,44(5):35-39,70.

[12]王相林，張善卿，王景麗譯.網(wǎng)絡(luò)計(jì)算核心技術(shù)[M].北京：清華大學(xué)出版社，2006.

[13] 郁磊，史峰，王輝，等.MATLAB智能算法30個案例分析[M].北京：北京航空航天大學(xué)出版社，2011.