基于遺傳和禁忌搜索混合算法的預制生產調度的研究

李 志，熊福力，汪琳婷，陳竑翰

(西安建筑科技大學 信息與控制工程學院，西安 710055)

0 引言

混凝土預制構件能流水生產能夠發揮節能環保、縮短施工周期、減少勞動力等優勢[1]。據調研，企業在流水生產混凝土預制構件時，大多依靠過往經驗，導致庫存緊張或者發生拖期，是構成裝配式建筑成本居高不下的一重要因素[2]。所以，混凝土預制構件提前和拖期懲罰(ETP,earliness and tardiness penalty)問題是亟需解決的一類生產調度問題。

流水車間調度問題是一項非確定性多項式難(NP-hard,non-deterministic polynomial hard)問題，研究者通常采用人工智能算法求解相關問題[3]，尤其在預制生產方面，遺傳算法使用居多。孟旭等[4]采用粒子群算法解決車間最大完工時間問題。謝思聰等[5]為解決預制構件流水生產調度問題，在GA的基礎上融合了一種關于構件生產參數的定量方法。Leu 等[6]建立了預制構件混合生產的調度模型，并采用GA求解。Chan等[7-8]建立了預制構件流水生產的調度模型，并運用GA求解庫存與拖期總加權懲罰最小化問題。Ko等[9]在解決預制構件流水生產相關問題時，考慮了相鄰工作站間的緩沖區容量，并利用GA解決該問題。Yang等[10]建立了多條預制流水車間生產線的調度模型，最后通過GA解決提出的問題。Ma等[11]在多條流水線的基礎上提出了重調度問題，并通過GA進行求解。Wang等[12]考慮了預制構件的整個供應鏈，并改進了傳統的預制構件生產調度模型，最后通過GA解決提出的調度問題。

雖然GA已成功運用到預制構件流水生產調度問題中，但由于GA局部搜索能力較差，容易出現過早收斂的問題。考慮到TS算法的局部搜索能力較強，因此利用TS改進GA算法的局部搜索能力，提高解質量。

1 問題描述

預制構件流水生產的主要工序依次為：1)模具安裝;2)鋼筋放置;3)混凝土澆筑;4)蒸汽養護;5)模具拆除;6)瑕疵修整。預制構件根據生產工藝的特征，分為可中斷和不可中斷工序，其中不可中斷工序為第三道和第四道工序，其余則為可中斷工序。而且構件在養護階段是并行處理過程，可同時養護多個構件。

預制構件企業在生產J個構件時，構件j發生拖期或提前完工分別會產生合同罰款和存儲成本。每個構件都有與之對應的交貨期(dj)、每單位時間的拖期懲罰成本(βj)、每單位時間的提前懲罰成本(ɑj)以及構件j在工序k的加工時間(pj,k)。

此外，在生產過程中滿足以下條件：

1)構件都可以在零時刻進行加工，并在機器上以相同的順序進行處理。

2)加工過程中禁止發生搶占活動。直到前一個構件完成為止，才可以處理下一個構件。

3)忽略機器故障等突發事件。

4)緩沖區大小和模具數量無限制。

2 調度模型

構件j的完工時間Cj小于交貨期dj，則產生提前懲罰；如果Cj大于dj，則會產生拖期懲罰。預制構件流水車間ETP問題的目標函數為：

(1)

構件j的完工時間Cj可通過以下約束計算。

車間工作制度通常分為上班時間(HW)、非上班時間(HN)，其中非上班時間包含加班時間(HO)。

(2)

其中:公式(2)中k= {1, 2, 5, 6}；Tj,k是構件j在工序k的累加時間；Dj,k是構件j距工廠開機的工作日數。Dj,k是一個非負整數并且公式└·┘代表的是向下取整函數，Tj,k和Dj,k可分別由等式(3)和(4)計算得到：

Tj,k=max(Cj-1,k,Cj,k-1)+pj,k

