求解作业车间JIT调度问题的VNS/MP混合算法

来源：计算机集成制造系统杂志2014年第2期北京时间：

作者：杨宏安,齐亮亮,李锦远,王宏浩

单位：西北工业大学现代设计与集成制造教育部重点实验室

摘要：针对作业车间准时制调度这类复杂的非正规性能指标调度问题,基于机器加工序列和工序开工时间的两阶段优化策略,提出一种结合变邻域搜索和数学规划的混合调度算法。在变领域搜索的每次迭代过程中,通过在Swap和Insertion两类邻域结构内跳转搜索获得较优的机器加工序列,由此松弛了调度模型中最难满足的机器析取约束;然后调用数学规划方法对当前机器加工序列上的各工序开工时间进行优化计算。以引导工序向各自交货期靠拢为邻域设计原则,提出以紧邻工序对为移动对象的Swap和Insertion邻域结构;为增加搜索空间的多样性,变领域搜索中的局域搜索算法采用基于调度目标值容许偏差的阈值接受策略。对72个准时制调度的Benchmark算例的仿真结果表明,变领域搜索/数学规划混合算法获得了35个算例的已知最好解,并且更新了其中25个算例的已知最好解。

关键词：作业车间,准时制调度,变邻域搜索,数学规划,邻域结构

基金资助：国家自然科学基金资助项目(50705076);西北工业大学研究生创业种子基金资助项目(Z2012048);教育部留学回国人员科研启动基金资助项目