基于粒子群和蟻群混合算法的柔性車間調度算法

王昱欽

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

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

1 柔性工作車間調度問題

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

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

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

1.1 約束條件

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

對于所有的工件，各工序之間存在著順序關系。也就是說，只有在前序工序完成后，才能在機床上加工后續工序。

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

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

1.2 目標函數

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

2 粒子群和蟻群混合算法

2.1 粒子群算法

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

2.2 蟻群算法

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

2.3 粒子群和蟻群混合搜索

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

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

2.4 求解FJSP的編碼方法

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

圖1 編碼方式

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

3 實驗

3.1 實驗案例

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

表1 不同機床的待機和空載功率

表2 工件到達和截止時間

3.2 不同算法的收斂性對比

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

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

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

3.3 結果分析

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

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

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

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

4 結論

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

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