基于博弈論的虛擬制造網(wǎng)絡車間調(diào)度優(yōu)化方法

聶 黎 張國輝 王小剛 白躍偉

1.上海第二工業(yè)大學智能制造與控制工程學院，上海，201209 2.鄭州航空工業(yè)管理學院管理科學與工程學院，鄭州，450015

0 引言

隨著全球供應鏈的迅速發(fā)展和廣泛應用，越來越多的中小企業(yè)聯(lián)合構(gòu)建虛擬制造網(wǎng)絡(virtual manufacturing network, VMN)來生產(chǎn)單個企業(yè)無法完成的特定復雜產(chǎn)品[1]。構(gòu)建及運行VMN的關(guān)鍵問題之一是對生產(chǎn)過程進行科學管理，以較高的柔性和效率滿足客戶個性化需求。在作業(yè)調(diào)度決策過程中，需要考慮顧客和制造商的利益：來自不同顧客的訂單都應盡快得以滿足；VMN應以最高的效率和最低的成本完成所有加工任務。然而顧客和制造商雙方利益有時互相促進，有時互相沖突，因此有必要開發(fā)一種具有協(xié)調(diào)機制的作業(yè)調(diào)度方法以均衡雙方利益。

博弈論是平衡多方利益的有效工具之一，近年來許多學者將之用于作業(yè)調(diào)度領(lǐng)域。TAYEB等[2]將博弈論原理用于帶機器故障維修計劃的車間作業(yè)調(diào)度問題。LI等[3]引入納什均衡方法來解決集成工藝規(guī)劃與調(diào)度問題，并設計了混合遺傳算法。ZHOU等[4]構(gòu)建了網(wǎng)絡化制造環(huán)境下作業(yè)調(diào)度問題的博弈論數(shù)學模型，并開發(fā)了基于遺傳算法的求解算法來求解該數(shù)學模型。周光輝等[5-6]針對服務型制造車間關(guān)鍵任務調(diào)度問題和服務型制造系統(tǒng)外包任務分配決策問題，開發(fā)了基于博弈論的Stackelberg模型。SUN等[7]、ZHANG等[8]應用非合作博弈理論，建立了動態(tài)生產(chǎn)環(huán)境下柔性作業(yè)車間調(diào)度問題的調(diào)度博弈模型。但這些研究都忽略了顧客和制造商雙方利益的均衡。本文針對虛擬制造網(wǎng)絡的車間調(diào)度問題，利用博弈論的納什均衡策略使各顧客和制造商VMN之間的利益達到均衡。

1 虛擬制造網(wǎng)絡車間調(diào)度問題描述

VMN車間調(diào)度問題可以表述如下：一個VMN由多個企業(yè)組成，每個企業(yè)提供不少于一臺的加工設備用于共享。這些共享的設備記作Mj(j= 0，1，…，m-1)，其中，m為設備的臺數(shù)。該VMN需要加工一批來自不同客戶訂單的工件，記作Ji(i=0，1，…，n-1)，其中，n為工件的個數(shù)。工件Ji包含hi道工序，記作Oi,l(l=0，1，…，hi-1)。每個工件的工序必須按照事先約定的順序進行操作。工序Oi,l有ki,l個加工設備可供選擇，工序Oi,l的候選加工設備集合記作Mi,l。工序Oi,l在其第q個候選加工設備上的加工時間記作pi,l,q(q=0，1，…，ki,l-1)。工序Oi,l的最小加工時間記作pi,l，pi,l=min(pi,l,q)。本文假設VMN中所有加工設備都已準備就緒且不發(fā)生故障。

2 虛擬制造網(wǎng)絡車間調(diào)度博弈模型

本文采用博弈論思想，將上述VMN車間調(diào)度問題建模為一個包含n+1個參與者的非合作博弈模型。該模型表述為三元組G=(n+1,S,U)，其中，S為所有參與者的行動策略集，S={s0，s1，…，sn}，st表示第t個參與者的策略，t=0，1，…，n；U為所有參與者的收益函數(shù)集，U={u0，u1，…，un}，ur為第r個參與者的收益函數(shù)，r=0，1，…，n。

2.1 參與者

在該博弈模型中，VMN及需要加工的n個工件都視為博弈的參與者。VMN決定工件的加工順序，每個工件選擇自己的加工路徑。

2.2 行動策略

