具有交货时间窗约束的无等待流水车间调度模型与算法  

Model and Algorithm for No-wait Flow Shop Scheduling Problem Based on E/T

作　　者：王晶[1] 王伟玲[2] 

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

出　　处：《中国机械工程》2010年第19期2334-2338,2344,共6页China Mechanical Engineering

基　　金：河北省社会科学发展研究课题(200905005);国家自然科学基金资助项目(71071134);河北省科学技术研究与发展计划资助项目(10457203D-16)

摘　　要：针对目标函数为提前/拖期惩罚最小、具有交货时间窗要求的无等待流水车间调度问题,建立了约束满足模型,提出了约束传播与邻域搜索相结合的求解方法。在求解过程中,首先应用约束传播的思想通过逐步安排最小加工时间窗工件构造初始调度,在此基础上利用变邻域搜索逐步迭代以获取满意调度,为避免陷入局部极值,迭代过程中采用多重交换邻域的扰动策略。仿真实验证明了算法的有效性。For the no-wait flow shop scheduling problem with a delivery time window to minimize the punishment of the E/T,a constraint satisfaction model was established,and a algorithm was proposed based on constraint propagation and neighborhood search.Firstly,an initial scheduling wasgenerated using heuristic method embedded constraint propagation.Secondly,a swap search based onneighborhood structure was designed for iterate operation,in order to avoid falling into local optimum,a disturbance strategy based on dynamic swap was used.The simulation results show the effectiveness of the algorithm.

关 键 词：无等待流水车间调度 提前/拖期 邻域搜索 约束满足 

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