第 27 卷 第 5 期
Vol. 27 No. 5
控 制 与 决 策
Control and Decision
2012 年 5 月
May 2012
基于 TSP 方法求解等待时间受限的置换流水车间调度
文章编号: 1001-0920 (2012) 05-0768-05
王柏琳, 李铁克, 孙 彬
(1. 北京科技大学 东凌经济管理学院，北京 100083；2. 钢铁生产
制造执行系统技术教育部工程研究中心，北京 100083)
摘 要: 等待时间受限的置换流水车间调度问题要求工件在连续两个机器间的等待时间满足上限值约束. 对
此, 分析了工件序列中相邻工件的加工持续时间及其上下界关系, 并且提出一种启发式方法. 首先, 建立旅行商问
题 (TSP) 以生成初始调度; 然后, 采用扩展插入方法优化调度解. 为了衡量算法性能, 给出问题下界的计算方法和相
关评价指标, 并通过数据实验验证了该启发式和下界计算方法的可行性和有效性.
关键词: 生产调度；置换流水车间；等待时间受限；启发式
中图分类号: TP301 文献标识码: A
TSP-based heuristic algorithm for permutation flowshop scheduling with
limited waiting time constraints
WANG Bai-lin, LI Tie-ke, SUN Bin
(1. Dongling School of Economics and Management，University of Science and Technology Beijing，Beijing
100083，China；2. Engineering Research Center of MES Technology for Iron & Steel Production，Ministry of
Education，Beijing 100083，China．Correspondent：WANG Bai-lin，E-mail：wangbailin 83@sina.com)
Abstract: In the permutation flowshop scheduling problem with limited waiting time constraints, the waiting time of each
job between two consecutive machines is restricted by some upper bound. Based on the deep discussion of the duration time
between two adjacent jobs in one job permutation and the relations of its upper and lower bound, a heuristic algorithm is
proposed. In the algorithm, a travelling salesman problem(TSP) concerning the duration times is built to obtain an initial
schedule, and then an extended inserting method is presented for the further optimization. To measure algorithm performance,
an approach to calculate a lower bound of the problem is proposed. Numerical results show effectiveness and feasibility of
this heuristic algorithm.
Key words: scheduling；permutation flowshop；limited waiting time ；heuristic
1 引引引 言言言
流水车间调度问题在工业中具有广泛的应用背
景, 一直是生产调度领域中的研究热点之一
[1]
. 然而
该问题在钢铁生产、玻璃制造等高温连续生产或中
间产品性质不稳定的车间生产过程中, 往往存在等
待时间受限的特殊约束, 要求工件在相邻阶段间的
等待时间不超过一定的上限值. 目前, 关于这类流水
车间调度问题的研究成果不多. 对于问题复杂性, 文
献 [2] 证明了两机情况下问题具有 NP 难特性, [3] 证
明了等待时间同时具有上下限约束的置换流水车间
调度是强 NP 难的; 在算法求解方面, [2-3] 采用分支
定界法求解; [4] 针对第 1 阶段存在批处理过程的两
机流水车间环境, 建立了混合整数规划模型, 并提出
启发式方法求解; [5] 对在不同车间环境下, 等待时间
受限的调度问题的建模机制进行了研究; [6] 分析了
等待时间上限与可行调度的解析关系以及目标函数
的特殊性质, 并提出一种启发式算法; [7] 提出最小化
加权设备完工时间的优化目标, 并对该目标下具有等
待时间上下限约束的置换流水车间调度问题设计了
分支定界算法; [8] 采用分支定界法求解一类等待时
间严格等于定值的置换流水车间调度问题; [9] 针对
等待时间受限的流水车间问题，提出嵌入约束满足
收稿日期: 2010-11-07；修回日期: 2011-01-23.
基金项目: 教育部博士学科点专项科研基金项目 (20100006110006)；国家自然科学基金项目 (70771008)；中央高校基
本科研业务费专项资金项目 (FRF-AS-09-007B).
作者简介: 王柏琳 (1983−), 女, 讲师, 博士, 从事生产调度、智能算法等研究；李铁克 (1958−), 男, 教授, 博士生导师, 从
事先进制造管理、生产计划与调度等研究.
资源评论
weixin_38610277
- 粉丝: 8
- 资源: 906
最新资源
- stm32+uCOS，个人学习整理，仅供参考
- 高分课程设计-基于Java实现校园一卡通系统(学校学生管理系统) +项目源码+文档说明+运行说明
- 随机共振检测微弱信号matlab代码
- 预计2030年全球压电微型泵市场规模将达到0.7亿美元
- （存储过程）梳理Job定时任务的使用详解.pdf
- 车辆主动悬架防侧翻控制 利用Simulink和Carsim进行联合仿真，搭建主动悬架以及防倾杆模型，在不同转角工况下进行仿真试验，设置滑模等控制器计算维持车辆侧倾稳定性所需的力矩，将力矩分配到
- 基于二阶锥规划的主动配电网动态最优潮流求解 关键词：配电网优化 二阶锥优化 动态优化 最优潮流 仿真代码:MATLAB YAL
- 预计2030年全球医用二氧化碳吸收剂市场规模将达到1.3亿美元
- 基于二阶锥规划的主动配电网最优潮流求解
- 预计2030年全球医用毫米波雷达市场规模将达到1.7亿美元
- 华为6508AC2024年的升级固件
- 基于二阶锥规划的主动配电网最优潮流求解.zip
- 机械设计双工位漏液测试机sw18非常好的设计图纸100%好用.zip
- 预计2030年全球异山梨醇市场规模将达到8.9亿美元
- cplex配电网重构多时段，二阶锥规划 参考文献名：主动配电网最优潮流研究及其应用实例（中国电机工程学报） 最优潮流研究在配电网
- comsol扭转MoO3完美圆二向色
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