該模型包含行動策略不同的兩類參與者：工件及整個制造系統(tǒng)VMN。加工工件Ji的策略si=(mi,1,mi,2,…,mi,hi)，其中，mi,l∈Mi,l。假設某工件有3道工序，且每道工序有3臺可供選擇的機器，那么該工件可能的行動策略有27個。VMN的策略sn= (l1，l2，…，ln)表示n個加工工件之間的相對加工順序關(guān)系。

2.3 收益函數(shù)

博弈過程中，每個參與者根據(jù)自己的策略采取行動，從而獲得收益，并期望最大化自身利益。加工工件的目標是希望以最快的速度完成加工，VMN的目標是以最短的時間完成所有工件。

加工工件的流程時間越短，收益越大，故加工工件收益函數(shù)設計為加工工件流程時間的遞減函數(shù)，即加工工件Ji的收益函數(shù)為

ui=ui(S)=1/fi

(1)

式中，fi為工件Ji的流程時間。

VMN完成所有工件所耗時間makespan越短，收益就越大，故其收益函數(shù)設計為makespan的遞減函數(shù)，即VMN的收益函數(shù)為

un=un(S)=1/(ms)

(2)

每個參與者的收益不僅與自身的行動策略有關(guān)，還受其他參與者行動策略的影響。有時它們之間的相互影響是積極的，若所有工件都能以最短的流程時間完成加工，則VMN的makespan最短。有時它們之間的相互影響是消極的，某個工件在追求自身的最短流程時間時，可能要延遲其他工件的加工，從而引起其他工件的流程時間延長，有時甚至導致整個VMN的makespan延長。所以，需要找到所有參與者利益的平衡點。

2.4 納什均衡

(3)

本文的n+1非合作博弈模型不一定存在純納什均衡。為了解決此問題，本文定義使得每個參與者都獲得最大收益的解為理想納什均衡。很明顯，如果博弈模型滿足

fi=fi

(4)

則該博弈模型存在理想納什均衡，反之亦然。

式(4)是個極強條件，大多數(shù)調(diào)度問題都不具備該性質(zhì)。本文針對不存在理想納什均衡的博弈模型定義一個解與理想納什均衡之間的距離：

fi)+(ms-m)

(5)

可見，使得D越小的解越優(yōu)。本文把具有最小D的解稱為D最小納什均衡。如果一個解是理想納什均衡，那么它對應的D為0。

由此，本文將調(diào)度問題轉(zhuǎn)化為尋找D最小納什均衡問題。下一小節(jié)將具體闡述利用遺傳算法求解D最小納什均衡。在這此前，通過一個例子來理解本文的博弈模型。

表1給出的調(diào)度實例考察了一個包含3個加工機器的VMN(假設時間單位為min)?，F(xiàn)有3個工件需要安排加工，工件J0只要完成工序O0,0和O0,1就可以交付。由于工序O0,0有2臺可選加工機器，工序O0,1有3臺可選加工機器，所以工件J0有6種不同的加工路徑策略。同理，工件J1有12種加工路徑策略，工件J2有6種加工路徑策略。3個工件有3！種不同加工順序關(guān)系，所以一共有6×12×6×6=2 592種可能的調(diào)度方案。該調(diào)度實例對應的博弈模型有4個參與者，一共有2 592種不同的行動策略組合。在不同的行動策略組合下，4個參與者可能得到不同的收益。表2比較了2個不同行動策略組合下的各參與者收益情況。由表2發(fā)現(xiàn)，策略S1和S2的區(qū)別在于：根據(jù)策略S1，工序O2,0在機器M2上加工，而根據(jù)策略S2，工序O2,0在機器M0上加工；另外，3個工件加工順序也不同。不難發(fā)現(xiàn)，策略S2是一個納什均衡，而S1不是。

表1 調(diào)度實例的相關(guān)數(shù)據(jù)

表2 兩種行動策略下參與者收益比較

注：表中的收益是按照式(1)或式(2)計算結(jié)果的倒數(shù)

3 基于遺傳算法的D最小納什均衡求解算法

本文設計了基于遺傳算法的優(yōu)化算法來尋找博弈模型的D最小納什均衡。算法流程如下：

(1)設定算法的參數(shù)。如果式(4)成立，則該實例存在理想納什均衡，輸出理想納什均衡，算法終止；否則該實例不存在理想納什均衡，進入下一步驟。

(2)隨機生成初始種群，評估每個個體的適合度。

(3)通過各種遺傳操作，如選擇、變異和交叉，由當前種群演變成新一代種群。

(4)判斷本次迭代是否滿足終止條件即是否達到一定的迭代次數(shù)。如果滿足條件，則算法終止，最佳個體即為所求；否則，轉(zhuǎn)到步驟(3)，進入下一次迭代。

由于篇幅有限，僅側(cè)重于編碼與解碼機制以及適應度函數(shù)的討論。

3.1 編碼與解碼機制

編碼是將調(diào)度問題可行解描述為遺傳算法“染色體”的過程。“染色體”包含的調(diào)度問題可行解的信息就是博弈模型中每個參與者的行動策略。編碼設計中，一方面需要考慮如何在染色體中完整包含這些信息，另一方面還需要盡量以緊湊的方式表達這些信息，以減少存儲空間開銷，同時還要方便遺傳算法在進化過程中對染色體進行的各種遺傳算子操作。

假設調(diào)度問題包括n個工件，則每個染色體被設計成n+1個部分。前n個部分對應n個工件的行動策略，即工件的各道工序所選擇的加工機器。最后一個部分對應VMN，該部分染色體決定了所有工件的加工順序。以表1中的實例為例，((1,0), (1,2,0), (2,0), (0,2,1))就是一個染色體。該染色體由4個部分組成。第1部分(1,0)是第1個工件J0的行動策略，它表達的意思是該工件的第1道工序O0,0在其候選加工設備集合中的機器M2上加工；該工件的第2道工序O0,1在其候選加工設備集合中的機器M0上加工。第2部分(1,2,0)是第2個工件J1的行動策略，它表達的意思是該工件的第1道工序O1,0在其候選加工設備集合中的機器M1上加工；該工件的第2道工序O1,1在其候選加工設備集合中的機器M2上加工；該工件的第3道工序O1,2在其候選加工設備集合中的機器M1上加工。第3部分(2,0)是第3個工件J2的行動策略。它表達的意思是該工件的第1道工序O2,0在其候選加工設備集合中的機器M2上加工；該工件的第2道工序O2,1在其候選加工設備集合中的機器M0上加工。最后一部分(0,2,1)是VMN給各個工件排序的策略，它表達的意思是第1個工件最先加工，其次是第3個工件，最后加工第2個工件。該編碼機制的優(yōu)點在于保持了染色體的線性表達，也保證了各種基本變異和交叉操作能很容易地在染色體上實現(xiàn)而不會產(chǎn)生非法解。

解碼是編碼的逆過程，把按照規(guī)則編寫的染色體翻譯成為可行的調(diào)度方案。以表1的實例來說明如何將染色體((1,0), (1,2,0), (2,0), (0,2,1))解碼為活動調(diào)度方案。第1個工件J0的第1道工序O0,0在M2上加工并且在加工順序中處于第1位，所以工序O0,0在0～4 min內(nèi)在M2上加工。然后，J0的第2道工序O0,1在4～6 min內(nèi)在M0上加工。第2個工件J1的第1道工序O1,0選擇在M1上加工，由于此時M1上沒有其他工件搶占機器，所以工序O1,0在0～4 min內(nèi)在機器M1上加工。然后，J1的第2道工序O1,1選擇在M2上加工。然而，第3個工件J2的第1道工序O2,0此時也選擇在M2上加工。由于工件J2加工順序相對于工件J1較前，所以工序O2,0在4～6 min內(nèi)在機器M2上加工，而工序O1,1在6～7 min內(nèi)在機器M2上加工。剩余的解碼過程不再贅述。最終該染色體可解碼成的活動調(diào)度方案如圖1所示。

圖1 染色體對應的甘特圖Fig.1 Gantt chart corresponding the chromosome

3.2 適應度函數(shù)

遺傳算法評估每個個體的適應度時，適應度函數(shù)起到非常重要的作用。本文設計的適應度函數(shù)為

m)]-1

(6)

前期仿真實驗得到的合適遺傳算法參數(shù)如下：種群的大小為100，最大迭代次數(shù)為100，交叉和變異操作的概率分別為0.8和0.2。

4 仿真實驗及結(jié)果分析

