基于改進PSO的壓鑄自動化生產線優化調度

陶麗華，遲曉晨，谷東偉

（長春工業大學 機電工程學院，長春 130012）

0 引言

隨著信息技術和人工智能的發展，智能制造作為“中國制造2025”國家戰略的重要舉措，已經引起各個行業的廣泛關注[1]。鑄造行業作為制造業的重要基礎產業，迫切需要進行智能化轉型升級，壓鑄自動化生產線（Die casting automatic production line，簡稱DAPL）已成為現代壓鑄企業提高生產效率、消除重體力勞動和清潔環境的重要舉措。多品種小批量DAPL智能調度屬于一類帶有運輸機約束的并行機調度問題（Parallel Machine Scheduling Problem，PMSP），運輸機作為原料供應站與壓鑄機之間的紐帶，確定合適的運輸機速度，優化原料到各壓鑄機的調度序列，實現原料在各壓鑄機之間無障礙流轉，減少壓鑄機的空閑等待時間，對于壓鑄企業實現清潔生產、提高生產效率、降低成本具有重要的現實意義。

1 基于多目標的DAPL調度數學模型建立

1.1 問題描述

某鋁制品DAPL由一臺運輸機和多臺不同類型的壓鑄機組成，運輸機為各壓鑄機服務，每次運送一個坩堝的高溫鋁液到某一壓鑄機進行壓鑄生產。DAPL調度問題是一類帶有運輸機約束的異構并行機調度問題，可描述為：1）有多臺機器，每臺機器生產與自身模具對應的一種類型的鋁件，產出的鋁件可自動進入后續產線。2）每個坩堝的鋁液只在一臺機器上壓鑄生產，產出一定數目的某類鑄件。所有坩堝的鋁液容量是相同的，每個坩堝的鋁液可被運往機器集中的任一臺機器上生產。3）同一時刻一臺壓鑄機只能對單位坩堝鋁液進行操作加工。4）每個坩堝的鋁液在機器的生產過程中是不可中斷的。5）假定運輸機是勻速的，運輸機每次從供應站運送一個坩堝的鋁液到機器，然后，運輸機返回供應站繼續運輸，運輸機在供應站和機器之間的運輸過程是不可中斷的。

1.2 符號定義

為了準確描述DAPL調度問題的數學模型，定義符號如下：hT為每日工作時間；M為機器集合；m為機器數量；N為hT內完成的坩堝鋁液集合，坩堝數量nc；n為鋁件的類型數，n等于m；OMj為單位坩堝鋁液在機器j上的產出鋁件數；nj為j機器計劃產出鋁件數量，假定數值是OMj的整數倍；v為運輸機速度；vmin為運輸機速度最小值；vmax為運輸機速度最大值；DSj為供應站與j機器的距離；yTj為運輸機在供應站和j機器之間的運輸時間；mTi，j為i坩堝鋁液在機器j上的壓鑄時間；BTi，j為i坩堝鋁液在機器j的開始時間，i=1，2，...，nc，j=1，2，...，m；ETi,j為i坩堝鋁液在機器j的完成時間，i=1，2，...，nc，j=1，2，...，m；aBTi,j為運輸機運送i坩堝鋁液從供應站到機器j的出發時間，i=1，2，...，nc，j=1，2，...，m）；aETi,j為運輸機運送i坩堝鋁液從供應站到達機器j后，返回供應站的時間；Mi為i坩堝鋁液的加工機器；Cj為機器j上最后一個坩堝的完工時間；xi,j=1時，i坩堝在機器j上生產；xi,j=0時，i坩堝不在機器j上生產。

1.3 DAPL多目標調度數學模型

在DAPL中運輸機速度的改變直接影響運輸機運送鋁液到達機器的時間，從而影響坩堝鋁液的生產調度。為了提高DAPL的效率，需要確定合理的運輸機速度和坩堝鋁液的機器調度序列，避免因運輸機速度過快而造成鋁液溢出，并避免因速度過慢而增加機器的空閑等待時間，在規定的時間段和機器計劃產量的約束下，以機器總空閑時間最短、設備負荷均衡、最大化產出鋁件數和最小化運輸機等待時間為目標，并采用加權平均法建立DAPL優化調度的多目標數學模型。

1）以所有壓鑄機的總空閑時間最少作為優化目標f1如式（1）：

其中：式（2）表示每臺機器的結束時間，式（3）指運輸機勻速運行，式（4）指第1個坩堝鋁液進入系統的時刻0，式（5）指運輸機在供應站和機器之間運輸過程不可中斷，式（6）指每坩堝鋁液一旦開始生產就不能中斷，式（7）指每臺機器同一時刻只能加工一個坩堝鋁液，式（8）和式（9）指速度和時間限制。

2）設備負荷的均衡程度定義為優化目標f2，如式（10）所示，設備負荷的均衡程度用各機器負荷的方差表示，各機器負荷的均值如式（11）所示：

3）以所有機器產出的鋁件數為優化目標f3，由于f1和f2這兩個目標的優化是求解最小化問題，為了使f3目標的優化與f1和f2保持一致，將f3目標的最大化問題轉化為最小化問題，如式（12）所示。其中，B為忽略運輸機的所有機器在hT時間段產出鋁件的數量，如式（13）所示，式（14）指每臺機器產出鋁件的數量受制于計劃產量要求：

4）在運輸過程中，為了使鋁液在坩堝中保持盡量平穩，運輸機的速度越小越好，運輸機速度越小，運輸機總等待時間越短，定義運輸機的總等待時間為優化目標f4，如式（15）所示：

2 改進粒子群算法設計

2.1 改進粒子群算法流程

為了提高壓鑄自動化生產效率，減少設備的空閑等待時間，實現一個流的均衡生產和清潔生產，依據1.3節數學模型，在標準粒子群算法（Particle Swarm Optimization，簡稱PSO）的基礎上提出一種改進的粒子群算法求解DAPL中運輸機速度及調度優化問題。在粒子進化過程中，速度的更新依賴個體極值和群體極值，容易造成算法的提前收斂，因此將一定數量的較好的個體極值和群體極值保存起來，分別建立個體極值庫和群體極值庫。針對每一個當前粒子，分別將個體極值庫中的每一個個體極值和群體極值庫中的每一個群體極值配對，利用每一對個體極值和群體極值對當前粒子進行速度和位置的更新，可得到多個臨時粒子，并采用模擬退火算法（Simulated Annealing，簡稱SA）對每個臨時粒子進行局部尋優，根據優化后的臨時粒子更新個體極值庫，并將最優臨時粒子作為當前粒子的新一代粒子。以每一代粒子群的個體極值庫更新群體極值庫。個體極值庫、群體極值庫的建立與基于SA的優化改進提高了PSO的搜索效率和尋優能力。改進粒子群算法流程如圖1所示。

圖1 改進粒子群算法流程

2.2 改進粒子群算法的操作設計

1）粒子的編碼和初始粒子群的生成。每一個粒子的位置采取一維實數進行編碼操作，實數值即為運輸機的運輸速度。給定粒子位置和速度的搜索范圍，為了保證初始粒子群的多樣性，在該范圍內隨機生成初始位置與初始速度[2]。

2）適應度函數的設計。以綜合目標值的大小評價粒子的優劣[3]，適應度函數G(v)定義見式（20）：

3）粒子的更新。粒子的更新分為粒子的速度更新和位置更新[4]，速度更新如式（21）所示，位置更新如式（22）所示。在速度更新中，通過擾動因子δ干預個體極值和群體極值，避免算法提前收斂，提高算法的開發能力，并引入動態慣性權重w均衡算法的搜索能力，w的取值與進化代數gen有關，如式（23）所示。動態慣性權重w使算法在進化的早期以較大慣性繼承粒子當前的速度，搜索力度較大，從而實現全局搜索；在后期算法以較小慣性繼承粒子當前速度，使算法盡快收斂于全局最好解[5]。

式中：wmin∈(0,1]；c1和c2為學習因子；piD為i粒子的個體極值；pgD為群體極值；gen為當前代數；maxgen為最大代數。

4）基于SA算法的局部尋優[6]。在粒子的更新過程中，將當前粒子作為初始解，采用SA算法對當前粒子進行小范圍細致搜索，以提高算法的局部尋優能力。

5）保優策略。在每一代粒子更新后，通過個體極值庫的更新記錄粒子到目前為止遍歷過的10個最好位置，并根據所有個體極值庫的最優粒子中的前4個粒子更新群體極值庫，使得全局最優粒子始終保留在群體極值庫當中，避免了最優粒子在算法進化過程中丟失。

6）停止準則。當算法運行至最大代數時終止，輸出最優粒子對應的運輸機速度和該速度下運輸機運送坩堝的最優調度序列。

3 實驗仿真

3.1 實例驗證

某鋁制品壓鑄自動化生產線由5臺壓鑄機、1臺運輸機和1個供應站組成，運輸機負責將高溫鋁液運送到各壓鑄機，設備信息如表1所示。采用本文提出的改進粒子群算法確定運輸機的最佳速度和每日各坩堝鋁液的調度分配序列。

表1 設備信息

假定每日工作時間為8 h（即480 min），各優化目標權重及比例系數如表2所示，粒子群規模為50，學習因子c1和c2均為1.494 45。慣性權重w取值范圍為[0.4,0.9][7]，擾動因子為0.01，運輸機速度范圍為[10，30] m/min，個體極值庫的規模為10，群體極值庫的規模為4，算法運行100代。SA的初始溫度為100 ℃，停止溫度為20 ℃，降溫速率為0.9，等溫鏈長為30。各目標的收斂曲線如圖2所示，其中星號代表最優解，括號中左側數據為目標最優時的代數，右側數據為目標值。

表2 目標的權重及比例系數

由圖2可見，隨著代數的增加，算法運行到第4代時總目標收斂于最小值717.5194，此時運輸機最佳速度收斂于21.9968 m/min，機器總空閑時間收斂于38.197 min，各機器負荷的方差在第1代就收斂于24，各機器產出鋁件數在第1代就收斂于622個，運輸機等待時間在第4代收斂于274.53 min。坩堝鋁液在各機器上的最優分配序列如表3所示，表3顯示當日58個坩堝鋁液的設備分配情況，基于設備的調度甘特圖如圖3所示。

圖2 各目標收斂曲線

圖3 基于設備的調度甘特圖

表3 坩堝-設備的調度分配

由圖3可見，運輸機和壓鑄機的調度采用不同的顏色表示，在壓鑄機上每個矩形框代表某坩堝鋁液在機器上的停留時間，上邊的數字代表坩堝鋁液的序列號，例如壓鑄機1生產坩堝鋁液的順序依次為5、9、14、19…。由圖3可直觀看出，在運輸機速度達到21.9968 m/min時，各機器幾乎滿負荷工作，總空閑時間較少，僅為38.197 min，各機器負荷比較均衡，在8 h內各機器共完成58個坩堝鋁液的生產，共產出鋁件數622件。運輸機作為瓶頸設備需要不停地在各機器間流轉，運輸機上每個矩形框代表運輸機為了運送某坩堝鋁液到機器，從供應站到機器再返回到供應站的時間，雖然運輸機比較繁忙，但當運輸機達到最佳速度21.9968 m/min時，運輸機的總空閑時間最短為274.53 min。因此，采用本文提出的改進粒子群算法較好地解決了某壓鑄自動化生產線運輸機最佳速度的求解問題，降低了各壓鑄機的總空閑時間，實現了壓鑄自動化生產線一個流的均衡生產。

3.2 算法的性能驗證

Rosenbrock函數又稱為香蕉函數，是用來評價算法搜索性能的著名測試函數[8]，函數式如式（24）。該函數的特點是在[100,100]n上只有一個全局極值點，且在全局極小點臨近的狹長區域內取值變化極為緩慢[9]，如圖4所示，常用該函數評價粒子群優化算法的搜索性能：

圖4 Rosenbrock函數圖

為了測試本文提出的改進粒子群算法的尋優性能，利用本文提出的改進粒子群算法分別求解維度為30、100、500、1000的Rosenbrock函數的極值點，粒子群規模為30，算法進化500代，SA的初始溫度為100 ℃，停止溫度為20 ℃，降溫速率為0.9，等溫次數為30，運行100次。運行結果與文獻[10]之間的對比如表4所示，文獻[10]采用花授粉算法求解各維度下的Rosenbrock函數問題。由表4可見，在求解不同維度的Rosenbrock問題時，本文提出的改進粒子群算法在100次運行結果的均值、最好解、最差解和標準差都遠遠優于文獻[10]的算法。由此可見，本文提出的改進粒子群算法具有較強的尋優性能和穩定性。

表4 兩種算法數據對比

4 結論

壓鑄自動化生產線屬于典型的異構并行機調度問題，其運輸機最佳速度的確定直接影響生產線的效率和生產環境。本文以設備總空閑時間、設備負荷均衡、產出鋁件數和運輸機等待時間為目標，建立了DAPL多目標優化調度數學模型，提出了一種性能和尋優效率較好的改進粒子群算法對DAPL優化調度問題進行優化求解，滿足了壓鑄自動化生產線一個流的均衡生產需求。在實際生產過程中，由于運輸機的速度不一定是勻速的，若將運輸過程中的加速和減速過程考慮進去，將更符合DAPL的生產實際。