柔性車(chē)間調(diào)度的解空間距離聚類(lèi)和變鄰域搜索粒子群算法①

杜兆龍, 徐玉斌, 崔志華, 李建偉, 趙俊忠

(太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 太原 030024)

柔性車(chē)間調(diào)度的解空間距離聚類(lèi)和變鄰域搜索粒子群算法①

杜兆龍, 徐玉斌, 崔志華, 李建偉, 趙俊忠

(太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 太原 030024)

根據(jù)柔性車(chē)間調(diào)度問(wèn)題提出基于解空間距離聚類(lèi)和變鄰域搜索的粒子群算法. 在粒子群算法基礎(chǔ)上采用貪婪策略引入變鄰域搜索方式, 即調(diào)整關(guān)鍵路徑上最大關(guān)鍵工序的機(jī)器位置, 調(diào)整關(guān)鍵路徑上工序相對(duì)位置變化, 加強(qiáng)局部搜索能力; 根據(jù)機(jī)器加工工序的空間距離, 采用K-means聚類(lèi)得到機(jī)器加工工序“優(yōu)良個(gè)體”, 加大局部搜索性能. 同時(shí)對(duì)于粒子群算法速度更新采用局部停滯策略, 保留局部片段相對(duì)位置不變特性. 通過(guò)實(shí)驗(yàn)仿真, 優(yōu)化算法取得了較好的效果, 與一般的粒子群算法相比較收斂速度迅速且性能良好.

柔性車(chē)間調(diào)度; 變鄰域搜索; 空間距離K-means聚類(lèi); 速度局部停滯

柔性車(chē)間調(diào)度是車(chē)間生產(chǎn)中的一類(lèi)特殊形式. 所謂的柔性車(chē)間調(diào)度是指m臺(tái)機(jī)器加工n件工件, 每個(gè)工件每個(gè)工序可以在多臺(tái)機(jī)器上加工完成, 最終得到一種調(diào)度安排使得n種工件加工完成的時(shí)間最小的方案[1,2]. 該類(lèi)問(wèn)題因其隨著工件和機(jī)器規(guī)模的擴(kuò)大, 其求解規(guī)模伴隨有爆炸性特點(diǎn). 研究已經(jīng)證實(shí)柔性車(chē)間調(diào)度問(wèn)題是一類(lèi)非確定多項(xiàng)式NP難問(wèn)題[3]. 因此用直接查找算法很難獲得較優(yōu)的答案; 然而伴隨著啟發(fā)式搜索算法和群智能算法的發(fā)展, 則出現(xiàn)了越來(lái)越多的近似求解算法.

針對(duì)柔性車(chē)間的調(diào)度問(wèn)題, 已有研究主要有: 遺傳算法、粒子群算法、蜂群算法、蟻群算法、免疫算法等. 為了增強(qiáng)求解問(wèn)題的能力, 相關(guān)學(xué)者進(jìn)行了一系列研究. 曾建潮、崔志華等[4]提出一種基于主動(dòng)調(diào)度編碼的遺傳算法, 實(shí)現(xiàn)將所有工序以不可重復(fù)的自然數(shù)進(jìn)行編碼, 優(yōu)點(diǎn)是編碼唯一且可行. 孔飛[5]提出的基于雙層粒子群優(yōu)化算法ITLPSO, 以工件號(hào)為工序編碼, 相同工件的工序編碼相同, 同時(shí)采用慣性權(quán)重w凸凹函數(shù)變化及其停滯阻滯策略, 在一定程度上加速收斂性能和搜索規(guī)模. 董蓉等[6]則提出一種以析取圖模型為基礎(chǔ)的混合GA-CAO算法, 在遺傳算法結(jié)果基礎(chǔ)上利用蟻群算法尋得較優(yōu)的解. 徐華等[7]提出的DPSO算法使用基于NEH的最短用時(shí)分解策略避免早熟和提高全局搜索能力. 謝志強(qiáng)等[8]提出的動(dòng)態(tài)關(guān)鍵路徑策略和短用時(shí)調(diào)度策略實(shí)現(xiàn)以縱向?yàn)橹骷骖櫃M向的雙向調(diào)度優(yōu)化. 趙詩(shī)奎[9]提出基于空閑時(shí)間的鄰域結(jié)構(gòu)給出最大限度查詢(xún)關(guān)鍵工序相關(guān)機(jī)器空閑時(shí)間的方法, 移動(dòng)關(guān)鍵工序到空閑時(shí)間位置實(shí)現(xiàn)搜索優(yōu)化.張國(guó)輝[10]對(duì)VNS-變鄰域搜索進(jìn)行了總結(jié), 強(qiáng)調(diào)利用某種算法為VNS提供較好質(zhì)量的初始解集. 高永超[11]參考的Big Valley分布理論和骨架尺寸的研究與討論,其中Boose推斷TSP等類(lèi)似問(wèn)題的最優(yōu)解分布于一個(gè)大谷內(nèi). 孫元?jiǎng)P等[12]提出的解空間距離矩陣、衡量解空間規(guī)模的特征數(shù)和分隔因子、決定局部解空間崎嶇形狀的加工時(shí)間分布形式, 給出問(wèn)題難易程度的衡量標(biāo)準(zhǔn). 已有研究表明, 單一算法在全局或者局部搜索過(guò)程中都存在一定問(wèn)題. 同時(shí)對(duì)于柔性車(chē)間調(diào)度問(wèn)題本身特性的研究也有助于算法性能的提高.

由于柔性車(chē)間調(diào)度問(wèn)題復(fù)雜性, 本文采用一種基于解空間距離聚類(lèi)和變鄰域搜索策略的PSO算法, 附加速度停滯控制, 在調(diào)度過(guò)程中不斷優(yōu)化機(jī)器工序位置, 以得到近似最優(yōu)解.

1 問(wèn)題描述

柔性車(chē)間調(diào)度問(wèn)題, 是指具有m臺(tái)機(jī)器, 加工n件工件的調(diào)度優(yōu)化問(wèn)題. 加工工件的機(jī)器集合為為第i臺(tái)機(jī)器,i=1,2,3,...,m. 工件的集合為第j件工件,j=1,2,3,...,n. 每個(gè)工件的工序數(shù)和加工次序都是確定的, 對(duì)應(yīng)于每個(gè)工件的工序集合, 如工件pj對(duì)應(yīng)的工序數(shù)為nj, 故對(duì)應(yīng)的工序集而所有工件對(duì)應(yīng)的工序數(shù)集合對(duì)應(yīng)第j個(gè)工件的總工序數(shù). 工件的工序集在機(jī)器集上加工時(shí)間矩陣為大小為的矩陣. 如果工序不能在機(jī)器上加工, 設(shè)置相應(yīng)的時(shí)間設(shè)置為0標(biāo)記. 時(shí)間矩陣集合目標(biāo)函數(shù)為最后一個(gè)被加工完的工件時(shí)間的最小值, 即:

其中Cj為第j個(gè)工件加工完成時(shí)的時(shí)間.

同時(shí)在建模過(guò)程中假設(shè):

1) 同工件同時(shí)刻至多一道工序在某臺(tái)機(jī)器加工;

2) 同時(shí)刻某臺(tái)機(jī)器至多加工一工件的一道工序;

3) 工件開(kāi)始加工后必須完成該工件所有工序;

4) 工件加工按照確定的加工工序次序進(jìn)行;

5) 每一工序只能在一臺(tái)機(jī)器上加工, 不能選擇多臺(tái)機(jī)器.

2 基于解空間和鄰域搜索策略粒子群算法

2.1 微粒群算法

Kennedy和Eberhart共同提出的微粒群算法[13],主要是針對(duì)于鳥(niǎo)類(lèi)群體行為的覓食或者飛向棲息地的過(guò)程的建模. 在飛行進(jìn)化過(guò)程中主要受個(gè)體速度慣性部分、個(gè)體認(rèn)知部分、群體社會(huì)認(rèn)知三部分影響. 標(biāo)準(zhǔn)的微粒群算法包括速度和位移兩個(gè)進(jìn)化公式:

