服務(wù)型制造車間關(guān)鍵任務(wù)調(diào)度的Stackelberg博弈研究

周光輝 程元森 肖忠東 苗發(fā)祥 王 蕊

西安交通大學(xué)機(jī)械制造系統(tǒng)工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，西安，710049

0 引言

在新一代服務(wù)型制造車間中，高效高質(zhì)量滿足外包加工任務(wù)的加工需求是贏得利潤(rùn)的源泉［1－4］。由于服務(wù)型制造車間的開(kāi)放性以及源于不同的服務(wù)外包客戶的加工任務(wù)之間的競(jìng)爭(zhēng)性（包括交貨期、成本等），在特定的時(shí)間段內(nèi)，因某個(gè)／某些任務(wù)加工需求的迫切性而成為關(guān)鍵任務(wù)，該任務(wù)是否能高效完工對(duì)整個(gè)服務(wù)型制造車間的生產(chǎn)效率、效益均具有很大影響，需優(yōu)先考慮調(diào)度關(guān)鍵任務(wù)。在此情況下，車間任務(wù)調(diào)度不僅要考慮關(guān)鍵任務(wù)與非關(guān)鍵任務(wù)集之間的競(jìng)爭(zhēng)因素，同時(shí)還需考慮非關(guān)鍵任務(wù)集內(nèi)部各任務(wù)之間的競(jìng)爭(zhēng)因素，這就導(dǎo)致了服務(wù)型制造車間任務(wù)調(diào)度的復(fù)雜性。

傳統(tǒng)的制造車間的關(guān)鍵任務(wù)調(diào)度以制造車間為主體，執(zhí)行綜合調(diào)度操作，達(dá)到總體目標(biāo)最優(yōu)［5－7］。這忽略了各任務(wù)之間的競(jìng)爭(zhēng)性需求，難以實(shí)現(xiàn)各加工任務(wù)自身利益最大化。因此，需尋求一種新的任務(wù)調(diào)度策略和模型來(lái)解決該問(wèn)題，最終達(dá)到服務(wù)型制造車間中各任務(wù)利益均衡的調(diào)度目標(biāo)。

據(jù)此，圍繞服務(wù)型制造車間的關(guān)鍵任務(wù)調(diào)度問(wèn)題，采用博弈理論［8］，提出了兩層次嵌套的Stackelberg博弈調(diào)度模型。設(shè)計(jì)了基于爬山搜索的混合自適應(yīng)遺傳算法，該算法用于實(shí)現(xiàn)對(duì)該博弈調(diào)度模型Stackelberg均衡點(diǎn)的有效求解。所提出的任務(wù)調(diào)度模型與算法為解決服務(wù)型制造車間關(guān)鍵任務(wù)的調(diào)度決策提供了方案和實(shí)現(xiàn)途徑。

1 服務(wù)型制造車間關(guān)鍵任務(wù)調(diào)度描述

服務(wù)型制造車間的關(guān)鍵任務(wù)調(diào)度問(wèn)題可描述如下：在某服務(wù)型制造車間中，包含m臺(tái)設(shè)備，n個(gè)待加工任務(wù)，其中存在一個(gè)關(guān)鍵任務(wù)，每個(gè)任務(wù)包含多道工序，加工同一工序的設(shè)備至少有一臺(tái)。任務(wù)的加工費(fèi)用、運(yùn)輸費(fèi)用、庫(kù)存費(fèi)用及拖期懲罰費(fèi)用分別與設(shè)備加工時(shí)間、任務(wù)運(yùn)輸時(shí)間、任務(wù)存儲(chǔ)時(shí)間及拖期時(shí)間成正比，任務(wù)的調(diào)度不僅受設(shè)備資源限制，而且受成本（包括加工成本、運(yùn)輸成本、存儲(chǔ)成本、和拖期懲罰成本）影響。任務(wù)調(diào)度的目標(biāo)是在保證關(guān)鍵任務(wù)順利完工的情況下使得各任務(wù)的綜合成本值最小。同時(shí)設(shè)定如下的假設(shè)條件：

