方彥軍，唐 猛

（武漢大學(xué) 自動化系，武漢 430072）

隨著“集中檢驗(yàn)、統(tǒng)一配送”的電能計(jì)量裝置管理模式的推廣，近年來，多個(gè)省級電力公司都相繼建立了各自的省級計(jì)量檢定中心。同時(shí)，電力需求側(cè)管理現(xiàn)代化發(fā)展水平的不斷提高，也對電能計(jì)量裝置的管理、檢定的效率提出了更高要求。電能計(jì)量設(shè)備自動檢定流水線是一種現(xiàn)代化電能表檢定裝置，能夠?qū)崿F(xiàn)電能表檢定過程的全程自動化。因此，如何提高自動檢定流水線的檢定效率，已成為目前各省級計(jì)量檢定中心亟待解決的難題。

為提高檢定效率，需將不同批次、相同電壓等級的計(jì)量裝置放在一條流水線上進(jìn)行檢定，這就對檢定流水線的調(diào)度提出了更高要求。對于該類混合流水線調(diào)度問題HFSP（hybrid flow-shop scheduling problem），文獻(xiàn)[1-6]均進(jìn)行了深入研究。本文針對其特點(diǎn)，設(shè)計(jì)了一種包含檢定排序和設(shè)備選擇信息的編碼和解碼方法，將遺傳算法得到的精英解作為禁忌算法的初始解，并運(yùn)用“高”鄰域候選集策略，來提高遺傳禁忌混合算法的尋優(yōu)能力。

1 自動檢定流水線調(diào)度問題數(shù)學(xué)模型

1.1 問題描述

為了提高智能計(jì)量設(shè)備自動檢定流水線的效率，生產(chǎn)調(diào)度中心會依據(jù)用戶需求、智能立庫存儲量及檢定周期等因素，將不同批次的同類型計(jì)量器具（單相電能表）或相同電壓等級的不同類型器具（單相電能表和終端）放在一條流水線上進(jìn)行檢定。同時(shí)，在至少一個(gè)檢定環(huán)節(jié)（如：多功能檢定環(huán)節(jié)）中存在多條獨(dú)立的并行檢定單元，且每個(gè)檢定單元含有多個(gè)檢定工位，可實(shí)現(xiàn)多批次、多計(jì)量設(shè)備的同時(shí)檢測。因此需要將待檢器具進(jìn)行分批組處理，每個(gè)批組的大小也可不同。

根據(jù)上述分析，本文將此類自動檢定流水線定義為帶批組的并行混合流水線[17-19]。帶批組并行混合流水線調(diào)度問題可描述為：n個(gè)計(jì)量器具分為B個(gè)批組在流水線上進(jìn)行S個(gè)環(huán)節(jié)的檢測，各環(huán)節(jié)至少有一臺檢定設(shè)備且至少有一個(gè)環(huán)節(jié)存在并行的檢定設(shè)備，同一環(huán)節(jié)中各檢定設(shè)備檢測同一計(jì)量器具的檢測時(shí)間均相同[11]，每個(gè)批組在同一環(huán)節(jié)的檢測時(shí)間不完全相同，在每一環(huán)節(jié)各待檢器具均要完成一道工序，但各待檢器具的每道工序可在相應(yīng)環(huán)節(jié)中的任意并行檢定設(shè)備上檢定，已知待檢器具各道工序的檢定時(shí)間，要求確定所有待檢批組的排序以及每一環(huán)節(jié)中并行檢定設(shè)備的任務(wù)分配情況，從而使得總檢定完成時(shí)間最小，即最小化最大檢定時(shí)間，圖1為自動檢定流水線流程圖。

1.2 數(shù)學(xué)模型

令 Ji為待檢器具的編號，i={1，2，……，n}，其中n為待檢器具總數(shù)；bL為第L批組中的待檢器具數(shù)量，L={1，2，……，B}，其中 B 為待檢器具的批組總表示批組 L 中的第 f個(gè)待檢器具，f={1，2，……，bL}，aL，f與 Ji是一一對應(yīng)的；md為檢定環(huán)節(jié) d 中的并行設(shè)備數(shù)，d={1，2，……，S}，其中 S 為環(huán)節(jié)總數(shù)；td，L為批組 L 在環(huán)節(jié) d 的檢測時(shí)間；Sd，L為批組L在環(huán)節(jié)d的檢測開始時(shí)間；ed，L為批組L在環(huán)節(jié)d的檢測結(jié)束時(shí)間；CL為批組L的檢定完成時(shí)間；Cmax=max{C1，C2，……，CB}為所有批組檢定完成的最大時(shí)間；則具體的數(shù)學(xué)模型為

