• CN:11-2187/TH
  • ISSN:0577-6686

机械工程学报 ›› 2015, Vol. 51 ›› Issue (14): 175-184.doi: 10.3901/JME.2015.14.175

• 交叉与前沿 • 上一篇    下一篇

求解柔性作业车间调度问题的两级邻域搜索混合算法

赵诗奎   

  1. 济南大学机械工程学院 济南 250022
  • 出版日期:2015-07-20 发布日期:2015-07-20

Bilevel Neighborhood Search Hybrid Algorithm for the Flexible Job Shop Scheduling Problem

ZHAO Shikui   

  1. School of Mechanical Engineering, University of Jinan, Jinan 250022
  • Online:2015-07-20 Published:2015-07-20
  • Supported by:
    国家自然科学基金资助项目(11072205,11202174)

摘要: 针对柔性作业车间调度问题(Flexible job shop scheduling problem,FJSP),以优化最大完工时间为目标,提出一种融合两级邻域搜索和遗传算法的混合算法。基于通过利用机器空闲时间来减小最大完工时间的想法,构造邻域结构,对关键路径上的关键工序进行移动,实现邻域搜索,以改进当前解;设计针对FJSP问题特点的两级邻域搜索方式,第一级邻域搜索为跨机器移动工序,将工序移动到除当前加工机器之外的其他可选机器上,第二级邻域搜索为同机器移动工序,将工序在当前加工机器上进行移动;给出两级邻域搜索相应的保证可行解工序移动条件;兼顾FJSP问题求解算法的全局搜索能力和局部搜索能力,利用遗传算法实现全局搜索,两级邻域搜索实现局部搜索;采用国际通用的FJSP问题基准算例进行测试,验证了所提方法的有效性。

关键词: 两级邻域搜索, 邻域结构, 柔性作业车间调度问题, 遗传算法

Abstract: For the flexible job shop scheduling problem (FJSP), in order to optimize the maximum completion time, a hybrid algorithm mixed with bilevel neighborhood search and genetic algorithm is proposed. The neighborhood structure is constructed by using machine idle time to reduce the maximum completion time. In order to improve the current solution, critical operations of the critical path are moved to achieve neighborhood search. The method of bilevel neighborhood search is designed according to the characteristics of FJSP. The first level neighborhood search is the cross-machine moving operation, and the operation is moved to other optional machines in addition to current processing machine. The second level neighborhood search is the same-machine moving operation, and the operation is moved on current processing machine. Operation moving conditions corresponding to the bilevel neighborhood search are given to ensure feasible solutions. Both of global search ability and local search ability of FJSP solving algorithm are considered, and to use genetic algorithm to achieve global search, bilevel neighborhood search to achieve local search. The internationally accepted FJSP benchmark examples are adopted to test the validity of the proposed method.

Key words: bilevel neighborhood search, flexible job shop scheduling problem, genetic algorithm, neighborhood structure

中图分类号: