基于非合作博弈的制造網絡資源調度研究*

郝洪艷 孔凡新

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

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

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

1 制造網絡資源調度問題的描述

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

圖1所示為制造網絡資源調度過程，用戶采用統一的Web頁面，由資源管理器完成資源調度過程。當用戶在Web頁面上提交網絡制造任務時，多個任務將自動進入網絡任務管理機構維護的任務隊列中，資源管理器根據資源實時監控器監測多個制造資源的動態負載情況，調用資源調度器。資源調度器根據網絡資源調度策略從任務隊列中選擇合適的任務分配到適合的資源上執行，任務完工后由資源提交給任務回收器。此時，檢查是否有未完成的任務，如果有，就重復上述調度過程，如果沒有就將調度結果反饋回給用戶。

在制造網絡平臺上，假定有n個網絡資源節點，用戶提交m個待完成制造任務，每個制造任務又包含若干個子任務，完成同一子任務的網絡資源節點有多個，則制造網絡資源調度問題可描述為：

(1)存在m個任務和n個資源節點(不同地理位置)。

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

(3)一個網絡資源至少能夠完成一種子任務。

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

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

(6)每個制造任務之間無先后約束關系，機會均等。

(7)任務在網絡資源之間運輸時間不能忽略。

基于上述分析，競爭驅動下的網絡資源調度目標就是尋求在滿足約束條件下，使得所有制造任務均能達到完工時間和總執行成本組合目標值最小的利益均衡調度結果。

2 基于非合作博弈的網絡資源調度模型

基于非合作博弈的網絡資源調度模型可描述為如下三元組：

G=(T,Si,Zi)

(1)

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

(2)

式中：tji為任務Ti已完成子任務時間;tgi為網絡資源gj上已加工時間。

(3)

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

必須對任務Ti的完工時間及完工需要花費的總成本的取值進行歸一化處理，再根據用戶偏好度對完工時間和總成本取不同權重構建收益函數(即，目標函數)為：

Zi(si)=w1tei+w2ci/5

(4)

式中：si∈Si,w1和w2是權重系數，且w1+w2=1。

依據同一任務的各個子任務在同一時刻不能同時執行，得約束條件為：

(5)

(6)

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

基于非合作博弈模型，網絡資源調度問題可以轉化為Nash均衡點求解。當每個制造任務單獨改變策略時，都不能獲得更好的收益，此時便達到納什均衡，即滿足:

(7)

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

基于上述非合作博弈數學模型，本文采用多層編碼遺傳算法對Nash均衡點進行求解。算法流程如圖2所示。

3.1 編碼設計

對制造任務和網絡資源采用整數編碼的雙層編碼方式，每個染色體個體代表一個可行解，表示任務的完成順序及對應制造網絡資源，其編碼為:

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

(8)

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

(9)

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

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

與BT=[3,1,2,3,1]編碼相對應，假定任務3的子任務1可以在[4,2]資源上完成,任務1的子任務1可以在[2,3]資源上完成, 任務2的子任務1可以在[1]資源上完成, 任務3的子任務2可以在[2,4,3] 資源上完成，任務1的子任務2可以在[1,2]資源上完成，那么BS=[2,3,1,4,2]就是一個合法的資源編碼，資源完成上述任務的順序為：資源2→資源3→資源1→資源4→資源2。

3.2 適應度函數設計

為實現基于非合作博弈的網絡資源調度目標，使得每個制造任務的組合目標值均最優，從而達到彼此之間的利益均衡。考慮到制造任務競爭性要求，設計適應度函數為：

(10)

3.3 遺傳算法進化操作設計

(1)選擇操作

采用輪盤賭方法[13]對適應度最優個體進行選擇。設種群規模為Q，個體q的適應度為Fq，則個體q被選中遺傳到下一代群體的概率為：

(11)

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

(2)交叉操作

本文采用兩點交叉方案。由于是雙層編碼，在交叉時隨機選擇一層進行交叉。例如，隨機產生交叉位置為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]

修補→ [2,2,1,2,1,1] [2,1,1,2,2,1]

修補方法：交叉后，取交叉片段的補集重新隨機排列到非交叉片段。

(3)變異操作

由于采用雙層編碼，在變異時第一層采用兩點互易進行變異，第二層采用單點進行變異。

染色體兩點變異為：

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

染色體單點變異為：

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

4 實例分析

采用表1～4中的有關參數構建基于非合作博弈的網絡資源調度模型，收益函數中的權值均取0.5。利用遺傳算法對模型進行求解，算法中的種群規模Q取200，交叉概率取0.8，變異概率取0.05，最大迭代次數限定為500次。迭代計算結果如圖3所示。由圖3設定終止閾值ξ為20，可得在第469代時模型達到Nash均衡。此時，對應的甘特圖如圖4所示，圖中，k-l的k表示制造任務編號，l表示該制造任務的子任務編號，縱坐標表示完成子任務的資源，橫坐標表示子任務執行時間與順序。由圖4可以看出，當達到Nash均衡時，8×8個子任務對應的網絡資源為{{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}}，執行順序也可由對應的橫坐標讀出。對應的完工時間、總成本和組合收益如表5所示。

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

表1 制造任務與可選資源信息表

任務編號子任務編號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 制造任務交貨期及成本相關信息

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

表3 網絡資源單位加工成本表

資源編號g1g2g3g4g5g6g7g8g9g10cpi1224153123

表4 網絡資源節點之間的運輸時間與運輸成本表

資源節點g1g2g3g4g5g6g7g8g9g10tyicyityicyityicyityicyityicyityicyityicyityicyityicyityicyig1--514142534252415251g2----3241625163434143g3------31335261223221g4--------314372616252g5----------5241522131g6------------42716272g7--------------423122g8----------------3263g9------------------42g10--------------------

表5 第450代(Nash均衡前)及469代(Nash均衡點)時各調度結果

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

5 結語

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

[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]周永利.基于效益驅動的制造網絡資源管理和調度問題研究[D].長沙：國防科學技術大學，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]劉海霞，李仁旺，李學，等.基于遺傳模擬退火算法的制造網絡資源調度策略[J].計算機工程與應用，2008，44(6): 234-237.

[8]宋書強，葉春明.基于量子粒子群算法的制造網絡資源調度問題研究[J].制造業自動化，2008，30(10):40-43.

[9]劉麗蘭，俞濤，施戰備.制造網絡中基于服務質量的資源調度研究[J].計算機集成制造系統，2005，11(4): 475-480.

[10]葉林，劉人境.網絡化制造環境下任務調度的非合作博弈模型及實現[J].中國機械工程,2006,17(8): 819- 822.

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

[12]王相林，張善卿，王景麗譯.網絡計算核心技術[M].北京：清華大學出版社，2006.

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