求解多Hoist循環(huán)調度問題的帝國主義競爭算法

毛永年，唐秋華，張利平

（1.遵義師范學院工學院，貴州 遵義 563000；2.武漢科技大學冶金裝備及其控制教育部重點實驗室，湖北 武漢 430081；3.武漢科技大學機械傳動與制造工程湖北省重點實驗室，湖北 武漢 430081）

1引言

Hoist調度問題[1]來源于以生產印刷電路板（Printed Circuit Board，PCB）為代表的電鍍生產線。

印刷電路板（PCB）是計算機、手機、以及幾乎所有自動化設備的重要元器件。在制造PCB的電鍍工藝環(huán)節(jié)，工件（半成品）需要依次經歷多個處理槽以完成必備的工藝要求。工件在這些處理槽中的加工過程具有一定的柔性，即工件的加工時間可以在給定的上下限范圍內變動。工件的這種允許變動的加工時間范圍被稱為時間窗口。受計算機編程控制的Hoist必須在給定的時間窗口內，將工件從當前處理槽轉移到其下一工序所在的處理槽；否則，工件將會因為制造缺陷而產生質量問題。為了便于管理，自動化的電鍍生產線常采用循環(huán)生產模式，即Hoist在每一個生產循環(huán)內執(zhí)行相同的搬運作業(yè)序列以完成大批量工件的生產。因此，規(guī)劃與調度Hoist搬運作業(yè)對系統(tǒng)的生產效率、產品質量有重要影響。為了克服由運輸設備（Hoist）造成的生產瓶頸，同一條軌道上通常安裝有多臺Hoist以協(xié)同完成電鍍生產線上的運輸作業(yè)。典型的多Hoist電鍍生產線布局，如圖1所示。圖中，處理槽呈線性排列，且工件的入口和出口在同一個位置，在處理槽上方的軌道上，多臺Hoist同時保持運行。

雖然，多臺Hoist協(xié)同作業(yè)可以顯著提高電鍍生產線的生產效率[2-3]，但同時也增加了調度Hoist搬運作業(yè)的難度。首先，相比于基本的單Hoist調度問題[1]，多Hoist調度不僅要決策搬運作業(yè)的執(zhí)行時間，同時還要決策Hoist的分配，從而使得問題規(guī)模變得更為龐大。此外，由于多臺Hoist在同一條軌道上運行，必須處理它們之間潛在的碰撞沖突，從而增加了調度的復雜性。

圖1 多Hoist電鍍生產線示例Fig.1 The Example of Electroplating Production Line with Multiple Hoists

文獻[3]首次提出了多Hoist循環(huán)調度問題的混合整數(shù)線性規(guī)劃（MILP）模型。針對該模型中Hoist搬運作業(yè)不能跨越周期的缺陷，文獻[4]提出了一個改進的MILP模型以完善文獻[3]的模型。針對具有雙向工件運輸流的電鍍生產線，文獻[2]分析了多種Hoist避碰條件，提出了該問題的MILP模型以及基于混合整數(shù)規(guī)劃的分支定界算法。此外，基于啟發(fā)式的求解方法[5-6]被提出以求解針對只有兩臺Hoist的循環(huán)調度問題。由于時間窗口約束使得該類問題的可行解空間十分有限，研制針對此類問題的元啟發(fā)式算法變得極為困難?，F(xiàn)有的相關研究[7-9]僅考慮一個運輸資源（Hoist/Robot）的情形。針對多Hoist調度，文獻[10]將電鍍生產線劃分為若干個互不重疊的區(qū)域，每臺Hoist只負責一個區(qū)域內的搬運作業(yè)，并使用模擬退火算法求解最佳的區(qū)域劃分方法。然而，由于區(qū)域劃分的方法限制了Hoist可能的移動區(qū)域，因而該方法不具有最優(yōu)性。此外，區(qū)域劃分的方法不適合的具有雙向工件流的電鍍生產線，如圖1所示。

