基于粒子群和蟻群混合算法的柔性車間調(diào)度算法

王昱欽

（江蘇自動化研究所信息技術(shù)研究部，江蘇連云港 222006）

隨著經(jīng)濟(jì)和社會的發(fā)展，工廠化生產(chǎn)已經(jīng)越來越普及。在流水線的生產(chǎn)過程中，合理安排工件的訂單和使用的機(jī)器可以使整個生產(chǎn)過程的時間和機(jī)器功率消耗降到最低，這也被稱為作業(yè)車間調(diào)度或作業(yè)車間問題（Job-shop Scheduling Problem,JSP）[1]。由于JSP 的優(yōu)化經(jīng)常涉及許多復(fù)雜的約束條件，并且這些條件往往是非線性的，因此傳統(tǒng)的線性規(guī)劃方法難以解決[2]。進(jìn)化算法由于其穩(wěn)健性和強(qiáng)大的適應(yīng)性，其已經(jīng)在眾多研究中顯示出處理復(fù)雜約束條件時的有效性。最近，關(guān)于JSP 的研究不僅在模型本身上得到了發(fā)展，而且在求解方法上取得了較大進(jìn)步。柔性工作車間調(diào)度問題（Flexible Job-shop Scheduling Problem,FJSP）是現(xiàn)代制造系統(tǒng)中經(jīng)典工作車間調(diào)度問題的一個實際有用的擴(kuò)展，它允許一個操作由給定的任何機(jī)器來處理[3]。

1 柔性工作車間調(diào)度問題

傳統(tǒng)的JSP 模型只考慮一個優(yōu)化目標(biāo)，一般是最小化整個過程的完成時間。然而，很多時候制造商對完工時間并不敏感，因為一般來說生產(chǎn)的最后期限總是多余的。相反，由于經(jīng)濟(jì)原因，較低的能源消耗通常被視為優(yōu)化目標(biāo)。近期，關(guān)注柔性作業(yè)車間調(diào)度問題的研究變得火熱，其中，黎陽[4]等人為解決大規(guī)模(工件數(shù)＞100)置換流水車間調(diào)度問題，提出一種改進(jìn)的模擬退火算法，并通過實驗進(jìn)行了驗證；李尚函[5]等人則提出一種混合超啟發(fā)式遺傳算法(HHGA)，考慮了最小化最大模糊完工時間，用于求解一類采用三角模糊數(shù)表示工件加工時間的模糊柔性作業(yè)車間調(diào)度問題。

在對FJSP 進(jìn)行求解時，已有的文獻(xiàn)大都只考慮了問題規(guī)模較小，復(fù)雜度不高的情況[6-8]。在一些復(fù)雜問題上，已有的文獻(xiàn)往往只注重于快速地收斂，而忽視了種群本身的多樣性問題。這就會導(dǎo)致種群早熟的問題[9]。具體來說，對于簡單的遺傳算法求解FJSP，算法在初期（前10 代），種群中的個體就變得幾乎一樣，大大降低了種群跳出局部最優(yōu)解的概率。另一方面，過早的收斂也會導(dǎo)致剩余的搜索變得無效。因此，為了解決這個問題，該文提出了一種全新的基于粒子群[10]和蟻群[11]的混合算法，具體來說，蟻群算法具有較好的局部搜索能力，而粒子群算法具有較強(qiáng)的全局搜索能力。通過將兩個算法進(jìn)行混合，可以在前期以較大概率采用粒子群搜索算法進(jìn)行初步探索，在這一階段，種群的收斂性不是算法的首要目標(biāo)。接著在算法運行的中后期，設(shè)置較大的概率，使用蟻群算法進(jìn)行局部探索。在這一階段，引入了局部搜索策略以提高種群的收斂能力。為了驗證該文所提算法的有效性，在一個規(guī)模較大的算例上進(jìn)行了對比實驗，實驗結(jié)果表明該文所提算法收斂能力較強(qiáng)。

JSP 是計算機(jī)科學(xué)和運籌學(xué)中的一個經(jīng)典優(yōu)化問題[12]，其中不同的工件需要在規(guī)定時間內(nèi)被分配到指定的機(jī)床上進(jìn)行加工，從而在規(guī)定時間內(nèi)完成所有的加工任務(wù)。為了簡潔地進(jìn)行表達(dá)，在該研究中給出了最基本的版本。給定n個處理時間不同的作業(yè)J1,J2,…,Jn，這些作業(yè)需要被安排在處理能力不同的機(jī)器上。安排的目標(biāo)是試圖使全部任務(wù)的完成時間最小化。makespan 是計劃的總長度（即所有工作都完成處理）。一般來說，該過程的目標(biāo)是使makespan 最小化。隨著制造業(yè)的發(fā)展，其他目標(biāo)也被考慮在內(nèi)，如能源消耗最小化，機(jī)床利用率最大化等[13]。柔性作業(yè)車間問題（FJSP）是經(jīng)典作業(yè)車間調(diào)度問題的擴(kuò)展，它允許一個任務(wù)由給定的任何機(jī)器來處理。文中考慮一個基于基本FJSP 的模型。在一個靈活的加工車間，有I種需要加工的工件類型，其中每一種都包含有Ji道工序，在這個車間里，機(jī)床的數(shù)量為M。

