作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2024, Vol. 50 ›› Issue (6): 336-345. doi: 10.19678/j.issn.1000-3428.0067326

• 开发研究与工程应用 • 上一篇    下一篇

基于改进MOEA/D的模糊柔性作业车间调度算法

郑锦灿1,2, 邵立珍1,2, 雷雪梅3   

  1. 1. 北京科技大学自动化学院, 北京 100083;
    2. 北京科技大学顺德创新学院, 广东 佛山 528399;
    3. 北京科技大学信息化建设与管理办公室, 北京 100083
  • 收稿日期:2023-04-04 修回日期:2023-06-16 发布日期:2024-06-11
  • 通讯作者: 雷雪梅,E-mail:xmlei@ustb.edu.cn E-mail:xmlei@ustb.edu.cn
  • 基金资助:
    国家自然科学基金面上项目(12071025);佛山市科技创新专项资金(BK20AE004)。

Fuzzy Flexible Job-Shop Scheduling Algorithm Based on Improved MOEA/D

ZHENG Jincan1,2, SHAO Lizhen1,2, LEI Xuemei3   

  1. 1. School of Automation and Electrical Engineering, University of Science and Technology Beijing, Beijing 100083, China;
    2. Shunde Innovation School, University of Science and Technology Beijing, Foshan 528399, Guangdong, China;
    3. Office of Information Construction and Management, University of Science and Technology Beijing, Beijing 100083, China
  • Received:2023-04-04 Revised:2023-06-16 Published:2024-06-11

摘要: 针对实际生产车间中加工时间的不确定性,将加工时间以模糊数的形式表示,建立以最小化模糊最大完工时间和模糊总材料消耗为优化目标的多目标模糊柔性作业车间调度问题数学模型,提出一种改进基于分解的多目标进化算法(IMOEA/D)进行求解。该算法基于机器和工序两层编码并采用混合的初始化策略提高初始种群的质量,利用插入式贪婪解码策略对机器的选择进行解码,缩短总加工时间;采用基于邻域和外部存档的选择操作结合改进的交叉变异算子进行种群更新,提高搜索效率;设置邻域搜索的启动条件,并基于4种邻域动作进行变邻域搜索,提高局部搜索能力;通过田口实验设计方法研究关键参数对算法性能的影响,同时得到算法的最优性能参数。在Xu 1~Xu 2、Lei 1~Lei 4和Remanu 1~Remanu 4测试集上将所提算法与其他算法进行对比,结果表明,IMOEA/D算法的解集数量和目标函数值均较优,在Lei 2算例获得的解集个数为对比算法的2倍以上。

关键词: 模糊柔性作业车间调度问题, 基于分解的多目标进化算法, 混合初始化, 选择策略, 邻域搜索

Abstract: Considering the uncertainty of the processing time in an actual production workshop, the processing time is expressed in the form of fuzzy numbers. A multi-objective Fuzzy Flexible Job-shop Scheduling Problem(FFJSP) model that minimizes the fuzzy maximum completion time and the fuzzy total cost is presented, and an Improved Multi-Objective Evolutionary Algorithm based on Decomposition(IMOEA/D) is proposed. In this algorithm, a two-layer encoding method based on operations and machines is used for encoding, and a mixed initialization strategy is used to improve the quality of the initial population. An insertion greedy decoding method is used to decode and minimize the total machine processing time. The selection operation based on neighborhood and external population combined with improved crossover and mutation operators are used to update the population to accelerate searching. The condition for neighborhood search is set, and a variable neighborhood search based on four neighborhood actions is performed to improve the local search ability of the algorithm. A Taguchi design of the experimental method is used to examine the effects of key parameters on the algorithm. Simultaneously, the optimal performance parameters of the algorithm are obtained. The proposed algorithm is compared with other algorithms based on the Xu 1-Xu 2, Lei 1-Lei 4, and Remanu 1-Remanu 4 datasets. The results show that the IMOEA/D algorithm obtains better solutions and objective function values than the other algorithms. The number of solutions obtained by the proposed algorithm based on Lei 2 is more than twice those obtained by the other algorithms.

Key words: Fuzzy Flexible Job-shop Scheduling Problem(FFJSP), Multi-Objective Evolutionary Algorithm based on Decomposition(MOEA/D), hybrid initialization, selection strategy, neighborhood search

中图分类号: