劉 茜，鄭瀾波

（武漢理工大學(xué) 物流工程學(xué)院，湖北 武漢 430063）

1 引言

我國是世界上最大的煤炭生產(chǎn)與消費國，由于煤炭生產(chǎn)與消費地理的不平衡，煤炭行業(yè)形成了煤炭生產(chǎn)、輸送、消費的供應(yīng)鏈，煤炭供應(yīng)鏈的可持續(xù)發(fā)展對國民經(jīng)濟具有重大影響，而煤炭行業(yè)的均衡、穩(wěn)健發(fā)展依賴于設(shè)備的安全、可靠運轉(zhuǎn)。隨著設(shè)備向大型化、專業(yè)化及自動化方向發(fā)展，設(shè)備的維護(hù)管理問題日益突出。當(dāng)前煤炭行業(yè)內(nèi)的企業(yè)各自獨立的由經(jīng)驗豐富的維修工人根據(jù)生產(chǎn)計劃制定維護(hù)計劃，這種分散的維護(hù)計劃使得供應(yīng)鏈上各企業(yè)的生產(chǎn)運作不均衡，造成了供應(yīng)鏈整體效率較大的損失。

工業(yè)領(lǐng)域和學(xué)術(shù)界針對設(shè)備維護(hù)管理展開了研究。國內(nèi)對煤炭行業(yè)設(shè)備維護(hù)的研究主要集中在：（1）設(shè)備管理制度和管理信息系統(tǒng)的探討；（2）狀態(tài)監(jiān)測和故障診斷技術(shù)[1]。陳文靜[2]、劉藝杰[3]介紹了維修管理理論，自修、外包等維修組織形式，指出現(xiàn)有設(shè)備維修體制存在的缺陷、維修決策水平不足、設(shè)備維護(hù)信息系統(tǒng)不完善等問題，并提出基于可靠性理論的設(shè)備預(yù)防性維護(hù)策略。范體軍[4]提出設(shè)備維護(hù)外包的三種外包策略，并分析了不同策略對設(shè)備維護(hù)計劃組織的影響。設(shè)備維護(hù)計劃的決策研究已有部分成果。崔維偉[5]考慮生產(chǎn)與設(shè)備維護(hù)的集成調(diào)度問題，認(rèn)為工件生產(chǎn)與設(shè)備維護(hù)相互關(guān)聯(lián)、共同影響車間的生產(chǎn)效率，構(gòu)建了以工件流程時間最短、維修成本最小的多目標(biāo)模型，并設(shè)計出一種改進(jìn)的遺傳算法進(jìn)行求解，實現(xiàn)了車間生產(chǎn)調(diào)度與設(shè)備維護(hù)計劃的有效協(xié)調(diào)。然而上述研究沒有考慮維修設(shè)備的關(guān)聯(lián)性，對此，王紅等人[6]提出故障鏈的概念對維修部件間的關(guān)系進(jìn)行描述，建立了具有故障相關(guān)關(guān)系的復(fù)雜機械系統(tǒng)中各部件的可靠度模型。當(dāng)前國內(nèi)對煤炭行業(yè)的設(shè)備維護(hù)管理的研究還停留在維護(hù)管理模式及組織形式的探討上，少數(shù)關(guān)于維護(hù)計劃的決策研究對象或者局限于系統(tǒng)的一部分，或者沒有考慮預(yù)防性維護(hù)的動態(tài)性，沒有成果刻畫制定的設(shè)備維護(hù)計劃對持續(xù)生產(chǎn)的影響，更沒有研究煤炭供應(yīng)鏈上多個企業(yè)從宏觀層面結(jié)成維護(hù)的戰(zhàn)略聯(lián)盟，協(xié)同制定預(yù)防性維護(hù)計劃以降低維護(hù)中斷對持續(xù)生產(chǎn)系統(tǒng)造成的影響的成果。本文從設(shè)備維護(hù)計劃對降低煤炭供應(yīng)鏈吞吐量影響的角度展開研究，揭示其中規(guī)律，為系統(tǒng)設(shè)備維護(hù)規(guī)劃與管理提供科學(xué)決策。

