有限等待流水车间调度邻域搜索算法  

Neighborhood Search Algorithm for Flow Shop Scheduling Problem with Limited Waiting Time Constraints

作　　者：王晶[1] 姚辉[2] 王艳亮[1] 

机构地区：[1]燕山大学经济管理学院,河北秦皇岛066004 [2]首都师范大学资源环境与旅游学院,北京100048

出　　处：《工业工程与管理》2010年第3期55-59,共5页Industrial Engineering and Management

基　　金：河北省社会科学基金项目(HB08BYJ027);2009年度河北省社会科学发展研究课题(200905005);2010年河北省科技厅软科学项目(1045720D-16)

摘　　要：针对工序间等待时间受限,目标函数为最大完工时间最短的流水车间调度问题,提出了一种动态变邻域搜索算法。算法采用工件对比较算法和贪婪插入规则,构建了初始调度;通过嵌入3-opt,2-opt实现动态变邻域搜索;并在迭代过程中加入动态禁忌策略。A dynamic variable neighborhood search algorithm is proposed,aiming at flow shop scheduling problem with limited waiting time constraints and the objective is to minimize makespan.Firstly,the algorithm produces the initial schedule with job pair comparison and greed insert algorithm.Secondly,two kinds of swap search method,3-opt and 2-opt,are embedded into the algorithm to achieve the dynamic variable neighborhood search.At the same time,dynamic tabu list is added to the iterative process.

关 键 词：流水车间调度 有限等待 邻域搜索 

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