首次提出使用基于群智能的元啟發(fā)式算法（帝國主義競爭算法）求解考慮具有重疊區(qū)域的多Hoist/Robot循環(huán)調度問題。首先，基于搬運作業(yè)的最小時間間隔法建立該問題的MILP模型?？紤]到此類問題的可行解空間極為有限這一特點[8]，在設計算法時，提出在給定Hoist分配條件下的啟發(fā)式目標函數(shù)以引導種群向有利方向進化。同時，為了提高算法搜索效率和求解質量，針對種群進化過程中產生的大量不可行解，提出基于Hoist分配的可行解修復策略以修復搬運作業(yè)的優(yōu)先關系。最后，與專業(yè)優(yōu)化軟件CPLEX以及遺傳算法的對比測試結果驗證了所提出的方法的有效性。

2 問題描述和數(shù)學模型

研究圖1所示的電鍍生產線，包括m臺Hoist、n個處理槽。其中裝載站0和卸載站（n+1）同在一個位置。Hoist的編號從左到右依次是1、2、…、m。每個工件自裝載站進入系統(tǒng)，依次經歷從處理槽1到處理槽n，最后被Hoist運輸?shù)叫遁d站。裝載/卸載站的容量設為無限大。處理槽1至n的容量為1個工件。由于處理槽之間沒有緩沖設施，工件在當前處理槽完成加工后（必須滿足時間窗口約束），須立即被Hoist運輸?shù)较乱粋€工序所在的處理槽。

文獻[2]基于搬運作業(yè)的最小時間間隔法構建了具有無碰撞約束的最優(yōu)化MILP模型，為了研究方便，對該模型進行了簡化處理，并使用如下定義：

搬運作業(yè)i—Hoist將工件從處理槽i上取出，然后將其搬運到處理槽i+1，最后將其卸載到該處理槽內的全部過程，0≤i≤n；

Li—工件在處理槽i上的最小處理時間，0≤i≤n；

Ui—工件在處理槽i上的最大處理時間，0≤i≤n；

di—執(zhí)行搬運作業(yè)i所需的時間，0≤i≤n；

αh—搬運作業(yè)i的優(yōu)先級高于搬運作業(yè)j時，執(zhí)行此兩項搬

ij運作業(yè)的最小時間間隔。其中h=q-p，p、q分別為執(zhí)行搬運作業(yè)i和j的Hoist編號。

M—足夠大的正數(shù)。

該問題的決策變量為：

T—周期長度；

ti—執(zhí)行搬運作業(yè)i的開始時間，0≤i≤n；

0≤i≤n，1≤k≤m；

文獻[2]模型的簡化版可以表示為：

模型的目標函數(shù)是最小化周期長度T。式（1）表示任何一項搬運作業(yè)只能分配給一臺Hoist。式（2）強調任意兩個搬運作業(yè)之間只有唯一一種優(yōu)先關系。式（3）～式（6）為時間窗口約束。當yi-1，i=1時，式（3）～式（4）強調工件的加工時長不小于允許的最小加工時間Li同時不大于允許的最大加工時間Ui。當yi-1，i=0時，工件在處理槽i上的加工跨越了兩個周期，那么工件的實際加工時長為（ti+T）-（ti-1+di-1）。式（5）～式（6）表示，當yi-1，i=0時，工件的加工時長同樣不小于允許的最小加工時間Li，同時不大于允許的最大加工時間Ui。式（7）～式（9）是與Hoist移動軌跡相關的約束。假設Hoist p執(zhí)行搬運作業(yè)i、Hoist q執(zhí)行搬運作業(yè)j（即zip=zjq=1），式（7）表示當搬運作業(yè)i的優(yōu)先級高于搬運作業(yè)j時（即yij=1），搬運作業(yè)i、j的開始時間間隔tj-ti不小于參數(shù)αq-pij，從而保證執(zhí)行搬運作業(yè)i、j的Hoist有足夠的時間來完成相應的移動或者避免潛在的碰撞沖突。當yij=0時，式（8）與式（7）的情形相反。式（9）保證Hoist移動軌跡在兩個周期之間的連續(xù)性，即：在完成上一周期內的搬運作業(yè)后，每一臺Hoist都有足夠的時間回到下一個周期的起始位置。不失一般性，式（10）表示任何搬運作業(yè)的開始時間必須在一個周期［0，T）的調度域內。