(3)

Dj,k=|Tj,k/24|

(4)

混凝土澆筑工序的完工時間由下式表示：

(5)

養護階段對應的表達式為：

(6)

式中，Tj,4為構件的養護完工時間，Tj,4=Cj,3+pj,4

3 GA_TS算法

GA具有并行搜索能力，從解空間中多點出發搜索問題的最優或者近優解，適用于求解多種組合優化問題，但GA的局部搜索能力差，容易過早收斂。TS算法由于其靈活的記憶功能，以便跳出局部最優解，并轉向解空間的其它區域，提高獲得全局最優或近優解的概率。為了充分發揮兩種算法的優勢，提出了一種GA和TS的混合算法GA_TS，算法步驟如下：

1)設置GA_TS算法各參數，產生初始種群。

2)計算各染色體的適應度值。

3)通過選擇、交叉、變異等算子更新種群。

4)將適應度值最優的染色體作為TS的初始解。

5)進行TS，得到局部最優解。

6)將TS得到的局部最優解替換種群中適應度值最差的染色體。

7)判斷是否滿足終止條件。若滿足，停止迭代尋優；反之，轉至步驟3)進行下次尋優。

3.1 編碼方式

待加工構件的有J個，從區間[1,J]生成J個數字不重復的序列。染色體的編碼示意圖如圖1所示，共有10個構件在流水線生產，構件編號按流水生產順序依次為8，7，3，2，5，6，10，1，9，4。

87325610194

圖1 染色體編碼方案

一旦確定染色體內的基因內容，即構件排序，每道工序皆需按此順序生產。

3.2 遺傳算法

3.2.1 產生初始種群

種群由pop條染色體組成，每條染色均按小節3.1所述方式隨機產生。

3.2.2 計算適應度值

在此步驟當中，通過目標函數公式(1)求得每條染色體i的目標函數值，再取其倒數作為該染色體的適應度值，即fit(i)=1 /f(i)。適應度值越大的染色體，被選擇的概率越大。

3.2.3 選擇

3.2.4 交叉

交叉在GA中起到關鍵作用，通常采用單點交叉和兩點交叉。為了使種群能夠多樣性，采用兩點交叉操作。兩點交叉示意圖如圖2所示。

圖2 兩點交叉示意圖

3.2.5 變異

變異操作是為了保證種群基因的多樣性，避免陷入局部最優。變異操作的步驟為：在每條染色條內隨機確定兩個位置，交換這兩個位置所對應的構建編號，如圖3所示。

圖3 變異示意圖

最后由產生的子代更新種群。

3.3 禁忌搜索

3.3.1 產生鄰域解

禁忌搜索的鄰域解由Nsize條鄰居解構成，每條鄰居解根據當前解獲得，主要需要兩個步驟：首先隨機選擇當前解s中的兩個索引位置，然后交換這兩個位置的構件編號，即生成鄰居解sN。交換操作如圖4所示。

圖4 兩點交換示意圖

3.3.2 禁忌表和禁忌長度

禁忌表主要作用是防止在搜索過程中避免陷入局部最優，從而可以搜索更多解空間。若禁忌表的長度太短，則搜索過程可能會進入死循環；相反，則導致計算時間太長。

禁忌表的長度代表每個禁忌對象的禁忌次數。

TS算法的偽代碼如算法1所示。

算法1：

1):輸入初始解s′，初始目標值f(s′)

2):設置禁忌長度tl，迭代次數TS_Iter，初始化禁忌表A

3):repeat

4):N(s′) ← 產生初始解s′的鄰域解

5):f(s*) ←N(s′)中的最優目標值

6):iff(s*) >f(s′)，將解s*放入禁忌表A

7):更新禁忌表A，并令s′←s*,f(s′) ←f(s*)

8):記錄目前最優解，S←s*

9): else

