基于改進(jìn)PSO的壓鑄自動化生產(chǎn)線優(yōu)化調(diào)度

陶麗華，遲曉晨，谷東偉

（長春工業(yè)大學(xué) 機電工程學(xué)院，長春 130012）

0 引言

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

1 基于多目標(biāo)的DAPL調(diào)度數(shù)學(xué)模型建立

1.1 問題描述

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

1.2 符號定義

為了準(zhǔn)確描述DAPL調(diào)度問題的數(shù)學(xué)模型，定義符號如下：hT為每日工作時間；M為機器集合；m為機器數(shù)量；N為hT內(nèi)完成的坩堝鋁液集合，坩堝數(shù)量nc；n為鋁件的類型數(shù)，n等于m；OMj為單位坩堝鋁液在機器j上的產(chǎn)出鋁件數(shù)；nj為j機器計劃產(chǎn)出鋁件數(shù)量，假定數(shù)值是OMj的整數(shù)倍；v為運輸機速度；vmin為運輸機速度最小值；vmax為運輸機速度最大值；DSj為供應(yīng)站與j機器的距離；yTj為運輸機在供應(yīng)站和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坩堝鋁液從供應(yīng)站到機器j的出發(fā)時間，i=1，2，...，nc，j=1，2，...，m）；aETi,j為運輸機運送i坩堝鋁液從供應(yīng)站到達(dá)機器j后，返回供應(yīng)站的時間；Mi為i坩堝鋁液的加工機器；Cj為機器j上最后一個坩堝的完工時間；xi,j=1時，i坩堝在機器j上生產(chǎn)；xi,j=0時，i坩堝不在機器j上生產(chǎn)。

1.3 DAPL多目標(biāo)調(diào)度數(shù)學(xué)模型

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

1）以所有壓鑄機的總空閑時間最少作為優(yōu)化目標(biāo)f1如式（1）：

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

2）設(shè)備負(fù)荷的均衡程度定義為優(yōu)化目標(biāo)f2，如式（10）所示，設(shè)備負(fù)荷的均衡程度用各機器負(fù)荷的方差表示，各機器負(fù)荷的均值如式（11）所示：

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

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

2 改進(jìn)粒子群算法設(shè)計

2.1 改進(jìn)粒子群算法流程

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

圖1 改進(jìn)粒子群算法流程

2.2 改進(jìn)粒子群算法的操作設(shè)計

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

2）適應(yīng)度函數(shù)的設(shè)計。以綜合目標(biāo)值的大小評價粒子的優(yōu)劣[3]，適應(yīng)度函數(shù)G(v)定義見式（20）：

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

式中：wmin∈(0,1]；c1和c2為學(xué)習(xí)因子；piD為i粒子的個體極值；pgD為群體極值；gen為當(dāng)前代數(shù)；maxgen為最大代數(shù)。

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

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

6）停止準(zhǔn)則。當(dāng)算法運行至最大代數(shù)時終止，輸出最優(yōu)粒子對應(yīng)的運輸機速度和該速度下運輸機運送坩堝的最優(yōu)調(diào)度序列。

3 實驗仿真

3.1 實例驗證

某鋁制品壓鑄自動化生產(chǎn)線由5臺壓鑄機、1臺運輸機和1個供應(yīng)站組成，運輸機負(fù)責(zé)將高溫鋁液運送到各壓鑄機，設(shè)備信息如表1所示。采用本文提出的改進(jìn)粒子群算法確定運輸機的最佳速度和每日各坩堝鋁液的調(diào)度分配序列。

表1 設(shè)備信息

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

表2 目標(biāo)的權(quán)重及比例系數(shù)

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

圖2 各目標(biāo)收斂曲線

圖3 基于設(shè)備的調(diào)度甘特圖

表3 坩堝-設(shè)備的調(diào)度分配

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

3.2 算法的性能驗證

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

圖4 Rosenbrock函數(shù)圖

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

表4 兩種算法數(shù)據(jù)對比

4 結(jié)論

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