陳竑翰 熊福力 王冬源 杜瑤 儲(chǔ)夢(mèng)伶

摘要：合理的調(diào)度方案可以顯著改善預(yù)制構(gòu)件生產(chǎn)效率，降低能耗并提高客戶(hù)滿(mǎn)意度。針對(duì)預(yù)制構(gòu)件生產(chǎn)調(diào)度優(yōu)化問(wèn)題，傳統(tǒng)的遺傳算法往往優(yōu)化效率較低。因此提出了一種新型的混合遺傳禁忌算法，其中考慮了不同的編碼方式以及初始種群的生成方式對(duì)算法的影響，首先通過(guò)遺傳算法找到一個(gè)較好的可行解作為禁忌搜索算法的初始解，而后使用禁忌搜索算法在這個(gè)初始解的鄰域內(nèi)進(jìn)行局部搜索尋優(yōu)。最后設(shè)計(jì)實(shí)驗(yàn)驗(yàn)證了單層隨機(jī)數(shù)編碼方式優(yōu)于多層隨機(jī)數(shù)編碼方式。并在基準(zhǔn)時(shí)間下運(yùn)行算法，實(shí)驗(yàn)結(jié)果表明，在工件數(shù)較少時(shí)禁忌搜索算法效果較好，而在工件數(shù)較多的情況下混合算法更優(yōu)。

Abstract： A reasonable scheduling scheme can significantly improve the production efficiency of prefabricated components， reduce energy consumption and increase customer satisfaction. In order to optimize the production scheduling of prefabricated components， traditional genetic algorithms often have lower optimization efficiency. Therefore， a new type of hybrid genetic tabu algorithm is proposed， which takes into account the effects of different coding methods and initial population generation methods on the algorithm. First， a better feasible solution is found through the genetic algorithm as the initial solution of the tabu search algorithm. A tabu search algorithm is used to perform local search optimization in the neighborhood of this initial solution. Finally， design experiments verify that single-layer random number encoding is better than multi-layer random number encoding. The algorithm is run at the benchmark time. The experimental results show that the tabu search algorithm works well when the number of artifacts is small， and the hybrid algorithm is better when the number of artifacts is large.

關(guān)鍵詞：預(yù)制構(gòu)件;遺傳算法;禁忌搜索算法;混合算法

Key words： precast component;genetic algorithm;tabu search algorithm;hybrid algorithm

中圖分類(lèi)號(hào)：TU756 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文章編號(hào)：1006-4311（2020）17-0247-04

0 ?引言

裝配式建筑是指在工廠預(yù)制，現(xiàn)場(chǎng)裝配而成的建筑[1]，與傳統(tǒng)現(xiàn)澆式施工和砌體結(jié)構(gòu)相比，裝配式建筑可以預(yù)先在預(yù)制場(chǎng)中進(jìn)行生產(chǎn)，減少了環(huán)境污染和材料耗費(fèi)。裝配式建筑需求量不斷增加，然而，目前我國(guó)裝配式建筑并沒(méi)有得到廣泛的推廣，主要有技術(shù)不完善和生產(chǎn)調(diào)度混亂兩方面原因。在過(guò)去幾十年中，不斷有學(xué)者對(duì)預(yù)制構(gòu)件的調(diào)度模型進(jìn)行改進(jìn)，Chan和Hu[2]提出了預(yù)制構(gòu)件生產(chǎn)的流水車(chē)間排序模型（FSSM），將目標(biāo)改為最小化延遲和提前的懲罰值。Leu等人[3]考慮了起重機(jī)和工廠工人的限制，以最小完工時(shí)間為目標(biāo)。Li等人[4]提出了生產(chǎn)成本最低的調(diào)度模型，將生產(chǎn)資源約束整合到模型中。Wang等人[5]在原有的六道工序基礎(chǔ)上，考慮了模具制造、預(yù)制件存儲(chǔ)和運(yùn)輸三個(gè)過(guò)程。目前的研究已經(jīng)發(fā)現(xiàn)預(yù)制構(gòu)件的生產(chǎn)調(diào)度優(yōu)化屬于NP難題[6]，因此在解決預(yù)制構(gòu)件的調(diào)度問(wèn)題時(shí)，研究人員大多采用啟發(fā)式算法，包括Gupta[7]、Palmer[8]等方法。Chan等人[9]通過(guò)將遺傳算法與Palmer等算法進(jìn)行比較，驗(yàn)證了遺傳算法在流水車(chē)間排序模型上的優(yōu)勢(shì)。遺傳算法雖然可以較好的解決預(yù)制構(gòu)件的調(diào)度問(wèn)題，但在應(yīng)用上仍然存在局部搜索能力差的問(wèn)題。本文提出了一種混合算法。最后將兩種算法與混合算法的性能進(jìn)行比較，驗(yàn)證了混合算法在預(yù)制構(gòu)件調(diào)度優(yōu)化問(wèn)題上的優(yōu)勢(shì)。