（1）當(dāng)某個(gè)任務(wù)的某道工序在某臺(tái)設(shè)備上加工時(shí)，在完成之前不能被中斷；

（2）優(yōu)先調(diào)度關(guān)鍵任務(wù)，其余任務(wù)機(jī)會(huì)均等；

（3）不同工序不能同時(shí)在某臺(tái)設(shè)備上加工；

（4）任務(wù)的工序和加工時(shí)間已知，且不隨加工排序改變，任務(wù)的裝卸時(shí)間計(jì)算在加工時(shí)間內(nèi)；

（5）任務(wù)在設(shè)備間的運(yùn)輸時(shí)間確定。

2 關(guān)鍵任務(wù)調(diào)度的Stackelberg博弈模型

針對(duì)上述關(guān)鍵任務(wù)調(diào)度問(wèn)題的描述，基于Stackelberg博弈理論［9］，建立了關(guān)鍵任務(wù)調(diào)度的Stackelberg博弈模型。在該模型中，將關(guān)鍵任務(wù)映射為領(lǐng)導(dǎo)者，先行決策，非關(guān)鍵任務(wù)映射為追隨者，在關(guān)鍵任務(wù)調(diào)度之后再安排調(diào)度。下面定義該模型及相關(guān)符號(hào)。

設(shè)服務(wù)型制造車間關(guān)鍵任務(wù)調(diào)度的Stackelberg博弈模型為一三元組：

各參數(shù)解釋如下：

（1）Jl為作為領(lǐng)導(dǎo)者的關(guān)鍵任務(wù)，Jf為非關(guān)鍵任務(wù)組成的追隨者集，記Jf＝ （Jf1，Jf2，…，Jf（n－1））；任務(wù)Ji包含JNi道工序，記Oi，j為Ji的第j道工序，則Ji＝ ｛Oi，j｜1≤j≤JNi，j∈Z｝。

（2）Si為Ji的所有可選策略集（對(duì)應(yīng)于與Ji相關(guān)的可選加工設(shè)備集）。Sl為Jl的策略集，Sf為Jf的策略集，Sf＝ （Sf1，Sf2，…，Sf（n－1）），Sfi為Jfi的策略集；si為Ji的某一策略，si∈Si；M 為面向待調(diào)度任務(wù)集合的所有可選加工設(shè)備的集合，記M ＝ （f1，f2，…，fm）。據(jù)此得出Si? M。

（3）Ul為Jl的收益函數(shù)，Uf為Jf的收益函數(shù)集，Uf＝ （Uf1，Uf2，…，Uf（n－1））。在 描 述收益函數(shù)的表達(dá)式前，給出如下定義：sti，j（fk）為Ji的Oi，j在fk上的開(kāi)始加工時(shí)間；pti，j（fk）為Ji的Oi，j在fk上的加工時(shí)間；cti，j（fk）為Ji的Oi，j在fk上的完工時(shí)刻為fk的加工費(fèi)率為Ji的單位時(shí)間運(yùn)輸費(fèi)率；ai為Ji拖期一次性懲罰金額為Ji除一次性懲罰金額外單位拖期時(shí)間懲罰費(fèi)率；為Ji提前完工的單位時(shí)間庫(kù)存費(fèi)率；dti、ati、bti分別為Ji的交貨期、提前時(shí)間、拖期時(shí)間，且ati＝ max（0，dti－cti，JNi（fk）），bti＝ max（0，cti，JNi（fk）－dti）。

基于以上定義，可得出Ji的加工成本為

Ji的拖期懲罰費(fèi)用和提前完工發(fā)生的庫(kù)存費(fèi)用（假設(shè)這兩項(xiàng)費(fèi)用分別是滯后時(shí)間和提前時(shí)間的線性函數(shù)）為