獵人谷煤炭供應(yīng)鏈協(xié)調(diào)機構(gòu)數(shù)據(jù)顯示，設(shè)備年度停機維護(hù)造成的系統(tǒng)中斷會導(dǎo)致年吞吐量約15%的損失。獵人谷煤炭供應(yīng)鏈協(xié)調(diào)機構(gòu)協(xié)調(diào)供應(yīng)鏈中各環(huán)節(jié)設(shè)備的維護(hù)窗口，分配容量，以使得計劃期內(nèi)因維護(hù)造成的吞吐量損失最少。Natashia Boland等人[7]利用“帶邊中斷動態(tài)網(wǎng)絡(luò)最大流（簡稱MaxTFFAO）”模型來研究煤炭供應(yīng)鏈中設(shè)備維護(hù)的計劃，清晰地闡明了帶邊中斷動態(tài)網(wǎng)絡(luò)最大流問題的結(jié)構(gòu)特點。由于該問題的強NP難性，已有的多數(shù)方法均為啟發(fā)式算法。Benders分解算法（以下簡稱BD算法）是一種運用分解思想求解混合變量規(guī)劃問題的巧妙方法[9]，將原問題分解為主問題（Master Problem，簡稱MP）和子問題（Sub-problem，簡稱SP），它適用于MaxTFFAO問題的求解，實驗證明了BD算法的可行性和有效性。

2 問題概述

2.1 動態(tài)網(wǎng)絡(luò)結(jié)構(gòu)及最大流

圖1表示一個煤炭供應(yīng)鏈網(wǎng)絡(luò)G=(V,A,C)，左側(cè)為鐵路網(wǎng)絡(luò)，右側(cè)橢圓內(nèi)為煤碼頭作業(yè)網(wǎng)絡(luò)。左側(cè)圓圈表示裝煤點，方框表示煤炭匯集的鐵路站點。碼頭中的大圓圈表示堆場。A為有向弧集，表示煤炭在設(shè)施設(shè)備間的流動軌跡：煤炭裝載流、鐵路輸送流以及傾貨、堆料、取料、裝船和離泊作業(yè)流。煤炭需求量、鐵路運煤能力、碼頭機械設(shè)備的工作能力分別表示相應(yīng)弧的容量C。煤礦裝煤中斷、鐵路因維護(hù)而中斷、煤碼頭中機械設(shè)備停機維護(hù)都會使得煤炭供應(yīng)網(wǎng)絡(luò)的弧斷開，弧容量降為零，造成該段時間內(nèi)網(wǎng)絡(luò)煤吞吐量減少；而維護(hù)結(jié)束后，弧容量恢復(fù)，即網(wǎng)絡(luò)中弧的容量隨維護(hù)的實施而變動。選擇碼頭一段時期內(nèi)輸出煤炭量這一指標(biāo)來評估供應(yīng)鏈的效率，可見獵人谷煤炭供應(yīng)鏈優(yōu)化問題本質(zhì)上是一個帶邊中斷的動態(tài)網(wǎng)絡(luò)最大流問題。

圖1 煤炭供應(yīng)網(wǎng)絡(luò)

2.2 設(shè)施設(shè)備維護(hù)調(diào)度

煤炭供應(yīng)鏈設(shè)備的預(yù)防性維護(hù)都有一個維護(hù)時間窗，調(diào)度維護(hù)工作的計劃表會對計劃期內(nèi)網(wǎng)絡(luò)總輸出流量產(chǎn)生不同的影響。待維修設(shè)備的故障相關(guān)關(guān)系使得其預(yù)防性維護(hù)計劃必須協(xié)調(diào)起來制定。因此，煤炭供應(yīng)鏈設(shè)備維護(hù)調(diào)度問題可抽象為帶邊中斷動態(tài)網(wǎng)絡(luò)最大流問題，它研究如何調(diào)度容量網(wǎng)絡(luò)邊的中斷時刻，動態(tài)性地分配容量，以最大化計劃期內(nèi)網(wǎng)絡(luò)的總吞吐量。

3 模型構(gòu)建及求解

3.1 參數(shù)及變量定義

