1、湖北汽车工业学院学报Journal of Hubei University of Automotive Technology第 37 卷第 1 期2023 年 3 月Vol.37 No.1Mar.2023doi：10.3969/j.issn.1008-5483.2023.01.012基于改进NSGA-算法求解柔性作业车间调度问题别俊，陈君宝，杨振华（湖北汽车工业学院 机械工程学院，湖北 十堰 442002）摘 要：为了得到柔性作业车间调度最优解，以最大完工时间、最大负荷机床和总机床负荷为目标建立数学模型。改进了NSGA-算法，采用全局选择和快速选择结合的方法初始化种群，基于工序排序和机床选择对
2、个体进行编码，对基因进行IPOX交叉和多点交叉，引入多重变异和变邻域搜索策略。通过MATLAB对算法进行仿真，验证了改进算法的可行性和有效性。关键词：柔性作业车间调度；NSGA-算法；变邻域搜索中图分类号：TH165；TP18文献标识码：A文章编号：1008-5483（2023）01-0061-04Solving Flexible Job Shop Scheduling Problem Based onImproved NSGA-AlgorithmBie Jun,Chen Junbao,Yang Zhenhua（School of Mechanical Engineering,Hubei Un
3、iversity of Automotive Technology,Shiyan 442002,China）Abstract：To obtain the optimal solution for flexible job shop scheduling,a mathematical model was established with the objective of maximum completion time,maximum load of machine tool and minimumthe total load of machine tool.NSGA-algorithm was
4、improved.A combination of global selection andrapid selection was used to initialize the population.Individuals were coded based on process sequencing and machine tool selection.IPOX crossover and multi-point crossover were performed for genes.Multiple mutations and variable neighborhood search stra
5、tegies were introduced.The algorithm was simulated based on MATLAB,which verified the feasibility and effectiveness of the improved algorithm.Key words：flexiblejobshopscheduling;NSGA-algorithm;variableneighborhoodsearch收稿日期：2022-02-23；修回日期：2022-11-20第一作者：别俊（1995-），男，硕士生，从事优化设计方面的研究。E-mail：通信作者：陈君宝（1
6、975-），男，教授，从事智能制造与工业机器人应用方面的研究。E-mail：柔性作业车间调度问题（flexible job scheduling problem，FJSP）作为传统车间调度问题的扩展1，在面对客户需求的多样化和个性化，车间生产模式的“多品种、小批量、低能耗”等挑战时，可以扩大解的求解范围、提供更加灵活的方案。FJSP相较于传统车间调度延伸出了新的决策内容，主要包含工序排序和机床选择，是NP-hard中求解难度更为复杂的类型。随着计算机和工程技术等学科相互交叉渗透，许多人工智能方法被应用到研究中。Cinar2等基于优先权遗传算法，将迭代局部搜索应用于每个再现过程的染色体,以加快收
7、敛速度；刘胜3等提出了兼顾调度鲁棒性与稳定性指标2023年3月湖北汽车工业学院学报的改进2阶段多种群遗传算法,有效解决工序与机床的约束问题；黄海松4等针对FJSP改善碳排放量和加工时间耦合性为目标，对模拟退火算法进行改进，提高了算法运行速度；王思涵5等针对FJSP提出改进鲸鱼群算法，采用协同搜索扩大个体范围，并引入变领域搜索算法，提高种群全局和局部搜索能力；黎书文6等基于离散制造车间柔性度调化，提出学习因子自适应调节的改进粒子群算法，提高了收敛速度及全局搜索能力。上述研究能够在很大程度上提升算法的运行效率，保证算法的适应性和稳定性，但存在一定冗余。此外，对于算法过早收敛导致局部产生最优解的问题
8、，还有提升的空间。受上述文献的启发，文中对多目标FJSP展开研究，选择针对此类问题更为专业的非支配排序遗传算法NSGA-进行改进，并引入变邻域搜索策略改善算法的局部搜索能力。1问题描述FJSP可描述如下：n个工件 J1,J2,Jn要在m台机床W1,W2,Wm进行加工，所有的工件都有一定的工序和加工顺序，其中工件ji由p道工序Oi1,Oi2,Oip组成。工件的每道工序可在不同的机床进行加工，且加工时间随着所选机床的不同而发生变化。在实际生产中，FJSP有多个评价指标，在不同约束条件下，采用优化方法对工序排序和机床选择进行合理分配，最终得到非劣调度方案。考虑在3个性能指标下建立数学模型，最大完工时
9、间最小化公式为f1=min(maxCi)（1）最大机床负荷最小化公式为f2=min(max1 k m(i=1nj=1piTijkXijk)（2）总机床负荷最小化公式为f3=min(i=1nj=1pik=1mTijkXijk)（3）式中：f1为最大完工时间；f2为最大机床负荷；f3为总机床负荷；Ci为工件Ji完工时间；Tijk为工件Ji的工序Oij在机床Wk上的加工时间；Xijk为工件i的第j道工序在机器k上加工；n为工件总数；m为机床总数；pi为工件i的总工序数。结合工程实际情况和满足工艺问题的需要，规定FJSP的约束条件7：1）各工序开始加工就不能中断；2）各工件加工优先级相同；3）同种工件
10、的工序有先后顺序约束；4）同一机床在某一时刻只能加工1个工件的某一道工序；5）同一工件的某一工序只能被1台机床加工。相关公式为Sij+TijkXijk Si(j+1)（4）Sij+Tij Shj+Q(1-yijhlk)（5）Cij Si(j+1)+Q(1-yiji(j+1)k)（6）k=1mXijk=1（7）式中：Sij为工件i的第j道工序开始加工时间；Q为足够大的正数；yijhlk为在机器k上，工件i的第j道工序较工件h的第l道工序是否先加工，是则取1，反之取0；Cij为工件i的第j道工序停止时间；yiji()j+1 k表示在机器k上,工件i的第j道工序较工件i的第()j+1道工序是否先加工
11、，是则取1，反之取0；Xijk为工件i的第j道工序在机器k上加工。2算法设计遗传算法包括遗传、变异、选择及杂交等一系列操作8。目前广泛应用于求解车间调度问题中，一定数量的个体可抽象为染色体，使种群向更好的解进化，经过多次进化最终得到优化结果。NSGA-是解决多目标优化问题的首选算法，具有运行速度快、降低算法复杂度和解集收敛性好的优点9。根据FJSP多目标问题的特点，选择NSGA-算法进行改进，以增强算法收敛速度和稳定性。2.1 算法改进1）染色体编码和解码针对FJSP的工序排序和机床选择，采用分段式编码。工序层编码由工件号组成，根据加工任务出现的先后顺序确定工序号，即出现的次数代表当前工件的工
12、序号。机床层编码表示每个工件的工序所选择的机床编号，编码长度等于各个工件工序总数之和10。例如1个34的FJSP调度问题，工件1至3分别有3道工序，配有4台机床可供选择，编码见图1。工序编码中第2个1表示工件1的第二道工序在2号机床上加工。为了获得较好的解，采用插入式贪婪算法进行解码：工序121213323机床432312143图1 染色体编码 62第37卷 第1期ta=max(Ci(j-1),LSkr)（8）tb=max(Ci(j-1),FMk)（9）ta+Tijk LEkr（10）式中：ta、tb为工序的加工起始时间；Ci(j-1)为工件i的第()j-1道工序停止加工的时间；LSkr为机器
13、k上第r个空闲时间段的开始时间；LEkr为机器k上第r个空闲时间段的结束时间；FMk为机器k上最后一道工序的结束时间。首先计算当前机器上所有加工空闲时间段LSkr,LEkr，利用式（8）计算各工序的ta，根据式（9）判断当前工序能否在当前机器上向前插入空闲间隙，若能则按ta进行加工，若不能则根据式（10）计算tb进行加工。2）种群初始化为了得到较好的初始解，在全局选择的基础上结合快速选择方法进行种群初始化。利用全局选择把工件加工工序分配到当前负荷最小的机床上，确保各机床工作负荷平衡。利用快速选择把各工序分配到加工该道工序所需时间最短的机床上，保证初始解的多样性。3）交叉为了加快收敛，使解达到希
14、望的最佳区域，文中采用IPOX交叉和多点交叉方式对染色体进行操作。工序编码采用具有低约束和良好基因继承等特性的IPOX交叉算子，机床编码采用多点交叉，减小工序允许机床加工的限制，并且不会破坏基因有效序列。2个父代染色体P1和P2通过交叉产生子代C1和C2，操作步骤如下11：先利用rand函数随机产生1组与染色体长度相等的数组，依次从P2中选出P1与数组中1的位置对应的工序，将对应的机床进行交换；父代染色体中其他机器的加工顺序保留到子代，分别产生子代C1和C2。4）变异变异操作使算法具有局部搜索能力，当算法通过交叉操作接近最优解邻域时，加速向最优解收敛12。同时变异操作还可以维持群体多样性，防止
15、出现早熟现象13。文中采用随机机床和最小加工时间机床选择，确保种群多样性。For i=0.5：popif rand Pm随机产生数组rand 0,1if rand 0.5PmIf L（pos）=1如果数组的位置等于1，在pos对应工序选择加工时间最小的机床End ifElseIf L（pos）=1 随机选择一个可选机床End ifEnd ifEnd ifEnd For5）变邻域搜索策略文中对工序层编码参考王玉芳变邻域搜索策略，利用不同的动作构成的邻域结构进行交替搜索，在集中性和疏散性之间达到平衡14。首先列出1个染色体的所有情况。在工序编码中任意选择1个染色体，在给定的工件集中随机选择一部分工
16、件，为选中的每个工件任意确定1道工序，对已选中的染色体基因进行枚举排序，未被选中的工序编码基因位置不变，产生1组新的工序编码染色体基因，对新的工序编码染色体做适应度计算，并和原工序染色体适应度比较，如果得到的适应度值大于原来的值，就替换原解；反之，保留原解。然后随机打乱1段工序编码，最后交换工序编码中任意2个位置的元素。2.2 算法流程根据改进NSGA-算法策略，具体算法流程如图2所示。开始初始化种群及相关参数非支配排序及拥挤度计算二元锦标赛选择IPOX、多点交叉结束输出结果终止变邻域搜索多重变异NY图2 算法流程图3仿真验证实验3.1 算法仿真选用Brandimarte算例和车间生产数据来验证改进后NSGA-的可行性。算法测试选择MATLAB 2019b软件，运行在Windows10操作系统、CPU为2.8 GHz、内存为8G的笔记本电脑上。相关参数设置为：种群数量为80，迭代次数为400，交叉概率为0.8，变异概率为0.2，变邻域动作参数为5、扰动因数为3。为了更好地验证算法性能，测试分为单目标实验和三目标实验。1）单目标实验从单目标函数f1最大完工时间最小化来评估改进后的算法，采
