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

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

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

0 引言

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

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

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

1 問題描述

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

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

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

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

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

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

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

2 調(diào)度模型

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

(1)

構(gòu)件j的完工時間Cj可通過以下約束計算。

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

(2)

其中:公式(2)中k= {1, 2, 5, 6}；Tj,k是構(gòu)件j在工序k的累加時間；Dj,k是構(gòu)件j距工廠開機的工作日數(shù)。Dj,k是一個非負(fù)整數(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)護階段對應(yīng)的表達(dá)式為：

(6)

式中，Tj,4為構(gòu)件的養(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)設(shè)置GA_TS算法各參數(shù)，產(chǎn)生初始種群。

2)計算各染色體的適應(yīng)度值。

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

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

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

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

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

3.1 編碼方式

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

87325610194

圖1 染色體編碼方案

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

3.2 遺傳算法

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

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

3.2.2 計算適應(yīng)度值

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

3.2.3 選擇

3.2.4 交叉

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

圖2 兩點交叉示意圖

3.2.5 變異

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

圖3 變異示意圖

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

3.3 禁忌搜索

3.3.1 產(chǎn)生鄰域解

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

圖4 兩點交換示意圖

3.3.2 禁忌表和禁忌長度

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

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

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

算法1：

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

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

3):repeat

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

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

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 目標(biāo)解S，目標(biāo)值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算法也將進(jìn)行實驗。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)參結(jié)果如下：

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 實驗結(jié)果及分析

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

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

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

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

表3 結(jié)果統(tǒng)計

從表3的統(tǒng)計結(jié)果可看出，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ān)于構(gòu)件規(guī)模的平均標(biāo)準(zhǔn)差趨勢圖，如圖5所示。

圖5 關(guān)于構(gòu)件數(shù)量的平均標(biāo)準(zhǔn)差趨勢圖

5 結(jié)束語

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