改進PSO算法求解具有柔性生產(chǎn)路徑鋼鐵產(chǎn)品分配問題

金春華，王 雷

(1. 北京信息科技大學(xué) 經(jīng)濟管理學(xué)院，北京 100192；2. 北京科技大學(xué) 東凌經(jīng)濟管理學(xué)院，北京 100083；3. 鋼鐵生產(chǎn)制造執(zhí)行系統(tǒng)技術(shù)教育部 工程研究中心，北京 100083)

0 引言

企業(yè)在每個時期都會集中制定產(chǎn)品的銷售計劃，按照產(chǎn)品的種類和區(qū)域市場來劃分產(chǎn)品的銷售量，銷售人員根據(jù)企業(yè)的銷售計劃，有指導(dǎo)的接受產(chǎn)品訂單。訂單來至不同的區(qū)域市場，集中到企業(yè)進行生產(chǎn)。如果企業(yè)接受的訂單集中在某些區(qū)域，在企業(yè)生產(chǎn)能力有限的情況下，企業(yè)的產(chǎn)品生產(chǎn)就會影響前期制定的銷售計劃，打亂企業(yè)的生產(chǎn)銷售戰(zhàn)略。針對企業(yè)生產(chǎn)銷售狀況，企業(yè)應(yīng)該在滿足產(chǎn)品區(qū)域市場的需求量滿足原則下進行產(chǎn)品分配。因此，企業(yè)在產(chǎn)品分配的過程中，不僅要將企業(yè)的盈利能力最大化作為目標(biāo)，同時還要從企業(yè)長期戰(zhàn)略發(fā)展出發(fā)，協(xié)調(diào)好各區(qū)域市場之間的關(guān)系，以市場產(chǎn)品需求滿足率為導(dǎo)向，進而達到提高區(qū)域市場企業(yè)的滿意度最終提高企業(yè)的長期盈利能力。由于企業(yè)自身產(chǎn)能的限制，在產(chǎn)品分配過程中要不斷提高生產(chǎn)線設(shè)備的綜合利用率，充分發(fā)揮企業(yè)的生產(chǎn)能力。此外，企業(yè)產(chǎn)品如果存在多條生產(chǎn)路徑，不同生產(chǎn)路徑生產(chǎn)出的產(chǎn)品具有不同的生產(chǎn)成本，在產(chǎn)品分配過程中盡可能選擇成本最小的生產(chǎn)路徑來提高企業(yè)的利潤率。因此，多目標(biāo)產(chǎn)品分配問題的解決對企業(yè)的生產(chǎn)銷售實際有重要的影響。

陳菊新等[1]建立了產(chǎn)品分配的時變模型，并將其分為兩層子問題。下層子問題為基本的運輸問題，按一般的線性方程求解，上層子問題采用遺傳算法進行求解，實驗取得較好的效果。唐加福[2]考慮了全球制造環(huán)境下多產(chǎn)品生產(chǎn)分銷網(wǎng)絡(luò)問題，提出了基于拉格朗日松弛的兩層分解啟發(fā)式算法來求解包括生產(chǎn)商指定的生產(chǎn)任務(wù)、生產(chǎn)批量、生產(chǎn)商和分銷商之間的交貨量的聯(lián)合決策模型。張翠華等[3]針對多供應(yīng)商環(huán)境下JIT采購的訂單分配問題，提出在滿足一定送貨及時率及采購策略條件下生產(chǎn)商的總采購成本最小化模型，通過企業(yè)實例仿真求解出較好的結(jié)果。潘偉等[4]通過考慮訂單分配信息的不確定性和模糊性，構(gòu)建一個包含模糊目標(biāo)、模糊權(quán)重和隨機約束的訂單分配模型。然后，利用數(shù)值算例證明了模型的可行性。劉曉冰等[5]建立了以企業(yè)集團訂單排產(chǎn)量最大和集團利潤最大為目標(biāo)的鋼鐵企業(yè)訂單分配多目標(biāo)優(yōu)化模型，提出了模型求解的算法流程，最后通過實例驗證了模型和算法。姜意揚等[6]建立基于物流供應(yīng)商具有的訂單、物流能力可獲得性、配送效率、缺失率與成本的供應(yīng)商選擇與訂單分配組合優(yōu)化模型，并采用相應(yīng)算法進行算例分析。Calvete等[7]分析由于供應(yīng)商和分銷商有各自的目標(biāo)，不能實現(xiàn)產(chǎn)銷計劃的最優(yōu)。他們在兩階段供應(yīng)鏈環(huán)境下利用蟻群優(yōu)化方法得出了一體化產(chǎn)銷優(yōu)化配置，平衡了供應(yīng)商和分銷商之間的分配關(guān)系。Kawtummachai等[8]研究了供應(yīng)鏈條件下的訂單分配流程，建立了數(shù)學(xué)模型。目的使總購買成本最小和維持特定的服務(wù)水平，通過求解算法證明了模型的可行性。