為了驗證本文優(yōu)化調(diào)度方法的有效性，從相關(guān)文獻中選擇了若干具有代表性的benchmark問題進行測試。首先，本文以文獻[4]中實例為例進行了測試，該實例規(guī)模為6×6，不存在理想納什均衡。圖2為用傳統(tǒng)方法和用本文方法得到的優(yōu)化調(diào)度方案甘特圖。表3給出了兩種方法的結(jié)果，其中，S1表示傳統(tǒng)方法得到的最優(yōu)解所對應的各個個體行動策略，S2表示本文方法得到的D最小納什均衡所對應的各個參與者行動策略。當參與者是工件時，“加工機器/加工順序”欄是工件對應的加工機器；當參與者是V(表示VMN)時，“加工機器/加工順序”欄是所有工件的加工順序。

由表3可以看出,兩種方法都可以得到最優(yōu)的makespan=36。然而，傳統(tǒng)方法中并沒有考慮各個顧客的利益，即不能在滿足整個VMN生產(chǎn)成本最低的情況下，保證每個顧客訂單盡可能早地完工交付，而本文方法在保證不延長makespan的基礎上，使得工件J1、J3和J5比傳統(tǒng)方法分別提前2 min、2 min和1 min單位完工。

圖2 在文獻[4]實例上的調(diào)度甘特圖Fig.2 Gantt chart for the instance in [4]

行動策略S1行動策略S2參與者加工機器/加工順序收益加工機器/加工順序收益J0M0,M3,M0,M1,M3,M132M0,M3,M0,M2,M5,M132J1M1,M0,M5,M4,M2,M028M1,M0,M5,M4,M1,M026J2M4,M0,M5,M0,M4,M136M4,M0,M3,M0,M4,M136J3M3,M1,M2,M3,M1,M235M3,M1,M2,M3,M1,M233J4M2,M4,M3,M4,M2,M536M2,M1,M5,M4,M3,M536J5M5,M0,M1,M4,M0,M336M5,M2,M1,M2,M0,M335VJ0,J1,J2,J3,J4,J536J0,J1,J2,J3,J4,J536

注：表中的收益是按照式(1)或式(2)計算結(jié)果的倒數(shù)

另外，還選擇了文獻[9]中的10個實例進行了測試。該10個實例規(guī)模從2×2到4×5，其中，實例SFJS07存在理想納什均衡，其他實例不存在理想納什均衡。表4列出了各個實例的結(jié)果。當參與者是工件時，“加工機器/加工順序”欄是工件對應的加工機器；當參與者是V(表示VMN)時，“加工機器/加工順序”欄是所有工件的加工順序。從表4中結(jié)果可以看到，實例SFJS04和SFJS08不可能同時使VMN的makespan和各個工件的流程時間都達到最小，但本文方法可以適當?shù)鼐釼MN和各個工件之間的利益。實例SFJS08不考慮各個工件的利益時，VMN的最優(yōu)makespan是253 min；均衡各個工件利益時，VMN的最優(yōu)makespan是256 min。雖然比傳統(tǒng)方法得到的makespan多3 min，但保證了每個工件都獲得盡可能小的流程時間，這意味著VMN以較小的成本代價使得所有顧客的要求盡早得以滿足。圖3、圖4為2種方法在實例SFJS04和SFJS08的甘特圖。

表4 D最小納什均衡對應的策略和收益

注：表中的收益是按照式(1)或式(2)計算結(jié)果的倒數(shù)

圖3 在實例SFJS04上的調(diào)度甘特圖Fig.3 Gantt chart for the instance of SFJS04

圖4 在實例SFJS08上的調(diào)度甘特圖Fig.4 Gantt chart for the instance of SFJS08

5 結(jié)語

本文將虛擬制造網(wǎng)絡車間調(diào)度問題視為一場博弈，采用博弈論的概念和建模方法，提出了n+1非合作博弈調(diào)度優(yōu)化模型，并設計了基于遺傳算法的D最小納什均衡求解算法。對多個實例的測試驗證了所提調(diào)度優(yōu)化方法是有效的，該方法能夠均衡多個顧客和VMN之間的利益，保證制造商生產(chǎn)效率和顧客滿意度的雙贏。進一步的研究將使用博弈論的Stackelberg策略來開發(fā)虛擬制造網(wǎng)絡環(huán)境下車間調(diào)度問題的優(yōu)化方法，讓虛擬制造網(wǎng)絡中的某個企業(yè)占主導地位，其他企業(yè)作為跟隨者，為支撐生產(chǎn)經(jīng)營活動良好運作提供優(yōu)化的車間調(diào)度解決方案。