包 博， 李體方， 張 搏

(空軍工程大學(xué)防空反導(dǎo)學(xué)院， 陜西 西安 710051)

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

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

1 問(wèn)題分析及數(shù)學(xué)模型

1.1 工序并行性

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

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

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

表1 工序并行關(guān)系

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

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

。

(1)

1.2 維修作業(yè)車間調(diào)度數(shù)學(xué)模型

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

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

筆者在柔性作業(yè)車間調(diào)度的基礎(chǔ)上，考慮工序可并行的特點(diǎn)。設(shè)PNi(i=1,2,…,n)為裝備Ni在維修工藝路線中存在先后順序約束的相鄰工序?qū)希粚?duì)于裝備Ni，設(shè)Vik為可與工序Oik并行進(jìn)行的工序集合，當(dāng)Vik=?時(shí)，維修作業(yè)車間調(diào)度問(wèn)題即轉(zhuǎn)變?yōu)閭鹘y(tǒng)的柔性作業(yè)車間調(diào)度問(wèn)題。因此，維修作業(yè)車間調(diào)度問(wèn)題是傳統(tǒng)柔性作業(yè)車間調(diào)度問(wèn)題的拓展。

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

(2)

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

2 遺傳算法設(shè)計(jì)與實(shí)現(xiàn)

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

圖2 基于雙層編碼遺傳算法的車間調(diào)度算法流程

2.1 染色體編碼與解碼

采用雙層編碼結(jié)構(gòu)進(jìn)行染色體編碼時(shí)，第1層表示裝備維修工序的順序，第2層表示裝備的每道工序?qū)?yīng)的維修單元。設(shè)染色體為

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

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

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

2.2 適應(yīng)度函數(shù)

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

(7)

圖3 染色體解碼過(guò)程甘特圖

染色體的適應(yīng)度值越小，說(shuō)明維修任務(wù)完成時(shí)間越短，相應(yīng)的染色體越好。

2.3 遺傳算子

2.3.1 選擇算子

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

(8)

2.3.2 交叉算子

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

2.3.3 變異算子

進(jìn)行變異操作時(shí)，首先在第1層隨機(jī)選擇2個(gè)變異點(diǎn)，然后將第1層維修工序碼和第2層維修單元碼的對(duì)應(yīng)位置上的基因進(jìn)行互換。如對(duì)某染色體選擇在位置2、3上進(jìn)行的交叉變異操作為

3 算例分析

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

表2 工序可選維修單元及維修時(shí)間

表3 裝備N1、N2工序的并行關(guān)系

表4 裝備N3、N4的工序并行關(guān)系

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

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

1) 并行調(diào)度維修方案

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

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

圖4 并行調(diào)度維修方案的甘特圖

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

2) 串行調(diào)度維修方案

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

圖6 串行調(diào)度維修方案的甘特圖

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

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

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

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

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

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

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

圖7 不同并行性水平下調(diào)度維修方案的仿真結(jié)果

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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

[7] 蘇兆鋒,邱洪澤.柔性作業(yè)調(diào)度的串并行模型對(duì)比與求解[J].計(jì)算機(jī)工程與應(yīng)用,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] 徐本柱,費(fèi)曉璐,章興玲.柔性作業(yè)車間批量劃分與并行調(diào)度優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng),2016,22(8):1953-1964.

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

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

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

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

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