1 ?預(yù)制構(gòu)件調(diào)度模型

1.1 目標(biāo)函數(shù)

在文中，考慮預(yù)制供應(yīng)鏈環(huán)境下的預(yù)制過(guò)程主要由九個(gè)步驟組成：（S1）模具制造;（S2）模具組裝;（S3）鋼筋預(yù)埋;（S4）混凝土澆筑;（S5）蒸汽養(yǎng)護(hù);（S6）脫模;（S7）整理精修;（S8）存儲(chǔ);（S9）運(yùn)輸。本文采用準(zhǔn)時(shí)交付的目標(biāo)，無(wú)論工件提前交付還是延期交付都會(huì)有相應(yīng)的罰金，目標(biāo)函數(shù)為最小化總罰金，如公式（1）所示。

（1）

其中，Cj為第j個(gè)工件的完工時(shí)間，dj為第j個(gè)工件的交付時(shí)間。？琢j為第j個(gè)工件的延期懲罰系數(shù)，？茁j為第j個(gè)工件的提前懲罰系數(shù)。

1.2 可中斷工作完工時(shí)間

在預(yù)制構(gòu)件的生產(chǎn)過(guò)程中，若在當(dāng)天的工作時(shí)間內(nèi)不能完成工件在該工作站的加工，可以暫時(shí)中斷工作，并在下一個(gè)工作日的工作時(shí)間繼續(xù)加工。完工時(shí)間的計(jì)算如式（2）-式（4）所示。

（2）

（3）

（4）

其中，HW是一個(gè)工作日的工作時(shí)間，HN是一個(gè)工作日的非工作時(shí)間，T是累積完工時(shí)間，D是工作天數(shù)，24D則代表一整個(gè)工作日，floor為一個(gè)向下取整函數(shù)。

1.3 不可中斷工作完工時(shí)間

若某些工作在當(dāng)天加班時(shí)間內(nèi)也不能完成，則須等到下一段工作時(shí)間開(kāi)始時(shí)再開(kāi)始加工。完工時(shí)間的計(jì)算如式（5）所示。

（5）

其中，HA是允許的加班時(shí)間。

1.4 并行處理工作完工時(shí)間

并行處理的工作可以對(duì)多個(gè)工件可以同時(shí)進(jìn)行加工，完工時(shí)間計(jì)算如式（6）-式（7）所示。

（6）

（7）

2 ?混合算法的設(shè)計(jì)

遺傳算法（genetic algorithm，GA）是一種著名的啟發(fā)式算法。其基本思想是通過(guò)編碼技術(shù)模擬染色體，并通過(guò)群體中不同染色體交叉、變異的過(guò)程，淘汰弱勢(shì)染色體，使群體不斷進(jìn)化，最終找到最優(yōu)個(gè)體。其優(yōu)點(diǎn)是具有很強(qiáng)的全局搜索能力，不容易陷入局部最優(yōu)，缺點(diǎn)是在搜索過(guò)程中有可能忽視局部最優(yōu)解。且容易到達(dá)收斂早熟，使搜索效果下降。禁忌搜索（Tabu Search，TS）最初是由Glover [10]提出的，是對(duì)局部搜索方法的一種擴(kuò)展。其最大的特點(diǎn)是可以禁止重復(fù)性的工作，避免陷入局部最優(yōu)解。優(yōu)點(diǎn)是局部搜索能力較強(qiáng)，缺點(diǎn)是較為依賴(lài)初始解。本文通過(guò)結(jié)合兩種算法的優(yōu)點(diǎn)，并在GA的初始種群中加入NEH算法，提出了一種混合遺傳禁忌算法。

2.1 用于預(yù)制構(gòu)件調(diào)度的GA設(shè)計(jì)

2.1.1 編碼方式

無(wú)論在使用遺傳算法或者禁忌搜索算法來(lái)解決預(yù)制構(gòu)件調(diào)度問(wèn)題時(shí)，首先要進(jìn)行的工作就是對(duì)工件的施工順序進(jìn)行編碼。本文使用[0，1]之間的隨機(jī)數(shù)編碼來(lái)表示預(yù)制構(gòu)件在各工作站的施工順序，隨機(jī)數(shù)越小優(yōu)先級(jí)越高。編碼工作根據(jù)各工作站工件順序是否相同又分為單層編碼和多層編碼。

