求解柔性作业车间调度问题的一种新邻域结构

A new neighborhood structure for solving the flexible job-shop scheduling problem

针对柔性作业车间调度问题(flexible job-shop scheduling problem,FJSP),提出了一种新的邻域结构,该邻域结构保证任意一次邻域移动可以改进当前解,从而显著地缩小了邻域规模.在此基础上,在求解FJSP问题的禁忌搜索算法中,设计了基于该邻域结构的两级邻域搜索策略,该策略既增加了邻域搜索的有效性,又保证了最优解的连通性.最后,针对69个FJSP的Benchmark问题进行了测试,实验结果验证了新邻域结构的有效性,并更新了 4个Benchmark问题的历史最优解.

For flexible job-shop scheduling problem,a new neighborhood structure is proposed.The neighborhood structure guarantees each move can produce an improved solution,which significantly reduce the size of neighborhood.Based on the neighborhood structure,a two-pace neighborhood search strategy is designed to insert into the procedure of tabu search.The strategy not only enhances search efficiency,but also holds the optimum connectivity.Finally,69 famous benchmark instances of the FJSP are used to verify the performance of the proposed neighbourhood structure and the best known solutions for 4 benchmark instances are updated.