基于混合遺傳禁忌算法的預制構件調度研究

陳竑翰 熊福力 王冬源 杜瑤 儲夢伶

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

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.

關鍵詞：預制構件;遺傳算法;禁忌搜索算法;混合算法

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

中圖分類號：TU756 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文章編號：1006-4311（2020）17-0247-04

0 ?引言

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

1 ?預制構件調度模型

1.1 目標函數

在文中，考慮預制供應鏈環境下的預制過程主要由九個步驟組成：（S1）模具制造;（S2）模具組裝;（S3）鋼筋預埋;（S4）混凝土澆筑;（S5）蒸汽養護;（S6）脫模;（S7）整理精修;（S8）存儲;（S9）運輸。本文采用準時交付的目標，無論工件提前交付還是延期交付都會有相應的罰金，目標函數為最小化總罰金，如公式（1）所示。

（1）

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

1.2 可中斷工作完工時間

在預制構件的生產過程中，若在當天的工作時間內不能完成工件在該工作站的加工，可以暫時中斷工作，并在下一個工作日的工作時間繼續加工。完工時間的計算如式（2）-式（4）所示。

（2）

（3）

（4）

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

1.3 不可中斷工作完工時間

若某些工作在當天加班時間內也不能完成，則須等到下一段工作時間開始時再開始加工。完工時間的計算如式（5）所示。

（5）

其中，HA是允許的加班時間。

1.4 并行處理工作完工時間

并行處理的工作可以對多個工件可以同時進行加工，完工時間計算如式（6）-式（7）所示。

（6）

（7）

2 ?混合算法的設計

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

2.1 用于預制構件調度的GA設計

2.1.1 編碼方式

無論在使用遺傳算法或者禁忌搜索算法來解決預制構件調度問題時，首先要進行的工作就是對工件的施工順序進行編碼。本文使用[0，1]之間的隨機數編碼來表示預制構件在各工作站的施工順序，隨機數越小優先級越高。編碼工作根據各工作站工件順序是否相同又分為單層編碼和多層編碼。

多層隨機數編碼使用一個矩陣對施工順序進行編碼。矩陣的一行代表一個工作站的施工順序，有多少工作站矩陣就有多少行，矩陣的列數代表預制構件的數量，如圖1所示。工作站的流水順序為：工作站1→工作站2→工作站3→工作站4。其中，工作站1的施工順序為：（2，5，1，3，6，4）;工作站2的施工順序為（4，1，6，2，5，3）;工作站3的施工順序為（1，5，6，4，3，2）;工作站4的施工順序為（4，2，1，6，5，3）。在單層隨機數編碼中，由于工件在各個工作站上的施工順序相同，所以用向量對各工作站的施工順序進行編碼。圖2展示了6個預制構件的單層隨機數編碼方式。其中，所有工作站的施工順序均為（3，4，5，1，2，6）。單層隨機數編碼和多層隨機數編碼各有利弊且搜索效果不同，需要設計實驗并根據實驗結果選擇更適合預制構件調度的編碼方式，本文后續小節使用遺傳算法進行編碼方式的選擇與論證。

2.1.2 初始種群的生成

使用GA進行尋優的第一步是生成初始種群，傳統的GA大多采用直接生成隨機數作為初始種群。為了提高GA搜索效率，本文對初始種群生成方法進行改進。

①NEH算法預搜索。

在過去的研究中，NEH啟發式算法被廣泛認為是解決流水車間問題的一種較好的算法。NEH算法最大的優點是搜索時間較短，在本文中將NEH算法應用于預制構件的調度問題，用來生成GA的初始種群。使用NEH算法進行預搜索的實驗結果如表1所示。

②工件緊急密度定義。

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

（8）

式中，ED（？滋）是第？滋個工件的緊急程度，Tp（？滋）是第？滋個工件在各工序的加工時間之和，Td（？滋）是第？滋個工件的交付時間。緊急密度ED（？滋）越大，工件的加工優先級越高，排序越靠前。？棕1和？棕2分別是交付時間和加工時間的權重系數，？棕1越大說明加工時間對緊急程度的影響越大，？棕2越大說明交付時間對緊急程度的影響越大。

③初始種群生成方法。

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

2.1.3 種群的更新

生成初始種群后，在遺傳過程中為了讓種群不斷向目標方向進化，每一代都需要對種群進行更新。種群的更新一般可以分為個體選擇、染色體交叉、染色體變異三項操作。

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

2.1.4 適應度計算

在預制構件調度問題中，可以用懲罰值來描述個體在自然界中的適應度。懲罰值越小，個體的適應度越高。本文中適應度使用目標函數的倒數。

2.2 用于預制構件調度的TS算法設計

本文用于預制構件調度的TS算法步驟如下：

①初始化。選擇禁忌對象，設置禁忌長度，并清空禁忌表。