現(xiàn)有文獻大多是研究企業(yè)在收到客戶訂單后，如何安排產(chǎn)品生產(chǎn)最后送達給客戶，而很少有研究根據(jù)現(xiàn)有銷售計劃的指導(dǎo)，將不同工藝路線生產(chǎn)的產(chǎn)品分配到各區(qū)域市場的客戶，達到生產(chǎn)線和市場需求的平衡。本文在考慮市場產(chǎn)品滿足率的基礎(chǔ)上，綜合考慮了鋼鐵企業(yè)經(jīng)營總利潤和不同工藝路線上生產(chǎn)線上設(shè)備的利用率，建立柔性生產(chǎn)路徑鋼鐵產(chǎn)品分配模型，設(shè)計多目標(biāo)改進粒子群優(yōu)化算法求解，通過實驗考察模型和求解算法的可行性和有效性。

1 問題建模

1.1 問題描述

鋼鐵企業(yè)的每種產(chǎn)品生產(chǎn)具有多條工藝路線，同時產(chǎn)品具有多品種、小批量的特點，而市場對產(chǎn)品需求也是多種多樣。那么，鋼鐵企業(yè)的產(chǎn)品分配問題是在滿足生產(chǎn)和市場約束的條件下，確定各種產(chǎn)品大類和具體產(chǎn)品的產(chǎn)量，使得問題的目標(biāo)函數(shù)最優(yōu)。在鋼鐵企業(yè)經(jīng)營環(huán)境下，產(chǎn)品分配問題以各市場需求為導(dǎo)向，在確定各種產(chǎn)品總產(chǎn)量的同時，還需確定分配至各市場上的產(chǎn)品產(chǎn)量。而同種產(chǎn)品可能來至不同的生產(chǎn)工藝路線，各生產(chǎn)工藝路線由不同的生產(chǎn)線構(gòu)成?？紤]到鋼鐵企業(yè)的生產(chǎn)情況和各市場的需求情況，問題存在以下約束：1）產(chǎn)品的品種大類不得超出最大量限制；2）各類產(chǎn)品的產(chǎn)量受到生產(chǎn)線生產(chǎn)能力限制，不得超出各生產(chǎn)線的最大產(chǎn)量；3）由于生產(chǎn)加工工藝的特殊要求，某類產(chǎn)品的產(chǎn)量存在最小值約束；4）各類市場對于各類產(chǎn)品的需求量均存在期望上限，因而，鋼鐵企業(yè)分配給各市場的產(chǎn)品量不能超過市場的最大需求量；5）各市場對某類產(chǎn)品存在特定需求，企業(yè)將此類產(chǎn)品分配給各市場的產(chǎn)量不得小于最小需求量。

在制定產(chǎn)品分配方案時，鋼鐵企業(yè)需要滿足各市場需求為導(dǎo)向，綜合考慮以下問題：1）產(chǎn)品生產(chǎn)利潤最大化原則；2）生產(chǎn)線上設(shè)備的最大平均利用率原則；3）滿足各市場產(chǎn)品需求，達到各市場產(chǎn)品需求最大化。所以，本文研究的柔性生產(chǎn)路徑鋼鐵企業(yè)產(chǎn)品分配問題以最大化利潤、設(shè)備利用率以及市場產(chǎn)品滿足率為優(yōu)化目標(biāo)。

1.2 符號定義

1) 下標(biāo)符號

i為產(chǎn)品品種編碼，i∈I；

l為產(chǎn)品工藝路線編碼， l ∈ ∪P Li, i∈I ；

m為市場編碼，共有M個市場，1≤m≤M；

j工藝路線上的節(jié)點數(shù)（生產(chǎn)線）j=(1,2,… ,Nl)，Nl為第l條工藝路線的最后一個節(jié)點；

k為實際生產(chǎn)線的編號 k =(1,2,… ,K)。

2) 集合

I為產(chǎn)品品種集合；PLi為產(chǎn)品i的生產(chǎn)工藝路線集合，i∈I；MPm為第m個市場需要的所有產(chǎn)品集合，1≤m≤M。

3) 參數(shù)

Maxk為第k條生產(chǎn)線的最大生產(chǎn)能力；

Mink為第k條生產(chǎn)線的最小生產(chǎn)能力；

Piml為第l條產(chǎn)品工藝路線上生產(chǎn)的產(chǎn)品i在市場m上的單位利潤， i ∈ M Pm,1 ≤ m ≤ M , l∈PLi；

MaxMpim為市場m對產(chǎn)品i的最大需求量，i∈ I , 1 ≤m ≤ M ；

MinMpim為市場m對產(chǎn)品i的最小需求量，i∈ I , 1 ≤m ≤ M 。

4) 變量

zmiml為第l條工藝路線上生產(chǎn)的產(chǎn)品i在m市場的需求量， i ∈ M Pm,1 ≤ m ≤ M , l∈ P Li。

1.3 問題模型

以企業(yè)利潤最大化、生產(chǎn)線上設(shè)備平均利用率最大化、市場產(chǎn)品滿足率最大化為目標(biāo)，本文建立了多目標(biāo)產(chǎn)品分配模型為：

目標(biāo)函數(shù)(1)表示企業(yè)利潤最大化；目標(biāo)函數(shù)(2)表示生產(chǎn)線上的設(shè)備平均利用率最大化；目標(biāo)函數(shù)(3)表示最大化市場產(chǎn)品滿足率；約束(4)表示生產(chǎn)線上的產(chǎn)出量不能大于規(guī)定的最大量；約束(5)表示生產(chǎn)線上的產(chǎn)出量不能小于最小量；約束(6)表示企業(yè)的產(chǎn)品銷量不能超過市場需求產(chǎn)品的最大需求量；約束(7)企業(yè)的產(chǎn)品銷量必須滿足市場需求產(chǎn)品的最小需求量；約束(8)為平衡約束，即產(chǎn)品的產(chǎn)量必須等于其產(chǎn)品的需求量；約束(9)(10)定義了產(chǎn)品的分配去向與產(chǎn)量之間的關(guān)系；約束(9)～(12)為變量取值約束。

2 求解算法

上述建立的鋼鐵產(chǎn)品分配模型是一類多目標(biāo)、多約束和多變量的組合優(yōu)化問題，由于變量具有很大的維數(shù)，解的搜索空間大，不能夠用精確的算法在有效的時間內(nèi)求解。同時，多目標(biāo)優(yōu)化問題要綜合考慮多個子目標(biāo)之間的聯(lián)系，使得問題的求解難度更大。因此，智能優(yōu)化算法提供了這類問題的求解技術(shù)。粒子群優(yōu)化算法(Particle Swarm Optimization, PSO)是由Kennedy和Eberhart[9]通過模擬鳥群覓食行為而提出的一種基于群體協(xié)作的隨機搜索算法。由于粒子群算法具有參數(shù)少、全局優(yōu)化效果好、收斂速度快的優(yōu)點，該算法在許多多目標(biāo)優(yōu)化問題中得到了較好的應(yīng)用[10-11]。

基本粒子群算法的數(shù)學(xué)模型如下所示：

其中，w稱為慣性權(quán)重，通常取0.9～0.4；c1、c2稱為加速因子，通常取c1=c2=2；r1、r2為(0,1)之間的隨機數(shù)。

2.1 初始解的生成

