柔性作业车间调度的精确邻域结构混合进化算法

Evolutionary Algorithm with Precise Neighborhood Structure for Flexible Workshop Scheduling

摘要:

为解决现有基于关键路径的邻域搜索存在无效移动多、盲目性大以及仅优化单一目标的问题，设计了更加明确精准有效的邻域结构，包括同机器移动和跨机器移动两步操作；在此基础上，给出相应的关键工序精确移动条件，并将其从优化最大完工时间推广到多目标优化；为兼顾算法局部搜索和全局搜索，将其与进化算法进行混合，实现局部与全局的优势互补，并给出相应的混合算法框架；最后，通过两个国际通用的案例集进行测试，并将测试结果与成熟的算法进行对比，验证了所设计算法的有效性和高效性。

关键词:多目标优化;车间调度;邻域搜索;进化算法

Abstract:

In order to solve the problems of the existing neighborhood search based on critical path， such as too many invalid moves， too much blindness and optimization one objective， a more precise and effective neighborhood structure is designed， including the two-step operation of the same machine movement and the cross-machine movement. Based on which， the corresponding operation movement conditions are given and extended from the optimization of the maximum completion time to multi-objective optimization. Besides， to realize the complementary advantages of local and global search， the algorithm is mixed with the evolutionary algorithm， and the corresponding hybrid algorithm framework is given. Moreover， two internationally used case sets are tested， and the test results are compared with those of other algorithms to verify the effectiveness and efficiency of the proposed algorithm.

Key words:multi-objective optimization;workshop scheduling;neighborhood search;evolutionary algorithm