混合粒子群算法求解單機(jī)批調(diào)度問題

?？×?孟彥軍 王 慶 葉 賓

(中國(guó)礦業(yè)大學(xué)信息與電氣工程學(xué)院，江蘇 徐州 221006)

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

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

1 數(shù)學(xué)模型①

單機(jī)批調(diào)度問題描述如下：工件到達(dá)之后，在滿足機(jī)器容量Bmax和工件到達(dá)時(shí)間的約束下，可以將多個(gè)工件作為一批同時(shí)進(jìn)行加工，并且只有加工時(shí)間相同的工件才可以加入同一批中，同一批工件具有相同的開始和結(jié)束加工時(shí)間。從一批開始加工直到該批加工完成，該過程不允許中斷，也不允許有工件中途退出或加入該批，因?yàn)橥慌械墓ぜ梢慌_(tái)機(jī)器進(jìn)行加工，具有共同速度，所以批加工時(shí)間由批中工件的加工時(shí)間最大的工件決定。到達(dá)時(shí)間、交貨期都是已知的。

根據(jù)上述描述，所求問題的數(shù)學(xué)模型和約束條件為：

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)

優(yōu)化目標(biāo)函數(shù)為：

minLmax=max(Li)

(7)

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

單機(jī)批調(diào)度問題可以分為兩個(gè)過程：工件成批和批的加工。工件成批主要是對(duì)工件到達(dá)時(shí)間按升序排列后，在滿足機(jī)器批容量的前提下，已到達(dá)工件中加工時(shí)間相等的工件加入一批，否則新建批。分批完成后將工件分配到批處理機(jī)進(jìn)行加工，得到目標(biāo)函數(shù)。

2 算法設(shè)計(jì)

2.1 標(biāo)準(zhǔn)粒子群(PSO)算法描述

基于微粒群優(yōu)化算法獨(dú)特的搜索機(jī)制，PSO算法首先在可行解空間和速度空間隨機(jī)初始化微粒群，即確定微粒的初始位置和初始速度，通過評(píng)價(jià)各微粒的目標(biāo)函數(shù)，確定t時(shí)刻每個(gè)微粒所經(jīng)過的最佳位置pi和群體最佳位置pg，再按下列公式分別更新各微粒的速度和位置：

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

(8)

xijk+1=xijk+vijk+1

(9)

式中c1——自身經(jīng)驗(yàn)學(xué)習(xí)因子；

c2——社會(huì)經(jīng)驗(yàn)學(xué)習(xí)因子；

r1、r2——[0,1]之間的隨機(jī)數(shù)；

w——慣性權(quán)重因子。

2.2 混合粒子群算法

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

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

2.2.1慣性權(quán)重正弦調(diào)整

首先對(duì)由式(8)、(9)組成的系統(tǒng)進(jìn)行穩(wěn)定性分析。為便于表達(dá)，把式(8)、(9)中的問題簡(jiǎn)化為一維，記φ1=c1r1，φ2=c2r2，則粒子i的運(yùn)動(dòng)狀態(tài)方程為：

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

(10)

xik+1=xik+vik+1

(11)

根據(jù)文獻(xiàn)[14]所得結(jié)論可知：

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

(12)

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

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

(13)

粒子的位置變化過程也是一個(gè)二階差分方程。將粒子速度變化過程看成是一個(gè)時(shí)間連續(xù)過程，對(duì)時(shí)間求導(dǎo)得到一個(gè)典型的二階差分方程：

(14)

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

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

(15)

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

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

(16)

特征方程的所有零點(diǎn)均在z平面上一個(gè)以原點(diǎn)為圓心的單位圓內(nèi),這是二階線性系統(tǒng)穩(wěn)定的必要條件。由羅斯判據(jù)可知二階線性系統(tǒng)穩(wěn)定的充要條件是特征方程各項(xiàng)系數(shù)均為正值，可得式(13)穩(wěn)定的條件為：

(17)

由于φ1、φ2為正實(shí)數(shù)，所以在不考慮隨機(jī)量且個(gè)體最優(yōu)值、全局最優(yōu)值位置不變的情況下，單個(gè)粒子速度變化過程穩(wěn)定的條件由式(17)的后兩個(gè)不定式?jīng)Q定，且兩個(gè)條件不能同時(shí)取等號(hào)，滿足條件時(shí)單個(gè)粒子的速度將趨向于0。用同樣的方法對(duì)粒子位置變化過程進(jìn)行分析，得到粒子位置變化過程穩(wěn)定的條件：

(18)

較大的w值有利于跳出局部最優(yōu)，進(jìn)行全局尋優(yōu)；較小的w值有利于局部尋優(yōu)，加速算法收斂。筆者提出一種正弦調(diào)整的粒子群算法慣性權(quán)重：

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)區(qū)間的隨機(jī)數(shù)，式(17)、(18)所有條件均可得到滿足，從理論上說明了粒子群算法的收斂性能。由正弦變化規(guī)律可知w值的變化對(duì)算法的影響，在算法開始時(shí)粒子在其自身附近作局部尋優(yōu)，在一定時(shí)期后粒子的搜索范圍逐漸增大，進(jìn)行全局尋優(yōu)，最后讓最優(yōu)粒子進(jìn)行局部搜索。

2.2.2自適應(yīng)變異全局最優(yōu)值

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

(20)

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

(21)

由于粒子在當(dāng)前全局最優(yōu)值gBest的作用下可能發(fā)現(xiàn)更好的位置，因此新算法將變異操作設(shè)計(jì)成一個(gè)隨機(jī)算子，即對(duì)滿足變異條件的gBest按一定的概率pm變異。pm的計(jì)算公式如下：

(22)

其中，k=rand(0.1,0.3)；σd2的取值與實(shí)際問題有關(guān)，一般遠(yuǎn)小于σ2的最大值；fd可以設(shè)置為理論最優(yōu)值。

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

gBestk=gBestk(1+0.5η)

(23)

首先判斷算法是否滿足收斂準(zhǔn)則，如果不滿足，對(duì)粒子進(jìn)行位置和速度的更新，判斷此時(shí)粒子適應(yīng)度值是否滿足fi

3 實(shí)驗(yàn)設(shè)計(jì)與仿真

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

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

表1 兩種算法運(yùn)行結(jié)果的比較

表2 兩種算法運(yùn)行時(shí)間的比較

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

圖1 運(yùn)算結(jié)果均值和運(yùn)行時(shí)間百分比偏差

圖2 標(biāo)準(zhǔn)差值的分布

由圖1可知，HPSO算法相對(duì)GA算法有一定的改進(jìn)，但對(duì)于J1t1算例均值百分比偏差出現(xiàn)不穩(wěn)定的狀態(tài)，對(duì)于大部分算例是隨著問題規(guī)模的增大效果越明顯，而且兩種不同加工時(shí)間下相比較，改進(jìn)比較穩(wěn)定。對(duì)于運(yùn)行時(shí)間的改進(jìn)則表明，隨著問題規(guī)模的增大，改進(jìn)效果越明顯，表現(xiàn)在算例中則是收斂速度變大?？傮w來說HPSO算法更能適應(yīng)復(fù)雜的調(diào)度環(huán)境。

由圖2可以看出，除了算例J3t1和J3t2的標(biāo)準(zhǔn)差出現(xiàn)波動(dòng)外，HPSO算法的標(biāo)準(zhǔn)差均比GA算法的小，表明HPSO算法的尋優(yōu)能力比GA算法尋優(yōu)能力強(qiáng)，能夠跳出局部最優(yōu)區(qū)域。標(biāo)準(zhǔn)差表明組內(nèi)算例間的離散程度，也就是算例結(jié)果偏離平均值的程度，同時(shí)反映數(shù)據(jù)波動(dòng)范圍大小，能不能在有限的迭代次數(shù)內(nèi)尋到最優(yōu)值。由此可知，HPSO算法所得數(shù)據(jù)波動(dòng)范圍較小，更適合對(duì)此類調(diào)度問題分析。

4 結(jié)束語

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