多層隨機(jī)數(shù)編碼使用一個(gè)矩陣對(duì)施工順序進(jìn)行編碼。矩陣的一行代表一個(gè)工作站的施工順序，有多少工作站矩陣就有多少行，矩陣的列數(shù)代表預(yù)制構(gòu)件的數(shù)量，如圖1所示。工作站的流水順序?yàn)椋汗ぷ髡?→工作站2→工作站3→工作站4。其中，工作站1的施工順序?yàn)椋海?，5，1，3，6，4）;工作站2的施工順序?yàn)椋?，1，6，2，5，3）;工作站3的施工順序?yàn)椋?，5，6，4，3，2）;工作站4的施工順序?yàn)椋?，2，1，6，5，3）。在單層隨機(jī)數(shù)編碼中，由于工件在各個(gè)工作站上的施工順序相同，所以用向量對(duì)各工作站的施工順序進(jìn)行編碼。圖2展示了6個(gè)預(yù)制構(gòu)件的單層隨機(jī)數(shù)編碼方式。其中，所有工作站的施工順序均為（3，4，5，1，2，6）。單層隨機(jī)數(shù)編碼和多層隨機(jī)數(shù)編碼各有利弊且搜索效果不同，需要設(shè)計(jì)實(shí)驗(yàn)并根據(jù)實(shí)驗(yàn)結(jié)果選擇更適合預(yù)制構(gòu)件調(diào)度的編碼方式，本文后續(xù)小節(jié)使用遺傳算法進(jìn)行編碼方式的選擇與論證。

2.1.2 初始種群的生成

使用GA進(jìn)行尋優(yōu)的第一步是生成初始種群，傳統(tǒng)的GA大多采用直接生成隨機(jī)數(shù)作為初始種群。為了提高GA搜索效率，本文對(duì)初始種群生成方法進(jìn)行改進(jìn)。

①NEH算法預(yù)搜索。

在過(guò)去的研究中，NEH啟發(fā)式算法被廣泛認(rèn)為是解決流水車(chē)間問(wèn)題的一種較好的算法。NEH算法最大的優(yōu)點(diǎn)是搜索時(shí)間較短，在本文中將NEH算法應(yīng)用于預(yù)制構(gòu)件的調(diào)度問(wèn)題，用來(lái)生成GA的初始種群。使用NEH算法進(jìn)行預(yù)搜索的實(shí)驗(yàn)結(jié)果如表1所示。

②工件緊急密度定義。

為了找到一些合理的解生成GA的初始種群，本文定義了工件的緊急密度，如式（8）所示。

（8）

式中，ED（？滋）是第？滋個(gè)工件的緊急程度，Tp（？滋）是第？滋個(gè)工件在各工序的加工時(shí)間之和，Td（？滋）是第？滋個(gè)工件的交付時(shí)間。緊急密度ED（？滋）越大，工件的加工優(yōu)先級(jí)越高，排序越靠前。？棕1和？棕2分別是交付時(shí)間和加工時(shí)間的權(quán)重系數(shù)，？棕1越大說(shuō)明加工時(shí)間對(duì)緊急程度的影響越大，？棕2越大說(shuō)明交付時(shí)間對(duì)緊急程度的影響越大。

③初始種群生成方法。

本文中，GA的初始種群生成方法為：一個(gè)個(gè)體是NEH預(yù)搜索的解;九個(gè)個(gè)體是由定義的工件緊急程度得到的排序，？棕1從0.1到0.9，？棕2從0.9到0.1;其余個(gè)體由隨機(jī)數(shù)生成，保證初始種群多樣性。

2.1.3 種群的更新

生成初始種群后，在遺傳過(guò)程中為了讓種群不斷向目標(biāo)方向進(jìn)化，每一代都需要對(duì)種群進(jìn)行更新。種群的更新一般可以分為個(gè)體選擇、染色體交叉、染色體變異三項(xiàng)操作。

在本文中使用輪盤(pán)賭方法作為選擇算子。確定選擇算子后，要對(duì)選中的兩個(gè)個(gè)體進(jìn)行染色體交叉操作。本文使用雙點(diǎn)交叉隨機(jī)產(chǎn)生兩個(gè)點(diǎn)位，并交換兩個(gè)點(diǎn)位之間的基因。交叉操作后，緊接著進(jìn)行變異操作。本文使用的變異算子先隨機(jī)選出兩個(gè)基因，將后面的基因插入到前面基因的前方。

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

在預(yù)制構(gòu)件調(diào)度問(wèn)題中，可以用懲罰值來(lái)描述個(gè)體在自然界中的適應(yīng)度。懲罰值越小，個(gè)體的適應(yīng)度越高。本文中適應(yīng)度使用目標(biāo)函數(shù)的倒數(shù)。

2.2 用于預(yù)制構(gòu)件調(diào)度的TS算法設(shè)計(jì)

本文用于預(yù)制構(gòu)件調(diào)度的TS算法步驟如下：

①初始化。選擇禁忌對(duì)象，設(shè)置禁忌長(zhǎng)度，并清空禁忌表。