Ji的運(yùn)輸成本為

式中，tti，j（fm，fk）為Ji從fm到fk之間的運(yùn)輸時(shí)間。

據(jù)此，得出Ji的總成本如下：

得出Ji的收益函數(shù)如下：

其中，s ＝ （s1，…，si，…，sn），si∈ Si，并 受 如 下約束：

本文建立的Stackelberg博弈調(diào)度模型中，存在兩個(gè)層次上的子博弈，第一層為關(guān)鍵任務(wù)與非關(guān)鍵任務(wù)集之間Stackelberg動(dòng)態(tài)子博弈，第二層為非關(guān)鍵任務(wù)集中各任務(wù)之間的非合作靜態(tài)子博弈。兩層次子博弈組合構(gòu)成Stackelberg博弈調(diào)度模型框架如圖1所示。

圖1 Stackelberg博弈調(diào)度模型框架

從圖1中看出，設(shè)所有任務(wù)的某一調(diào)度方案策略集s＝ （sl，sf），其中，sf＝ （sf1，sf2，…，sf（n－1））。關(guān)鍵任務(wù)Jl先行決策，與非關(guān)鍵任務(wù)集Jf進(jìn)行Stackelberg動(dòng)態(tài)子博弈；非關(guān)鍵任務(wù)集Jf依據(jù)關(guān)鍵任務(wù)Jl的策略sl進(jìn)行反應(yīng)，并在Jf內(nèi)部各任務(wù)之間進(jìn)行非合作靜態(tài)子博弈，形成相應(yīng)的策略集，并通過(guò)如下的反應(yīng)函數(shù)式反饋至Stackelberg動(dòng)態(tài)子博弈并執(zhí)行下一步子博弈：

當(dāng)且僅當(dāng)同時(shí)滿足下兩式：

3 基于混合自適應(yīng)遺傳算法博弈模型解算

為實(shí)現(xiàn)上述Stackelberg博弈調(diào)度模型的均衡點(diǎn)的有效求解，設(shè)計(jì)了混合自適應(yīng)遺傳算法，通過(guò)引入爬山搜索方法來(lái)提高算法的收斂精度與效率，其中基于爬山搜索方法的混合自適應(yīng)遺傳算法求解流程參見(jiàn)文獻(xiàn)［10-11］。

3.1 染色體編碼設(shè)計(jì)

為提升算法的運(yùn)行效率，本文采用基于工序的編碼方法實(shí)現(xiàn)對(duì)染色體的編碼：所有同一任務(wù)的工序采用相同的符號(hào)，該符號(hào)在染色體中出現(xiàn)的順序代表該任務(wù)的工序次序。如表1所示，染色體中第一次出現(xiàn)“3”表示任務(wù)3的第一道工序，第2次出現(xiàn)“3”表示任務(wù)3的第二道工序，以此類推。

表1 基于工序的染色體編碼

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

服務(wù)型制造車間關(guān)鍵任務(wù)Stackelberg博弈調(diào)度目標(biāo)就是尋求保證關(guān)鍵任務(wù)順利完工的情況下使得每個(gè)任務(wù)均能達(dá)到綜合成本目標(biāo)值最小的利益均衡調(diào)度結(jié)果，需要設(shè)計(jì)新的適應(yīng)度函數(shù)來(lái)反映每個(gè)任務(wù)的競(jìng)爭(zhēng)性加工需求。據(jù)此，設(shè)計(jì)出了如下的適應(yīng)度函數(shù)：

當(dāng)同時(shí)滿足如下三個(gè)不等條件時(shí)，我們認(rèn)為算法達(dá)到工程意義上的Stackelberg策略均衡：

其中，ξ、ξl、ξfi為閾值，用來(lái)確定求解 Stackelberg動(dòng)態(tài)子博弈均衡解及非合作靜態(tài)子博弈Nash均衡解的條件。為求解方便起見(jiàn)，本文令ξl＝ξfi。

3.3 算法的進(jìn)化操作

在本文提出的混合自適應(yīng)遺傳算法中，進(jìn)化操作由選擇、交叉、變異與爬山4種算子組成，其中，選擇操作采用輪盤賭方法；交叉操作采用文獻(xiàn)［12］提出的集合法實(shí)現(xiàn)，在提高交叉效率的同時(shí)，防止產(chǎn)生非法染色體；對(duì)于變異操作，隨機(jī)選取染色體上兩個(gè)位置，將其之間的基因串逆轉(zhuǎn)，由于后部分染色體中基因的任意排序都對(duì)應(yīng)合理的工序排列，因此變異后得到的是合理染色體，不需修復(fù)。爬山搜索法具體的算法設(shè)計(jì)及自適應(yīng)交叉概率與變異概率設(shè)計(jì)參見(jiàn)文獻(xiàn)［10-11］。

4 實(shí)例仿真與分析

4.1 初始條件與參數(shù)

在算例中，設(shè)在某時(shí)間段服務(wù)型制造車間有8個(gè)加工任務(wù)，每個(gè)任務(wù)由8道工序構(gòu)成，其中任務(wù)J3為關(guān)鍵任務(wù)，其余任務(wù)為非關(guān)鍵任務(wù)，同時(shí)該車間包含8臺(tái)機(jī)床。表2～表6分別為任務(wù)的工藝信息、交貨期、費(fèi)率等參數(shù)。在表2中，圓括弧里的數(shù)字表示某任務(wù)的某道工序的可選加工設(shè)備，方括弧則為對(duì)應(yīng)的可選加工設(shè)備加工該工序所需的加工時(shí)間。

表2 制造任務(wù)的基本工藝信息

表3 制造任務(wù)的交貨期、提前／拖期系數(shù)

表4 加工設(shè)備工時(shí)費(fèi)率

表5 設(shè)備間運(yùn)輸時(shí)間

表6 混合自適應(yīng)遺傳算法初始輸入?yún)?shù)

4.2 仿真結(jié)果與分析

根據(jù)設(shè)定的初始條件與參數(shù)，對(duì)建立的關(guān)鍵任務(wù)調(diào)度Stackelberg博弈模型進(jìn)行調(diào)度仿真分析。圖2所示為關(guān)鍵任務(wù)調(diào)度結(jié)果甘特圖及適應(yīng)度值曲線（圖中方括號(hào)［i，j］中的i表示制造任務(wù)的編號(hào)，j表示關(guān)聯(lián)該任務(wù)的工序編號(hào)）。從圖2看出，采用Stackelberg博弈調(diào)度模型，優(yōu)先安排關(guān)鍵任務(wù)J3，算法在140代收斂，所有任務(wù)均提前順利完工。表7列出了在140代求得Stackelberg模型均衡解時(shí)各制造任務(wù)的方案集（加工設(shè)備集）與收益值（綜合調(diào)度成本）。

圖2 關(guān)鍵任務(wù)調(diào)度結(jié)果甘特圖及適應(yīng)度值曲線

表7 關(guān)鍵任務(wù)Stackelberg博弈調(diào)度均衡點(diǎn)方案集及收益值

由表7看出，采用基于Stackelberg博弈調(diào)度模型實(shí)現(xiàn)對(duì)關(guān)鍵任務(wù)的調(diào)度中，所有參與調(diào)度的制造任務(wù)均提前完工，這是由于提前完工帶來(lái)的庫(kù)存成本遠(yuǎn)小于拖期懲罰成本所致。從各任務(wù)的提前庫(kù)存成本與運(yùn)輸成本兩項(xiàng)累計(jì)成本中可以看出，關(guān)鍵任務(wù)J3的成本最低，遠(yuǎn)遠(yuǎn)小于其他非關(guān)鍵任務(wù)的累計(jì)成本，而其他非關(guān)鍵任務(wù)的各累計(jì)成本基本相當(dāng)，這是符合Stackelberg博弈思想的。

