基于新型邻域结构的混合算法求解作业车间调度

针对作业车间调度问题(Job shop scheduling problem,JSP),以优化最大完工时间为目标,提出一种融合新型邻域结构的混合求解方法。混合算法由具有全局搜索能力的遗传算法和基于邻域结构的邻域搜索算法构成。在邻域结构的设计中,研究了基于甘特图的工序头尾长度计算方法,以及关键工序查找方法。通过分析已有各种邻域结构及相关理论性质,指出邻域结构的根本在于引导关键工序对机器空闲时间进行利用,并将利用方式分为两种情况:直接利用和间接利用。综合两种利用方式,科学指导关键工序的移动,根据关键工序的类型定义相应的移动操作,使其移动范围突破了工序块的内部、紧前、紧后位置限制,扩大了有效移动范围。结合43个基准算例进行测试分析,验证了所提算法具有良好的求解性能。此外,所设计的邻域结构可以进一步融合其他智能算法求解JSP问题。

A Hybrid Algorithm with a New Neighborhood Structure for the Job Shop Scheduling Problem

In order to optimize the maximum completion time, a hybrid solving method with a new neighborhood structure is proposed for the job shop scheduling problem (JSP). In the hybrid algorithm, genetic algorithm is adopted for global search, and local search is achieved based on neighborhood structure. In the design of the neighborhood structure, the calculation method of operation head and tail length, and the key operations searching method are studied based on Gantt chart. Through the analysis of various neighborhood structures and related theories, it points out that the foundation of neighborhood structure is to guide the key operations to utilize machine idle time, and can be divided into two types: direct use and indirect use. The two utilization ways are both comprehensively considered, and the corresponding movement strategies are defined according to the type of key operations with scientific guidance. The effective movement range is expanded, breaking through the location restrictions of inside, direct adjacent before and behind of the operation block. The experimental results of 43 benchmarks show that the proposed algorithm has good performance. In addition, the new neighborhood structure can further be integrated with other intelligent algorithms for solving JSP problem.