基于组合变邻域的无等待流水车间调度研究  

Research on No-wait Flowshop Scheduling Problem Based on Combination Variable Neighborhood Search

作　　者：王晶[1,2] 李铁克[1] 张文学[1] 

机构地区：[1]北京科技大学,北京100083 [2]燕山大学,秦皇岛066004

出　　处：《中国机械工程》2009年第16期1932-1936,共5页China Mechanical Engineering

基　　金：国家自然科学基金资助项目(70771008);河北省教育厅自然科学基金资助项目(2008207)

摘　　要：针对无等待流水车间中目标函数为流程时间最短的问题,首先根据目标函数特征将该问题转化成旅行商问题,构造费用矩阵,将费用矩阵看作指派问题的效率矩阵并求解;然后根据问题特征将解转化为初始加工序列,再利用组合变邻域方法优化改进解的质量。实验证明,与现存的算法相比,该算法的计算时间有所缩短,搜索效果有所提高。This paper presented a hybrid algorithm for no--wait flowshop scheduling problem with makespan criterion. The algorithm included three stages. In the first stage, the problem was changed to TSP, and constructed the expenses matrix according the characteristics of the problem, but the expenses matrix was solved as an assign problem; then an initial solution was got in the second stage; and in the third stage the current solution was optimized using the combination variable neighborhood search. The proposed algorithms are evaluated and found to be relatively more effective in finding better quality solutions than that from existing algorithms.

关 键 词：无等待流水车间 指派问题 变邻域搜索 动态搜索 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]