改进遗传算法求解织造车间并行批调度问题

杜利珍，叶 涛，宣自风，王宇豪

改进遗传算法求解织造车间并行批调度问题

杜利珍，叶 涛，宣自风，王宇豪

（武汉纺织大学 机械工程与自动化学院，湖北 武汉 430200）

针对织造车间并行批处理调度问题，提出一种改进遗传算法用于最大完工时间最小化求解。首先，采用实数编码方式进行编码操作；然后，引入模拟退火算法的Metropolis机制，从而增强遗传算子在该调度问题的可行解集空间中寻优的能力；最后，通过随机生成的150个仿真测试集对算法进行求解性能上的比较分析，并将测试结果与文献中提到的BSNRPSO算法和另外一种差分进化算法进行比较分析。经过实验证明，本文改进遗传算法在求解性能上明显优于对比算法。

遗传算法；实数编码；Metropolis机制；织造车间

批调度属于车间调度问题的一个重要的分支，在制造业生产过程中也有广泛应用，如半导体制造[1]、晶圆制造、纺织车间等。国内不少学者就该方向进行了不少研究，现阶段针对该研究采用的方法大多是针对某算法的缺点，通过分析后将其他算法规则融入到该算法中进行对应问题的求解，从而有效的避免收敛过快等缺点。Jia等[2]针对具有任意容量的并行批处理机上的调度问题，以总加权交付时间最小化为目标，提出了改机蚁群算法(UACO)和粒子群算法(PSO)和一种元启发式算法，解决需要考虑作业和批次之间关系情况下的排产调度问题，经过实验证明，文中提出的此方法在求解性能上优于其他算法。Jia等[3]针对在模糊环境下不同容量下并行批处理机器的调度问题，以最大完工时间最小化为目标，提出了一种模糊的蚁群算法解决了具有不相同作业大小和模糊处理时间的调度优化问题，为提高解的质量，引入了FLO(Fuzzy Local Optimization)局部优化算法，通过模糊实验和统计测试证明，该提出的算法在合理的时间内能找到更好的解。常俊林等[4]针对并行多机批调度问题展开研究，以最大完工时间最小化为目标，提出了一种基于批序列编码的混合粒子群算法解决了该调度问题，在引入学习因子二阶振荡、随机权重、最大速度线性递减等方法后，有效避免了算法收敛速度慢及寻优能力差等问题。Zhou等[5]针对具有任意作业规模的均匀并行批处理机的调度问题，以最大限度的缩短完工时间为目的，提出了一种有效的基于差分进化算法(DE)来解决大规模问题，通过随机生成的测试案例将其结果与商业解算器(MIP)、随机密钥遗传算法(RKGA)和粒子群算法(PSO)进行比较，实验结果证明了该算法在求解质量和鲁棒性方面的优越性。

本文重点研究遗传算法(Genetic Algorithm，GA)的优缺点，针对织造车间生产实际所存在的约束，建立混合整数线性规模型(MILP），将模拟退火算法(SA)的Metropolis准则引入到该算法中，以提高算子在可行解集空间中寻优的能力，最后通过随机生成的150个测试案例进行该算法求解性能上的对比分析，经过实验证明了此方法在求解能力上明显优于其他对比算法。

1 织造车间并行批调度问题描述

本文以河南省杰瑞织造科技有限公司纺织服装(毛衫)生产线作为研究对象，该服装生产车间前道工序为：织片—套口—洗水—后整，洗水车间的工序为将“织片—套口”两道工序处理后的毛衫制品按照不同类型进行分类，送洗水车间进行批次处理，该工序可以视作为一个并行批处理调度的问题。其生产过程实景图如图1所示。

图1 生产实景

约束1为优化的目标函数；约束2为判断批次中的工件是否在对应批处理机器上进行加工；约束3表示批次中工件的加工尺寸总和不能超过批处理机器的加工容量；约束4表示批次的加工时间为批中工件最大加工时间；约束5表示最大完成时间至少大于所有批次加工时间总和；约束6表示布尔变量的取值范围。

2 算法设计

2.1 GA算法简介

遗传算法在车间调度领域已得到广泛的使用。该算法自20世纪70年代由Holland提出，自此得到了广泛的关注。遗传算法已成功应用与解决各类复杂的组合优化问题，该算法是通过模仿自然界生物进化机制发展起来的随机全局搜索和优化的方法，借鉴了达尔文的进化论及孟德尔的遗传学说。遗传算法的算子在其搜索过程中能够做到自动获取和积累搜索空间知识的特点，并自适应地控制其搜索过程以求得最佳解。

2.2 编解码

所研究的调度问题属于离散优化问题，遗传算法属于连续优化方法，通过实数编码的方式将此问题转化为连续型问题进行求解，其编码原理通过随机生成一组实数，将此数组与工件序列配对，通过基于该实数组的降序排列来规划工件的加工次序，数组的长度表示工件的数目，具体如表1所示。

表1 实数编码

如表1所示，通过第一行实数的排序间接的规定加工序列号，工件{1,2,3,4,5,6,7,8}经过编码后的加工次序为I4、I6、I8、I7、I3、I2、I5、I8。

2.3 算法内操作

2.3.1 选择操作

该遗传算法的选择操作采取“随机联赛选择”机制，该机制主要通过从种群中随机选择几个适应度最高的个体(编码)，然后将其个体一个个的传递到子代种群中去，同时方便交叉、变异操作。

2.3.2 交叉操作

图2 均匀交叉操作

2.3.3 变异操作

图3 基本位变异

2.4 改进遗传算法步骤及流程图

改进遗传算法的流程如图4所示，步骤如下：

步骤1：初始化算法参数，主要包括：种群数量、交叉率、变异率、最大遗产代数。

步骤2：分别对算法的种群进行对应适应度值得求解。

步骤3：基于模拟退火算法的Metropolis机制，对原有的适应度值进行再次更新，其主要根据该机制在可行解集空间中寻得比当前解更优的解。

步骤4：基于“随机联赛选择”机制，从种群中选取适应值最好几个对应的个体，将其传递给子代。

步骤5：基于“均匀交叉”机制，对父代、母代个体进行概率交叉操作，增加种群的多样性。

步骤6：基于“基本位变异”机制，对经过交叉后留下的子代(当前变异操作的新父代)进行概率性变异，增强种群的稳定性。

图4 改进遗传算法流程图

步骤7：循环进行步骤2～步骤6，直到满足终止条件(一般为最大迭代次数)，若满足，则输出最优个体及适应值，否则再次进入循环体，直到满足终止条件。

2.5 运算复杂度

3 实验仿真分析

为了测试改进遗传算法在求解织造车间并行批调度问题上的性能，通过测试案例进行对应的仿真实验，所有的算法代码编写均在Matlab R2016实现，操作系统为Window 7，处理器为Intel(R) Core(TM)i5-5200U CPU @ 2.20GHz。

表2 算例参数设置

表3 批调度测试结果

从表3中的数据可知，就算法的最优值、最差值、平均值进行比较，IGA算法在大多数情况下都比BSNPPSO的效果好，少数在工件数为50、150，加工时间在[1,20]情况下其求解效果较BSNRPSO差一点，相比于DE算法，其结果明显优于DE算法求解的效果，为了更好的比较3种算法的性能优越性，采用相对改进率作为新的评价指标，改进遗传算法(GA)相对于DE算法的改进率为：

根据公式（7），IGA算法相对于BSNRPSO算法和DE算法的平均值改进率结果见表4所示。并且根据表4的结果做出算法的平均值改进率图，如图5所示。

由图4可知，IGA算法相对于DE在求解性能方面有一定的改进，但相对于BSNRPSO其改进不是很稳定，尤其表现在J2t1～J4t1这个区间，在区间J2t2～J4t2其改善相对稳定，这说明IGA在面对加工时间长、工件数多的情况下更能胜任，面对加工时间短、工件数多时存在一定误差性。综合以上数据，IGA在求解织造车间并行批调度问题上，比BSNRPSO和DE都能更好的找到最优解。

表4 算法平均值改进率

图5 算法平均值改进率

4 结论

针对遗传算法自身存在的优缺点提出一种改进算法，并将其运用到求解织造车间并行批调度问题上，经过仿真实验验证，这种改进的算法对求解该调度问题是有效的。并在改进遗传算法中采用了实数编码机制，结合模拟退火算法中的Metropolis进一步提高算子在可行解集空间中寻优的能力，使得改进遗传算法相比于BSNRPSO和DE更加合适于解决此类调度问题，对实际的织造车间批调度具有一定的指导意义。

[1] Chandru V，Lee C Y，Uzsoy R．Minimizing total completion time on a batch processing machine with job families[J]. Operations Research Letters，1993，13：61-65.

[2] Jia Z H，Huo S Y，Li K，et al．Integrated scheduling on parallel batch processing machines with non-identical capacities[J]. Engineering Optimization，2019，52 (4)：715-730.

[3] Jia Z，Yan J，Leung J Y T，et al．Ant colony optimization algorithm for scheduling jobs with fuzzy processing time on parallel batch machines with different capacities[J]. Applied Soft Computing，2019，75：548-561.

[4] 常俊林, 王庆, 孟彦军, 等. 并行多机批调度的混合粒子群算法研究[J]. 化工自动化及仪表, 2014, 41(04): 397- 454.

[5] Zhou S，Liu M，Chen H，et al．An effective discrete differential evolution algorithm for scheduling uniform parallel batch processing machines with non-identical capacities and arbitrary job sizes [J]．International Journal of Production Economics，2016，179：1-11.

Improved Genetic Algorithm for Parallel Batch Scheduling in Weaving Workshop

DU Li-zhen, YE Tao, XUAN Zi-feng, WANG Yu-hao

(School of Mechanical Engineering and Automation, Wuhan Textile University，Wuhan Hubei 430200, China)

Aiming at the parallel batch scheduling problem in weaving workshop，an improved genetic algorithm is proposed to minimize the maximum completion time.Firstly，the real number coding method is used for coding operation；Then，the metropolis of simulated annealing algorithm is introduced to enhanced the optimization ability of genetic operator in the feasible solution set space of the scheduling problem；Finally，the performance of the algorithm is compared and analyzed through 150 randomly generated simulation test sets. Then, the test results are compared with the BSNRPSO algorithm mentioned in the literature and another differential evolution algorithm.Experiments show that the improved genetic algorithm is significantly better than its comparison algorithm in solving performance.

genetic algorithm; real coding; metropolis mechanism; weaving workshop

TP39

A

2095－414X(2022)04－0008－05

杜利珍（1975-），女，副教授，博士，研究方向：智能调度、系统建模仿真与优化.

国家重点研究计划（2019YFB1706300）.