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

陶麗華，遲曉晨，谷東偉

（長春工業(yè)大學(xué) 機(jī)電工程學(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)度屬于一類帶有運(yùn)輸機(jī)約束的并行機(jī)調(diào)度問題（Parallel Machine Scheduling Problem，PMSP），運(yùn)輸機(jī)作為原料供應(yīng)站與壓鑄機(jī)之間的紐帶，確定合適的運(yùn)輸機(jī)速度，優(yōu)化原料到各壓鑄機(jī)的調(diào)度序列，實(shí)現(xiàn)原料在各壓鑄機(jī)之間無障礙流轉(zhuǎn)，減少壓鑄機(jī)的空閑等待時間，對于壓鑄企業(yè)實(shí)現(xiàn)清潔生產(chǎn)、提高生產(chǎn)效率、降低成本具有重要的現(xiàn)實(shí)意義。

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

1.1 問題描述

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

1.2 符號定義

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

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

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

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

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

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

3）以所有機(jī)器產(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為忽略運(yùn)輸機(jī)的所有機(jī)器在hT時間段產(chǎn)出鋁件的數(shù)量，如式（13）所示，式（14）指每臺機(jī)器產(chǎn)出鋁件的數(shù)量受制于計(jì)劃產(chǎn)量要求：

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

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

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

為了提高壓鑄自動化生產(chǎn)效率，減少設(shè)備的空閑等待時間，實(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中運(yùn)輸機(jī)速度及調(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è)計(jì)

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

2）適應(yīng)度函數(shù)的設(shè)計(jì)。以綜合目標(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)前的速度，搜索力度較大，從而實(shí)現(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)算法運(yùn)行至最大代數(shù)時終止，輸出最優(yōu)粒子對應(yīng)的運(yùn)輸機(jī)速度和該速度下運(yùn)輸機(jī)運(yùn)送坩堝的最優(yōu)調(diào)度序列。

3 實(shí)驗(yàn)仿真

3.1 實(shí)例驗(yàn)證

某鋁制品壓鑄自動化生產(chǎn)線由5臺壓鑄機(jī)、1臺運(yùn)輸機(jī)和1個供應(yīng)站組成，運(yùn)輸機(jī)負(fù)責(zé)將高溫鋁液運(yùn)送到各壓鑄機(jī)，設(shè)備信息如表1所示。采用本文提出的改進(jìn)粒子群算法確定運(yùn)輸機(jī)的最佳速度和每日各坩堝鋁液的調(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，運(yùn)輸機(jī)速度范圍為[10，30] m/min，個體極值庫的規(guī)模為10，群體極值庫的規(guī)模為4，算法運(yùn)行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ù)的增加，算法運(yùn)行到第4代時總目標(biāo)收斂于最小值717.5194，此時運(yùn)輸機(jī)最佳速度收斂于21.9968 m/min，機(jī)器總空閑時間收斂于38.197 min，各機(jī)器負(fù)荷的方差在第1代就收斂于24，各機(jī)器產(chǎn)出鋁件數(shù)在第1代就收斂于622個，運(yùn)輸機(jī)等待時間在第4代收斂于274.53 min。坩堝鋁液在各機(jī)器上的最優(yōu)分配序列如表3所示，表3顯示當(dāng)日58個坩堝鋁液的設(shè)備分配情況，基于設(shè)備的調(diào)度甘特圖如圖3所示。

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

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

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

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

3.2 算法的性能驗(yàn)證

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

圖4 Rosenbrock函數(shù)圖

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

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

4 結(jié)論

壓鑄自動化生產(chǎn)線屬于典型的異構(gòu)并行機(jī)調(diào)度問題，其運(yùn)輸機(jī)最佳速度的確定直接影響生產(chǎn)線的效率和生產(chǎn)環(huán)境。本文以設(shè)備總空閑時間、設(shè)備負(fù)荷均衡、產(chǎn)出鋁件數(shù)和運(yùn)輸機(jī)等待時間為目標(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)需求。在實(shí)際生產(chǎn)過程中，由于運(yùn)輸機(jī)的速度不一定是勻速的，若將運(yùn)輸過程中的加速和減速過程考慮進(jìn)去，將更符合DAPL的生產(chǎn)實(shí)際。