蟻群禁忌搜索融合算法求解調度問題

劉博省，毛范海，錢 峰

（大連理工大學機械工程學院，遼寧 大連116024）

1 引言

車間調度是一個歷史悠久的優化問題，其本質是通過資源的分配和時間的先后順序來完成不同的生產任務，使預定目標最優化。隨著汽車行業的發展，其部件的裝配生產線越來越多的面對著多品種、小批量和個性化的制造需求［1］。一方面，傳統的憑借經驗或簡單的確定性規則的排產算法（大多數企業當前的排產方法）難以得到使預訂目標最優化的調度；另一方面，動態規劃、分枝定界等優化方法可以得到理論上的最優解，但由于算力的制約無法解決大規模的調度問題。所以研究者們將一系列元啟發式算法應用在車間調度問題上，取得了一些成果。

文獻［2］針對作業車間調度問題，提出了一種并行模擬退火算法，在小規模Job-shop問題上取得了較好的效果；文獻［3］提出了一種改進遺傳算法來解決JSP問題，運用多種策略豐富解的空間，獲得了較好的解；文獻［4］針對采用粒子群優化算法解決流水車間調度問題進行了研究綜述；文獻［5］采用粒子群算法來解JSP問題，用MK01-MK10等十個問題驗證了解的有效性。

為解決發動機缸體混流生產線的生產調度問題，將其抽象為Job-shop問題后提出一種基于蟻群和禁忌搜索的混合算法，并進行實例仿真得出此方法的有效性和性能。

2 JSP問題描述及其數學模型建立

2.1 Job-shop問題的描述

n個工件在m臺機器上加工，工件均包含m個工序，要求最大完工時間最小（Makespan：最大完工時間，JSP中最常用的研究指標）。Job-shop問題的基本約束條件如下：

（1）各工件服從工藝路線約束；

（2）各工序必須在指定機器上加工；

（3）同一時刻一臺機器只能加工一個工序；

（4）必須等到前一道工序加工完畢后一個工序才能開始加工；

（5）每個工序在可用機器上的加工時間確定；

（6）允許工件和機器存在等待時間；

（7）工序一旦開始則不允許中斷；

Job-shop問題的求解也即為得到一個滿足上述約束條件的可行解，從而優化特定的生產性能指標。

2.2 Job-shop的數學模型

Job-shop是許多實混流裝配線的簡化模型，也是目前研究非常廣泛的生產調度問題的簡化模型，其數學模型可表示為下：

式中：cik—i工件在機器k上的完成時間，pih—i工件在機器h上的加工時間，aihk—指示系數，其意義為：

式中：xihk—知識變量，其意義為：

式（2）表示工序約束，即工件的后一個工序要在前一個工序的加工完成的基礎上才能開始加工；式（3）表示資源約束，即同一臺機器上不能有兩項工序同時加工；式（4）表示每個工件的每個工序的加工時間都為正數；M是一個足夠大的正數。文獻［6］問題求解是一個典型的NP-hard問題，至今沒有找到可以精確求得最優解的多項式算法。

3 融合算法原理與步驟

3.1 蟻群算法原理

蟻群算法由文獻［7］首先提出并應用于Job-shop問題，蟻群算法在Job-shop問題應用方式如下：使用蟻群算法求解Job-shop問題時，螞蟻從0結點出發，遍歷每一個結點直至10結點，得到的工序序列即為問題的一個解。螞蟻爬行時結點選擇由狀態轉移規則確定；每只螞蟻爬行過程中進行信息素更新，由信息素更新公式確定。

故本研究采用狀態轉移規則和信息素更新方法有所改進的蟻群系統（Ant Colony System）進行求解。

（1）改進的狀態轉移規則

式中：Sk—序號為k的螞蟻所選擇的下一個工序；q—一個生成的隨機數；q0—閾值，若螞蟻選擇結點時的隨機數q≤q0，則按照第一種情況選擇下一個結點，即所選結點使得整個表達式的值最大，這被稱為對知識的“利用”；反之，若q≥q0，則按照以下公式計算待選工序各自的概率，然后按照“輪盤賭”方法做出選擇，這被稱為“探索”。

（2）改進的信息素更新方法

基本蟻群算法在一次迭代中所有螞蟻爬行完成后進行信息素的更新，更新公式如下：

式中：蒸發因子ρ∈(0,1)，Δτij—所有螞蟻信息素增量之和，在本算法中采用蟻周模型（Ant-Quantity System），計算方法如下：

蟻群系統在在基本蟻群算法信息素更新的基礎上增加了“信息素局部更新機制”，在螞蟻爬行結束時即更新信息素，用來擴大搜索范圍，公式如下：