3 改進的帝國主義競爭算法

帝國主義競爭算法（ImperialistCompetitive Algorithm，ICA）[11]是一種受社會行為啟發(fā)的群智能隨機搜索算法，該算法在調度及優(yōu)化等領域得到廣泛應用[12]。與遺傳算法[13]相比，ICA的多種群進化機制使得算法不易陷入局部最優(yōu)。利用該特點，同時將遺傳算法（GA）的交叉、變異操作引入到ICA的同化機制中，使得改進的帝國主義競爭算法同時具有GA的特征。

3.1 編碼方式

圖2 編碼示例Fig.2 An Example of Coding

染色體編碼由兩部分組成，分別用序列μ=｛h0，h1，…，hn｝與λ=｛x0，x1，…，xn｝序列表示種群中任意一條染色體。序列μ中的第i個基因hi對應執(zhí)行搬運作業(yè)i的Hoist編號；序列λ中的第i個基因xi所擁有的搬運作業(yè)優(yōu)先級為i。序列λ中的搬運作業(yè)越靠前，其優(yōu)先級越高。用8項搬運作業(yè)為例說明了此編碼方式，如圖2所示。在圖2中，由于基因“2”分別在序列μ中的第0、2、5個位置出現(xiàn)，因此，編號為0、2、5的搬運作業(yè)分配給2號Hoist執(zhí)行。其次，由于此三項任務在序列λ中出現(xiàn)的順序為2、0、5，因此，2號Hoist按照此順序依次執(zhí)行這三項搬運任務。同理，可獲得其它Hoist的搬運作業(yè)以及排序。此外，根據(jù)搬運作業(yè)在序列λ中出現(xiàn)的先后順序，也可獲得由不同Hoist執(zhí)行的搬運作業(yè)之間的優(yōu)先關系。

3.2 啟發(fā)式評價函數(shù)

所研究問題的標準目標函數(shù)為：

當搬運作業(yè)優(yōu)先關系序列λ和Hoist分配序列μ為已知時。式（1）～式（10）則可轉換為如下形式：

式中：a—實數(shù)，b的取值為-1、0或者1。

事實上，式（12）是一類特殊的線性規(guī)劃問題，可以用賦權有向圖來描述[7-8]。文獻[14]提出了計算復雜度為o（n2m log n）的多項式算法以求解此問題，此處n為圖中節(jié)點數(shù)量，m為圖中弧的數(shù)量。為了提高算法運行效率，在使用文獻[14]中的多項式算法求解染色體（u，λ）的最短周期T之前，可先對染色體（u，λ）進行可行性判斷。如果該染色體不可行，則可直接設置f1=T0，其中

染色體（u，λ）的不可行主要由Hoist移動能力不能滿足工件的加工時間窗口所導致。當yi-1，i=1時，若序列｛x0，…，i-1→…→i，…，xn｝中從搬運作業(yè)i-1到搬運作業(yè)i的優(yōu)先關系序列不可行，則染色體（u，λ）一定不可行；當yi-1，i＝0時，若序列｛i-1→…xn|x0→…→i｝中從搬運作業(yè)i-1到搬運作業(yè)i的優(yōu)先關系序列不可行，染色體（u，λ）也一定不可行。為了方便描述，定義序列Sj為序列λ中分別以搬運作業(yè)i-1開始、搬運作業(yè)i結束的一串有序優(yōu)先關系子序列。由于一個循環(huán)序列λ包含n個Sj，因此，任意一個子序列不可行都會導致整條染色體不可行。交叉、變異操作會產生大量的不可行解，這些不可行解隱含了種群的進化信息，為了區(qū)分這些不可行解，記參數(shù)ω為所有不可行子序列S的個數(shù)之和，并采用式（13）計算不可行染色體的適應度值。

