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

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

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

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

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

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

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

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

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

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

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

1 問題描述

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

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

同時在建模過程中假設:

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

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

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

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

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

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

2.1 微粒群算法

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

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

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

2.2 速度局部停滯控制

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

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

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

假設之前的速度和位置分別為

變化后的速度為

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

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

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

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

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

2.3 解空間K-means聚類

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

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

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

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

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

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

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

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

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

通過計算當前解在每臺機器上工序的逆序數, 然后進行聚類分析可以衡量當前解的工件加工的工序對于尋找最優過程的影響.

2.4 變鄰域搜索策略

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

機器策略:

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

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

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

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

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

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

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

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

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

3.2粒子群速度和位置更新

圖1 算法流程圖

對于機器更新, 假設之前機器位置如下所示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等數值如下:

根據公式(3)當前第i個個體的速度更新為

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

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

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

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

3.3 空間距離K均值聚類

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

3.4 VNS變鄰域搜索

初始化VNS搜索的最大次數, 函數為

其中n為當次循環, N為循環最大次數.

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

4 實驗分析

4.1 實驗設計

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

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

4.2 仿真結果

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

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

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

圖3 Kacem 8*8調度優化甘特圖

圖4 Kacem數據的算法收斂曲線

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

表1 Kacem各實例的計算結果統計

表2 Kacem基準問題各方法運行30次結果比較

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

表3 Hurink數據集[14]運行結果

表4 Brandimarte數據集[14]運行結果

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

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

5 結語

本文對于柔性車間調度問題提出了SVNS-vPSO算法. 即通過解空間距離K均值聚類、貪婪變鄰域搜索、粒子群停滯控制等策略提高了優化算法的收斂速度和搜索結果. 通過研究發現, 工序與機器之間彼此近似孤立進化, 將影響整體的搜索結果. 下一步對工序和機器進化進行協同研究, 或者是采用工序和機器整體編碼的方式[15]研究. 同時對于機器使用率和整體加工時間等多目標優化問題可以通過基于空間距離、機器逆序數等因素進行優化研究.

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 曾建潮,崔志華,等.自然計算.長沙:國防工業出版社,2012.

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

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

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

8 謝志強,楊靜等.基于工序集的動態關鍵路徑多產品制造調度算法.計算機學報,2011,34(2):406–412.

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

10 張國輝.柔性作業車間調度方法研究[博士學位論文].上海:華中科技大學,2009.

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

12 孫元凱,劉民,等.調度問題及其解空間的特征分析.電子學報,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