改進人工免疫算法求解柔性作業車間調度問題

張永強， 高銳敏

(1.河南財經政法大學 計算機與信息工程學院 河南 鄭州 450002；2.河南牧業經濟學院 基礎部 河南 鄭州 450044)

改進人工免疫算法求解柔性作業車間調度問題

張永強1， 高銳敏2

(1.河南財經政法大學 計算機與信息工程學院 河南 鄭州 450002；2.河南牧業經濟學院 基礎部 河南 鄭州 450044)

柔性作業車間的合理調度是提高生產效率和效益的關鍵，為了解決柔性作業車間調度問題求解過程中的難題，提出一種改進人工免疫算法的柔性作業車間調度方法.首先對當前柔性作業車間調度的研究現狀進行分析，然后基于總加工時間最短構建數學模型，采用人工免疫算法進行求解，并針對標準人工免疫算法存在的不足，引入粒子群算法保持種群的多樣性，以避免出現局部最優解，最后采用標準算例集對算法的性能進行仿真測試.結果表明，相對于其他算法，改進人工免疫算法獲得了較優的柔性作業車間調度方案，尤其在解決大規模問題時，優勢更加顯著.

柔性車間調度； 人工免疫算法； 粒子群優化算法； 變異算子

0 引言

隨著生產制造市場化的加劇，生產資源并不是可無限利用的，單從每道工序的加工時間來講也往往不是一成不變的，這便形成了生產過程的柔性.柔性作業車間調度問題(flexible job-shop scheduling problem，FJSP)應運而生，其更加符合實際的生產情況，但是也增加了問題的復雜性[1].FJSP是一種典型的組合優化問題，屬于非確定性多項式(non-deterministic polynomial,NP)難題，一直是生產制造業領域研究中的重點和難點[2].

針對FJSP問題，大量學者和研究人員投入了許多時間和精力進行深入研究，取得了一些研究進展，提出許多FJSP問題求解算法[3].當前FJSP問題的求解算法大致可分為3類：精確求解算法、啟發式算法和人工智能算法.分支定界法是最為經典的精確求解算法，其簡單、易實現，對于小規模FJSP問題，求解效率高；然而隨著生產制造業規模的不斷壯大，加工產品規模越來越大，分支定界法難以滿足現代生產制造業的FJSP問題求解要求[4].

啟發式算法最具代表性的為拉格朗日松弛法，其對小規模FJSP問題求解效率高，但是存在精確求解算法一樣的缺陷，應用范圍受限[5].人工智能算法主要通過模擬自然界的生物群體行為，具有并行性、搜索速度快等優點，在FJSP問題求解中應用最廣，成為當前主要的研究方向[6].

一些學者采用遺傳算法、模擬退火、微粒群優化算法、蟻群算法、螢火蟲算法對FJSP問題進行求解，獲得了比較好的效果[7-9].然而在實際應用中，這些人工智能算法均存在各自不足，如后期收斂速度慢、易獲得局部最優解等.相對于其他進化算法，人工免疫算法(artificial Immune algorithm，AIA)具有較好的全局搜索能力，己經在云計算資源調度、機器人路徑規劃等領域成功應用[10]，為解決FJSP問題提供了新的研究工具.

為獲得更加理想的FJSP問題優化方案，降低生產制造業生產成本，本文提出一種改進人工免疫算法(modified artificial immune algorithm，MAIA)的FJSP問題求解方法，并采用一些標準算例對算法的性能進行測試.

1 FJSP的數學模型

FJSP的目標函數為：

式中的相關參數定義見文獻[11] .

2 改進人工免疫算法求解FJSP

2.1 人工免疫算法

人工免疫算法是一種受生物免疫系統啟發的算法，相對其他算法更簡單、易實現，比較適合于FJSP問題的求解，其工作流程如圖1所示[12].

2.2 人工免疫算法的改進

粒子群優化(particle swarm optimization，PSO)算法，相對于其他進化算法如遺傳算法，易于實現﹑調整參數少，在許多領域得到了廣泛應用.第i個粒子位置表示為向量Xi=(xi1,xi2,…,xiD)，第i個粒子歷史最優位置為Pi=(pi1,pi2,…,piD)，整個粒子群歷史最優位置為Pg=(pg1,pg2,…,pgD)，第i個粒子的速度為向量Vi=(vi1,vi2,…,viD)，每個粒子的位置按如下公式進行變化：

其中:c1,c2為正常數，稱為加速常數；rand ()為[0,1]之間的隨機數；ω為慣性權[13].

AIA算法到了后期，易使種群多樣性降低，出現局部最優解概率大.為此，本文融合了粒子種群優化算法與人工免疫算法的優點，將PSO算法引入到抗體優化過程中，提出一種改進人工免疫算法.

為了測試本文對AIA改進的有效性，采用標準函數測試AIA和MAIA的性能 .

f2(x)=exp(-(x1-4)2-(x2-4)2)+exp(-(x1+4)2-(x2-4)2)+

對于上述函數，AIA和MAIA的求解結果如圖2所示.對圖2的結果進行對比與分析，可以發現，改進后算法優點體現在：MAIA的求解效率明顯加快，求解的精度更高，較好地解決了AIA算法存在的難題 .

圖2 人工免疫算法改進前后性能對比

2.3 求解FJSP的改進人工免疫算法設計

2.3.1 初始化種群 采用隨機方式產生初始種群，產生的種群對應著初始工序分配方案，而且滿足各個工件的所有工序的執行順序.

2.3.4 變異算子 在免疫算法中，抗體變異率的選擇需要兼顧種群的多樣性和最優解的穩定性 .本文采用基于親和度的變異率，即當親和度越大，搜索空間越小，反之則搜索空間越大，從而實現了自動調節各代抗體的搜索空間.假設k為當前迭代次數，自適應變異率為

式中：P為初始變異率；G為總迭代次數；fmax(k)為第k代抗體的最大親和度；fmax為前k代抗體的最大親和度；pl為變異調節因子.

3 MAIA在JSP問題中的應用實例

3.1 仿真參數

為了全面測試MAIA算法的性能，在Intel 雙核 2.85 GHz的CPU，4GB的RAM，Windows XP的個人計算機上，采用VC++語言編程實現算法.在標準算例集XWdata[14]中選取8工件8機器、10工件10機器以及15工件10機器的3個不同規模問題進行仿真測試.

為了使本文的結果更具說服力，選擇粒子群優化算法(PSO)、遺傳算法(GA)、基本人工免疫算法(AIA)進行對比實驗.粒子群優化算法參數設置為：學習因子c1=c2=2，種群大小為20；遺傳算法的參數設置為：交叉概率為Pc=0.85，變異概率為Pm=0.01，種群大小為20；改進人工免疫算法的參數設置為：初始變異率p=0.95；種群大小為10.

3.2 結果與分析

3.2.1MAIA的求解結果MAIA對3組算例仿真結果的甘特圖如圖3～圖5所示.從圖3～圖5可知，MAIA可以對FJSP問題進行有效求解，獲得十分理想的柔性車間調度方案，優化結果可以為生產制造業提供有價值的參考意見，有利于企業提高生產效率，降低成本，創造更多的利潤.

圖3 8×8的 JSP 求解結果

圖4 10×10的 JSP 求解結果

圖5 15×10的 JSP 求解結果

3.2.2 與其他算法性能對比 MAIA、AIA、PSO、GA的20次仿真實驗的結果如表1所示，主要統計找到最優的解次數及相應的迭代次數.從表1可以看出，對于8×8問題、10×10問題以及15×10問題， MAIA得到最優解成功次數顯著高于對比算法.而且得到最優解的迭代次數相對較少，綜合性能要優于對比算法.對比結果表明，MAIA具有種群規模小、迭代次數少的優點，在解決大規模問題時，具有較好的穩定性和收斂性.

表1 不同算法的算例集實驗結果對比

圖6 算法的平均CPU時間對比Fig.6 Average CPU time of the above algorithm

3.2.3 求解效率對比 為了測試所有算法對柔性作業車間調度問題的求解效率，采用平均執行時間作為性能評價指標，所有算法平均執行時間統計結果如圖6所示.從圖6可以清楚看出，相對于其他算法，MAIA的平均CPU時間最短，求解速度最快，大幅度提高了FJSP的求解效率，可以滿足大規模制造業的FJSP優化要求，這主要是由于MAIA集成了人工免疫算法和粒子群算法全局搜索能力優點，可在較短時間內得到滿意解.

4 結束語

柔性作業車間調度通常面臨多個相互矛盾的優化目標，有多個條件約束.針對柔性車間調度問題，融合了粒子種群優化算法與人工免疫算法的優點，提出一種改進人工免疫算法的FJSP求解方法，將粒子群優化算法作為算子嵌入人工免疫算法中，增加了種群的多樣性，避免陷入局部最優問題出現.通過標準算例集XWdata對算法性能進行測試，并與其他智能算法進行對比仿真實驗.結果表明，MAIA較好地克服其他人工智能算法存在的缺陷，加快了問題的尋優速度，可在較短時間內得到滿意解.仿真實驗結果證明了本文算法的有效性和優越性.

