張永強(qiáng)， 高銳敏

(1.河南財(cái)經(jīng)政法大學(xué) 計(jì)算機(jī)與信息工程學(xué)院 河南 鄭州 450002；2.河南牧業(yè)經(jīng)濟(jì)學(xué)院 基礎(chǔ)部 河南 鄭州 450044)

改進(jìn)人工免疫算法求解柔性作業(yè)車間調(diào)度問題

張永強(qiáng)1， 高銳敏2

(1.河南財(cái)經(jīng)政法大學(xué) 計(jì)算機(jī)與信息工程學(xué)院 河南 鄭州 450002；2.河南牧業(yè)經(jīng)濟(jì)學(xué)院 基礎(chǔ)部 河南 鄭州 450044)

柔性作業(yè)車間的合理調(diào)度是提高生產(chǎn)效率和效益的關(guān)鍵，為了解決柔性作業(yè)車間調(diào)度問題求解過程中的難題，提出一種改進(jìn)人工免疫算法的柔性作業(yè)車間調(diào)度方法.首先對(duì)當(dāng)前柔性作業(yè)車間調(diào)度的研究現(xiàn)狀進(jìn)行分析，然后基于總加工時(shí)間最短構(gòu)建數(shù)學(xué)模型，采用人工免疫算法進(jìn)行求解，并針對(duì)標(biāo)準(zhǔn)人工免疫算法存在的不足，引入粒子群算法保持種群的多樣性，以避免出現(xiàn)局部最優(yōu)解，最后采用標(biāo)準(zhǔn)算例集對(duì)算法的性能進(jìn)行仿真測(cè)試.結(jié)果表明，相對(duì)于其他算法，改進(jìn)人工免疫算法獲得了較優(yōu)的柔性作業(yè)車間調(diào)度方案，尤其在解決大規(guī)模問題時(shí)，優(yōu)勢(shì)更加顯著.

柔性車間調(diào)度； 人工免疫算法； 粒子群優(yōu)化算法； 變異算子

0 引言

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

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

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

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

為獲得更加理想的FJSP問題優(yōu)化方案，降低生產(chǎn)制造業(yè)生產(chǎn)成本，本文提出一種改進(jìn)人工免疫算法(modified artificial immune algorithm，MAIA)的FJSP問題求解方法，并采用一些標(biāo)準(zhǔn)算例對(duì)算法的性能進(jìn)行測(cè)試.

1 FJSP的數(shù)學(xué)模型

FJSP的目標(biāo)函數(shù)為：

式中的相關(guān)參數(shù)定義見文獻(xiàn)[11] .

2 改進(jìn)人工免疫算法求解FJSP

2.1 人工免疫算法

人工免疫算法是一種受生物免疫系統(tǒng)啟發(fā)的算法，相對(duì)其他算法更簡(jiǎn)單、易實(shí)現(xiàn)，比較適合于FJSP問題的求解，其工作流程如圖1所示[12].

2.2 人工免疫算法的改進(jìn)

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

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

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

為了測(cè)試本文對(duì)AIA改進(jìn)的有效性，采用標(biāo)準(zhǔn)函數(shù)測(cè)試AIA和MAIA的性能 .

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

對(duì)于上述函數(shù)，AIA和MAIA的求解結(jié)果如圖2所示.對(duì)圖2的結(jié)果進(jìn)行對(duì)比與分析，可以發(fā)現(xiàn)，改進(jìn)后算法優(yōu)點(diǎn)體現(xiàn)在：MAIA的求解效率明顯加快，求解的精度更高，較好地解決了AIA算法存在的難題 .

圖2 人工免疫算法改進(jìn)前后性能對(duì)比

2.3 求解FJSP的改進(jìn)人工免疫算法設(shè)計(jì)

2.3.1 初始化種群 采用隨機(jī)方式產(chǎn)生初始種群，產(chǎn)生的種群對(duì)應(yīng)著初始工序分配方案，而且滿足各個(gè)工件的所有工序的執(zhí)行順序.

2.3.4 變異算子 在免疫算法中，抗體變異率的選擇需要兼顧種群的多樣性和最優(yōu)解的穩(wěn)定性 .本文采用基于親和度的變異率，即當(dāng)親和度越大，搜索空間越小，反之則搜索空間越大，從而實(shí)現(xiàn)了自動(dòng)調(diào)節(jié)各代抗體的搜索空間.假設(shè)k為當(dāng)前迭代次數(shù)，自適應(yīng)變異率為

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

