鋼結(jié)構(gòu)企業(yè)多項目調(diào)度的混沌粒子群算法優(yōu)化研究

雷兆明 ，李秀婷，花季偉，王東澤

（1.河北工業(yè)大學(xué) 控制科學(xué)與工程學(xué)院，天津 300130；2.天津師范大學(xué) 計算機(jī)與信息工程學(xué)院，天津 300387）

隨著近年來科技的高速發(fā)展，鋼結(jié)構(gòu)產(chǎn)品越來越受到人們的青睞，大多數(shù)的鋼結(jié)構(gòu)企業(yè)所接收的項目不再單一，且客戶要求各有不同，不同的項目對鋼結(jié)構(gòu)企業(yè)的人力、資源、工期以及鋼構(gòu)件要求各有差異，企業(yè)想要在各個不同項目執(zhí)行中最大限度的滿足客戶需求且使企業(yè)效績最優(yōu)，就必須將多項目調(diào)度問題作為企業(yè)調(diào)度管理的重中之重[1]。

目前，對于以上提到的問題，許多學(xué)者紛紛提出了切實有效的辦法。文獻(xiàn)[2]提出一種緩存更換搜索算法（CRS-PSO），將基本算法和緩存的概念設(shè)計在一起，有效地解決了收斂速度慢的問題。文獻(xiàn)[3]使用混沌粒子群算法結(jié)合混合優(yōu)先規(guī)則優(yōu)化多項目管理問題，對項目管理中的柔性資源受限問題提出了較好的解決辦法。文獻(xiàn)[4]嘗試開發(fā)新的數(shù)學(xué)模型和一個標(biāo)簽化的啟發(fā)式搜索方法作為方案解決多項目調(diào)度問題。本文針對傳統(tǒng)的粒子群優(yōu)化算法易陷入局部收斂的特性，提出將混沌擾動加入算法流程，并對粒子的速度位置進(jìn)行改進(jìn)，進(jìn)而在資源約束的情況下，對鋼結(jié)構(gòu)企業(yè)多項目調(diào)度問題進(jìn)行優(yōu)化。

1 鋼結(jié)構(gòu)多項目調(diào)度優(yōu)化模型描述

一個典型的鋼結(jié)構(gòu)多項目調(diào)度問題可描述為企業(yè)有Q個獨立的項目，每個項目均包含不同鋼構(gòu)件數(shù)的工作，即第i個項目包含Qi件工作；每件工作有不同或相同的工序，每個工序使用不同或相同的資源，在資源庫中有R種資源，每種工序加工時間固定， j∈［1，Qi］，i∈［1，Q］。 針對所述問題，采用取最小方差的方法進(jìn)行建模。要求鋼構(gòu)項目資源分配均衡，并且要根據(jù)項目的優(yōu)先級來合理分配資源。

式中：T為所有鋼構(gòu)項目的總的預(yù)定完成工期；Rk為第k種資源的總量；Rk（t）為第t個工作日所有鋼構(gòu)項目對第 k 種資源的需求量；Rij，k（t）為第 i個鋼構(gòu)項目中第j件工作的工序在第t個工作日對第k種資源的需求量；φ為各個鋼構(gòu)項目的優(yōu)先級權(quán)重；φi為第i個鋼構(gòu)項目的權(quán)重。

模型約束條件如下：

第i個鋼構(gòu)項目中第j件的工序在t時刻的資源消耗量必須小于該資源的供應(yīng)量。

保證t時刻進(jìn)行的工序沒有超出工期范圍：

保證決策變量為正整數(shù)：

式中：Tij為第i個鋼構(gòu)項目第j件工序的開始時間；dij為第i個鋼構(gòu)項目第j件工序的持續(xù)時間；HTij為第i個鋼構(gòu)項目第j件工作工序總富余時間；Uij為所有緊前工作的緊前工序集；TUij為第i個鋼構(gòu)項目第j件工序的緊前工序開始時間；dUij為第i個鋼構(gòu)項目第j件工序的緊前工序持續(xù)時間；Rk為第k種資源的平均需求量。

考慮到不同鋼構(gòu)項目的重要程度不同，所有鋼構(gòu)項目權(quán)重表示如下：

2 基于混沌粒子群的鋼結(jié)構(gòu)企業(yè)多項目調(diào)度算法

2.1 局部模型和全局模型的統(tǒng)一粒子群算法

通過對鳥群捕食行為和自然群聚的研究，文獻(xiàn)[5-6]中提出了微粒群優(yōu)化算法PSO（particle swarm optimization）。

