劉 茜，鄭瀾波

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

1 引言

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

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

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

2 問題概述

2.1 動態(tài)網(wǎng)絡結構及最大流

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

圖1 煤炭供應網(wǎng)絡

2.2 設施設備維護調(diào)度

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

3 模型構建及求解

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

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

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

設置變量：φ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ù)學模型

目標函數(shù)：

約束條件：

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

4 BD算法

4.1 BD轉(zhuǎn)化模型

將變量xat與φat分離到兩個問題中，分別構成具有調(diào)度元素的MP與最大流SP。又因為任一時刻網(wǎng)絡最大流僅與該時刻網(wǎng)絡各邊的中斷情況xat有關，因此可以將一段時間內(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，構建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，得新的當前解值、θt及 yjt，；若，轉(zhuǎn)Step5，否則轉(zhuǎn)Step7；

Step5：檢索 xat',t'∈[T]，如果 xat'是Y的鍵，取Y中xat'鍵對應的值(x0,ua|a∈[A]) ，否則，求解SP，將結果置于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ù)實驗對所設計的BD算法的求解效果進行分析評價。計算實驗的標準測試數(shù)據(jù)來源于文獻[7]，包括8個規(guī)模不一的網(wǎng)絡結構、2組可選的維護時間窗口大小不同的數(shù)據(jù)集，每組數(shù)據(jù)集中，對應每一個網(wǎng)絡結構都有10個單獨的實例，那么總共運行的數(shù)據(jù)實例有160個。通過比較BD算法及Gurobi求解器在1 800s內(nèi)給出實例的結果來分析算法的優(yōu)劣。采用Python2.7語言編程，Gurobi6.5建立模型，在Intel Core i7處理器（2.5GHz）、12GB內(nèi)存的計算機上測試。通過分析BD算法上、下界的gap，運行時間以及算例能被求得最優(yōu)的個數(shù)等指標，分析三種方法的特點，實驗結果見表1、表2。

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

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

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

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

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

6 實際案例分析

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

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

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

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

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

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

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

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

7 結論與展望

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

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

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

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

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

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

[6]王紅,杜維鑫,劉志龍,等.聯(lián)合故障與經(jīng)濟相關性的動車組多部件系統(tǒng)維護[J].上海交通大學學報,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.