改进文化基因算法求解双资源约束柔性作业车间调度问题  

Improved Memetic Algorithm for Flexible Job-shop Scheduling Problem with Dual Resource Constraints

作　　者：王玉芳[1,2,3] 陈凡[1] 姚彬彬 曾亚志 WANG Yufang;CHEN Fan;YAO Binbin;ZENG Yazhi(College of Automation;Collaborative Innovation Center of Atmospheric Environment and Equipment Technology(CICAEET);Engineering Research Center on Meteorological Energy Using and Control(C-MEIC),Nanjing University of Information Science&Technology,Nanjing 210044,China)

机构地区：[1]南京信息工程大学自动化学院,江苏南京210044 [2]南京信息工程大学大气环境与装备技术协同创新中心,江苏南京210044 [3]南京信息工程大学气象能源利用与控制工程技术研究中心,江苏南京210044

出　　处：《控制工程》2024年第6期981-994,共14页Control Engineering of China

基　　金：国家自然科学基金资助项目(51705260)。

摘　　要：针对具有机器和工人的双资源约束柔性作业车间调度问题,以最小化最大完工时间为目标构建调度模型,并设计一种改进文化基因算法对其进行求解。由于该调度问题需要同时考虑工序排序、机器选择及工人选择3个子问题,故采用三层序列编码。考虑传统解码方式存在收敛速度慢、收敛不完全的弊端,设计一种扩展型插入式主动解码方式,以提高算法的收敛速度;针对进化算法易陷入局部最优的缺陷,设计一种基于负载平衡的机器和工人再分配算子,增强算法的全局搜索能力,对种群中的优秀个体采用改进变邻域搜索以提高算法的局部寻优能力。最后,利用仿真算例及航空设备生产实例进行实验,验证所提算法求解双资源约束调度问题的有效性。For the flexible job-shop scheduling problem with dual resource constraints of machines and workers,a scheduling model is constructed with the goal of minimizing the maximum completion time,and an improved memetic algorithm is designed to solve it.Due to the scheduling problem requiring simultaneous consideration of three sub problems:process sorting,machine selection,and worker selection,a three-layer sequence encoding is adopted.Considering the drawbacks of slow and incomplete convergence in traditional decoding methods,an extended plug-in active decoding is designed to improve the convergence speed of the algorithm.To address the drawback of evolutionary algorithms being prone to local optimization,a machine and worker reassignment operator based on load balancing is designed to enhance the algorithm’s global search ability.An improved variable neighborhood search is used for outstanding individuals in the population to improve the algorithm’s local optimization ability.Finally,simulation examples and aviation equipment production examples are used for experiments to verify the effectiveness of the algorithm in solving the dual resource constrained scheduling problem.

关 键 词：柔性作业车间调度 双资源约束 文化基因算法 负载平衡 变邻域搜索 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TH165[自动化与计算机技术—控制科学与工程]