進(jìn)一步令θf(wàn)＝θl＝1／n，各任務(wù)權(quán)重相等，將基于關(guān)鍵任務(wù)調(diào)度的Stackelberg博弈模型轉(zhuǎn)化為各任務(wù)機(jī)會(huì)均等條件下的非合作博弈調(diào)度模型。同樣采用上述初始條件與參數(shù)，對(duì)其進(jìn)行仿真分析。圖3所示為非合作博弈任務(wù)調(diào)度結(jié)果甘特圖及適應(yīng)度函數(shù)曲線，算法在130代收斂，達(dá)到Nash均衡。從圖3看出，任務(wù)J3的完工時(shí)間超過(guò)其交貨期。表8列出了在130代求得Nash均衡解時(shí)各制造任務(wù)的方案集（加工設(shè)備集）與收益值（綜合調(diào)度成本）。

圖3 非合作博弈任務(wù)調(diào)度結(jié)果甘特圖及適應(yīng)度值曲線

表8 非合作博弈調(diào)度Nash均衡點(diǎn)的各任務(wù)方案集及收益值

對(duì)比表7與表8中的調(diào)度結(jié)果可以看出，在基于非合作博弈的調(diào)度中，所有任務(wù)機(jī)會(huì)均等，任務(wù)J3失去了優(yōu)先調(diào)度權(quán)利，超期完工，由于拖期懲罰導(dǎo)致其總成本劇增，其余各任務(wù)在非合作博弈調(diào)度中優(yōu)先度較基于Stackelberg博弈的調(diào)度中提高，其綜合成本總體上較Stackelberg博弈調(diào)度減小。由此可見(jiàn)，在存在關(guān)鍵任務(wù)而其余任務(wù)機(jī)會(huì)均等的情況下的服務(wù)型制造車間任務(wù)調(diào)度中，非合作博弈調(diào)度模型不再適合，而基于Stackelberg博弈的調(diào)度模型則能很好地解決此類問(wèn)題。

5 結(jié)束語(yǔ)

本文針對(duì)服務(wù)型制造車間的關(guān)鍵任務(wù)調(diào)度問(wèn)題進(jìn)行了深入研究。針對(duì)服務(wù)型制造車間關(guān)鍵任務(wù)的調(diào)度新需求，采用Stackelberg博弈理論，建立了一種面向關(guān)鍵任務(wù)調(diào)度的兩層次嵌套的Stackelberg博弈模型，將關(guān)鍵任務(wù)調(diào)度問(wèn)題轉(zhuǎn)化為尋求該Stackelberg博弈調(diào)度模型的均衡解問(wèn)題；通過(guò)設(shè)計(jì)一種混合自適應(yīng)遺傳算法實(shí)現(xiàn)了對(duì)該Stackelberg博弈模型均衡解的有效解算；通過(guò)設(shè)計(jì)相應(yīng)的調(diào)度實(shí)例實(shí)現(xiàn)了對(duì)建立的模型與算法的仿真分析，并與機(jī)會(huì)均等條件下的任務(wù)調(diào)度非合作博弈結(jié)果進(jìn)行了對(duì)比分析，結(jié)果表明，所提出的Stackelberg博弈調(diào)度模型與混合自適應(yīng)遺傳算法能很好地解決服務(wù)型制造車間客戶競(jìng)爭(zhēng)驅(qū)動(dòng)的關(guān)鍵任務(wù)調(diào)度問(wèn)題。

［1］汪應(yīng)洛.推進(jìn)服務(wù)型制造：優(yōu)化我國(guó)產(chǎn)業(yè)結(jié)構(gòu)調(diào)整的戰(zhàn)略思考［J］.西安交通大學(xué)學(xué)報(bào)，2010，30（2）：26－31.Wang Yingluo.Boosting Service－type Manufacturing－a Strategic Consideration on Optimizing the Adjustment of China’s Industrial Structure［J］.Journal of Xi’an Jiaotong University，2010，30（2）：26－31.

