包 博， 李體方， 張 搏

(空軍工程大學防空反導學院， 陜西 西安 710051)

在維修設備、人員和材料有限的情況下，合理有效地進行維修作業(yè)車間調度，有利于提升維修車間的維修效率。依據(jù)車間構成的不同，車間調度問題主要分為單機調度[1]、并行機調度[2]、流水車間調度[3]和作業(yè)車間調度[4]等。其中：作業(yè)車間調度在實踐中應用最為廣泛，對其工藝路線柔性以及設備柔性的相關研究較為豐富。楊少華等[5]在柔性作業(yè)車間調度模型的基礎上，構建了軍用飛機維修作業(yè)調度模型。朱昱等[6]針對戰(zhàn)時裝備修理任務調度問題，提出了一種針對串行維修流程，多專業(yè)、多作戰(zhàn)單元的維修調度模型。隨著車間調度技術應用領域的拓展，在調度模式上，出現(xiàn)了工序間并行性增強的新特點，尤其在裝備維修車間調度領域，維修作業(yè)工序并行性特點更為突出。蘇兆鋒等[7]對柔性作業(yè)調度的串并行模型進行了對比與求解。JAMESC等[8]對包含并行機和返工的作業(yè)車間調度問題進行了研究，提出了一種新的調度算法。徐本柱等[9]提出了相同工件的同批工序間、不同工序間可并行的車間調度算法，有效地解決了批量加工車間調度問題。對于裝備維修作業(yè)車間調度問題，在提高調度柔性的同時，考慮工序的并行性也十分重要。

筆者針對工序可并行條件下的裝備維修作業(yè)車間調度問題，在柔性作業(yè)車間調度問題的基礎上，考慮了裝備維修工序的并行性特點，建立以維修任務完成時間最小為目標函數(shù)的數(shù)學模型，設計遺傳算法對調度模型進行求解，并通過算例驗證方法的可行性和有效性。

1 問題分析及數(shù)學模型

1.1 工序并行性

裝備維修調度包括串行調度和并行調度，并嚴格按照設定的維修工藝路線執(zhí)行各項工序。與單個零件生產(chǎn)中的串行流水生產(chǎn)模式不同，裝備維修的流程更加復雜，通常包括分解、部件送修、分裝和總裝4個環(huán)節(jié)，維修工藝路線具有明顯的并行性。維修工藝路線的并行性通常依據(jù)專家經(jīng)驗和計算機輔助工藝規(guī)劃，在維修規(guī)劃階段形成并確定。然而，無論是串行調度還是并行調度，維修工序都必須滿足拓撲排序。對于串行調度，在任意時刻，只允許執(zhí)行至多1項工序；對于并行調度，在任意時刻，沒有優(yōu)先關系的工序可在不同維修單元上同時進行處理。如某型裝備的維修工藝路線共包含5道工序，其中：工序1、2與工序3、4之間不存在先后約束，在調度中可并行進行。其維修工藝路線示意圖如圖1所示。

圖1 某型裝備維修工藝路線示意圖

可采用表格的形式來描述工序間的并行關系，圖1中各工序間并行關系的表格描述如表1所示。由表1可更加清晰地了解到任意2道維修工序間的并行關系。

表1 工序并行關系

為了更好地描述調度中裝備維修工藝路線的并行性水平，筆者提出了工序并行率，其計算公式為

P=并行關系數(shù)/總關系數(shù)， 0≤P≤1

。

(1)

1.2 維修作業(yè)車間調度數(shù)學模型

1) 設Ni(i=1,2,…,n)為第i臺待修裝備，Mj(j=1,2,…,m)為待修裝備的第j個維修單元，Lik為維修第i臺待修裝備的第k(k=1,2,…,l)道維修工序；Tijk為對裝備Ni中第j個維修單元Mj進行維修時所需的維修時間。

2) 當裝備按照一定的維修工序順序進行維修時，每道工序可選擇若干個維修單元進行維修。在滿足實際約束的條件下，需要將各維修單元合理地安排到各道維修工序上，使調度方案達到最優(yōu)化。

筆者在柔性作業(yè)車間調度的基礎上，考慮工序可并行的特點。設PNi(i=1,2,…,n)為裝備Ni在維修工藝路線中存在先后順序約束的相鄰工序對集合；對于裝備Ni，設Vik為可與工序Oik并行進行的工序集合，當Vik=?時，維修作業(yè)車間調度問題即轉變?yōu)閭鹘y(tǒng)的柔性作業(yè)車間調度問題。因此，維修作業(yè)車間調度問題是傳統(tǒng)柔性作業(yè)車間調度問題的拓展。

綜上所述，工序可并行的裝備維修柔性作業(yè)車間調度問題的數(shù)學描述為

(2)

