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

doi:10.13196/j.cims.2014.02.yanghongan.0414.10.20140222

计算机集成制造系统 ›› 2014, Vol. 20 ›› Issue (2): 414-.DOI: 10.13196/j.cims.2014.02.yanghongan.0414.10.20140222

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

杨宏安,齐亮亮,李锦远,王宏浩

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

出版日期:2014-03-28 发布日期:2014-03-28
基金资助:
国家自然科学基金资助项目(50705076);西北工业大学研究生创业种子基金资助项目(Z2012048);教育部留学回国人员科研启动基金资助项目

Hybrid algorithm of VNS/MP for JIT Job-shop scheduling problem

Online:2014-03-28 Published:2014-03-28
Supported by:
Project supported by the National Natural Science Foundation,China(No.50705076),the Graduate Starting Seed Fund of Northwestern Polytechnical University,China(No.Z2012048),and the Scientific Research Foundation for the Returned Overseas Chinese Scholars of Ministry of Education,China.

摘要/Abstract

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

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

Abstract: Aiming at the complex informal performance index scheduling problem such as Just-In-Time Job-shop Scheduling Problem(JIT-JSP),a hybrid scheduling algorithm of Variable Neighborhood Search(VNS)and Mathematical Programming(MP)based on two-stage optimization strategy was proposed.In each iteration procedure of VNS,the better machine process sequence was obtained by searching between the two neighborhoods of Swap and Insertion.The MP method was used to optimize each procedure's start time in machine process sequence.To impose more diversification,the local search was developed as a threshold accepting method based on two mentioned neighborhood structures.Computational results on 72 benchmark JIT scheduling problems showed that the VNS/MP algorithm could find the best known solution for 35 problems,and the best known solutions for 25 problems were updated.

Key words: Job-shop, just-in-time scheduling, variable neighborhood search, mathematical programming, neighborhood structure

中图分类号:

TP301

杨宏安,齐亮亮,李锦远,王宏浩. 求解作业车间JIT调度问题的VNS/MP混合算法[J]. 计算机集成制造系统, 2014, 20(2): 414-.

[1]	顾九春,姜天华,朱惠琦. 多目标离散灰狼优化算法求解作业车间节能调度问题[J]. 计算机集成制造系统, 2021, 27(8): 2295-2306.
[2]	黎英杰,刘建军,陈庆新,毛宁. 多层级装配作业车间等量分批策略与调度算法[J]. 计算机集成制造系统, 2021, 27(8): 2307-2320.
[3]	杨艳华,姚立纲. 基于时间递推建模及交叉熵算法求解柔性作业车间调度问题[J]. 计算机集成制造系统, 2021, 27(6): 1703-1713.
[4]	段建国,李豪晨,张青雷. 面向绿色制造的半组合式船用曲轴结构件生产车间多目标调度优化[J]. 计算机集成制造系统, 2021, 27(6): 1714-1727.
[5]	杨小佳,刘建军,陈庆新,毛宁. 变扰动强度下柔性装配作业车间调度性能分析[J]. 计算机集成制造系统, 2021, 27(3): 800-814.
[6]	詹欣隆,张超勇,孟磊磊,连裕翔,薛燕社. 面向高效低碳的切削参数与柔性作业车间调度集成建模与优化[J]. 计算机集成制造系统, 2021, 27(12): 3519-3535.
[7]	葛艳,王爱民,叶介然. 基于遗传退火算法的质检扰动应对方法[J]. 计算机集成制造系统, 2021, 27(11): 3159-3171.
[8]	连裕翔,张超勇,孟磊磊,薛燕社,詹欣隆,吕畅. 基于改进Jaya算法的柔性作业车间调度问题[J]. 计算机集成制造系统, 2021, 27(11): 3172-3184.
[9]	刘雪红,段程,王磊. 基于改进候鸟算法的柔性作业车间分批调度问题[J]. 计算机集成制造系统, 2021, 27(11): 3185-3195.
[10]	薛玲玲. 作业车间调度的块结构邻域搜索遗传算法[J]. 计算机集成制造系统, 2021, 27(10): 2848-2857.
[11]	李峥峰,刘阳阳. 考虑充电的多AGV的作业车间调度问题[J]. 计算机集成制造系统, 2021, 27(10): 2872-2879.
[12]	罗焕,陈浩杰,宋小欣,张剑. 带有缓存约束的作业车间调度求解方法[J]. 计算机集成制造系统, 2021, 27(10): 2880-2888.
[13]	陈久梅,李英娟,胡婷,但斌,李俊. 开放式带时间窗车辆路径问题及变邻域搜索算法[J]. 计算机集成制造系统, 2021, 27(10): 3014-3025.
[14]	李聪波,寇阳,雷焱绯,肖溱鸽,李玲玲. 基于动态事件的柔性作业车间重调度节能优化[J]. 计算机集成制造系统, 2020, 26(第2): 288-299.
[15]	汤洪涛,费永辉,陈青丰,詹燕,鲁建厦,李晋青. 基于工业大数据的柔性作业车间动态调度[J]. 计算机集成制造系统, 2020, 26(9): 2497-2510.

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

Hybrid algorithm of VNS/MP for JIT Job-shop scheduling problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics