服務型制造車間關鍵任務調度的Stackelberg博弈研究

周光輝 程元森 肖忠東 苗發祥 王 蕊

西安交通大學機械制造系統工程國家重點實驗室，西安，710049

0 引言

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

傳統的制造車間的關鍵任務調度以制造車間為主體，執行綜合調度操作，達到總體目標最優［5－7］。這忽略了各任務之間的競爭性需求，難以實現各加工任務自身利益最大化。因此，需尋求一種新的任務調度策略和模型來解決該問題，最終達到服務型制造車間中各任務利益均衡的調度目標。

據此，圍繞服務型制造車間的關鍵任務調度問題，采用博弈理論［8］，提出了兩層次嵌套的Stackelberg博弈調度模型。設計了基于爬山搜索的混合自適應遺傳算法，該算法用于實現對該博弈調度模型Stackelberg均衡點的有效求解。所提出的任務調度模型與算法為解決服務型制造車間關鍵任務的調度決策提供了方案和實現途徑。

1 服務型制造車間關鍵任務調度描述

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

（1）當某個任務的某道工序在某臺設備上加工時，在完成之前不能被中斷；

（2）優先調度關鍵任務，其余任務機會均等；

（3）不同工序不能同時在某臺設備上加工；

（4）任務的工序和加工時間已知，且不隨加工排序改變，任務的裝卸時間計算在加工時間內；

（5）任務在設備間的運輸時間確定。

2 關鍵任務調度的Stackelberg博弈模型

針對上述關鍵任務調度問題的描述，基于Stackelberg博弈理論［9］，建立了關鍵任務調度的Stackelberg博弈模型。在該模型中，將關鍵任務映射為領導者，先行決策，非關鍵任務映射為追隨者，在關鍵任務調度之后再安排調度。下面定義該模型及相關符號。

設服務型制造車間關鍵任務調度的Stackelberg博弈模型為一三元組：

各參數解釋如下：

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

（2）Si為Ji的所有可選策略集（對應于與Ji相關的可選加工設備集）。Sl為Jl的策略集，Sf為Jf的策略集，Sf＝ （Sf1，Sf2，…，Sf（n－1）），Sfi為Jfi的策略集；si為Ji的某一策略，si∈Si；M 為面向待調度任務集合的所有可選加工設備的集合，記M ＝ （f1，f2，…，fm）。據此得出Si? M。

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

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

Ji的拖期懲罰費用和提前完工發生的庫存費用（假設這兩項費用分別是滯后時間和提前時間的線性函數）為

Ji的運輸成本為

式中，tti，j（fm，fk）為Ji從fm到fk之間的運輸時間。

據此，得出Ji的總成本如下：

得出Ji的收益函數如下：

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

本文建立的Stackelberg博弈調度模型中，存在兩個層次上的子博弈，第一層為關鍵任務與非關鍵任務集之間Stackelberg動態子博弈，第二層為非關鍵任務集中各任務之間的非合作靜態子博弈。兩層次子博弈組合構成Stackelberg博弈調度模型框架如圖1所示。

圖1 Stackelberg博弈調度模型框架

從圖1中看出，設所有任務的某一調度方案策略集s＝ （sl，sf），其中，sf＝ （sf1，sf2，…，sf（n－1））。關鍵任務Jl先行決策，與非關鍵任務集Jf進行Stackelberg動態子博弈；非關鍵任務集Jf依據關鍵任務Jl的策略sl進行反應，并在Jf內部各任務之間進行非合作靜態子博弈，形成相應的策略集，并通過如下的反應函數式反饋至Stackelberg動態子博弈并執行下一步子博弈：

當且僅當同時滿足下兩式：

3 基于混合自適應遺傳算法博弈模型解算

為實現上述Stackelberg博弈調度模型的均衡點的有效求解，設計了混合自適應遺傳算法，通過引入爬山搜索方法來提高算法的收斂精度與效率，其中基于爬山搜索方法的混合自適應遺傳算法求解流程參見文獻［10-11］。

3.1 染色體編碼設計

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

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

3.2 適應度函數設計

服務型制造車間關鍵任務Stackelberg博弈調度目標就是尋求保證關鍵任務順利完工的情況下使得每個任務均能達到綜合成本目標值最小的利益均衡調度結果，需要設計新的適應度函數來反映每個任務的競爭性加工需求。據此，設計出了如下的適應度函數：

當同時滿足如下三個不等條件時，我們認為算法達到工程意義上的Stackelberg策略均衡：

其中，ξ、ξl、ξfi為閾值，用來確定求解 Stackelberg動態子博弈均衡解及非合作靜態子博弈Nash均衡解的條件。為求解方便起見，本文令ξl＝ξfi。

3.3 算法的進化操作

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

4 實例仿真與分析

4.1 初始條件與參數

在算例中，設在某時間段服務型制造車間有8個加工任務，每個任務由8道工序構成，其中任務J3為關鍵任務，其余任務為非關鍵任務，同時該車間包含8臺機床。表2～表6分別為任務的工藝信息、交貨期、費率等參數。在表2中，圓括弧里的數字表示某任務的某道工序的可選加工設備，方括弧則為對應的可選加工設備加工該工序所需的加工時間。

表2 制造任務的基本工藝信息

表3 制造任務的交貨期、提前／拖期系數

表4 加工設備工時費率

表5 設備間運輸時間

表6 混合自適應遺傳算法初始輸入參數

4.2 仿真結果與分析

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

圖2 關鍵任務調度結果甘特圖及適應度值曲線

表7 關鍵任務Stackelberg博弈調度均衡點方案集及收益值

由表7看出，采用基于Stackelberg博弈調度模型實現對關鍵任務的調度中，所有參與調度的制造任務均提前完工，這是由于提前完工帶來的庫存成本遠小于拖期懲罰成本所致。從各任務的提前庫存成本與運輸成本兩項累計成本中可以看出，關鍵任務J3的成本最低，遠遠小于其他非關鍵任務的累計成本，而其他非關鍵任務的各累計成本基本相當，這是符合Stackelberg博弈思想的。

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

圖3 非合作博弈任務調度結果甘特圖及適應度值曲線

表8 非合作博弈調度Nash均衡點的各任務方案集及收益值

對比表7與表8中的調度結果可以看出，在基于非合作博弈的調度中，所有任務機會均等，任務J3失去了優先調度權利，超期完工，由于拖期懲罰導致其總成本劇增，其余各任務在非合作博弈調度中優先度較基于Stackelberg博弈的調度中提高，其綜合成本總體上較Stackelberg博弈調度減小。由此可見，在存在關鍵任務而其余任務機會均等的情況下的服務型制造車間任務調度中，非合作博弈調度模型不再適合，而基于Stackelberg博弈的調度模型則能很好地解決此類問題。

5 結束語

本文針對服務型制造車間的關鍵任務調度問題進行了深入研究。針對服務型制造車間關鍵任務的調度新需求，采用Stackelberg博弈理論，建立了一種面向關鍵任務調度的兩層次嵌套的Stackelberg博弈模型，將關鍵任務調度問題轉化為尋求該Stackelberg博弈調度模型的均衡解問題；通過設計一種混合自適應遺傳算法實現了對該Stackelberg博弈模型均衡解的有效解算；通過設計相應的調度實例實現了對建立的模型與算法的仿真分析，并與機會均等條件下的任務調度非合作博弈結果進行了對比分析，結果表明，所提出的Stackelberg博弈調度模型與混合自適應遺傳算法能很好地解決服務型制造車間客戶競爭驅動的關鍵任務調度問題。

［1］汪應洛.推進服務型制造：優化我國產業結構調整的戰略思考［J］.西安交通大學學報，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］.中國機械工程，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］胡雅麗，楊建軍.基于約束規則的作業車間調度研究［J］.航空精密技術，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］張鐵男，韓兵，于渤.生產能力約束條件下的柔性作業車間調度優化［J］.系統工程理論與實踐，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］席裕庚，王長軍.控制、規劃和調度問題中的博弈論應用［J］.中國計量學院學報，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 業務的Stackelberg博弈策略與算法［J］.計算機工程與應用，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］周光輝，王蕊，江平宇，等.作業車間任務調度的非合作博弈模型與混合自適應遺傳算法［J］.西安交通大學學報，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.