其中：式（1）為調(diào)度優(yōu)化指標(biāo)；式（2）表示每個(gè)優(yōu)先級位置只能對應(yīng)一個(gè)批組；式（3）表示每個(gè)批組只能占有一個(gè)優(yōu)先級位置；式（4）表示每個(gè)環(huán)節(jié)每個(gè)批組只能在一臺檢定設(shè)備上進(jìn)行檢測；式（5）表示同一環(huán)節(jié)檢測開始時(shí)間與完成時(shí)間的關(guān)系；式（6）表示同一批組在不同環(huán)節(jié)間的先后約束關(guān)系；式（9）表示同一環(huán)節(jié)排位越前的批組開始檢測的時(shí)間越早；式（10）表示同一環(huán)節(jié)分配在同一設(shè)備上的不同批組，優(yōu)先級靠前的批組檢測完后才允許后面的批組進(jìn)行檢測。

2 基于GATS算法的自動檢定流水線調(diào)度

2.1 遺傳禁忌混合算法

遺傳算法是通過將具體問題的求解抽象成生物“染色體”種群的一代代進(jìn)化，包括選擇、交叉和變異等操作，最終找到“最適應(yīng)環(huán)境”的最優(yōu)個(gè)體，從而完成對問題最優(yōu)解的自適應(yīng)搜索。該算法的大范圍搜索能力較強(qiáng)，但局部搜索能力較差[13]。

禁忌搜索TS（tabu search）算法具有靈活的記憶功能，在搜索過程中可以接受劣解，從而跳出局部最優(yōu)解，具有很強(qiáng)的局部搜索能力，但該算法對于初始解的依賴性較強(qiáng)[14]。將遺傳算法與具有記憶功能和較強(qiáng)“爬山”能力的禁忌算法混合使用，一方面能夠提高禁忌算法搜索效率，同時(shí)又能克服GA爬坡能力弱的缺點(diǎn)[7]。為了結(jié)合兩種算法的各自優(yōu)勢，本文采用一種改進(jìn)的遺傳禁忌算法，并運(yùn)用多精英策略[8-9]，即選取適應(yīng)度排位靠前的精英解與非精英解進(jìn)行交叉操作。對遺傳操作得到的解集進(jìn)行重新排位，選取適應(yīng)度排位靠前的精英解作為禁忌操作的初始解，并利用禁忌搜索中得到的最優(yōu)解對初始解進(jìn)行替代更新，直至滿足一定條件跳出算法得到最優(yōu)解。算法流程如圖2所示。

圖2 改進(jìn)的遺傳-禁忌混合算法流程Fig.2 Procedure of improved GATS algorithm

2.2 編碼與解碼

待檢器具的批組總數(shù)為B，則令染色體長度為B，編碼矩陣 AS*B構(gòu)成一個(gè)染色體，見式（11），表示一共B個(gè)批組需要經(jīng)過S個(gè)檢定階段，至少一個(gè)階段存在md臺并行檢定設(shè)備，每個(gè)染色體與解集是一一對應(yīng)的。 其中矩陣中的元素 ad，L為區(qū)間（1，1+md）的一個(gè)隨機(jī)實(shí)數(shù)，表示批組L的第d個(gè)檢定階段在第 Int（ad，L）臺并行設(shè)備上進(jìn)行檢定，染色體中包含了各個(gè)批組在不同檢定階段的檢定順序及設(shè)備選擇信息。例如，個(gè)體［a1，1，a1，2，a1，3……］=［1.1，1.3，1.2……］，1.3表示批組2的第一個(gè)階段在設(shè)備1上進(jìn)行檢定，小數(shù)位“3”表示在同一階段選擇同一設(shè)備的批組檢定順序，所有待檢批組的序號在個(gè)體中的位置表示各批組的檢定排序，因此基因在染色體中的相對位置直接反映出各批組的檢定順序。根據(jù)1.2節(jié)所述的約束條件確定同時(shí)包含各批組檢定排序和各階段并行檢定設(shè)備的任務(wù)分配策略即稱為解碼。