定義[m,n]={m,m+1,...,n}，[m]={1,2,...,m}，m,n∈Z+。G=(V,A,s,s',C)表示一個網(wǎng)絡(luò)，其中[V]為節(jié)點集合，[A]為網(wǎng)絡(luò)中弧的集合，s為源點，s'為匯點，[C]為弧容量集合，Ca表示弧a的容量。節(jié)點v∈[V]，δ-(V)和δ+(V)分別表示進(jìn)出節(jié)點v的弧集。設(shè)置網(wǎng)絡(luò)總時間跨度為T。

網(wǎng)絡(luò)G中散布著一系列維護(hù)作業(yè)j∈[J]，其中[J]為作業(yè)集，作業(yè)j∈[J]有一系列屬性：處理時間pj∈[T]，最早開始維護(hù)時間rj∈[T]，最遲維護(hù)截止時間dj∈[T]，作業(yè)一旦開始就不能提前終止，在其處理時間段內(nèi)，與作業(yè)j相關(guān)聯(lián)的弧aj上通過的流量為零。[Ja]是弧a上作業(yè)集合，假設(shè)a上任意兩作業(yè)的時間窗不重合。作業(yè)j∈[J]，維護(hù)開始時間，sj∈[rj,dj-pj+1]其中[rj,dj-pj+1]稱為該作業(yè)的維護(hù)時間窗，當(dāng)j∈[Ja]，t∈[sj,sj-pj+1]時，弧a的容量在t時刻為零，即當(dāng)弧a上有作業(yè)在處理時，弧a斷開，途徑a的流量為零。

設(shè)置變量：φat為時間t內(nèi)流經(jīng)a的流量；xat∈{0,1}表示a是否在時間t內(nèi)中斷，中斷為0，否則為1；yjt∈{0,1},j∈[J]表示作業(yè)j是否開始于時間t，是則為1，否則為0。

3.2 建立數(shù)學(xué)模型

目標(biāo)函數(shù)：

約束條件：

目標(biāo)（1）最大化時間跨度內(nèi)總流量。約束條件（2）和（3）是流量守恒和容量限制約束，（4）要求每一項設(shè)備維護(hù)作業(yè)j在其時間窗內(nèi)恰好被完成一次，（5）確保當(dāng)維護(hù)作業(yè)j正在處理中時，路徑弧a容量為零，（6）是非負(fù)約束和0-1約束。

4 BD算法

4.1 BD轉(zhuǎn)化模型

將變量xat與φat分離到兩個問題中，分別構(gòu)成具有調(diào)度元素的MP與最大流SP。又因為任一時刻網(wǎng)絡(luò)最大流僅與該時刻網(wǎng)絡(luò)各邊的中斷情況xat有關(guān)，因此可以將一段時間內(nèi)的動態(tài)最大流分解為該時間段內(nèi)每一時刻靜態(tài)最大流的和，分解后的這類單位時刻靜態(tài)最大流問題，可以利用線性規(guī)劃求解器快速求解，這種分解的BD算法能有效提高模型求解效率。

給定xat,t∈[T]的一個可行解為xat，則對?t∈[T]，SP的模型為：

S.t.

式（11）是加入到MP模型中的割平面。因此以單位時間t劃分后的MP模型如下：

S.t.

4.2 求解步驟

BD算法的求解步驟如下：

Step1：初始化。G=(V,A,s,s',C)，總時間跨度T，=+∞,=-∞,ε =0.09% ；

Step2：創(chuàng)建空Python字典Y，構(gòu)建SP和MP的模型；

Step3：初始化 xat=1,?a∈[A],?t∈[T]，求解SP得到最優(yōu)解x0、容量約束的對偶變量(ua|a∈[A])，將 xat作為字典Y的鍵，值為(x0,ua|a∈[A])，在MP中增加約束 θt≤x0,?t∈[T]；

Step4：求解 MP，得新的當(dāng)前解值、θt及 yjt，；若，轉(zhuǎn)Step5，否則轉(zhuǎn)Step7；

Step5：檢索 xat',t'∈[T]，如果 xat'是Y的鍵，取Y中xat'鍵對應(yīng)的值(x0,ua|a∈[A]) ，否則，求解SP，將結(jié)果置于Y中；

Step6：如果 θt'≥x0,?t'∈[T]，在MP中增加約束θt'≤∑a∈[A]Caxat'uat'(?t'∈[T]) ；否 則 t'←t'+1 ；若t'=T ，則，轉(zhuǎn)Step4，否則，轉(zhuǎn)Step5；

Step7：算法終止，輸出最優(yōu)解。

5 算例分析

通過數(shù)據(jù)實驗對所設(shè)計的BD算法的求解效果進(jìn)行分析評價。計算實驗的標(biāo)準(zhǔn)測試數(shù)據(jù)來源于文獻(xiàn)[7]，包括8個規(guī)模不一的網(wǎng)絡(luò)結(jié)構(gòu)、2組可選的維護(hù)時間窗口大小不同的數(shù)據(jù)集，每組數(shù)據(jù)集中，對應(yīng)每一個網(wǎng)絡(luò)結(jié)構(gòu)都有10個單獨的實例，那么總共運行的數(shù)據(jù)實例有160個。通過比較BD算法及Gurobi求解器在1 800s內(nèi)給出實例的結(jié)果來分析算法的優(yōu)劣。采用Python2.7語言編程，Gurobi6.5建立模型，在Intel Core i7處理器（2.5GHz）、12GB內(nèi)存的計算機上測試。通過分析BD算法上、下界的gap，運行時間以及算例能被求得最優(yōu)的個數(shù)等指標(biāo)，分析三種方法的特點，實驗結(jié)果見表1、表2。

表1 數(shù)據(jù)集1運行1 800s的結(jié)果數(shù)據(jù)

表2 數(shù)據(jù)集2運行1 800s的結(jié)果數(shù)據(jù)

觀察以上兩組實驗結(jié)果數(shù)據(jù)，得到如下結(jié)論：

（1）通過比較兩種算法能求解出實例的平均個數(shù)，可知分解算法的求解效率顯著高于Gurobi求解器的效率，尤其是在數(shù)據(jù)集合1中，BD算法得到的最優(yōu)解的個數(shù)在多數(shù)網(wǎng)絡(luò)中更加突出。

（2）在平均gap方面，BD算法與Gurobi求解的結(jié)果相差不大，但是在數(shù)據(jù)集合1中，BD算法表現(xiàn)更好，時間上，在大多數(shù)算例中，BD算法消耗的時間成本也較Gurobi更好。結(jié)果表明使用Benders分解，將原始模型分割成主問題和子問題的求解技術(shù)性能更好。

6 實際案例分析

當(dāng)前，國內(nèi)煤炭行業(yè)水平方向企業(yè)之間的競爭仍然是投資、資源體量之間的競爭。煤礦資源被進(jìn)一步開發(fā)，鐵路、煤碼頭吞吐量的設(shè)計呈井噴增長趨勢，這些粗放的資源開發(fā)與利用行為造成了嚴(yán)重的產(chǎn)能過剩和資源浪費，煤炭行業(yè)急需精細(xì)的資源管理來提高效率，降低浪費。

一般的，設(shè)備維護(hù)資源主要是維護(hù)工人、維護(hù)器具等，維護(hù)資源過少會引起維修不及時，而維護(hù)資源過多，又增加企業(yè)的成本。上文的MaxTFFAO模型假設(shè)，任意時刻都有足夠的維護(hù)資源對設(shè)備進(jìn)行維護(hù)，即同一時刻處于維護(hù)狀態(tài)的設(shè)備數(shù)量不受資源限制，這就需要企業(yè)具備足夠的維護(hù)資源。當(dāng)資源閑置時，產(chǎn)生浪費。假設(shè)G中每條邊上散布著數(shù)量不等的待維護(hù)作業(yè)，且每條邊上待維護(hù)作業(yè)的時間窗不重疊，考慮帶資源約束的煤炭供應(yīng)鏈設(shè)備維護(hù)計劃決策，在MaxTFFAO模型中添加資源約束（17）。

|A|表示G中弧的總數(shù)，K是維護(hù)資源總數(shù)。

煤炭供應(yīng)鏈上各環(huán)節(jié)的設(shè)備維護(hù)資源類型不同，各環(huán)節(jié)的維護(hù)資源僅僅維護(hù)自身環(huán)節(jié)的設(shè)備，如鐵軌維修工人檢修列車軌道，不會維修碼頭的堆料機，因此煤炭供應(yīng)鏈上各環(huán)節(jié)維護(hù)資源的數(shù)量需要分開進(jìn)行決策?？紤]多資源約束，對MaxTFFAO模型進(jìn)行修正：

