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

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

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

0 引言

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

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

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

1 問(wèn)題描述

預(yù)制構(gòu)件流水生產(chǎn)的主要工序依次為：1)模具安裝;2)鋼筋放置;3)混凝土澆筑;4)蒸汽養(yǎng)護(hù);5)模具拆除;6)瑕疵修整。預(yù)制構(gòu)件根據(jù)生產(chǎn)工藝的特征，分為可中斷和不可中斷工序，其中不可中斷工序?yàn)榈谌篮偷谒牡拦ば颍溆鄤t為可中斷工序。而且構(gòu)件在養(yǎng)護(hù)階段是并行處理過(guò)程，可同時(shí)養(yǎng)護(hù)多個(gè)構(gòu)件。

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

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

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

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

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

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

2 調(diào)度模型

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

(1)

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

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

(2)

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

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

(3)

Dj,k=|Tj,k/24|

(4)

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

(5)

養(yǎng)護(hù)階段對(duì)應(yīng)的表達(dá)式為：

(6)

式中，Tj,4為構(gòu)件的養(yǎng)護(hù)完工時(shí)間，Tj,4=Cj,3+pj,4

3 GA_TS算法

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

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

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

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

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個(gè)，從區(qū)間[1,J]生成J個(gè)數(shù)字不重復(fù)的序列。染色體的編碼示意圖如圖1所示，共有10個(gè)構(gòu)件在流水線生產(chǎn)，構(gòu)件編號(hào)按流水生產(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所述方式隨機(jī)產(chǎn)生。

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

在此步驟當(dāng)中，通過(guò)目標(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)鍵作用，通常采用單點(diǎn)交叉和兩點(diǎn)交叉。為了使種群能夠多樣性，采用兩點(diǎn)交叉操作。兩點(diǎn)交叉示意圖如圖2所示。

圖2 兩點(diǎn)交叉示意圖

3.2.5 變異

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

圖3 變異示意圖

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

3.3 禁忌搜索

3.3.1 產(chǎn)生鄰域解

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

圖4 兩點(diǎn)交換示意圖

3.3.2 禁忌表和禁忌長(zhǎng)度

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

禁忌表的長(zhǎng)度代表每個(gè)禁忌對(duì)象的禁忌次數(shù)。

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

算法1：

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

2):設(shè)置禁忌長(zhǎng)度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)化

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

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

常用的算法調(diào)參的方法有田口方法和方差分析，其中田口方法主要適用于大于有兩個(gè)參數(shù)的算法，方差分析適用于參數(shù)數(shù)量未超過(guò)兩個(gè)的算法。所以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 實(shí)驗(yàn)結(jié)果及分析

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

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

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

表2 兩工廠規(guī)模實(shí)驗(yàn)結(jié)果

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

從表3的統(tǒng)計(jì)結(jié)果可看出，GA算法的最佳Min在40個(gè)例子中占10個(gè)，最佳Avg在40個(gè)實(shí)例中占0個(gè)；TS產(chǎn)生最好或相等的Min和Avg分別在40個(gè)實(shí)例中占到10個(gè)和0個(gè)；GA_TS算法的Min和Avg分別在40個(gè)實(shí)例中占到40個(gè)和40個(gè)。這表明在所測(cè)試的算例中，GA_TS的性能比TS和GA更為有效，求得的提前和拖期懲罰值更小。

從表3還可看出，在40個(gè)例子中，其中有GA_TS得到的Std值也小于TS和GA得到的Std值，這表明GA_TS比TS和GA具有更強(qiáng)的魯棒性。為了更加清晰的表明提出的GA_TS算法的魯棒性，作出了關(guān)于構(gòu)件規(guī)模的平均標(biāo)準(zhǔn)差趨勢(shì)圖，如圖5所示。

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

5 結(jié)束語(yǔ)

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