對于確定待檢批組的檢定排序，即為確定不同批組在相同階段的檢定開始時(shí)間排序。本文采用以下策略：按照先到先服務(wù)FCFS（first come first service）的方式確定檢定排序，即前階段先完成的批組先進(jìn)行下一階段的檢定。若多個(gè)批組在該階段并行設(shè)備上的檢定完成時(shí)間相同，則仍然按照前一階段的排序進(jìn)行后續(xù)階段的檢定。對于并行檢定設(shè)備的分配問題，采用最先閑置機(jī)器原則[4]：

1）根據(jù)各批組在前一階段的檢定順序，依次計(jì)算每個(gè)批組在下一階段第k臺并行檢定設(shè)備上的最早允許檢定時(shí)間 Pd，L，k=max（Cd-1，L；rk），其中 rk為并行設(shè)備k的最先空閑時(shí)間。

2）計(jì)算下一階段各并行設(shè)備的優(yōu)先系數(shù)aL，k=max（Cd-1，L；rk）+td，L，選擇優(yōu)先系數(shù)值最小的設(shè)備作為其在該階段的檢定設(shè)備，并更新批組L在階段d的檢定完成時(shí)間Cd，L和設(shè)備k的最先空閑時(shí)間rk。

2.3 種群初始化

為了使初始解保持一定的分散性，本文采用隨機(jī)方法產(chǎn)生初始化解 Si，i=1，2，…Psize。

2.4 適應(yīng)度函數(shù)與選擇

本文的優(yōu)化目標(biāo)為所有待檢批組的最大完成時(shí)間，為了避免算法出現(xiàn)早熟和隨機(jī)漫游現(xiàn)象，采用乘冪變換對目標(biāo)函數(shù)進(jìn)行適度縮小，則適應(yīng)度函數(shù)為

式中，Cmax（Q）為第Q個(gè)染色體所代表的一個(gè)調(diào)度方案的最大檢定周期。選取每代中適應(yīng)度值排位在前ω的精英解采用最佳個(gè)體保存法，即直接復(fù)制到下一代，對其余解按照輪盤賭法進(jìn)行選擇。

2.5 交叉和變異

將適應(yīng)度值排在前列的精英解與非精英解進(jìn)行隨機(jī)的自適應(yīng)單點(diǎn)交叉操作[9]，并驗(yàn)證交叉后得到的解是否滿足所有約束條件。具體算法如下：

1）選取一個(gè)隨機(jī)概率大于預(yù)設(shè)交叉概率的非精英解與一隨機(jī)精英解進(jìn)行交叉操作，并對交叉后的解進(jìn)行有效性驗(yàn)證，包括驗(yàn)證其是否滿足上述所有約束條件；

2）將交叉后的子代與非精英父代的適應(yīng)度值進(jìn)行對比，若子代的適應(yīng)度值優(yōu)于父代，則子代個(gè)體自動取代非精英父代個(gè)體進(jìn)入下一代種群；否則仍然保留父代個(gè)體。

本文采用一種混合變異算子[10]，若當(dāng)前種群的目標(biāo)函數(shù)最大值與最小值之差小于某一正數(shù)時(shí)，采用高斯變異，否則采用邊界變異。因此，在進(jìn)化初期采用邊界變異，即首先選取不同類型的批組所在的基因位作為變異點(diǎn)，然后用兩者對應(yīng)的邊界基因之一替代原有基因值；后期主要進(jìn)行高斯變異來提升算法對重點(diǎn)區(qū)域的搜索能力。

2.6 禁忌搜索

2.6.1 鄰域結(jié)構(gòu)及候選集

本文首先采用交換鄰域結(jié)構(gòu)：任意選擇同一檢定設(shè)備上的兩個(gè)批組，交換其檢定順序。其次，采用“高”候選集策略產(chǎn)生候選集[15]，即：將總檢定完成時(shí)間最大的并行機(jī)上任意批組插入到總檢定時(shí)間最小的并行機(jī)上任一批組前。

2.6.2 禁忌表的設(shè)計(jì)