式中：sik、eik分別為工序Oik的開始和結束時刻。式(3)表示裝備的每道維修工序只選擇1個維修單元，其中xijk為0/1變量，當xijk=1時，表示維修時工序Oik選擇了維修單元Mj,當xijk=0時，表示維修時工序Oik未選擇維修單元Mj；式(4)描述了工序本身的時間約束；式(5)描述了裝備非并行工序的開始、結束時間約束，并行工序間不存在時間約束；式(6)描述了裝備維修單元上各道工序的時間約束，其中sju、eju分別表示維修單元Mj上第u道工序的開始和結束時刻。

2 遺傳算法設計與實現(xiàn)

柔性作業(yè)車間調度問題是一類典型的NP(Non-deterministic Polynomial)問題，針對NP問題，學者們提出了許多行之有效的求解算法，如禁忌搜索算法[10]、遺傳算法[11]、蟻群算法[12]、粒子群算法[13]等。其中遺傳算法對解決該類問題具有較好的適用性[14]，因此筆者采用遺傳算法來求解模型。對于維修車間調度問題，需要同時對裝備維修工序順序和工序維修單元2種信息進行描述。因此，采用基于雙層編碼遺傳算法的車間調度算法，其流程如圖2所示。

圖2 基于雙層編碼遺傳算法的車間調度算法流程

2.1 染色體編碼與解碼

采用雙層編碼結構進行染色體編碼時，第1層表示裝備維修工序的順序，第2層表示裝備的每道工序對應的維修單元。設染色體為

[x1,x2,…,xN,y1,y2,…,yN]，

其中：xt(t=1,2,…,N)為裝備序號；yt(t=1,2,…,N)為裝備對應的工序所選擇的維修單元。

依據(jù)工序可選維修單元、工序操作工時和可并行工序數(shù)進行染色體解碼。對于染色體[1,2,1,2,3,3,2,1,3,3,1,2]，設裝備N1、N2的2道工序可并行，裝備N3的2道工序只能串行，不考慮具體的工序維修工時，依據(jù)解碼規(guī)則，染色體解碼過程的甘特圖如圖3所示。

2.2 適應度函數(shù)

依據(jù)目標函數(shù)，以全部維修任務完成時間為染色體的適應度值，即

(7)

圖3 染色體解碼過程甘特圖

染色體的適應度值越小，說明維修任務完成時間越短，相應的染色體越好。

2.3 遺傳算子

2.3.1 選擇算子

選擇操作主要采用輪盤賭的方法，依據(jù)概率選出適應度好的染色體，適應度值越好,被選中的概率越大，概率計算公式為

(8)

2.3.2 交叉算子

交叉操作分為2步：一是對2個染色體在交叉點處進行基因互換；二是對交叉后的染色體進行局部調整，使染色體滿足約束條件。如：對2個染色體進行交叉處理，假設交叉位置為3，首先對交叉點處進行基因互換；但交叉后，發(fā)現(xiàn)裝備工序有增加或減少的情況，對此，將裝備工序多余的操作變?yōu)槿笔У牟僮鳎旧w后半部分不變，從而避免了非法染色體的產(chǎn)生，即

2.3.3 變異算子

進行變異操作時，首先在第1層隨機選擇2個變異點，然后將第1層維修工序碼和第2層維修單元碼的對應位置上的基因進行互換。如對某染色體選擇在位置2、3上進行的交叉變異操作為

3 算例分析

設某裝備修理廠需要完成4套裝備大修任務，每套裝備的維修任務均包含5道維修工序，由4組維修單元執(zhí)行維修任務。各裝備維修工序的可選維修單元以及對應的維修時間如表2所示。裝備N1、N2的維修工藝路線相同，其工序的并行關系如表3所示，裝備N3、N4的維修工藝路線相同，其工序的并行關系如表4所示。

表2 工序可選維修單元及維修時間

表3 裝備N1、N2工序的并行關系

表4 裝備N3、N4的工序并行關系

3.1 參數(shù)設置及方案生成

設種群數(shù)為40，遺傳代數(shù)為50，交叉率為0.8，變異率為0.6，采用MATLAB求解模型。

1) 并行調度維修方案

圖4為并行調度維修方案的甘特圖，圖中“i0k”表示裝備Ni的第k道工序。求解過程的尋優(yōu)收斂曲線如圖5所示。

由圖4可以看出計劃維修方案中裝備對應的維修單元以及工序的開始、結束時間，由此預期其任務完成時間為39天。在維修調度方案中，部分維修工序存在并行處理的情況，如工序O11-O12，O33-O34，工序并行處理縮短了總維修任務完成時間，提高了維修效率。

圖4 并行調度維修方案的甘特圖

圖5 遺傳算法尋優(yōu)收斂曲線

2) 串行調度維修方案

對染色體進行串行規(guī)則解碼，即設定裝備的維修工藝路線中不存在并行工序，則上述并行調度維修方案所對應的串行調度維修方案的甘特圖如圖6所示。

圖6 串行調度維修方案的甘特圖

