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

聶 黎 張國輝 王小剛 白躍偉

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

0 引言

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

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

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

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

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

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

2.1 參與者

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

2.2 行動(dòng)策略

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

2.3 收益函數(shù)

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

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

ui=ui(S)=1/fi

(1)

式中，fi為工件Ji的流程時(shí)間。

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

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

(2)

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

2.4 納什均衡

(3)

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

fi=fi

(4)

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

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

fi)+(ms-m)

(5)

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

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

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

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

表2 兩種行動(dòng)策略下參與者收益比較

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

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

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

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

(2)隨機(jī)生成初始種群，評(píng)估每個(gè)個(gè)體的適合度。

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

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

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

3.1 編碼與解碼機(jī)制

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

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

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

圖1 染色體對應(yīng)的甘特圖Fig.1 Gantt chart corresponding the chromosome

3.2 適應(yīng)度函數(shù)

遺傳算法評(píng)估每個(gè)個(gè)體的適應(yīng)度時(shí)，適應(yīng)度函數(shù)起到非常重要的作用。本文設(shè)計(jì)的適應(yīng)度函數(shù)為

m)]-1

(6)

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

4 仿真實(shí)驗(yàn)及結(jié)果分析

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

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

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

行動(dòng)策略S1行動(dòng)策略S2參與者加工機(jī)器/加工順序收益加工機(jī)器/加工順序收益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)計(jì)算結(jié)果的倒數(shù)

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

表4 D最小納什均衡對應(yīng)的策略和收益

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

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

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

5 結(jié)語

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