面向柔性作业车间调度问题的改进变邻域搜索算法

IMPROVED VARIABLE NEIGHBOURHOOD SEARCH ALGORITHM FOR FLEXIBLE JOB SHOP SCHEDULING PROBLEM

针对柔性作业车间调度问题的特点,提出一种求解该问题的改进变邻域搜索算法。结合问题特点设计合理的编码方式,采用遗传算法进行最优解搜索,将搜索的结果作为变邻域搜索算法的初始解,以提高初始解的质量。为提高局部搜索能力,设计3种不同的邻域结构,构建邻域结构集以产生邻域解,保证邻域解的搜索过程中解的可行性以提高求解效率。针对一系列典型的柔性作业车间调度问题的实例,运用所设计的改进变邻域搜索算法进行测试求解,并将计算结果与文献中其他算法的测试结果进行比较,验证了所提出方法求解柔性作业车间调度问题的可行性和有效性。

Aiming at the characteristics of flexible job shop scheduling problem （FJSP）,we propose an improved variable neighbourhood search （IVNS）algorithm to solve it.Combining the characteristics of the problem we design rational coding means and adopt the genetic algorithm for optimum solution search,as well as take the search result as an initial solution of variable neighbourhood search algorithm to improve the quality of initial solution.To improve the capabilities of local search,we design three different neighbourhood structures and construct neighbourhood solution set for producing the neighbourhood solution,thus ensure the feasibility of the neighbourhood solution in search process so as to improve the efficiency of solution.The proposed IVNS is applied to a series of typical FJSPs for test and solution,and the comparison is also made between the calculation results and the test results of other algorithms in literature,the feasibility and effectiveness of the proposed approach in solving FJSP are verified as well.