式中：局部蒸發因子ρ0∈(0,1)，當螞蟻爬行完成后，其走過的工序路徑的信息素以ρ0的速率蒸發，使得之后的螞蟻重復選擇路徑的概率較小。

3.2 禁忌搜索算法原理

禁忌搜索（Tabu Search，TS）的思想最先由文獻［8］于1986年提出，是對局部搜索算法的一種改進。該算法的基本原理是：對某問題給定一個初始解和領域結構，在領域中通過一定規則確定若干候選解；若這些候選解的值的值好于當前的最優解，則藐視準則被觸發，忽視禁忌狀態，用其替代當前解和最佳狀態，并納入禁忌表；若候選解均不好于最優解，則從候選解中找出最優，將其加入禁忌表中；如此不斷迭代上述過程，直至滿足停止準則。

禁忌搜索算法的核心問題有以下幾個：

（1）解的編碼

為了和蟻群算法更好的融合，禁忌搜索沿用了蟻群算法的編碼方式，即用自然數給工序排序，得到的自然數序列即為編碼。

（2）鄰域結構

采用互換操作隨機選擇編碼中不同的兩個基因進行交換。為保證交換后總能得到可行解，通過算法設計使得交換結果保證“屬于同一工件的不同工序不能發生變化”。

（3）終止準則

為保證算法的搜索范圍，采用連續m代最優解相同的終止準則。

3.3 融合原理與步驟

經過對上述兩種算法的原理與結構分析可知，這兩種算法具有以下共同性：

（1）概率型全局優化算法

交叉、狀態轉移、“輪盤賭”選擇等本質上都是基于概率的選取［9］，有利于在全局范圍內搜尋最優解。

（2）同為仿生元啟發式算法

蟻群算法和禁忌搜索均為基于仿生優化的元啟發式算法，適合大規模計算。

同時蟻群算法和禁忌搜索又具有各自的特點：

（1）蟻群算法特點

蟻群算法是基于生物群體啟發行為的隨機搜索優化方法，具有很強的解搜索能力和魯棒性［10］。正反饋特性能夠加快算法的進化速度，使其快速收斂；但蟻群算法也由于其正反饋特點容易陷入早熟陷阱，局部尋優能力有待提高。

（2）禁忌搜索算法特點

禁忌搜索采用禁忌方法，避免了算法選入局部最優，具有很強的局部搜索能力，但對初始解性能有很強的依賴，差的解會降低其收斂速度，甚至造成在有限時間內得不到可接受的解。

基于兩種算法的共同性和能夠產生互補增益的特點，進行蟻群禁忌搜索算法的融合來解決Job-shop問題，融合算法流程，如圖1所示。

圖1 融合算法流程圖Fig1.Fusion Algorithm Flow Chart

4 仿真與評價

4.1 基準實例仿真

為了驗證融合算法的性能，選取LA5作為基準實例進行仿真，該問題為10（工件）×5（機器）的經典Job-shop問題，經過融合算法得到最優調度序列，如圖2所示。

圖2 LA5調度結果甘特圖Fig2.Gantt Chart for Schedule of LA5

從圖上可看出最大完工時間（Makespan）為593，這也是LA5問題已知的最優解，證明了融合算法的可行性與有效性。

4.2 算法性能評價

將融合算法應用于Job-shop問題的5個基準實例，并與傳統算法得到的結果進行對比，如表1所示。

表1 算法結果對比Tab.1 Algorithms’Best Solution Comparison

可以看出，融合算法比傳統算法結果更要接近最優解，特別是在求解LA21、LA30等大型問題時，能夠得到更好的結果。

4.3 生產試驗

以營口HR公司的發動機混流裝配線上進行生產實驗，裝配關鍵工藝序列為“活塞環、活塞銷、后油封、油殼底、飛輪及離合器、凸輪軸、缸蓋螺栓、氣缸罩蓋、進氣管、正時系統”。以公司現有的同一平臺的7種不同產品為對象，運用蟻群禁忌搜索融合算法進行了生產調度，得到調度甘特圖，如圖3所示。

圖3 混流裝配線調度結果Fig3.Schedule of Mixed Assembly Line

調度得到的最大完工時間為773s，這一數據較現場現階段使用的傳統調度方案842s縮短了8.19%的裝配周期，證明了算法在實際生產調度中的有效性。

5 結束語

針對汽車發動機混流裝配線的調度問題進行研究，對問題進行了抽象和數學建模，應用蟻群禁忌搜索融合算法對模型進行求解，驗證了算法的有效性；同時基于基準實例仿真和生產試驗驗證了融合算法相對傳統算法的優越性，對于提升發動機缸體混流裝配生產線的效率有一定的實際意義。在已提出的融合算法基礎之上，元啟發式融合算法仍然有著廣闊的研究空間，例如蟻群算法部分的自適應信息素更新、禁忌搜索領域結構的優化等。