混合粒子群算法求解單機批調度問題

常俊林 孟彥軍 王 慶 葉 賓

(中國礦業大學信息與電氣工程學院，江蘇 徐州 221006)

粒子群算法是通過模擬鳥群覓食行為而發展起來的一種基于群體協作的隨機搜索算法，該算法已在工業中有了廣泛應用[1]。

單機調度是生產調度問題的一種特殊形式，半導體芯片的預燒、電路測試、港口貨物裝卸及金屬加工等都屬于該類型。在實際生產過程中，對于大規模的生產活動，需要進行批量處理，機器在處理工件時，可以將多個工件同時進行加工以提高生產效率，降低生產成本，這就是所謂的單機批調度問題。文獻[2]首先提出了該類問題的單機器模型，即單機批調度問題，證明了該類問題的制造跨度問題是強NP問題。文獻[3]求解極小化總完工時間的單機批調度問題，提出了基于工件序列的蟻群算法和基于批序列的蟻群算法。文獻[4]研究了單機環境下工件尺寸有差異的批調度問題，并設計了一種改進蟻群算法對問題的制造跨度進行優化。文獻[5]采用模擬退火方法求解最小化最大完工時間的單機批處理調度問題。隨著單機批處理調度問題研究的深入,對于調度問題的約束條件也越來越多，工件動態到達的單機批調度問題的研究也己逐漸成為一個很有價值的研究方向。但是目前研究工件動態到達的單機批調度的文獻很少[6，7]，并且在生產調度問題的優化研究方面，應用智能優化算法來改進求解的質量仍存在不足。文獻[8]利用分批的啟發式規則產生初始種群，然后重新設計了交叉算子和變異算子以優化制造跨度。但遺傳算法的求解性能依賴于種群規模，因此在解決大規模問題時收斂性能較差。文獻[9]中微粒群算法在對批調度問題求解時，主要是使用工件序列對解進行編碼，將改進操作放在成批階段，對微粒群算法得到的工件序列釆用動態規劃算法進行改進。上述啟發式方法不能充分考慮問題的約束條件，難以找到最優解，因此，另外一些學者采用了性能更優的元啟發式算法(meta-heuristic algorithm)。文獻[10]提出了求解最小化最大完工時間的單機批處理調度問題的啟發式算法和蟻群算法，并且考慮了工件尺寸不等和動態工件到達的約束條件。文獻[11]利用蟻群聚類算法求解工件具有不同到達時間的單機批調度問題。上述算法雖然能在一定程度上有效求得問題的優化解，但是隨著迭代次數的增加，算法容易陷入局部最優，降低算法的收斂速度。因此筆者提出利用混合粒子群算法來求解工件動態到達的單機批調度問題，并引入自適應策略和慣性權重正弦函數，防止算法陷入局部最優，同時也提高了算法的收斂速度。

1 數學模型①

單機批調度問題描述如下：工件到達之后，在滿足機器容量Bmax和工件到達時間的約束下，可以將多個工件作為一批同時進行加工，并且只有加工時間相同的工件才可以加入同一批中，同一批工件具有相同的開始和結束加工時間。從一批開始加工直到該批加工完成，該過程不允許中斷，也不允許有工件中途退出或加入該批，因為同一批中的工件由一臺機器進行加工，具有共同速度，所以批加工時間由批中工件的加工時間最大的工件決定。到達時間、交貨期都是已知的。

根據上述描述，所求問題的數學模型和約束條件為：

Rb=max{rj|j∈b}

(1)

Cb=Pb+Sb

(2)

Li=Cb-di

(3)

s.t.

Sb≥Rb

(4)

nb≤Bmax

(5)

Pb=max{pi}

(6)

優化目標函數為：

minLmax=max(Li)

(7)

其中，Rb、Pb、Sb、Cb分別為批b的釋放時間、加工時間、開始加工時間和最大完工時間；di、ri、Ci、Li分別為工件i的交貨期、釋放時間、最大完工時間和最大拖期時間；Lmax為最大拖期時間；約束條件(4)表示批b的開始加工時間要大于批的到達時間，約束條件(5)表示第nb個批工件個數不超過Bmax，約束條件(6)表示批加工時間等于批中工件最大加工時間。

單機批調度問題可以分為兩個過程：工件成批和批的加工。工件成批主要是對工件到達時間按升序排列后，在滿足機器批容量的前提下，已到達工件中加工時間相等的工件加入一批，否則新建批。分批完成后將工件分配到批處理機進行加工，得到目標函數。

2 算法設計

2.1 標準粒子群(PSO)算法描述

基于微粒群優化算法獨特的搜索機制，PSO算法首先在可行解空間和速度空間隨機初始化微粒群，即確定微粒的初始位置和初始速度，通過評價各微粒的目標函數，確定t時刻每個微粒所經過的最佳位置pi和群體最佳位置pg，再按下列公式分別更新各微粒的速度和位置：