在n維搜索空間中，將全局粒子群與局部粒子群相結(jié)合，粒子速度更新公式變?yōu)?/p>

式中，Gij（t+1）和 Lij（t+1）分別是全局/局部版本的速度更新公式，θ是統(tǒng)一模型參數(shù)（0≤θ≤1），用于調(diào)整全局粒子群與局部粒子群搜索能力，本文采用動態(tài)θ值。位置更新公式為

式中：ω為慣性權(quán)重；c1和c2為學(xué)習(xí)因子，值通常為2；r1和 r2為［0，l］之間的不同隨機(jī)數(shù)；γ 為約束因子，通常設(shè)置為1[7]。為了防止粒子飛行時脫離規(guī)定范圍，通常設(shè)置 Vij∈［-νmax，νmax］，Xij∈［-xmax，xmax］。

2.2 混沌改進(jìn)的統(tǒng)一粒子群（CPSO）算法

混沌變量在粒子群運動過程中起到控制粒子混沌程度的作用[8]。典型的混沌系統(tǒng)（Logistic方程）為

式中描述的是第n代與第n+1代間的邏輯關(guān)系，μ為控制參量；x為狀態(tài)變量；xn記錄第n代的狀態(tài)，xn∈［0，1］，0≤ μ≤4。

在統(tǒng)一粒子群中應(yīng)用混沌進(jìn)行粒子搜索，混沌擾動設(shè)在gbest鄰域進(jìn)行，基本步驟如下：

1）由式（9）產(chǎn)生l個軌跡不同的混沌變量Yi=（yi1，yi2，…，yin），1≤i≤l；

2）將Xi的各個分量載波到混沌擾動范圍［-η，η］，擾動量 Δy=（Δy1，Δy2，…，Δyn），且 Δyj=-η+2ηYij，ynew=gbestk+Δy；

3）計算 f（ynew），若 f（ynew）＜ f（gbestk），則 gbestk=ynew。

2.3 早熟處理機(jī)制

粒子在搜索過程中易出現(xiàn)早熟現(xiàn)象，采用適應(yīng)度方差來判斷粒子早熟，建立早熟處理機(jī)制，具體方法如下：

1）將粒子 Xak（k=1，…，n）按下式映射：

2）設(shè)迭代次數(shù)為N，產(chǎn)生混沌序列：

4）Xa經(jīng)Tent映射后得到的新的混沌點列：

2.4 算法的編/解碼方式

對于鋼結(jié)構(gòu)企業(yè)多項目調(diào)度問題，本文提出一種適用于粒子群算法的項目編解碼方法，將各項目和項目中工序的排序在編碼中表示出來，優(yōu)先值賦予公式為

設(shè)置總工序數(shù)為n，項目數(shù)為s，以n維的實數(shù)向量表示粒子的狀態(tài)，編/解碼的過程如下：

1）隨機(jī)生成1～s+1間n個任意實數(shù)向量表示粒子的狀態(tài)；

2）對此n個實數(shù)向量進(jìn)行分類，其中小數(shù)第一位相同的為一組；

3）在同一組中，按照實數(shù)向量的小數(shù)部分第二位的大小進(jìn)行排序，形成鋼結(jié)構(gòu)項目工序的調(diào)度順序。

假設(shè)某鋼結(jié)構(gòu)企業(yè)現(xiàn)有3個項目，總共8道工序，采用上述編碼方式如下：

P：（1.12，3.14，5.11，7.13），（2.23，3.21，4.25，6.21），（1.31，2.34，3.32，6.31，8.32）表示 3 個不同項目。 按上述解碼方法，將P中小數(shù)第一位相同的分在同一組，得 X=（1.12，1.31，2.23，2.34，3.21，3.14，4.25，4.32，5.11，6.21，6.31，7.13，8.32）；然后，在每個分組內(nèi)，按照P小數(shù)部分第二位從大到小排列，得到X=（1.12，1.31；2.34，2.23；3.14，3.21；4.25，4.32；5.11；6.21，6.31；7.13；8.32）。 將上述狀態(tài)映射到對應(yīng)的鋼結(jié)構(gòu)項目中，即可生成這組編碼對應(yīng)的優(yōu)先規(guī)則方案 Y=（1，3，3，2，1，2，2，3，1，2，3，1，3）， 表示第一個安排項目一中的工序，第二個安排項目三中的工序，第三個安排項目三中的工序，以此類推。

在上述編碼方式中，項目總工序的數(shù)與粒子維數(shù)相當(dāng)，只需進(jìn)行一次排序和取整運算即可解碼，對于像鋼結(jié)構(gòu)多項目這樣的大規(guī)模問題，可以節(jié)約計算時間。此編碼方式與混沌粒子群相切合，可以使用其已有規(guī)則，更快獲得最優(yōu)解。

