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

IMPROVED VARIABLE NEIGHBOURHOOD SEARCH ALGORITHM FOR FLEXIBLE JOB SHOP SCHEDULING PROBLEM

作　　者：刘巍巍[1,2] 马雪丽[3] 刘晓冰[1] 

机构地区：[1]大连理工大学管理与经济学部,辽宁大连116030 [2]沈阳工业大学机械工程学院,辽宁沈阳110870 [3]烟台大学经济管理学院,山东烟台264005

出　　处：《计算机应用与软件》2015年第4期234-238,共5页Computer Applications and Software

基　　金：国家自然科学基金重点项目(61034003);国家科技支撑项目(2012BAF12B08);国家科技支撑计划(SQ2011G X03E00708)

摘　　要：针对柔性作业车间调度问题的特点,提出一种求解该问题的改进变邻域搜索算法。结合问题特点设计合理的编码方式,采用遗传算法进行最优解搜索,将搜索的结果作为变邻域搜索算法的初始解,以提高初始解的质量。为提高局部搜索能力,设计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.

关 键 词：柔性作业车间调度 变邻域搜索 遗传算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]