禁忌表采用先進(jìn)先出的隊(duì)列來實(shí)現(xiàn)。在禁忌搜索過程中，會出現(xiàn)當(dāng)前解的領(lǐng)域全部被禁忌，或是某一解被禁忌后當(dāng)前最優(yōu)值將下降的情況，為了避免搜索算法丟失優(yōu)化狀態(tài)實(shí)現(xiàn)全局最優(yōu)，本文基于特赦規(guī)則：根據(jù)解的適應(yīng)度值，若出現(xiàn)某個(gè)候選解的適應(yīng)度值優(yōu)于當(dāng)前最優(yōu)解時(shí)，雖然從當(dāng)前最優(yōu)解到該解的變化被禁忌，但可以解禁該候選解作為當(dāng)前最優(yōu)解[12]。

2.6.3 關(guān)于精英解的禁忌算法

禁忌算法的終止規(guī)則選用目標(biāo)控制原則：當(dāng)前已存在的最優(yōu)解的適應(yīng)度值連續(xù)nt次大于之后搜索到的解適應(yīng)度值，則停止搜索[16]。禁忌搜索算法流程如圖3所示。

圖3 TS算法流程Fig.3 Flow chart of TS algorithm

3 實(shí)例

某省級電能計(jì)量設(shè)備自動檢定中心對一批含有9個(gè)不同批組的電能計(jì)量設(shè)備進(jìn)行檢定。每個(gè)批組都要經(jīng)過外觀、耐壓檢測環(huán)節(jié)，多功能檢測環(huán)節(jié)，分揀、封印及自動貼標(biāo)簽環(huán)節(jié)等3大環(huán)節(jié)共6個(gè)單元的檢定。其中在多功能檢測環(huán)節(jié)有3組并行且獨(dú)立的U型檢測工位，每個(gè)工位含有60個(gè)表位可同時(shí)進(jìn)行檢測，即 BL≤60，B∈（0，6），但是不同批組在每個(gè)環(huán)節(jié)的檢定時(shí)間不盡相同，具體檢定時(shí)間如表1所示。

表1 檢定時(shí)間Tab.1 Verification time of the instance

運(yùn)用Matlab編程來實(shí)現(xiàn)本文算法，混合算法參數(shù)設(shè)置如下：遺傳種群數(shù)量為80，交叉概率為0.9，變異概率為0.1，精英保留率取ω=20%，遺傳算法最大進(jìn)化代數(shù)為200，禁忌鄰域解個(gè)數(shù)為10，候選解的個(gè)數(shù)為8，禁忌表長度為8，禁忌終止條件為連續(xù)nt=8次無法找到適應(yīng)度值更優(yōu)的解。

為更好地驗(yàn)證該混合算法具有收斂快、優(yōu)化率高的特性，以實(shí)例為背景，將本文提出的IGATS與ABC[1]、TS[4]、PSO[6]進(jìn)行比較。 表 2 為每種算法獲得最好解的10次獨(dú)立運(yùn)行結(jié)果的平均值。

表2 實(shí)例的4種優(yōu)化算法比較Tab.2 Result comparision of four optimization algorithms under the instance

從表2中可看出，本文提出的IGATS算法經(jīng)過大概80次就趨于收斂，與其它3種優(yōu)化算法相比，收斂速度較快，計(jì)算時(shí)間較短，且最優(yōu)檢定完成時(shí)間為346 min，因此能夠?qū)さ搅硗?種算法找不到的最優(yōu)解，四種算法在尋優(yōu)成功率方面的表現(xiàn)相當(dāng)。綜上所述，該遺傳禁忌算法的搜索空間能力較強(qiáng)，并具有快速求出最好解的特性，綜合性能優(yōu)于其它3種算法，能夠?yàn)闄z定流水線的優(yōu)化調(diào)度提供更多的理論依據(jù)。IGATS算法的最優(yōu)解甘特圖如圖4所示。其中：橫坐標(biāo)為各批組在該階段所需時(shí)間；縱坐標(biāo)為批組在該階段所選擇的機(jī)器編號，如：機(jī)器2對應(yīng)的 “1-2”表示批組1的第2個(gè)階段在設(shè)備2上進(jìn)行檢定，方格長度代表所需時(shí)間的長短。

圖4 IGATS算法的最優(yōu)解甘特圖Fig.4 Gantt chat of the optimal solution

