计算机应用 ›› 2021, Vol. 41 ›› Issue (3): 860-866.DOI: 10.11772/j.issn.1001-9081.2020060833

所属专题: 前沿与综合应用

• 前沿与综合应用 • 上一篇    下一篇

基于改进遗传算法的标签印刷生产调度技术

马晓梅, 何非   

  1. 南京理工大学 机械工程学院, 南京 210094
  • 收稿日期:2020-06-17 修回日期:2020-10-19 出版日期:2021-03-10 发布日期:2020-12-22
  • 通讯作者: 何非
  • 作者简介:马晓梅(1994-),女,青海海北人,硕士研究生,主要研究方向:生产调度、优化调度;何非(1982-),男,江苏靖江人,副教授,博士,主要研究方向:先进制造、智能制造、物流与供应链管理。
  • 基金资助:
    国家自然科学基金资助项目(51575280)。

Label printing production scheduling technology based on improved genetic algorithm

MA Xiaomei, HE Fei   

  1. School of Mechanical Engineering, Nanjing University of Science and Technology, Nanjing Jiangsu 210094, China
  • Received:2020-06-17 Revised:2020-10-19 Online:2021-03-10 Published:2020-12-22
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (51575280).

摘要: 针对标签印刷生产过程中存在的多品种、小批量、客户定制化程度高、部分生产工序存在不确定性等问题建立了以最小化最大完工时间为目标的柔性作业车间调度模型,提出了一种改进遗传算法(GA)。首先,在标准遗传算法的基础上采用整数编码;然后,在选择操作阶段采用轮盘赌法,并通过引入精英解保留策略以确保算法收敛性;最后,提出动态自适应交叉和变异概率,从而保证算法在前期进行较大范围寻优,以避免早熟,而后期尽快收敛,以保证前期获得的优良个体不被破坏。为了验证所提改进遗传算法的可行性,首先采用Ft06基准算例把所提算法与标准遗传算法(GA)进行比较,结果显示改进遗传算法的最优解(55 s)优于标准遗传算法的最优解(56 s),且改进遗传算法的迭代次数明显优于标准遗传算法;然后通过柔性作业车间调度问题(FJSP)的8×8、10×10和15×10标准算例进一步验证了算法的稳定性和寻优性能,在3个标准测试算例上改进遗传算法均在较短时间内取得了最优解;最后,将该算法用于求解标签印刷车间的排产问题时,使得加工效率比原来提高了50.3%。因此,提出的改进遗传算法可以有效应用于求解标签印刷车间的排产问题。

关键词: 标签印刷生产, 多品种, 小批量, 遗传算法, 柔性作业车间调度

Abstract: There are a variety of problems in the label printing production process, such as multi-variety, small batch, high-degree customization and uncertainties in some working procedures. Aiming at these problems, a flexible job-shop scheduling model with the goal of minimizing the maximum completion time was established, and an improved Genetic Algorithm (GA) was proposed. First of all, integer coding was adopted based on the standard genetic algorithm. Secondly, the roulette method was used in the selection operation stage, and the convergence of the algorithm was guaranteed by introducing the elite solution retention strategy. Finally, dynamic adaptive crossover and mutation probabilities were proposed to ensure that the algorithm optimized in a wide range to avoid prematurity in the early stage, and the algorithm converged timely to ensure that the excellent individuals obtained previously were not destroyed in the later stage. In order to verify the feasibility of the proposed improved genetic algorithm, the Ft06 benchmark example was first used to compare the proposed algorithm with the standard genetic algorithm. The results showed that the optimal solution of the improved genetic algorithm (55 s) was better than the optimal solution of the standard genetic algorithm (56 s), and the number of iterations of the improved genetic algorithm was significantly better than that of the standard genetic algorithm. Then, through the 8×8, 10×10 and 15×10 standard examples of Flexible Job-shop Scheduling Problem (FJSP), the effectiveness, stability and optimization performance of the algorithm were verified. On all of three standard test examples, the improved genetic algorithm obtained the optimal solution in a short time. Finally, when the proposed algorithm was used to solve the production scheduling problem of the label printing job-shop, the processing efficiency was increased by 50.3% compared to the original one. Therefore, the proposed improved genetic algorithm can be effectively applied to solve the production scheduling problem of label printing job-shop.

Key words: label printing production, multi-variety, small batch, Genetic Algorithm (GA), Flexible Job-shop Scheduling Problem (FJSP)

中图分类号: