计算机工程与应用 ›› 2022, Vol. 58 ›› Issue (19): 318-325.DOI: 10.3778/j.issn.1002-8331.2111-0189

• 工程与应用 • 上一篇    下一篇

求解柔性作业车间调度问题的新型改进Jaya算法

裴小兵,祁文博,戴毓彤   

  1. 天津理工大学 管理学院,天津 300384
  • 出版日期:2022-10-01 发布日期:2022-10-01

New Improved Jaya Algorithm for Solving Flexible Job Shop Scheduling Problem

PEI Xiaobing, QI Wenbo, DAI Yutong   

  1. School of Management, Tianjin University of Technology, Tianjin 300384, China
  • Online:2022-10-01 Published:2022-10-01

摘要: 为有效解决复杂的柔性作业车间调度问题,以最小化最大完成时间为目标,提出了一种结合了变邻域搜索算法的新型改进Jaya算法来求解。为不断挖掘和优化探索最优解,提高算法求解的结果质量,通过Jaya算法的原理重新提出一种解的更新机制,此外在Jaya算法原理的基础上嵌入一种变邻域搜索策略,并在传统邻域结构的基础上重新设计了两种新型邻域结构,扩大了邻域搜索范围,增强了Jaya算法的局部搜索能力,避免算法因失去解的多样性从而陷入局部最优。运用基准算例对该算法的求解性能进行了验证,并与其他算法的仿真结果进行对比,结果表明该改进算法的求解效率更高。

关键词: 柔性作业车间, 生产调度, Jaya算法, 变邻域搜索

Abstract: In order to effectively solve the complex flexible job shop scheduling problem(FJSP) with the objective of minimizing the maximum completion time, a new and improved Jaya algorithm incorporating a variable-neighborhood search algorithm(NIJA) is proposed to solve it. In order to continuously explore and optimize the optimal solution and improve the quality of the result of algorithm solution, a solution update mechanism is re-proposed through the principle of Jaya algorithm, and in addition, a variable neighborhood search strategy is embedded on the basis of the principle of Jaya algorithm, and two new neighborhood structures are redesigned on the basis of traditional neighborhood structure to expand the neighborhood search range and enhance the local search capability of Jaya algorithm. The algorithm avoids losing the diversity of solutions and thus falls into local optimum. The algorithm performance is verified using benchmark cases and compared with the simulation results of other algorithms in the literature, which show that the improved algorithm is more efficient.

Key words: flexible job shop(FJS), production scheduling, Jaya algorithm, variable neighborhood search