其中|Ai|表示G中第i環(huán)節(jié)邊的數(shù)量，Ki為第i環(huán)節(jié)的維護(hù)資源數(shù)量，i=[q]則表示G中的某一個環(huán)節(jié)，整個供應(yīng)鏈分為q個環(huán)節(jié)。上述兩個模型分別對應(yīng)于單資源約束與多資源約束的情形。在資源不受限情形下，由MaxTFFAO模型計算網(wǎng)絡(luò)最大流及最大資源需求量K。隨后，在修正后的模型中，逐漸減少K值，網(wǎng)絡(luò)最大流保持不變，直到K=K1時，網(wǎng)絡(luò)最大流開始減少；當(dāng)K繼續(xù)減少到某一臨界值時，修正模型無可行解，此時可推算出最小資源數(shù)K2。修正后的模型可找到保持最大流不變情形下的最少資源需求量K1、設(shè)備維護(hù)作業(yè)能及時被處理的最少資源需求量K2以及煤炭供應(yīng)鏈設(shè)備維護(hù)計劃表。同理，可求出帶約束（18）模型的最少資源需求量組合及設(shè)備維護(hù)計劃表。

表3 單資源約束下數(shù)據(jù)集1網(wǎng)絡(luò)1的資源與最大流

表4 多資源約束下數(shù)據(jù)集1網(wǎng)絡(luò)1的資源組合與最大流