產(chǎn)品分配模型中有很多復(fù)雜的約束條件，使用隨機生成初始粒子群和初始解的方法能夠產(chǎn)生無效的粒子。本文研究的鋼鐵產(chǎn)品分配問題，可將各不同生產(chǎn)路徑下的產(chǎn)品在不同區(qū)域市場上的分配量和不同生產(chǎn)線上的產(chǎn)品量映射為變量量的取值范圍映射為變量的值域 D （zmiml,）= [ 0 , ∞），產(chǎn)品生產(chǎn)和分配約束映射為約束集合C，則產(chǎn)品生產(chǎn)和分配問題就能夠轉(zhuǎn)化為約束滿足問題。對于具有復(fù)雜約束關(guān)系的約束滿足問題，可以通過變量選擇、約束傳播等方法，從變量的值域中消除非可行解進而獲得較好的初始可行解。

2.2 設(shè)計適應(yīng)度函數(shù)

粒子的適應(yīng)度值是衡量粒子飛行位置好壞的標(biāo)準(zhǔn)，粒子群算法在搜索過程中根據(jù)適應(yīng)度函數(shù)來評價解的優(yōu)劣。由于粒子群進行的是隨機搜索，會產(chǎn)生不符合目標(biāo)函數(shù)值的解，所以本文引入懲罰函數(shù)來處理約束問題，將偏離目標(biāo)函數(shù)的解進行懲罰，使約束優(yōu)化問題轉(zhuǎn)換成無約束優(yōu)化問題。

將(15)～(17)作為本文改進算法的適應(yīng)度函數(shù)，其中，W是一個足夠大的正數(shù)， (x )+= m ax { x ,0}。

2.3 設(shè)置慣性權(quán)重

慣性權(quán)重值w對算法收斂性能的影響較大，較大的慣性權(quán)重能夠得到很好的全局搜索能力，而較小的慣性權(quán)重有利于算法的局部搜索能力[12]。在算法的開始階段由于種群的數(shù)量較大，所以應(yīng)該采用較大的慣性權(quán)重，而在進化的后期保證算法收斂到最優(yōu)值，強化局部搜索能力，選擇較小的慣性權(quán)重。

由于慣性權(quán)重對于搜索策略的重要影響，本文采用動態(tài)調(diào)整w值的方法，隨著迭代次數(shù)的不斷增加，慣性權(quán)重的最大值按照公式(18)從0.9到0.4逐次減小，t為當(dāng)前迭代次數(shù)，M為最大迭代次數(shù)[13]。

2.4 算法步驟

求解柔性生產(chǎn)路徑產(chǎn)品分配問題的改進PSO算法步驟如下：

步驟1 初始化

2）令群體迭代數(shù) t ← 0 ，加速系數(shù) c1=c2←2，慣性權(quán)重 w ← 0 .9，最大尋優(yōu)次數(shù)為MaxIter；

4）由約束滿足算法求得的三個目標(biāo)函數(shù)值作為初始粒子的適應(yīng)度；

步驟2 更新粒子群

2）根據(jù)公式(13)和(14)更新粒子i的速度和位置，其中公式(13)中的慣性權(quán)重w根據(jù)公式(18)動態(tài)決定；

3）按照公式(15)～(17)計算更新后的粒子適應(yīng)度，按照規(guī)則修改不可行粒子解，根據(jù)公式(15)～(17)重新計算修改后的粒子適應(yīng)度；

步驟3 終止條件判斷

1）令t←t+1,如果t＞M，轉(zhuǎn)2)，否則返回步驟2；

2）輸出粒子的適應(yīng)度函數(shù)值，結(jié)束算法。

3 數(shù)據(jù)實驗

3.1 實驗設(shè)計

本文采用Microsoft Visual C++ 2008實現(xiàn)改進的PSO算法，實驗環(huán)境為Pentium4/2.80GHZ/2.24GB/Windows7。實驗數(shù)據(jù)來源于國內(nèi)某大型鋼鐵企業(yè)。改進PSO算法參數(shù)設(shè)置為：種群規(guī)模大小為200；最大迭代次數(shù)為200。實驗數(shù)據(jù)設(shè)置如下：產(chǎn)品種數(shù)n=5,10；需求市場數(shù)m=4,8；工藝路線數(shù)l=4,8；工藝節(jié)點上的最大產(chǎn)品量Maxk∈DU[1 0 00,2400]；工藝節(jié)點上的最小產(chǎn)量Mink∈DU[1 0 ,80]；不同工藝路線上產(chǎn)品對區(qū)域市場的最大分配量 M axMpim∈DU[2 50,700]；不同工藝路線上產(chǎn)品對區(qū)域市場的最小分配量MinMpim∈DU[1 0 0,400]，其中DU[ a, b]表示區(qū)間為[a , b]的離散均勻分布。根據(jù)產(chǎn)品種類、市場的分配量和產(chǎn)品生產(chǎn)工藝的不同，將實驗分成6組，每組隨機生成60個算例，采用企業(yè)產(chǎn)品利潤、設(shè)備利用率和市場產(chǎn)品滿足率三個指標(biāo)評價算法的質(zhì)量。

3.2 實驗結(jié)果分析

改進PSO算法的算例中，隨機選取一組數(shù)據(jù)作為實驗的最終解，實驗結(jié)果如表1所示，其中CPU為改進PSO算法的實際計算時間。

上述實驗數(shù)據(jù)可以得到以下結(jié)論：

1）由表1可知，改進PSO算法在很短的時間內(nèi)能夠獲得質(zhì)量比較好的解。隨著問題規(guī)模的增大計算時間增加，但是都是在可接受范圍之內(nèi)。

2）產(chǎn)品數(shù)量增加一倍可以引起利潤額很大的提高，但是設(shè)備利用率和市場產(chǎn)品滿足率都有一定的下降。

3）市場數(shù)量增加一倍可以引起需求滿足率大規(guī)模的降低，利潤額能夠增加很小一部分，設(shè)備利用率減少不大。