為了統(tǒng)一染色體適應度值的計算，采用公式（14）來計算任意一條染色體的適應度值。

對于序列Sj，可采用的算法來判斷其可行性，如圖3所示。

圖3 子序列的可行性判斷Fig.3 Feasibility Judgment of Subsequence

3.3 同化與競爭

同化、競爭是ICA的兩個進化機制。在ICA中，帝國和其所屬的殖民地可以看成一個獨立的種群。種群中適應度值最好的一條染色體（解）被視為帝國，其它染色體都為其殖民地。每個帝國（種群）的進化是通過其內部的同化機制實現(xiàn)的。而帝國之間爭奪殖民地的過程被成為競爭，該過程體現(xiàn)了帝國（種群）之間的信息交流。在標準的ICA中，同化是所屬殖民地全部向帝國靠近的過程。引入遺傳算法的進化機制實現(xiàn)此過程。具體的，利用錦標賽選擇法進行選擇操作，針對搬運作業(yè)的優(yōu)先關系序列λ使用雙點交叉操作，如圖4所示。針對與之對應的Hoist分配序列μ使用單點交換交叉操作，如圖5所示。針對序列λ的變異操作使用Swap變異，即隨機選擇兩個基因位置并交換其基因，針對序列μ則使用隨機變異。

圖4 針對序列λ的雙點交叉操作Fig.4 Two-Point Crossover for Sequenceλ

圖5 針對序列μ的交換交叉操作Fig.5 Swap Crossover for Sequenceμ

使用標準的ICA競爭機制，即勢力最大的帝國奪取勢力最小的帝國中最弱的殖民地個體，因此，各帝國殖民地的規(guī)模在競爭中動態(tài)變化?？紤]到所研問題可行解空間極少這一特點，設置一個參數(shù)ρ（0<ρ<1），ICA在每次迭代中以小于ρ的概率進行競爭操作，從而適當控制殖民地掠奪這一過程，以盡可能的維持種群的多樣性。

3.4 給定Hosit分配時的不可行解修復策略

由于算法進化過程會產生大量的不可行解，針對不可行解的修復策略對提高算法的運行效率十分關鍵。在給定Hosit分配時，僅僅修復序列λ的某個特定子序列Sj往往會導致序列λ的其它子序列不可行，從而影響到修復策略的實際效果。這里提出，在修復不可行子片段Sj時，采用聯(lián)動機制，即在修復Sj子片段后同時修復與其相關的上游子片段Sj-1或者下游子片段Sj+1，并根據(jù)搜索進程不斷更新修復目標S，直到滿足終止條件。同時，使用方向禁忌表v記錄序列λ中各基因的移動方向，從而避免迂回搜索。針對序列λ的修復策略具體列出，如圖6所示。

圖6 不可行解修復策略Fig.6 Repair Strategy for Infeasible Solution

3.5 改進的帝國主義競爭算法步驟

綜上所述，設計的帝國主義競爭算法步驟如下：

Step1：設置種群總規(guī)模Npop、帝國主義國家數(shù)量Nimp、競爭概率ρ、交叉概率Pc、變異概率Pm、最大修復循環(huán)次數(shù)η。

Step2：隨機初始化種群，平均分配殖民地。

Step3：對帝國Ci（1≤i≤Nimp）進行評價，保存帝國Ci新產生的最好解。如果帝國Ci沒有新的最好解產生，則應用精英保留策略，即：用帝國Ci的歷史最好解隨機替換Ci的一個殖民地。

Step4：更新全局最優(yōu)解。如果滿足終止條件則算法停止；否則，進入下一步。

Step5：對帝國Ci（1≤i≤Nimp）進行同化、競爭操作。

Step6：對種群中的不可行解進行可行性修復。跳轉到Step3。