10):ifs*已被禁忌，選擇鄰居解中的次優解ssub放入禁忌表A

11):更新禁忌表A，并令s′ ←ssub

12):end if

13):end if

14):直至滿足停止條件

15):return 目標解S，目標值f(S)

3.4 算法參數優化

算法通過Matlab 2018a編程實現，計算機配置為Microsoft Windows 10，處理器為Intel Core i5-7200U CPU @ 2.5 GHz，8 GB RAM。

為評估所提出的GA_TS算法的性能，GA和TS算法也將進行實驗。GA有3個參數，分別是種群大小(pop)，交叉率(pc)和變異率(pm)。TS有兩個參數，禁忌長度(tl)和鄰域解數量(Nsize)。GA_TS有6個參數，分別為種群大小(pop)、交叉率(pc)、變異率(pm)、禁忌長度(tl)、鄰域解數量(Nsize)和禁忌搜索迭代次數(TS_Iter)。

常用的算法調參的方法有田口方法和方差分析，其中田口方法主要適用于大于有兩個參數的算法，方差分析適用于參數數量未超過兩個的算法。所以GA和GA_TS采用田口方法調參，TS采用方差分析調參。調參結果如下：

1)GA：pop=80，pc= 0.9，pm= 0.1；

2)GA_TS：pop= 60，pc= 0.85，pm= 0.1，Nsize=J+10，TS_Iter= 55，tl=round((J×(J-1)/2))1/2)；

3)TS：tl=round((J×(J-1)/2))1/2)，Nsize=J+5。

4 實驗結果及分析

為了評估各算法的性能，分別在20，30，50和70個構件數量進行實驗，其中每種規模數量下各生成10個算例。工件的生產數據來源于[13]，列于表1，所有規模的構件數據皆是在此數據的基礎上生成。構件j的交貨期在區間[PT/J, 3*J]內隨機產生，其中PT為所有工件的加工時間累加和。每個算例計算30次，記錄30個值的最小值(Min)、平均值(Avg)、標準差(Std)。3種算法均在同一CPU計算時間內停止運行，其計算時間設置為800 ×Jms。

表2記錄了3種算法的實驗結果，其中3個算法在同一例子中的最小Min用粗斜體表示、最小Avg用粗體表示。表3統計了各算法在每種工廠規模下獲得最好的Min、Avg、Std的算例數量，分別用符號No.Min、No.Avg、No.Std表示。

表1 預制生產數據

表2 兩工廠規模實驗結果

表3 結果統計

從表3的統計結果可看出，GA算法的最佳Min在40個例子中占10個，最佳Avg在40個實例中占0個；TS產生最好或相等的Min和Avg分別在40個實例中占到10個和0個；GA_TS算法的Min和Avg分別在40個實例中占到40個和40個。這表明在所測試的算例中，GA_TS的性能比TS和GA更為有效，求得的提前和拖期懲罰值更小。

從表3還可看出，在40個例子中，其中有GA_TS得到的Std值也小于TS和GA得到的Std值，這表明GA_TS比TS和GA具有更強的魯棒性。為了更加清晰的表明提出的GA_TS算法的魯棒性，作出了關于構件規模的平均標準差趨勢圖，如圖5所示。

圖5 關于構件數量的平均標準差趨勢圖

5 結束語

本文針對混凝土預制構件流水車間提前和拖期懲罰調度問題，建立了非線性整數規劃模型。為了在合理時間內獲得可行生產方案，提出了一種混合啟發式算法—GA_TS算法，用其求解本研究所提出的調度問題。實驗計算結果表明，提出的GA_TS算法在所測試的所有算例中計算得到的目標值、平均值以及標準差都要優于TS和GA算法，表現出了較強魯棒性。繼而可為實際生產提供理論性的指導以及技術性的服務。在未來的研究方向中，將機器故障、緊急插單等不確定情形集成到預制生產調度問題中，并開發出更有效的元啟發式算法。