基于遺傳和禁忌搜索混合算法的預制生產(chǎn)調(diào)度的研究

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

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

0 引言

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

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

雖然GA已成功運用到預制構件流水生產(chǎn)調(diào)度問題中，但由于GA局部搜索能力較差，容易出現(xiàn)過早收斂的問題?？紤]到TS算法的局部搜索能力較強，因此利用TS改進GA算法的局部搜索能力，提高解質(zhì)量。

1 問題描述

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

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

此外，在生產(chǎn)過程中滿足以下條件：

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

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

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

4)緩沖區(qū)大小和模具數(shù)量無限制。

2 調(diào)度模型

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

(1)

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

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

(2)

其中:公式(2)中k= {1, 2, 5, 6}；Tj,k是構件j在工序k的累加時間；Dj,k是構件j距工廠開機的工作日數(shù)。Dj,k是一個非負整數(shù)并且公式└·┘代表的是向下取整函數(shù)，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)

養(yǎng)護階段對應的表達式為：

(6)

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

3 GA_TS算法

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

1)設置GA_TS算法各參數(shù)，產(chǎn)生初始種群。

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

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

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

5)進行TS，得到局部最優(yōu)解。

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

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

3.1 編碼方式

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

87325610194

圖1 染色體編碼方案

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

3.2 遺傳算法

3.2.1 產(chǎn)生初始種群

種群由pop條染色體組成，每條染色均按小節(jié)3.1所述方式隨機產(chǎn)生。

3.2.2 計算適應度值

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

3.2.3 選擇

3.2.4 交叉

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

圖2 兩點交叉示意圖

3.2.5 變異

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

圖3 變異示意圖

最后由產(chǎn)生的子代更新種群。

3.3 禁忌搜索

3.3.1 產(chǎn)生鄰域解

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

圖4 兩點交換示意圖

3.3.2 禁忌表和禁忌長度

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

禁忌表的長度代表每個禁忌對象的禁忌次數(shù)。

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

算法1：

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

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

3):repeat

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

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

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

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

8):記錄目前最優(yōu)解，S←s*

9): else

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

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

12):end if

13):end if

14):直至滿足停止條件

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

3.4 算法參數(shù)優(yōu)化

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

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

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

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個構件數(shù)量進行實驗，其中每種規(guī)模數(shù)量下各生成10個算例。工件的生產(chǎn)數(shù)據(jù)來源于[13]，列于表1，所有規(guī)模的構件數(shù)據(jù)皆是在此數(shù)據(jù)的基礎上生成。構件j的交貨期在區(qū)間[PT/J, 3*J]內(nèi)隨機產(chǎn)生，其中PT為所有工件的加工時間累加和。每個算例計算30次，記錄30個值的最小值(Min)、平均值(Avg)、標準差(Std)。3種算法均在同一CPU計算時間內(nèi)停止運行，其計算時間設置為800 ×Jms。

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

表1 預制生產(chǎn)數(shù)據(jù)

表2 兩工廠規(guī)模實驗結果

表3 結果統(tǒng)計

從表3的統(tǒng)計結果可看出，GA算法的最佳Min在40個例子中占10個，最佳Avg在40個實例中占0個；TS產(chǎn)生最好或相等的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算法的魯棒性，作出了關于構件規(guī)模的平均標準差趨勢圖，如圖5所示。

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

5 結束語

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