[1] 曾強, 沈玲, 潘啟東, 等. 批量生產柔性作業車間多目標精細化調度方法[J]. 計算機工程與應用, 2014, 50(2): 263-270.

[2] GUO Y D, LUN S X. Flow shop scheduling problem with partial skill flexibility of workers[J]. Journal of Bohai university, 2013, 34(2):232-236.

[3] FENG M Y. A grouping particle swarm optimization algorithm for flexible job shop scheduling problem[C]∥ Proceedings of IEEE Pacific-asia Workshop on Computational Intelligence and Industrial Application. Wuhan, 2008: 332-336.

[4] RUIZ R, VAZQUEZ R J A. The hybrid flow shop scheduling problem[J]. European journal of operational research, 2010, 205(1): 1-18.

[5] KAHRAMAN C, ENGIN O, KAYA I, et al. Multiprocessor task scheduling in multistage hybrid flow-shops: a parallel greedy algorithm approach[J].Applied soft computing, 2010, 10(4): 1293-1300.

[6] ZHANG G H,ZHANG L J,WANG Y C,et al. An effective hybrid particle swarm optimization algorithm for flexible job-shop scheduling problem[J]. The open automation and control systems journal, 2014,6(1):1604-1611.

[7] 王長明, 聶建軍. 基于遺傳算法的二次曲面提取技術研究[J]. 鄭州大學學報(理學版),2013,45(1):65-68.

[8] 劉長平, 葉春明. 置換流水車間調度問題的螢火蟲算法求解[J].工業工程與管理,2012,17(3):56-59.

[9] 宋雪楓, 融合蟻群算法和遺傳算法的矩形件排樣問題研究[D]. 鄭州:鄭州大學, 2011.

[10] 唐建平, 宋紅生, 王東署. 一種移動機器人動態環境下的路徑規劃[J]. 鄭州大學學報(理學版), 2012, 44(1): 75-78.

[11] 薛宏全, 魏生民, 張鵬, 等. 基于多種群蟻群算法的柔性作業車間調度研究[J]. 計算機工程與應用, 2013, 49(24): 243-248.

[12] 申麗君, 劉麗, 陸銳, 等. 基于改進免疫進化算法的云計算任務調度[J]. 計算機工程, 2012, 38(9): 208-210.

[13] 宋存利. 求解柔性作業調度問題的協同進化粒子群算法[J]. 計算機工程與應用, 2013, 49(21): 15-18.

[14] ALVAREZ V R,FUERTES A, TAMARIT J M,et al. A heuristic to schedule flexible job shop in a glass factory [J]. European journal of operational research, 2005, 165(2):525-534.

(責任編輯：王浩毅)

Flexible Job-shop Scheduling Problem Solved by Improved Artificial Immune Algorithm

ZHANG Yongqiang1,GAO Ruimin2

(1.SchoolofComputerandInformationEngineering,HenanUniversityofEconomicsandLaw,Zhengzhou450002,China;2.DepartmentofBasicCourse,HenanUniversityofAnimalHusbandryandEconomy,Zhengzhou450044,China)

A novel flexible job shop scheduling method based on improved artificial immune algorithm was proposed. Mathematical model of the flexible job shop scheduling was established, and the total shortest processing time was taken as the objective function.The particle swarm optimization algorithm as the operator was embedded into artificial immune algorithm to maintain the diversity of population and prevent obtaining local optimal solution. The performance of the algorithm was tested by simulation experiments on standard set. Results showed that compared with other algorithms, the proposed algorithm could obtain better flexible job shop scheduling scheme, especially large-scale problems.

flexible job-shop scheduling; artificial immune algorithm； particle swarm optimization algorithm； mutation operator

2015-11-27

國家自然科學基金資助項目(61202285)；河南省科技攻關項目(132102210501).

張永強(1972—)，男，河南唐河人，副教授，主要從事智能推薦、軟件工程研究；E-mail: zyq0371@sina.com．

張永強，高銳敏.改進人工免疫算法求解柔性作業車間調度問題[J].鄭州大學學報(理學版)，2016,48(2):53-57.

TP301

A

1671-6841(2016)02-0053-05

10.13705/j.issn.1671-6841.2015288