蟻群禁忌搜索融合算法求解調(diào)度問題

劉博省，毛范海，錢 峰

（大連理工大學(xué)機械工程學(xué)院，遼寧 大連116024）

1 引言

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

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

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

2 JSP問題描述及其數(shù)學(xué)模型建立

2.1 Job-shop問題的描述

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

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

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

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

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

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

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

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

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

2.2 Job-shop的數(shù)學(xué)模型

Job-shop是許多實混流裝配線的簡化模型，也是目前研究非常廣泛的生產(chǎn)調(diào)度問題的簡化模型，其數(shù)學(xué)模型可表示為下：

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

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

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

3 融合算法原理與步驟

3.1 蟻群算法原理

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

故本研究采用狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新方法有所改進的蟻群系統(tǒng)（Ant Colony System）進行求解。

（1）改進的狀態(tài)轉(zhuǎn)移規(guī)則

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

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

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

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

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

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

3.2 禁忌搜索算法原理

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

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

（1）解的編碼

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

（2）鄰域結(jié)構(gòu)

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

（3）終止準則

為保證算法的搜索范圍，采用連續(xù)m代最優(yōu)解相同的終止準則。

3.3 融合原理與步驟

經(jīng)過對上述兩種算法的原理與結(jié)構(gòu)分析可知，這兩種算法具有以下共同性：

（1）概率型全局優(yōu)化算法

交叉、狀態(tài)轉(zhuǎn)移、“輪盤賭”選擇等本質(zhì)上都是基于概率的選?。?］，有利于在全局范圍內(nèi)搜尋最優(yōu)解。

（2）同為仿生元啟發(fā)式算法

蟻群算法和禁忌搜索均為基于仿生優(yōu)化的元啟發(fā)式算法，適合大規(guī)模計算。

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

（1）蟻群算法特點

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

（2）禁忌搜索算法特點

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

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

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

4 仿真與評價

4.1 基準實例仿真

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

圖2 LA5調(diào)度結(jié)果甘特圖Fig2.Gantt Chart for Schedule of LA5

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

4.2 算法性能評價

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

表1 算法結(jié)果對比Tab.1 Algorithms’Best Solution Comparison

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

4.3 生產(chǎn)試驗

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

圖3 混流裝配線調(diào)度結(jié)果Fig3.Schedule of Mixed Assembly Line

調(diào)度得到的最大完工時間為773s，這一數(shù)據(jù)較現(xiàn)場現(xiàn)階段使用的傳統(tǒng)調(diào)度方案842s縮短了8.19%的裝配周期，證明了算法在實際生產(chǎn)調(diào)度中的有效性。

5 結(jié)束語

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