［2］孫林巖，李剛，江志斌，等.21世紀(jì)的先進(jìn)制造模式－服務(wù)型制造［J］.中國(guó)機(jī)械工程，2007，18（19）：2307－2312.Sun Linyan，Li Gang，Jiang Zhibin，et al.Serviceembedded Manufacturing：Advanced Manufacturing Paradigm in 21st Century［J］.China Mechanical Engineering，2007，18（19）：2307－2312.

［3］Hu Yi，Zhou Xionghui，Li Congxing.Internetbased Intelligent Service－oriented System Architecture for Collaborative Product Development［J］.International Journal of Computer Integrated Manufacturing，2010，23（2）：113－125.

［4］Lu Zhen.An Analytical Study on Service－oriented Manufacturing Strategies［J］.International Journal of Production Economics，2012，139（1）：220－228.

［5］Mastrolilli M.Efficient Approximation Schemes for Scheduling Problems with Release Dates and Delivery Times［J］.Journal of Scheduling，2003，6（6）：521－531.

［6］胡雅麗，楊建軍.基于約束規(guī)則的作業(yè)車間調(diào)度研究［J］.航空精密技術(shù)，2012，48（5）：43－46.Hu Yali，Yang Jianjun.Job Shop Scheduling under Constraint Rules and Manual Intervention［J］.Aviation Precision Manufacturing Technology，2012，48（5）：43－46.

［7］張鐵男，韓兵，于渤.生產(chǎn)能力約束條件下的柔性作業(yè)車間調(diào)度優(yōu)化［J］.系統(tǒng)工程理論與實(shí)踐，2011，31（3）：505－511.Zhang Tienan，Han Bing，Yu Bo.Flexible Job—shop Scheduling Optimization Based on Improved Genetic Algorithm［J］.Systems Engineering－Theory ＆Practice，2011，31（3）：505－511.

［8］席裕庚，王長(zhǎng)軍.控制、規(guī)劃和調(diào)度問(wèn)題中的博弈論應(yīng)用［J］.中國(guó)計(jì)量學(xué)院學(xué)報(bào)，2005，16（1）：8－16.Xi Yugeng，Wang Changjun.The Game Theory Applications in Control，Planning and Scheduling Problems［J］.Journal of China Institute of Metrology，2005，16（1）：8－16.

［9］宿潔.OEM 業(yè)務(wù)的Stackelberg博弈策略與算法［J］.計(jì)算機(jī)工程與應(yīng)用，2008，21：227－230.Su Jie.Stackelberg Game Model and Algorithm of OEM［J］.Computer Engineering and Applications，2008，21：227－230.

［10］Zhou Guanghui，Xiao Zhongdong，Jiang Pingyu，et al.A Game－theoretic Approach to Generating Optimal Process Plans of Multiple Jobs in Networked Manufacturing［J］.International Journal of Computer Integrated Manufacturing，2010，23（12）：1118－1132.

［11］周光輝，王蕊，江平宇，等.作業(yè)車間任務(wù)調(diào)度的非合作博弈模型與混合自適應(yīng)遺傳算法［J］.西安交通大學(xué)學(xué)報(bào)，2010，44（5）：35－39，70.Zhou Ghuanghui，Wang Rui，Jiang Pingyu，et al.Non－cooperation Game Model and Hybrid Adaptive Genetic Algorithm for Job－shop Scheduling［J］.Journal of Xi’an Jiaotong University，2010，44（5）：35－39，70.

［12］Shi Guoyong.A Genetic Algorithm Applied to a Classic Job－shop Scheduling Problem［J］.International Journal of Systems Science，1997，28（1）：25－32.