4 算法驗證

為了驗證算法的性能，在CPU為3.2GHz的PC機上使用C++語言對改進的ICA進行編碼。同時，將遺傳算法（GA）作為對照項。GA使用與ICA相同的交叉、變異操作。此外，在Microsoft Visual Studio 2010軟件平臺下調用專業(yè)優(yōu)化軟件IBM ILOG CPLEX（版本12.5）求解MILP模型以獲得案例的最優(yōu)解。

標桿案例P&U[1]的測試結果，如表1所示。該案例的參數(shù)設置與文獻[2]相同。ICA的相關參數(shù)設置為：Npop=60，Nimp=3，ρ=0.1，Pc=0.9，Pm=0.1，η=3。針對GA，除了設置Nimp=1以外，其它參數(shù)設置與ICA相同。ICA和GA的終止條件為：全局最優(yōu)解連續(xù)200代不更新則終止。

表1 標桿案例P&U的測試結果Tab.1 The Result of Benchmark Instance P&U

從表1可以看出，GA和ICA在較快的時間內給出了標桿案例在m=1和m=3時的最優(yōu)解；當m=2時，ICA給出了最優(yōu)解而GA給出了近優(yōu)解。

為了進一步驗證算法的性能，使用CPLEX、GA、ICA求解了問題規(guī)模n分別為10、12、14、16、18時的隨機案例。隨機案例的設計方法與文獻[2]相同。ICA的相關參數(shù)設置為：Npop=100，Nimp=4，ρ=0.1，Pc=0.9，Pm=0.1，η=5。針對GA，除了設置Nimp=1以外，其它參數(shù)則與ICA相同。終止條件為：迭代次數(shù)達到200（n-5）代終止。針對每一個問題規(guī)模，30項隨機案例求解結果的平均值，如圖7、表2所示。

圖7 GA和ICA所獲得的最好解與最優(yōu)解的平均百分偏差Fig.7 The Mean Gap（%）of Solusion by GA and ICA Compared with the Optimal Solution

從圖7可以看出，當m=1時，GA和ICA每次都能獲得最優(yōu)解。這表明所提出的算法針對帶時間窗口的單Hoist循環(huán)調度問題十分有效。當m=2、3時，GA和ICA所獲得的結果與最優(yōu)解有一定的偏差，ICA的結果要優(yōu)于GA。此外，針對同樣的問題規(guī)模，算法的偏差并沒有因為Hoist數(shù)量的持續(xù)增加而擴大。相反，m=3時算法所獲得的結果要明顯比m=2時更接近最優(yōu)解。

表2 隨機案例的平均運行時間/sTab.2 The Mean CPU Time（s）for the Random ly Generated Instance

另一方面，從表2所給出的運行時間來看，ICA的求解時間要略大于GA的求解時間。此外，在求解小規(guī)模問題時，CPLEX表現(xiàn)出了較快的求解速度。但是，由于問題的解空間隨著m或n的增大而快速擴大，當m與n增長到一定程度時，CPLEX的求解時間則要遠遠大于群智能算法（ICA/GA）所需要的運行時間。因此，ICA/GA在求解中等或者大規(guī)模問題時展現(xiàn)出了較強的優(yōu)勢。

5 結論

首次提出基于群智能的元啟發(fā)式算法（ICA）求解帶時間窗口的多Hoist循環(huán)調度問題。將Hoist搬運作業(yè)的優(yōu)先關系以搬運作業(yè)序列的方式來表達，以方便處理Hoist無碰撞約束。提出了在給定Hoist分配條件下的啟發(fā)式目標函數(shù)，同時，針對種群進化過程中產生的大量不可行解，提出了搬運作業(yè)優(yōu)先關系的修復策略以提高算法的搜索效率以及求解精度。最后，基于標桿案例和隨機案例，分別與專業(yè)優(yōu)化軟件CPLEX以及遺傳算法進行對比，測試結果驗證了所提出的方法的有效性。