vijk+1=wvijk+c1r1(pijk-xijk)+c2r2(pgjk-xijk)

(8)

xijk+1=xijk+vijk+1

(9)

式中c1——自身經驗學習因子；

c2——社會經驗學習因子；

r1、r2——[0,1]之間的隨機數；

w——慣性權重因子。

2.2 混合粒子群算法

由于所求調度問題是離散的，所以采用基于工件序列的編碼方式可以更好地表達問題的解。為了保證編碼策略不遺漏問題的全局最優解，并使優化操作滿足狀態的可行性和合法性，設計一種針對隨機鍵編碼的基于升序排列(ranked-order-value，ROV)的操作，用于實現從微粒的連續位置矢量到工件排序的轉換。假定有6個工件的調度問題,設根據NEH啟發式算法和隨機方法產生粒子位置[1.9,1.8,0.7,3.5,2.4,1.2],采用ROV規則，基于升序排列得：4,3,1,6,5,2,所得排列即工件的加工序列。

在式(8)中，由于粒子速度向量vi本身具有隨機性和盲目性，導致算法收斂性較差，無法快速尋找到新的解區域。在考慮實際優化問題時，求解最優解的思想就是首先通過全局搜索，快速收斂于某一新的解空間，然后采用局部搜索來獲得高精度的解。慣性權重因子w是一個控制參數，不僅控制本次飛行速度對下次飛行速度的影響程度，還體現著粒子群優化算法對全局搜索與局部搜索的平衡。因此合理地選擇有利于更好地平衡算法的全局搜索能力和局部搜索能力，協調算法的搜索精度和收斂速度。在迭代初期階段，希望有較高的搜索能力以探索新的解空間跳出局部極值，而在后期則重視局部開發以加快收斂并發現精確解，通過對粒子群算法中慣性權重的分析，提出了一種慣性權重正弦調整方法來改進粒子群算法中的慣性權重[12]，以改善粒子群算法的收斂速度和全局收斂性。為了防止算法陷入局部最優，在改進算法的基礎上引入自適應變異全局極值的變異操作來開發算法跳出局部最優的能力[13]。

2.2.1慣性權重正弦調整

首先對由式(8)、(9)組成的系統進行穩定性分析。為便于表達，把式(8)、(9)中的問題簡化為一維，記φ1=c1r1，φ2=c2r2，則粒子i的運動狀態方程為：

vik+1=wvik+φ1(pik-xik)+φ2(pgk-xik)

(10)

xik+1=xik+vik+1

(11)

根據文獻[14]所得結論可知：

-(φ1+φ2)xik=vik+1-wvik-φ1pik-φ2pgk

(12)

對式(8)～(10)化簡，可知粒子的速度變化過程是一個二階差分方程：

vik+2-(1+w-φ1-φ2)vik+1-wvik=0

(13)

粒子的位置變化過程也是一個二階差分方程。將粒子速度變化過程看成是一個時間連續過程，對時間求導得到一個典型的二階差分方程：

(14)

其中e1、e2為方程λ2+(φ1+φ2-1-w)λ+w=0的根。根據式(14)解的一般形式可知，當粒子的速度趨向無窮大時，粒子的運動軌跡是發散的，導致整個粒子群的運動軌跡是發散的，粒子速度變化過程的穩定性對整個粒子群行為有著重要影響。假定φ1、φ2為常數，那么式(13)z變換后的系統方程則可看成是一個線性系統，其特征方程為：

z2+z(φ1+φ2-1-w)+w=0

(15)

對式(15)作雙線性變換，將z=(μ+1)/(μ-1)代入式(15)化簡得：

(φ1+φ2)μ2+(2-2w)μ+2(2w+2-φ1-φ2)=0

(16)

特征方程的所有零點均在z平面上一個以原點為圓心的單位圓內,這是二階線性系統穩定的必要條件。由羅斯判據可知二階線性系統穩定的充要條件是特征方程各項系數均為正值，可得式(13)穩定的條件為：

(17)

由于φ1、φ2為正實數，所以在不考慮隨機量且個體最優值、全局最優值位置不變的情況下，單個粒子速度變化過程穩定的條件由式(17)的后兩個不定式決定，且兩個條件不能同時取等號，滿足條件時單個粒子的速度將趨向于0。用同樣的方法對粒子位置變化過程進行分析，得到粒子位置變化過程穩定的條件：

(18)

較大的w值有利于跳出局部最優，進行全局尋優；較小的w值有利于局部尋優，加速算法收斂。筆者提出一種正弦調整的粒子群算法慣性權重：

w(k)=0.4+0.5sin(πk/maxgen)

(19)

令φ1=[w(k)+1]r1,φ2=[w(k)+1](2-r1)r2，r1、r2為均勻分布在(0,1)區間的隨機數，式(17)、(18)所有條件均可得到滿足，從理論上說明了粒子群算法的收斂性能。由正弦變化規律可知w值的變化對算法的影響，在算法開始時粒子在其自身附近作局部尋優，在一定時期后粒子的搜索范圍逐漸增大，進行全局尋優，最后讓最優粒子進行局部搜索。

