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

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

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

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

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

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

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

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

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

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

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

1 問題描述

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

其中Cj為第j個工件加工完成時的時間.

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

1) 同工件同時刻至多一道工序在某臺機器加工;

2) 同時刻某臺機器至多加工一工件的一道工序;

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

4) 工件加工按照確定的加工工序次序進行;

5) 每一工序只能在一臺機器上加工, 不能選擇多臺機器.

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

2.1 微粒群算法

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

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

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

2.2 速度局部停滯控制

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

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

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

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

變化后的速度為

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

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

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

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

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

2.3 解空間K-means聚類

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

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

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

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

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

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

在機器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道工序, 可以互稱為順位工序.

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

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

2.4 變鄰域搜索策略

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

機器策略:

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

(2) 關(guān)鍵路徑中工件的首道工序沒在初始時刻開始加工的調(diào)整到某臺機器的近似開始時刻;

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

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

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

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

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

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

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

3.2粒子群速度和位置更新

圖1 算法流程圖

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

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

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

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

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

對得到的工序位置進行升序排列

按照新位置順序重新排列工序為[121221],同時修正對應(yīng)的機器.

3.3 空間距離K均值聚類

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

3.4 VNS變鄰域搜索

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

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

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

4 實驗分析

4.1 實驗設(shè)計

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

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

4.2 仿真結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語

本文對于柔性車間調(diào)度問題提出了SVNS-vPSO算法. 即通過解空間距離K均值聚類、貪婪變鄰域搜索、粒子群停滯控制等策略提高了優(yōu)化算法的收斂速度和搜索結(jié)果. 通過研究發(fā)現(xiàn), 工序與機器之間彼此近似孤立進化, 將影響整體的搜索結(jié)果. 下一步對工序和機器進化進行協(xié)同研究, 或者是采用工序和機器整體編碼的方式[15]研究. 同時對于機器使用率和整體加工時間等多目標(biāo)優(yōu)化問題可以通過基于空間距離、機器逆序數(shù)等因素進行優(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 曾建潮,崔志華,等.自然計算.長沙:國防工業(yè)出版社,2012.

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

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

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

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

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

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

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

12 孫元凱,劉民,等.調(diào)度問題及其解空間的特征分析.電子學(xué)報,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;收到修改稿時間:2016-04-29

10.15888/j.cnki.csa.005482