2.5 算法優(yōu)化調(diào)度流程

根據(jù)上面對混沌粒子群算法優(yōu)化調(diào)度問題的描述，算法流程如圖1所示。

3 算例分析

以某鋼結(jié)構(gòu)企業(yè)多項目調(diào)度問題為例，設(shè)定有8種不同資源，10種不同工序，各工序間有緊前緊后約束時間，不同項目間有相同工序，不同工序也可使用同種資源，各項目在所需工序后面顯示編號，不需要則顯示0，具體情況如表1所示。

圖1 算法流程Fig.1 Flow chart of algorithm process

表1 各項目所需資源類型及時間約束Tab.1 Project resource types and time constraints

為了說明本文算法的有效性，經(jīng)編/解碼計算，優(yōu)先規(guī)則方案為 Y=（2，1，2，4，3，1，2，2，4，4，3，1，4，1，3，4），分別使用PSO、CPSO對調(diào)度問題進(jìn)行優(yōu)化。參數(shù)設(shè)置如下：種群規(guī)模50；最大迭代次數(shù)350；慣性因子ω=0.95；學(xué)習(xí)因子c1=c2=2；統(tǒng)一模型參數(shù)θ=0.78；CPSO的種群適應(yīng)度方差σ2=0.5。每種參數(shù)下均隨機(jī)運行40次，得到結(jié)果如表2所示，仿真圖如圖2所示。

表2 PSO、CPSO運算結(jié)果比較Tab.2 Comparison results of PSO and CPSO

圖2為該多目標(biāo)算例分別在基本粒子群算法和改進(jìn)后的混沌粒子群算法所得到的平均最優(yōu)適應(yīng)值曲線圖，即收斂圖的比較?？梢钥吹剑琍SO算法在求解該項目調(diào)度問題時，需要進(jìn)行219次迭代才能達(dá)到收斂效果，且容易出現(xiàn)局部收斂現(xiàn)象，而改進(jìn)的混沌粒子群算法只需52次迭代運算即可達(dá)到收斂，由此可見CPSO算法收斂性更好，全局收斂能力強(qiáng)，速度快且結(jié)果比較穩(wěn)定。

圖2 PSO、CPSO收斂性分析Fig.2 Convergence analysis of PSO and CPSO

4 結(jié)語

針對PSO存在著精度較低，易陷入局部收斂等缺點，利用混沌變量的隨機(jī)性，遍歷性，本文提出了使用統(tǒng)一粒子群優(yōu)化算法與混沌相結(jié)合的改進(jìn)思想。仿真結(jié)果表明，改進(jìn)后的算法較好地克服了標(biāo)準(zhǔn)粒子群優(yōu)化算法的缺點，尤其是在防止種群陷入局部最優(yōu)點上取得了很好的效果。將該優(yōu)化算法用于求解多項目管理優(yōu)化調(diào)度問題，能夠較好地兼顧計算速度和結(jié)果精度，并且能夠合理地處理約束條件，為多項目管理調(diào)度問題的優(yōu)化提供了一條有效的途徑。

[1]趙海洋.多項目協(xié)同管理系統(tǒng)的設(shè)計與實現(xiàn)[D].陜西：西北大學(xué)，2013.

[2]Mingyue Feng，Hua Pan.A modified PSO algorithm based on cache replacement algorithm[J].Computational Intelligence and Security（CIS），IEEE Con.2014，558-562.

[3]陳君蘭，葉春明.柔性資源受限多項目調(diào)度的混沌粒子群算法研究[J].計算機(jī)應(yīng)用研究，2013，30（1）：117-120.

[4]Roshanaei V，Ahmed Azab，ElMaraghy H.Mathematical modelling and ameta-heuristic forflexible job shop scheduling[J].International Journal of Production Research，2013：6247-6274.

[5]Kennedy J，EberhartR C.Particle swarm optimization[C]//Proceeding of 1995 IEEE International Conference on Neural Networks，New York，1995：1942-1948.

[6]Eberhart R C，Kennedy J.A new optimizerusingparticle swarm theory[C]//Proceedings of the Sixth International Symposium on Micro Machine and Human Science，New York，1995：39-43.

[7]曾建潮，介婧，崔志華.微粒群算法[M].北京：科學(xué)出版社，2004.

[8]胥小波，鄭康鋒，李丹，等.新的混沌粒子群優(yōu)化算法[J].通信學(xué)報，2012，33（1）：28-34，41.