基于混合变邻域遗传算法的柔性车间调度研究

RESEARCH ON FLEXIBLE JOB SHOP SCHEDULING PROBLEM BASED ON HYBRID VARIABLE NEIGHBORHOOD GENETIC ALGORITHM

针对柔性作业车间调度的问题,以最大完工时间为目标建立数学模型,提出一种混合变邻域遗传算法。采用三种初始化方法保证初始解的质量,用遗传算法进行初步搜索,将搜索的结果通过迭代贪婪策略进一步搜索,以提高解的质量,再对关键路径进行邻域搜索,设计“跨机器工序搜索邻域”、“同机器工序搜索邻域”、“次优工序搜索邻域”三种邻域结构,加强局部搜索能力。引入迭代贪婪策略和改进的邻域结构可显著提高算法的稳定性与迭代速度。通过对国际通用的柔性作业车间调度基准算例进行测试,实验结果表明所提改进算法能够有效求解柔性作业车间调度问题。

Aiming at flexible job-shop scheduling problem,a hybrid variable neighborhood genetic algorithm was proposed to establish a mathematical model with the goal of maximum completion time.In this paper,three initialization methods were used to ensure the quality of the initial solution.The genetic algorithm was used for preliminary search,and the search results were optimized by iterative greedy strategy to improve the quality of the solution.Three kinds of neighborhood structures,"cross-machine process search neighborhood","same-machine process search neighborhood"and"suboptimal process search neighborhood",were designed to strengthen the local search ability.Through the test of the international general flexible job shop scheduling benchmark example,the experimental results showed that the proposed algorithm could effectively solve the flexible job shop scheduling problem.The introduction of iterative greedy strategy and improved neighborhood structure could significantly improve the stability and iteration speed of the algorithm.