vj(t+1)為第(t+1)代第j個(gè)微粒的速度,xj(t+1)為第(t+1)代第j個(gè)微粒的位置, w為相應(yīng)的慣性權(quán)重,c1為個(gè)體認(rèn)知系數(shù),c2為社會(huì)系數(shù),為服從均勻分布的隨機(jī)數(shù);為第t代第j個(gè)微粒的個(gè)體歷史最優(yōu)位置,為第t代的群體歷史最優(yōu)位置.

針對(duì)車(chē)間生產(chǎn)調(diào)度, 首先是工序和機(jī)器的編碼問(wèn)題. 機(jī)器按照機(jī)器順序編碼. 工序編碼是按照某工件當(dāng)前出現(xiàn)次數(shù)表示該工件的工序數(shù)的編碼方式. 如工件數(shù)2、機(jī)器數(shù)3, 每個(gè)工件都包含3道工序, 下面矩陣中第一行表示工序排列, 第二行表示對(duì)應(yīng)工序加工所在機(jī)器排列. 矩陣第一列中工件號(hào)為1, 且第一次出現(xiàn), 代表工件1的第一道工序, 機(jī)器號(hào)為2; 第四列中工件號(hào)也為1, 但是工件號(hào)1到當(dāng)前位置已出現(xiàn)3次,故代表工件1的第三道工序, 機(jī)器號(hào)為1.

2.2 速度局部停滯控制

由Big Valley分布理論和骨架尺寸的研究與討論, Boose推斷TSP類(lèi)似問(wèn)題的最優(yōu)解可能分布于一個(gè)大谷內(nèi), 因此對(duì)于調(diào)度方面問(wèn)題也可以考慮對(duì)于局部進(jìn)行特殊搜索.

定義1. 種群中個(gè)體對(duì)于本次進(jìn)化, 其中某段或者某幾片段的進(jìn)化速度強(qiáng)制控制為0, 本次操作完成后,在下次的操作中再以極小概率選擇部分片段再次進(jìn)行強(qiáng)制控制, 這種控制稱(chēng)為速度局部停滯控制.

未選擇控制部分, 其工序位置可以自由交換. 如果所有位置自由交換都出現(xiàn)障礙, 對(duì)于搜索則會(huì)陷入停滯. 用稀疏矩陣s(i,:)和概率均勻分布矩陣u(i,:), 共同對(duì)于工序變化速度進(jìn)行選擇, 當(dāng)前第i個(gè)個(gè)體的速度停滯控制公式為:

假設(shè)之前的速度和位置分別為

變化后的速度為

而新的位置更新得到p'=[12.16112.5312],對(duì)于重新排序的到p', 第一行為位置數(shù)值, 第二行為排序序號(hào)

按照新位置的大小重新排列得到[111222],同時(shí)修正對(duì)應(yīng)的機(jī)器.

定義2. 由工件號(hào)重復(fù)多次出現(xiàn)的編碼方式造成對(duì)工件工序排列時(shí), 相同或者相鄰工件的工序容易湊到一起“扎堆”, 較遠(yuǎn)的工件號(hào)與其交流出現(xiàn)一定障礙,需要?dú)w一化操作, 以消除由于編碼產(chǎn)生的工件工序“扎堆”問(wèn)題, 這一操作稱(chēng)為工序編碼歸一化.

如果工件1各個(gè)工序的編碼都為1, 工件8各個(gè)工序編碼都為8, 這時(shí)假設(shè)工件8的工序變化為process_8=8+v, 與工件號(hào)為1,process_1=1+v_1,如果對(duì)得到的工序位置進(jìn)行排序的話(huà), 其位置交流可能就會(huì)出現(xiàn)障礙, 導(dǎo)致工件編號(hào)越小其工序越容易出現(xiàn)在調(diào)度的前面, 工件編號(hào)越大其工序越容易出現(xiàn)在后面. 為了解決這個(gè)問(wèn)題, 在進(jìn)行粒子群算法位置更新前對(duì)當(dāng)前工件工序排列進(jìn)行歸一化, 從而消除掉工件號(hào)編碼的問(wèn)題. 這里僅僅對(duì)工序編號(hào)進(jìn)行歸一化,而不對(duì)工序變化速度進(jìn)行處理, 可以保留各個(gè)工件工序變化的特殊性, 而且速度在一定程度上是個(gè)體慣性、個(gè)體和群體三者的影響結(jié)合體. 工序編碼歸一化函數(shù):

其中p為工序編碼矩陣,jobN為工件數(shù),v為工序的速度矩陣,EFp為歸一化后的工序.

2.3 解空間K-means聚類(lèi)

定義3. 如果將每個(gè)解都視為高維空間中的一個(gè)點(diǎn), 并且在高維空間中對(duì)于這些多維向量排列, 每個(gè)解都會(huì)與部分解或無(wú)效解相鄰, 由此構(gòu)成的高維向量集合, 或者說(shuō)是高維點(diǎn)陣集合, 稱(chēng)為問(wèn)題的原空間[12].

定義4. 原空間中由可行解構(gòu)成的集合稱(chēng)之為問(wèn)題的解空間[12].

定義5. 對(duì)于車(chē)間生產(chǎn)調(diào)度問(wèn)題而言, 取任意解s和t, 定義兩解之間的距離[12]:

其中PRECi,s(j,k)表示解s中第i臺(tái)機(jī)器上工序j和工序k之間的加工順序, 如果j在k的前面則否則為邏輯異或運(yùn)算符. 有是所有工件工序數(shù)之和, 在計(jì)算H(s,t)的時(shí)候采用的是工序的自然數(shù)編碼.

公式(5)衡量?jī)蓚€(gè)解之間距離, 作為種群中某個(gè)解與當(dāng)前最優(yōu)解的距離計(jì)算公式. 通過(guò)研究發(fā)現(xiàn)當(dāng)出現(xiàn)新的最優(yōu)解時(shí)當(dāng)前種群所有個(gè)體與最優(yōu)解的距離的平均值可能會(huì)發(fā)生較大的波動(dòng), 之后又會(huì)趨于穩(wěn)定直到下次出現(xiàn)新的最優(yōu)值.

對(duì)于如何衡量單個(gè)個(gè)體的性能, 以種群中某個(gè)解在所有機(jī)器上工序的逆序數(shù)和的形式表示, 表示當(dāng)前解的所有機(jī)器上的逆序數(shù)的總和, 如下

在機(jī)器i上,pi(j,k)為工序j,k逆序數(shù)表示, 如果工序j在k的前面, 那么pi(j,k)=0; 如果工序j在k的后面, 則pi(j,k)=1.

定義 6. 不同工件的工序, 如工件1的第2道工序, 和工件2,3,4,5等的第2道工序, 可以互稱(chēng)為順位工序.

如果同一工件的工序, 在同一個(gè)機(jī)器上加工, 因?yàn)榧庸ろ樞騿?wèn)題不會(huì)存在逆序數(shù); 但是不同工件的工序, 有可能產(chǎn)生逆序排列. 采用每臺(tái)機(jī)器上工序逆序數(shù)的分析, 可以確認(rèn)當(dāng)前機(jī)器上不同工件間相同順位工序被加工的次序, 如果相同順位工序排列的很緊湊、位置很靠近, 則應(yīng)該是一種較好的安排.

通過(guò)計(jì)算當(dāng)前解在每臺(tái)機(jī)器上工序的逆序數(shù), 然后進(jìn)行聚類(lèi)分析可以衡量當(dāng)前解的工件加工的工序?qū)τ趯ふ易顑?yōu)過(guò)程的影響.

2.4 變鄰域搜索策略

基于變鄰域搜索的鄰域動(dòng)作是由關(guān)鍵路徑?jīng)Q定的,目前有Nowicki和Smutnicki提出的N5結(jié)構(gòu); Balas和Vazacopoulos提出的N6結(jié)構(gòu), 張超勇提出的N7結(jié)構(gòu).在搜索可行解的基礎(chǔ)上采用機(jī)器調(diào)整和關(guān)鍵工序位置移動(dòng)策略. 首先利用整個(gè)工序的排列順序, 搜尋到相應(yīng)的關(guān)鍵路徑. 關(guān)鍵路徑可能有多條, 僅選擇其中的一條進(jìn)行調(diào)整. 其次從關(guān)鍵路徑中尋找到相應(yīng)的最大花費(fèi)工序, 簡(jiǎn)稱(chēng)最大關(guān)鍵工序. 每次進(jìn)行最大關(guān)鍵工序的機(jī)器位置調(diào)整, 同時(shí)在關(guān)鍵路徑上進(jìn)行工序位置的移動(dòng).

機(jī)器策略:

(1) 對(duì)于最大關(guān)鍵工序進(jìn)行機(jī)器調(diào)整, 選擇該工序花費(fèi)盡可能小的機(jī)器進(jìn)行調(diào)整;

(2) 關(guān)鍵路徑中工件的首道工序沒(méi)在初始時(shí)刻開(kāi)始加工的調(diào)整到某臺(tái)機(jī)器的近似開(kāi)始時(shí)刻;

(3) 關(guān)鍵路徑中最后一道工序, 如果存在可以調(diào)整機(jī)器使得調(diào)整后整體時(shí)間縮短則調(diào)整.

關(guān)鍵路徑上工序調(diào)整: 關(guān)鍵路徑上兩道工序?yàn)関w,...,vi,vi可以調(diào)整到vw之前, 除了該處位置的調(diào)整, 其它工序的相對(duì)位置不受影響, 但關(guān)鍵路徑的時(shí)間被縮短, 只要滿(mǎn)足以下條件之一:

(1) 如果vi為該道工件的首道工序, 可以直接移動(dòng);

(2) 如果vi的前道工序vi-1, 其完成的時(shí)間要比vw工序的完成時(shí)間早.

3 基于解空間和變鄰域搜索的粒子群算法

3.1 初始化PSO種群和W的變化策略

初始化PSO種群, 個(gè)體數(shù)為N, 維數(shù)為所有工件的工序數(shù)之和, 種群個(gè)體隨機(jī)產(chǎn)生. PSO慣性參數(shù)w采用凸凹函數(shù)形式:

3.2粒子群速度和位置更新

圖1 算法流程圖

對(duì)于機(jī)器更新, 假設(shè)之前機(jī)器位置如下所示m(t)=[232131], 按照之前介紹的粒子群進(jìn)化公式, 可以得到m'(t+1)=[3.52.42.20.82.42.1]向上取整則m'(t+1)=[433132], 4超出了機(jī)器編碼的范圍, 可以修正為編號(hào)為1, 則更新后的新的機(jī)器編碼為m(t+1)=[133132].

稀疏矩陣s(i,:)和概率均勻分布矩陣u(i,:); 粒子群速度v(pi,:), 位置pi等數(shù)值如下:

根據(jù)公式(3)當(dāng)前第i個(gè)個(gè)體的速度更新為

根據(jù)公式(4)歸一化工序編碼得EFp如下

EFp代替pi, 由公式(2)更新工序位置得

對(duì)得到的工序位置進(jìn)行升序排列

按照新位置順序重新排列工序?yàn)閇121221],同時(shí)修正對(duì)應(yīng)的機(jī)器.

3.3 空間距離K均值聚類(lèi)

根據(jù)空間距離計(jì)算的逆序數(shù)、機(jī)器加工工序數(shù)進(jìn)行聚類(lèi). 逆序數(shù)則是每臺(tái)機(jī)器上工序的逆序數(shù), 種群中每個(gè)個(gè)體的逆序數(shù)為一組向量, 整個(gè)種群則構(gòu)成一個(gè)逆序數(shù)矩陣. 機(jī)器加工工序數(shù)也是種群中每個(gè)個(gè)體由每臺(tái)機(jī)器上加工工序數(shù)組合成一個(gè)向量. 采用K-means聚類(lèi)算法, 聚類(lèi)結(jié)果數(shù)位N1, 迭代次數(shù)為Niter, 去掉重復(fù)個(gè)體. 通過(guò)聚類(lèi)可以將優(yōu)良的個(gè)體替代掉“年老”個(gè)體, 將優(yōu)良個(gè)體保持至下一代進(jìn)行進(jìn)化,提高優(yōu)良個(gè)體的局部搜索范圍.

3.4 VNS變鄰域搜索

初始化VNS搜索的最大次數(shù), 函數(shù)為

其中n為當(dāng)次循環(huán), N為循環(huán)最大次數(shù).

在循環(huán)過(guò)程中首先搜索每個(gè)個(gè)體一條關(guān)鍵路徑.在求解關(guān)鍵路徑的同時(shí), 將關(guān)鍵路徑上最大關(guān)鍵工序查找出來(lái). 將關(guān)鍵路徑上最大關(guān)鍵工序進(jìn)行相應(yīng)調(diào)整,每次只調(diào)整(1)(2)(3)中的一種情況; 然后再根據(jù)關(guān)鍵路徑上前后工序位置進(jìn)行移動(dòng); 至此完成一次工序和機(jī)器的內(nèi)部調(diào)整, 接著開(kāi)始下次VNS循環(huán).

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證實(shí)驗(yàn)效果, 采用Intel雙核處理器I5-5200U@2.20GHZ, 內(nèi)存4GB, 64為操作系統(tǒng), MATLAB為實(shí)驗(yàn)仿真工具, 采用數(shù)據(jù)集為Kacem、Hurink[14]、Brandimarte[14]等.

算法的參數(shù)設(shè)置: 種群中個(gè)體數(shù)N=60, 慣性參數(shù)W的范圍[0.1,0.9], c1=1.5,c2=1.5,r1,r2采用范圍在(0,1)之間的隨機(jī)數(shù), 慣性權(quán)重更新采用上文介紹的拋物線(xiàn)形式,整體迭代次數(shù)N=100, 當(dāng)前迭代次數(shù)為n, 因此每次VNS鄰域搜索的次數(shù)最大值設(shè)置count＜=20限制.

4.2 仿真結(jié)果

基于速度停滯控制、空間距離聚類(lèi)及變鄰域搜索的粒子群算法簡(jiǎn)稱(chēng)為SVNS-vPSO. 對(duì)于Kacem基準(zhǔn)問(wèn)題的10*10樣例, 其迭代過(guò)程中的H(s,t)距離均值變化曲線(xiàn)如圖2所示, 在當(dāng)次種群迭代中尋得較優(yōu)值時(shí)會(huì)發(fā)生H(s,t)均值跳動(dòng)反應(yīng). 因此搜索的結(jié)果極可能存在于這些跳動(dòng)位置處種群局部最優(yōu)個(gè)體身上.

對(duì)于Kacem基準(zhǔn)問(wèn)題的8*8算例, SVNS-vPSO算法生成的最優(yōu)調(diào)度甘特圖如圖3. 圖4為Kacem問(wèn)題集的本算法收斂曲線(xiàn). 表1為本算法下Kacem各個(gè)實(shí)例的具體運(yùn)行數(shù)據(jù). 對(duì)于圖4和表1表明算法能夠在較短時(shí)間與迭代次數(shù)內(nèi)獲得最優(yōu)解.

圖2 Kacem 10*10的H(s,t)均值變化曲線(xiàn)

圖3 Kacem 8*8調(diào)度優(yōu)化甘特圖

圖4 Kacem數(shù)據(jù)的算法收斂曲線(xiàn)

表2中對(duì)于PSO算法、ITLPSO雙層粒子群算法[5]、AL+CGA(局部最小化分配模型的進(jìn)化算法)、改進(jìn)GA、GA-ACO遺傳蟻群算法, 其中后三種算法參數(shù)設(shè)置按董蓉文中[6]參數(shù)形式, 最后搜索的結(jié)果如表2, 由數(shù)據(jù)可見(jiàn)SVNS-vPSO算法的搜索最優(yōu)和平均值較一般的粒子群算法較好, 但是在平均計(jì)算時(shí)間和平均結(jié)果上和AL+CGA、改進(jìn)GA算法比較而言相似甚至有些數(shù)據(jù)優(yōu)于它們, 但是較GA-ACO算法稍差些.

表1 Kacem各實(shí)例的計(jì)算結(jié)果統(tǒng)計(jì)

表2 Kacem基準(zhǔn)問(wèn)題各方法運(yùn)行30次結(jié)果比較

表3和表4中數(shù)據(jù)集來(lái)自于參考引用[14]網(wǎng)頁(yè)中的FJSPLIB文件. 這里選用Hurink數(shù)據(jù)集和Brandimarte數(shù)據(jù)集中數(shù)據(jù)進(jìn)行測(cè)試. 表中n代表工件數(shù), m代表機(jī)器數(shù), C**表示當(dāng)前的最優(yōu)值, Cmin為本文算法獲得的最優(yōu)值, RD(%)為本文算法最優(yōu)值與C**的相對(duì)誤差,其具體公式為:

表3 Hurink數(shù)據(jù)集[14]運(yùn)行結(jié)果

表4 Brandimarte數(shù)據(jù)集[14]運(yùn)行結(jié)果

由表3和表4測(cè)試結(jié)果表明, 該算法取得一定效果. 對(duì)于Hurink數(shù)據(jù), 當(dāng)工序數(shù)達(dá)到一定程度后, 相對(duì)誤差開(kāi)始增大; 對(duì)于Brandimarte類(lèi)型數(shù)據(jù), 其相對(duì)誤差值高些.

實(shí)驗(yàn)仿真結(jié)果表明, 當(dāng)工序數(shù)少時(shí)如Kacem問(wèn)題,可以快速搜索到有效的結(jié)果; 當(dāng)工序數(shù)增大后其效果將會(huì)出現(xiàn)一定偏差, 如Hurink和Brandimarte的數(shù)據(jù).算法中對(duì)工序和機(jī)器分別編碼, 然后進(jìn)行PSO算法速度和位置更新, 但進(jìn)化過(guò)程中兩者只有一個(gè)約束關(guān)系,即工序能不能夠在此機(jī)器上加工. 也就是說(shuō)工序和機(jī)器的進(jìn)化兩者近似于彼此獨(dú)立, 缺少進(jìn)化的有效協(xié)同,無(wú)法形成統(tǒng)一整體. 對(duì)工序和機(jī)器進(jìn)行整體編碼的方式, 可以解決類(lèi)似的問(wèn)題, 但其設(shè)計(jì)方法則更困難.

5 結(jié)語(yǔ)

本文對(duì)于柔性車(chē)間調(diào)度問(wèn)題提出了SVNS-vPSO算法. 即通過(guò)解空間距離K均值聚類(lèi)、貪婪變鄰域搜索、粒子群停滯控制等策略提高了優(yōu)化算法的收斂速度和搜索結(jié)果. 通過(guò)研究發(fā)現(xiàn), 工序與機(jī)器之間彼此近似孤立進(jìn)化, 將影響整體的搜索結(jié)果. 下一步對(duì)工序和機(jī)器進(jìn)化進(jìn)行協(xié)同研究, 或者是采用工序和機(jī)器整體編碼的方式[15]研究. 同時(shí)對(duì)于機(jī)器使用率和整體加工時(shí)間等多目標(biāo)優(yōu)化問(wèn)題可以通過(guò)基于空間距離、機(jī)器逆序數(shù)等因素進(jìn)行優(yōu)化研究.

1 Brucker P, Schlie R. Job-Shop scheduling with multipurpose machines. Computing, 1990, 45(4): 369–375.

2 Mati Y, Rezg N, Xie XL. An intergrated greedy heuristic for a flexible job shop scheduling problem. Proc. of IEEE International Conference on Systems, Man, and Cyberneticcs. Washington, D.C., USA. IEEE. 2001. 2534–2539.

3 Blazewica J, Finke G, Haaopt G, et al. New trends in machine scheduling. European Journal of Operational Research, 1988, 37(3): 303–317.

4 曾建潮,崔志華,等.自然計(jì)算.長(zhǎng)沙:國(guó)防工業(yè)出版社,2012.

5 孔飛,吳定會(huì),等.基于雙層粒子群優(yōu)化算法的柔性作業(yè)車(chē)間調(diào)度優(yōu)化.計(jì)算機(jī)應(yīng)用,2015,35(2):476–480.

6 董蓉,何衛(wèi)平.求解FJSP的混合遺傳-蟻群算法.計(jì)算機(jī)集成制造系統(tǒng)2012,18(11):2492–2501.

7 徐華,張庭.改進(jìn)離散粒子群算法求解柔性流水車(chē)間調(diào)度問(wèn)題.計(jì)算機(jī)應(yīng)用,2015,35(5):1342–1347,1352.

8 謝志強(qiáng),楊靜等.基于工序集的動(dòng)態(tài)關(guān)鍵路徑多產(chǎn)品制造調(diào)度算法.計(jì)算機(jī)學(xué)報(bào),2011,34(2):406–412.

9 趙詩(shī)奎,方水良,等.作業(yè)車(chē)間調(diào)度的空閑時(shí)間鄰域搜索遺傳算法.計(jì)算機(jī)集成制造系統(tǒng),2014,20(8):1930–1940.

10 張國(guó)輝.柔性作業(yè)車(chē)間調(diào)度方法研究[博士學(xué)位論文].上海:華中科技大學(xué),2009.

11 高永超.智能優(yōu)化算法的性能及搜索空間研究[博士學(xué)位論文].濟(jì)南:山東大學(xué),2007.

12 孫元?jiǎng)P,劉民,等.調(diào)度問(wèn)題及其解空間的特征分析.電子學(xué)報(bào),2001,29(8):1042–1045.

13 Eberhart R, Kennedy J. New optimizer using particle swarm theory. Proc. of the Sixth International Symposium on Micro Machine and Human Science, MHS’95. IEEE, Piscataway, NJ, USA. 1995. 39

14 http://people.idsia.ch/～monaldo/fjsp.html.

15 Singh MR, Mahapatra SS. A quantum hehaved particle swarm optimization for flexible job shop scheduling. Computer & Industrial Engineering. 2016, 93: 36–44.

Solution Space Distance Clustering-Variable Neighborhood Search Particle Swarm Optimization for Flexible Job Shop Scheduling Problem

DU Zhao-Long, XU Yu-Bin, CUI Zhi-Hua, LI Jian-Wei, ZHAO Jun-Zhong
(Department of Computer Science and Technology, Taiyuan University of Science and Technology, Taiyuan 030024, China)

Based on the Flexible Job-Shop Scheduling Problem(FJSP), an improved particle swarm optimization algorithm is proposed, which is based on solution space distance clustering and variable neighborhood search. In this algorithm, a better solution to the problem is that the greedy strategy is adopted to introduce a variable neighborhood search method, adjusting machine location of the biggest key processes on the critical path, adjusting the relative position changes which is on the critical path. According to the space distance of the machining process, the K-means clustering is used to get the “excellent individuals” of machine processing, increasing the local search performance. At the same time, the speed of the particle swarm optimization is updated with the local self-adaptive stagnation strategy, and the relative position of the local segment could be kept unchanged. Through the experimental simulation, the optimization algorithm achieves good effectiveness, and the convergence speed is rapider and the performance is better compared with the general PSO algorithm.

flexible job shop scheduling problem; variable neighborhood search; space distance K-means clustering; velocity local stagnation

2016-03-14;收到修改稿時(shí)間:2016-04-29

10.15888/j.cnki.csa.005482