4 結(jié)語

針對電能計(jì)量設(shè)備自動檢定流水線調(diào)度問題，本文提出一種有效的遺傳禁忌混合算法：設(shè)計(jì)了一種包含檢定排序和設(shè)備選擇信息的編碼和解碼方法，將遺傳算法得到的精英解作為禁忌算法的初始解，并運(yùn)用“高”鄰域候選集策略，來提高混合算法的尋優(yōu)能力。以某省級檢定中心自動檢定流水線為背景，將該算法與另外3種優(yōu)化算法進(jìn)行比較，表明該算法收斂速度更快、優(yōu)化率更高，得到的解最優(yōu)，具有較強(qiáng)的有效性和魯棒性。

[1] 王凌，周剛，許曄，等.求解不相關(guān)并行混合流水線調(diào)度問題的人工蜂群算法[J].控制理論與應(yīng)用，2012，29（12）：1551-1557.

[2] PAN Q K，TASGETIREN M F，SUGANTHAN P N，et al.A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem[J].Information Sciences，2010，181（12）：2455-2468.

[3] 王圣堯，王凌，許曄.求解相同并行機(jī)混合流水線車間調(diào)度問題的分布估計(jì)算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2013，12（6）：51-15.

[4] WANG X，TANG L.A tabu search heuristic for the hybrid flow-shop scheduling with finite intermediate buffers[J].Computers&Operations Research，2008，36（3）：907-918.

[5]ALAYKYRAN K，ENGIN O，DOYEN A.Using ant colony optimization to solve hybrid flow shop scheduling problem[J].InternationalJournalofAdvanced Manufacturing Tech-nology，2007，35（5/6）：541-550.

[6] TSENG C T，LIAO C J.A particle swarm optimization algorithm for hybrid flow-shop scheduling with multiprocess-or tasks[J].International Journal of Production Research，2008，46（17）：4655-4670.

[7] 姚靜，方彥軍，陳廣.遺傳和禁忌混合算法在機(jī)組負(fù)荷分配中的應(yīng)用[J].中國電機(jī)工程學(xué)報(bào)，2010，30（26）：95-99.

[8] 朱燦，梁昔明.一種多精英保存策略的遺傳算法[J].計(jì)算機(jī)應(yīng)用，2008，28（4）：929-931．

[9] 劉愛軍，楊育，邢青松，等.復(fù)雜制造環(huán)境下的改進(jìn)非支配排序遺傳算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2012，18（11）：446-458.

[10]呂瀟，孫躍.復(fù)合諧振感應(yīng)電能傳輸系統(tǒng)分析及參數(shù)優(yōu)化[J].電力系統(tǒng)自動化，2013，37（4）：119-124.

[11]ZHANG C S，OUYANG D T，NING J X.An artificial bee colony approach for clustering[J].Expen Systems with Applications，2010，37（7）：4761-4767.

[12]陳鐵梅，羅家祥.帶擾動和變異因子的改進(jìn)禁忌搜索算法求解貼片機(jī)過程優(yōu)化[J].控制與決策，2013，28（3）：363-368.

[13]ALFIERI A.Workload simulation and optimization in multicriteria hybrid flow-shop scheduling：A case study[J].International of Production Research，2009，47（18）：29-45.

[14]ORTMANN M C，VIGNIER A，DARDILHAC D，et al.Branch and bound crossed with GA to solve hybrid flow-shops[J].Europe Journal of Operational Research，1998，107（2）：389-400.

[15]Chiang C L.Genetic algorithms for power economic[J].IET on Generation Transmission and Distribution，2007，11（2）：261-269.

[16]蘇凱，劉吉臻，牛玉廣.考慮直吹式鋼球磨電耗的廠級負(fù)荷優(yōu)化分配[J].中國電機(jī)工程學(xué)報(bào)，2012，32（2）：24-30.

[17]XU Y，WANG L.Differential evolution algorithm for hybrid flow-shop scheduling problem[J].Journal of Systems Engineering and Electronics，2011，22（5）：794-798.

[18]王凌，周剛，許燁，等.混合流水線調(diào)度研究進(jìn)展[J].化工自動化及儀表，2011，38（1）：1-8.

[19]王凌.車間調(diào)度及其遺傳算法[M].北京：清華大學(xué)出版社，2003.■