4）工藝路線增加一倍可以引起利潤額很大的提高，但是設(shè)備利用率和市場產(chǎn)品滿足率都有一定的下降。

該數(shù)據(jù)實驗符合實際情況，當(dāng)鋼鐵企業(yè)向區(qū)域市場分配的產(chǎn)品種類增加時，不同種類產(chǎn)品的單位利潤不同，增加的產(chǎn)品會帶來利潤的上升。由于品種的增多，設(shè)備的利用率和市場產(chǎn)品滿足率會有一定幅度的下降。擴大產(chǎn)品的分配范圍，企業(yè)產(chǎn)品利潤和設(shè)備利用率不會有很大的變化，但是由于分配到區(qū)域市場的擴大，市場產(chǎn)品滿足率就會下降。增加生產(chǎn)工藝路線的數(shù)量，擴大了現(xiàn)有企業(yè)的產(chǎn)能能力，但是設(shè)備利用率會有所下降。

表1 實驗結(jié)果

4 結(jié)論

由于鋼鐵企業(yè)生產(chǎn)線由柔性生產(chǎn)路徑組成，如何把不同成本得到的產(chǎn)品有效分配到區(qū)域市場，如何在追求產(chǎn)品利潤最大化的同時，考慮企業(yè)生產(chǎn)的綜合設(shè)備利用率和市場產(chǎn)品滿足率，是實現(xiàn)鋼鐵企業(yè)生產(chǎn)面對的新問題。根據(jù)鋼鐵企業(yè)問題的特點，建立了多目標(biāo)的產(chǎn)品分配問題，考慮了企業(yè)利潤、設(shè)備利用率和市場產(chǎn)品滿足率為優(yōu)化目標(biāo)的模型，提出了改進PSO算法。算法由約束滿足技術(shù)生成初始可行解，利用懲罰函數(shù)思想處理不可行解。實驗表明算法能夠在較短的時間內(nèi)有效求解問題模型，實驗符合現(xiàn)實問題，能夠滿足實際應(yīng)用。

[1] 陳菊新,徐建閩,辛武平.基于遺傳算法的產(chǎn)品分配方案研究[J].華南理工大學(xué)學(xué)報(自然科學(xué)版),2001,29(2):90-93.

[2] 唐加福.基于Lagrange松弛分解的多產(chǎn)品生產(chǎn)-分銷系統(tǒng)的聯(lián)合決策[J].機械工程學(xué)報,2005,41(8):153-157.

[3] 張翠華,朱宏,馬林.基于JIT采購的訂單分配問題模型及仿真應(yīng)用[J].東北大學(xué)學(xué)報(自然科學(xué)版),2006,27(11):1291-1294.

[4] 潘偉,汪壽陽,華國偉,張金隆.基于模糊權(quán)重的多目標(biāo)訂單分配模型[J].中國管理科學(xué),2009,17(2):80-85.

[5] 劉曉冰,王宇春.鋼鐵企業(yè)集團訂單分配模型研究[J].控制與決策,2009,24(11):1629-1634.

[6] 姜意揚,王勇,鄧哲峰.基于LSSC的供應(yīng)商選擇與訂單分配[J].工業(yè)工程,2011,14(3):80-86.

[7] Herminia I.Calvete,Carmen.Gale.Bilevel model for production-distrbution planning solved by using ant colony optimization[J].Computers & Operations Research,2010,38(1):320-327.

[8] R. Kawtummachai, N.Van Hop.Order allocation in a multiple-supplier environment[J].International Journal of Production Economics,2005,93-94:231-238.

[9] Kennedy J, Eberhart R. Particle swarm optimization[C]//IEEE International Conference on Neural Networks（Perth, Australia）, IEEE Service Center, Piscataway,NJ, 1995, IV:1942-1948.

[10] 張文學(xué),李鐵克.基于粒子群和約束滿足的鋼軋一體化批量計劃優(yōu)化[J].計算機集成制造系統(tǒng), 2010,16(4):840-845.

[11] D.Y.Sha and H.Lin.A multi-objective PSO for job-shop scheduling problems[J].Expert Systems with Applications,2010,37(2):1065-1070.

[12] Shi.Y,Eberhart.R.A modified particle swarm optimizer[C].IEEE World Conf on Computational Intelligence.Piscataway:IEEE Press,1998:69-73.

[13] Shi Y, Eberhart R. Empirical study of particle swarm optimization[C]//Proceedings of the 1999 Congress on Evolutionary Computation,1999:1945-1950.