3 MAIA在JSP問題中的應(yīng)用實(shí)例

3.1 仿真參數(shù)

為了全面測(cè)試MAIA算法的性能，在Intel 雙核 2.85 GHz的CPU，4GB的RAM，Windows XP的個(gè)人計(jì)算機(jī)上，采用VC++語言編程實(shí)現(xiàn)算法.在標(biāo)準(zhǔn)算例集XWdata[14]中選取8工件8機(jī)器、10工件10機(jī)器以及15工件10機(jī)器的3個(gè)不同規(guī)模問題進(jìn)行仿真測(cè)試.

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

3.2 結(jié)果與分析

3.2.1MAIA的求解結(jié)果MAIA對(duì)3組算例仿真結(jié)果的甘特圖如圖3～圖5所示.從圖3～圖5可知，MAIA可以對(duì)FJSP問題進(jìn)行有效求解，獲得十分理想的柔性車間調(diào)度方案，優(yōu)化結(jié)果可以為生產(chǎn)制造業(yè)提供有價(jià)值的參考意見，有利于企業(yè)提高生產(chǎn)效率，降低成本，創(chuàng)造更多的利潤(rùn).

圖3 8×8的 JSP 求解結(jié)果

圖4 10×10的 JSP 求解結(jié)果

圖5 15×10的 JSP 求解結(jié)果

3.2.2 與其他算法性能對(duì)比 MAIA、AIA、PSO、GA的20次仿真實(shí)驗(yàn)的結(jié)果如表1所示，主要統(tǒng)計(jì)找到最優(yōu)的解次數(shù)及相應(yīng)的迭代次數(shù).從表1可以看出，對(duì)于8×8問題、10×10問題以及15×10問題， MAIA得到最優(yōu)解成功次數(shù)顯著高于對(duì)比算法.而且得到最優(yōu)解的迭代次數(shù)相對(duì)較少，綜合性能要優(yōu)于對(duì)比算法.對(duì)比結(jié)果表明，MAIA具有種群規(guī)模小、迭代次數(shù)少的優(yōu)點(diǎn)，在解決大規(guī)模問題時(shí)，具有較好的穩(wěn)定性和收斂性.

表1 不同算法的算例集實(shí)驗(yàn)結(jié)果對(duì)比

圖6 算法的平均CPU時(shí)間對(duì)比Fig.6 Average CPU time of the above algorithm

3.2.3 求解效率對(duì)比 為了測(cè)試所有算法對(duì)柔性作業(yè)車間調(diào)度問題的求解效率，采用平均執(zhí)行時(shí)間作為性能評(píng)價(jià)指標(biāo)，所有算法平均執(zhí)行時(shí)間統(tǒng)計(jì)結(jié)果如圖6所示.從圖6可以清楚看出，相對(duì)于其他算法，MAIA的平均CPU時(shí)間最短，求解速度最快，大幅度提高了FJSP的求解效率，可以滿足大規(guī)模制造業(yè)的FJSP優(yōu)化要求，這主要是由于MAIA集成了人工免疫算法和粒子群算法全局搜索能力優(yōu)點(diǎn)，可在較短時(shí)間內(nèi)得到滿意解.

4 結(jié)束語

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

[1] 曾強(qiáng), 沈玲, 潘啟東, 等. 批量生產(chǎn)柔性作業(yè)車間多目標(biāo)精細(xì)化調(diào)度方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 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] 王長(zhǎng)明, 聶建軍. 基于遺傳算法的二次曲面提取技術(shù)研究[J]. 鄭州大學(xué)學(xué)報(bào)(理學(xué)版),2013,45(1):65-68.

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

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

[10] 唐建平, 宋紅生, 王東署. 一種移動(dòng)機(jī)器人動(dòng)態(tài)環(huán)境下的路徑規(guī)劃[J]. 鄭州大學(xué)學(xué)報(bào)(理學(xué)版), 2012, 44(1): 75-78.

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

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

[13] 宋存利. 求解柔性作業(yè)調(diào)度問題的協(xié)同進(jìn)化粒子群算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 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.

(責(zé)任編輯：王浩毅)

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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61202285)；河南省科技攻關(guān)項(xiàng)目(132102210501).

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

張永強(qiáng)，高銳敏.改進(jìn)人工免疫算法求解柔性作業(yè)車間調(diào)度問題[J].鄭州大學(xué)學(xué)報(bào)(理學(xué)版)，2016,48(2):53-57.

TP301

A

1671-6841(2016)02-0053-05

10.13705/j.issn.1671-6841.2015288