對比分析串、并行調度維修方案的仿真結果，可以看出：并行調度維修方案中各工序之間的銜接更加緊密，部分工序的完成時間提前;同時，并行調度維修方案的維修完工時間相對較短，表明并行調度的維修效率更高。

3.2 參數(shù)并行率分析

參數(shù)并行率描述了裝備維修工藝路線中工序的并行性水平。筆者在工序數(shù)量、工序時長等參數(shù)不變的條件下，設置低、中、高3組不同并行性水平(并行率)的維修工藝路線，比較分析工藝路線的并行率對維修效率的影響。3組并行性水平設置如下：

1) 低并行率調度，各裝備維修工藝路線的全部工序只可進行串行操作，即各裝備的并行率均為0。

2) 中并行率調度，裝備維修工藝路線設置如表3、4所示，其中：裝備N1、N2的維修工藝路線的并行率為0.6;裝備N3、N4的維修工藝路線的并行率為0.3。

3)高并行率調度，裝備維修工藝路線的全部工序均可進行并行操作，即各裝備的并行率均為1。

對3組維修工藝路線參數(shù)進行仿真實驗，每組尋優(yōu)計算重復10次，結果如圖7所示。

圖7 不同并行性水平下調度維修方案的仿真結果

由圖7可以看出：調度中維修工序的并行性水平越高，裝備維修的效率越高，其中，完全并行調度(高并行率)較串行調度(低并行率)的平均任務完工時間縮短了26.4%。這是因為，當維修工藝路線中的并行性水平越高時，維修工序之間的時間約束就越少，可同時開展的工序就越多，因而減少了調度中維修單元的閑置等待時間，縮短了裝備維修任務完成時間，提高了裝備維修效率。

4 結論

針對裝備維修調度問題，筆者建立了工序并行條件下的維修作業(yè)車間調度模型，研究了維修調度中工序并行性對維修效率的影響，并通過算例進行了驗證，結果表明：模型符合裝備維修調度實際，可在一定程度上提高維修效率。在維修實踐中，工藝路線的并行性在工業(yè)路線規(guī)劃階段就已確定，因此，在設計維修工藝路線時，應盡量提高工序的并行性。在后續(xù)的研究中，將進一步挖掘柔性對并行性的影響，并對大批量、復雜工藝路線條件下的維修工序可并行維修作業(yè)車間調度問題進行研究。

參考文獻：

[1] YANG S J,YANG D L,Minimizing the total completion time in single-machine scheduling with aging/deteriorating effects and deteriorating maintenance activities[J]. Computers and mathematics with applications,2012,60(1):2161-2169.

[2] 許曉晴,崔文田,林軍,等.不確定加工時間下同型并行機的魯棒排程[J].系統(tǒng)工程,2012,30(2):100-104.

[3] 孫志剛,朱小冬,李鋒.一種考慮權重的多專業(yè)流水式批量維修任務調度模型[J].裝甲兵工程學院學報,2012,26(2):24-28.

[4] 丁雷,王愛民,寧汝新.工時不確定條件下的車間作業(yè)調度技術[J].計算機集成制造系統(tǒng),2010,16(1):96-108.

[5] 楊少華,王瑛,劉剛.多目標軍用飛機維修作業(yè)調度優(yōu)化研究[J].計算機工程與應用,2016,52(14):19-26.

[6] 朱昱,王連鋒,楊雪松.一種基于維修流程的裝備維修任務調度方法[J].兵工自動化,2012,31(12):28-31.

[7] 蘇兆鋒,邱洪澤.柔性作業(yè)調度的串并行模型對比與求解[J].計算機工程與應用,2008,44(9):235-238.

[8] JAMESC C,WU C C ,CHEN C W,et al. Flexible job shop scheduling with parallel machines using genetic algorithm and grouping genetic algorithm[J]. Expert systems with applications,2012,39(1):10016-10021.

[9] 徐本柱,費曉璐,章興玲.柔性作業(yè)車間批量劃分與并行調度優(yōu)化[J].計算機集成制造系統(tǒng),2016,22(8):1953-1964.

[10] 陸漢東,何衛(wèi)平,周旭,等.基于禁忌搜索的柔性作業(yè)車間分批調度[J].上海交通大學學報,2012,46(12):2003-2008.

[11] 李平,唐秋華,夏緒輝,等.基于雙層遺傳編碼的柔性作業(yè)車間自適應重調度研究[J].中國機械工程,2013,24(16):2195-2201.

[12] 張潔,張朋,劉國寶.基于兩階段蟻群算法的帶非等效并行機的作業(yè)車間調度[J].機械工程學報,2013,49(6):136-144.

[13] 張靜,王萬良,徐新黎.基于改進粒子群算法求解柔性作業(yè)車間批量調度問題[J].控制與決策,2012,27(4):513-518.

[14] 于春風,郭昊,王磊,等.面向任務的裝甲裝備基本維修單元配置優(yōu)化[J].裝甲兵工程學院學報,2016,30(1):26-28.