表3、4給出了文獻(xiàn)[7]中數(shù)據(jù)集合1對應(yīng)于10組不同維護(hù)作業(yè)下的網(wǎng)絡(luò)1在資源受限情形下的網(wǎng)絡(luò)最大流，可見對于每組維護(hù)作業(yè)，網(wǎng)絡(luò)1都有一個最小的維護(hù)資源量，使得計劃期內(nèi)的網(wǎng)絡(luò)最大流達(dá)到最大，同時也有最小的維護(hù)資源量數(shù)使得維護(hù)作業(yè)能及時得到處理。

7 結(jié)論與展望

本文針對煤炭供應(yīng)鏈中設(shè)備維護(hù)計劃問題，研究了帶邊中斷動態(tài)網(wǎng)絡(luò)最大流模型及其算法，取得了以下成果：（1）從供應(yīng)鏈管理的角度，對設(shè)備維護(hù)管理展開研究，建模并設(shè)計算法求解，對實際煤炭供應(yīng)鏈中設(shè)備維護(hù)作業(yè)計劃的調(diào)度問題有一定的指導(dǎo)意義；（2）詳述了BD算法，設(shè)計了該算法解決該問題及模型的具體步驟；（3）實驗結(jié)果表明BD算法是有效的，且在處理大規(guī)模網(wǎng)絡(luò)難題時，能比精確算法更有效提高解的質(zhì)量。此問題之后的研究方向：（1）考慮具有不確定性因素的“帶邊中斷動態(tài)網(wǎng)絡(luò)最大流”問題，如考慮弧容量隨不確定因素改變，利用BD算法設(shè)計具有穩(wěn)健性的作業(yè)中斷調(diào)度表；（2）本文BD算法中，未談?wù)搶嶒炛袇?shù)設(shè)置的規(guī)則，可進(jìn)一步改進(jìn)。

[1]宋之杰,陳文靜,侯貴賓,等.港口設(shè)備維修優(yōu)化模型及實例研究[J].物流技術(shù),2013,32(9):172-175.

[2]陳文靜.基于時間延遲模型的港口設(shè)備維修管理研究[D].秦皇島:燕山大學(xué),2012.

[3]劉藝杰.基于可靠性理論的退化設(shè)備預(yù)防維修策略研究[D].秦皇島:燕山大學(xué),2013.

[4]范體軍,許淑君,李宏余,等.設(shè)備維護(hù)外包策略及其對維護(hù)計劃組織的影響[J].工業(yè)工程與管理,2006,11(3):15-18.

[5]崔維偉,陸志強,潘爾順.基于多目標(biāo)優(yōu)化的生產(chǎn)調(diào)度與設(shè)備維護(hù)集成研究[J].計算機集成制造系統(tǒng),2014,20(6):1 398-1 404.

[6]王紅,杜維鑫,劉志龍,等.聯(lián)合故障與經(jīng)濟相關(guān)性的動車組多部件系統(tǒng)維護(hù)[J].上海交通大學(xué)學(xué)報,2016,50(5):660-667.

[7]Boland N,Kalinowski T,Waterer H,et al.Scheduling arc maintenance jobs in a network to maximize total flow over time[J].Discrete Applied Mathematics,2014,163(1):34-52.

[8]Boland N,Kalinowski T,Kapoor R,et al.Scheduling unit processing time arc shutdown jobs to maximize network flow over time:complexity results[J].Computer Science,2013,63(2):196-202.

[9]J F Benders.Partitioning procedures for solving mixed-variables programming problems[J].Computational Management Science,2005,2(1):3-19.

[10]Fischetti Lodi.Local branching[J].Mathematical Programming,2003,98(1):23-47.