1.1 約束條件

為了更好地理解該文研究的柔性工作車間調(diào)度問題，使用i、j、m分別代表工件、工件工序和機(jī)器代碼的索引。

對于所有的工件，各工序之間存在著順序關(guān)系。也就是說，只有在前序工序完成后，才能在機(jī)床上加工后續(xù)工序。

對于所有的機(jī)床來說，在整個加工過程中，同一時間內(nèi)只能加工一個工件，這一點可以表示如下：

工件只有在截止時間前到達(dá)并完成后才能進(jìn)行加工。如式（3）所示：

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

對于一個傳統(tǒng)的工作車間調(diào)度問題，有幾個目標(biāo)。然而，該文考慮的是最常見的兩個目標(biāo)。一個目標(biāo)是最小化整個過程的makespan 時間，另一個目標(biāo)函數(shù)是最小化單位時間的功耗，可以表示為：

2 粒子群和蟻群混合算法

2.1 粒子群算法

粒子群優(yōu)化（Particle Swarm Optimization,PSO）算法是一類非常經(jīng)典的算法。近年來，針對粒子群算法的改進(jìn)非常多。標(biāo)準(zhǔn)的粒子群優(yōu)化同時使用當(dāng)前的全局最佳位置和個體最佳位置。使用個體最佳的原因之一可能是為了增加高質(zhì)量解決方案的多樣性。然而，這種多樣性可以用一些隨機(jī)性來模擬。因此，除非優(yōu)化問題是高度非線性和多模態(tài)的，否則沒有令人信服的理由去使用個體最佳位置。

2.2 蟻群算法

蟻群算法(ACO)的靈感來自于螞蟻的覓食行為。這種行為的核心是螞蟻之間在化學(xué)信息素軌跡的幫助下進(jìn)行間接交流，使得它們能夠找到巢穴和食物來源之間的短路徑。ACO 算法具有很強(qiáng)的魯棒性以及良好的分散計算機(jī)制。局部螞蟻有能力向具有最佳解決方案的潛伏區(qū)域移動，這與區(qū)域k的過渡概率有關(guān)。

2.3 粒子群和蟻群混合搜索

與其他基于啟發(fā)式算法的進(jìn)化算法相比，PSO的優(yōu)勢在于易于實施，需要調(diào)整的參數(shù)數(shù)量較少。然而，眾所周知，最初的PSO 在控制探索（全局搜索）和利用（圍繞局部最優(yōu)的精細(xì)搜索）之間的平衡方面存在困難。另一方面，現(xiàn)有的進(jìn)化算法由于缺乏種群多樣性保持機(jī)制，因此極容易陷入局部最優(yōu)解[14-15]。為了改善PSO 的這一特點，該文提出使用粒子群和蟻群的混合搜索策略（hACOPSO）。

具體來說，hACOPSO 算法的實現(xiàn)包含了兩個種群，分別對應(yīng)粒子群和蟻群算法的種群。在初始化階段，粒子的位置和螞蟻的位置一一對應(yīng)。在每一次迭代過程中，首先計算出螞蟻的信息素濃度，并根據(jù)過渡概率選擇搜索方式。當(dāng)過渡概率低于預(yù)設(shè)值時，使用基于蟻群算法的局部搜索策略進(jìn)行搜索；反之，則使用粒子群算法進(jìn)行大規(guī)模搜索。值得注意的是，在每一次搜索完之后，如果個體的目標(biāo)函數(shù)值比原來較好，則同時更新螞蟻和粒子的位置，從而推動算法向最優(yōu)解不斷前進(jìn)。

2.4 求解FJSP的編碼方法

應(yīng)用進(jìn)化算法對現(xiàn)實世界的問題進(jìn)行求解的主要問題是如何對解決方案進(jìn)行編碼[16]。對于傳統(tǒng)的作業(yè)車間調(diào)度問題，大多數(shù)研究采用基于工序的編碼。但是，在解決柔性作業(yè)車間調(diào)度問題時，還需要為每道工序選擇合適的機(jī)床進(jìn)行處理，較以往問題更加復(fù)雜。鑒于上述問題，該文提出了一種兩層染色體編碼方法，其示意圖如圖1 所示。一個染色體就是一個調(diào)度問題的解決方案。從圖中可以看出，第一層編碼（即工序碼）用于確定不同工件對應(yīng)工序的順序，第二層（即機(jī)器碼）用于確定工序的機(jī)床。

圖1 編碼方式

工件碼的基因總數(shù)等于所有工件的工序數(shù)之和。在圖1 中，工件碼的基因總數(shù)為8。每個工件的工序直接用相應(yīng)的工件編號編碼，工件的累計出現(xiàn)次數(shù)等于其工序數(shù)。染色體的工序編碼從左到右進(jìn)行掃描。

3 實驗

3.1 實驗案例

表1 列出了每臺機(jī)器的待機(jī)功率和空載功率。表2 說明了每個工件的到達(dá)時間和最后期限，可以看出，整個過程的最后期限是60 000 s。此外，在該研究中，有5 個工件需要被加工。每個工件工序的數(shù)量分別為3、4、3、4 和4。

表1 不同機(jī)床的待機(jī)和空載功率

表2 工件到達(dá)和截止時間

3.2 不同算法的收斂性對比

文中提出了一種粒子群和蟻群的混合搜索算法。為了驗證該算法的有效性，選擇標(biāo)準(zhǔn)的粒子群算法、蟻群算法和粒子群和蟻群混合搜索算法進(jìn)行對比。為了保證實驗的公平性，統(tǒng)一設(shè)置種群大小為100，迭代次數(shù)為100 次。為了降低隨機(jī)因素帶來的影響，將所有實驗獨立運行31 次并取平均值。選擇最接近算法平均值的單次運行結(jié)果被進(jìn)行分析和展示。

圖2 顯示了不同的算法在求解該文研究問題時的最優(yōu)解收斂情況。可以看出，粒子群和蟻群混合搜索算法優(yōu)于其他兩個算法。值得注意的是，混合算法在收斂速度和收斂精度上均表現(xiàn)較好。這是因為，混合算法結(jié)合了兩種搜索策略的優(yōu)勢，在全局搜索和局部搜索中均能采用最合理的方式進(jìn)行搜索，因此表現(xiàn)較好。

圖2 不同算法的收斂示意圖

3.3 結(jié)果分析

為了探究所提算法的有效性，將粒子群和蟻群混合搜索算法的最終求解結(jié)果展示如圖3 和圖4 所示。從圖3中可以看到，最小的完成時間是365 044 s，此時的能量消耗為1 233.3 kW·h。可以看到，工件5是最后完工的。這是因為算法試圖盡可能早地關(guān)閉機(jī)器，這是一個精明的策略，以盡量減少電力的使用。因為，當(dāng)機(jī)器處于閑置狀態(tài)時，會有空載功耗，這完全是一種浪費。通過對工作車間的調(diào)度進(jìn)行建模，并采用適當(dāng)?shù)膬?yōu)化算法，可以在一定程度上減少不必要的電力消耗。

圖3 注重功耗的工序甘特圖

圖4 注重完工時間的工序甘特圖

圖4 所示是更加注重完工時間的工序甘特圖，其最小完成時間為405 390 s，所需要的能量為1 245.6 kW·h。

4 結(jié)論

隨著社會和制造業(yè)的發(fā)展，作業(yè)車間調(diào)度問題已經(jīng)得到了有效的解決。然而，對于規(guī)模較大或者非線性系統(tǒng)來說，傳統(tǒng)的優(yōu)化算法容易陷入局部最優(yōu)中，且收斂速度較慢。為了進(jìn)一步提高進(jìn)化算法在此類問題的搜索效率，文中給出了一個柔性工作車間調(diào)度模型，并進(jìn)行了明確的說明。考慮兩個目標(biāo)來優(yōu)化這個模型，一個目標(biāo)是最小化整個制造過程的完工時間，另一個目標(biāo)是最小化能量使用。并且提出了一種基于粒子群和蟻群算法的混合算法進(jìn)行求解。通過實驗結(jié)果，證明混合算法具有更快的收斂速度和收斂精度。

進(jìn)一步的研究包括制作一個更詳細(xì)的模型來對生產(chǎn)進(jìn)行指導(dǎo)。此外，該文提出的方法不僅可以在工作車間調(diào)度問題上進(jìn)行，也可以擴(kuò)展到其他問題。因此，對這種算法的進(jìn)一步研究，使其更適合也更容易用于解決現(xiàn)實世界的問題。