2.2.2自適應變異全局最優值

如果粒子群優化算法陷入早熟收斂或者達到全局收斂，粒子群中的粒子就會聚集在搜索空間的一個或幾個特定位置，群體適應度方差σ2等于零。設粒子群的粒子數目為n，fi為第i個粒子的適應度，favg為粒子群目前的平均適應度，根據適應度函數，適應度方差定義為：

(20)

其中f是歸一化定標因子，其作用是限制σ2的大小。令:

(21)

由于粒子在當前全局最優值gBest的作用下可能發現更好的位置，因此新算法將變異操作設計成一個隨機算子，即對滿足變異條件的gBest按一定的概率pm變異。pm的計算公式如下：

(22)

其中，k=rand(0.1,0.3)；σd2的取值與實際問題有關，一般遠小于σ2的最大值；fd可以設置為理論最優值。

對于gBest的變異操作，算法中采用增加隨機擾動的方法，η是服從Gauss(0,1)分布的隨機變量，gBest的第k維全局極值變異公式為：

gBestk=gBestk(1+0.5η)

(23)

首先判斷算法是否滿足收斂準則，如果不滿足，對粒子進行位置和速度的更新，判斷此時粒子適應度值是否滿足fi

3 實驗設計與仿真

為了驗證改進算法的性能，實驗中隨機產生測試算例，其中機器容量為3；工件數J[i]分別為20、50、100、150；加工時間服從t1=[0，20]、t2=[0，10]均勻分布；設置參數α和β分別用來控制工件的釋放時間分布和交貨期分布的松緊程度，其值分別為0.2和3；算法中最大迭代次數和種群規模都為100；w、v和x的取值范圍分別為[0.40,0.91]、[-4,4]和[0,4]；函數unifrnd(0,a)取(0，a)之間的隨機數，ri=unifrnd(0,αCmax)，di=ri+unifrnd(1,β)pi，這里暫不討論參數對算法的影響。

筆者將遺傳算法(GA)與提出HPSO算法進行比較，運行在Windows XP系統、CPU E6600 3.06GHz、內存1.96G的臺式電腦上。所有算法采用Matlab編程，每種算例運行30次。筆者對運行結果和運行時間從最差值、最優值、平均值及百分比偏差(百分比偏差=(L(HPSO)-L(GA))/L(GA))等方面進行比較，比較結果見表1、2。

表1 兩種算法運行結果的比較

表2 兩種算法運行時間的比較

從表1、2中可以看出，HPSO算法要明顯優于GA算法，隨著問題規模的增大，HPSO算法的解與GA算法的差距更為明顯，顯示了很好的穩定性。在運行時間上，HPSO算法在所有算例上的求解時間均小于GA算法，隨著問題規模的增大相對GA算法有著更快的收斂速度。為了更直觀地看出算法的性能優劣，分別用折線圖和條形圖描述了算法均值百分比偏差和標準差的分布情況(圖1、2)。

圖1 運算結果均值和運行時間百分比偏差

圖2 標準差值的分布

由圖1可知，HPSO算法相對GA算法有一定的改進，但對于J1t1算例均值百分比偏差出現不穩定的狀態，對于大部分算例是隨著問題規模的增大效果越明顯，而且兩種不同加工時間下相比較，改進比較穩定。對于運行時間的改進則表明，隨著問題規模的增大，改進效果越明顯，表現在算例中則是收斂速度變大。總體來說HPSO算法更能適應復雜的調度環境。

由圖2可以看出，除了算例J3t1和J3t2的標準差出現波動外，HPSO算法的標準差均比GA算法的小，表明HPSO算法的尋優能力比GA算法尋優能力強，能夠跳出局部最優區域。標準差表明組內算例間的離散程度，也就是算例結果偏離平均值的程度，同時反映數據波動范圍大小，能不能在有限的迭代次數內尋到最優值。由此可知，HPSO算法所得數據波動范圍較小，更適合對此類調度問題分析。

4 結束語

筆者提出了一種基于工件動態到達求解批調度問題最大拖期時間的改進粒子群算法(HPSO)。該算法在標準PSO算法的基礎上引入了改進的慣性權重正弦調整，改善了算法的收斂速度和全局收斂性。為了防止算法陷入局部最優并增強粒子群優化算法跳出局部最優解的能力，在改進慣性權重算法的基礎上引入自適應變異全局極值的變異操作來尋找全局最優解。采取工件序列對應粒子位置的編碼方式，通過實驗表明，在求解基于工件動態到達的單機批調度問題上，無論從尋優能力還是運行時間方面，HPSO算法的性能要優于GA算法性能。筆者應用改進算法求解的是單機調度問題，對于應用此算法求解基于工件動態到達的多機批調度問題還有待進一步研究。