序列相关Setup单机调度的最小化最大拖期分枝定界算法

• 作者: 刘晓 刘长勇 王成恩 罗小川
• 来源期刊: 东北大学学报（自然科学版）
• 学科: 工学
• 关键词: 序列相关Setup 交货期 最大拖期 单机调度 分枝定界
• 年，卷（期）: 2005,（10）
• 所属期刊栏目: 信息与控制
• 页码范围: 938-941
• 页数: 4页
• 分类号: TP301.6
• 字数: 3344字
• 语种: 中文
• DOI: 10.3321/j.issn:1005-3026.2005.10.006

摘要

研究了具有序列相关Setup带交货期的单机调度NP问题,优化目标是最小化最大拖期.通过松弛子路径连通约束,提出了基于AP算法的下界方法.在算法下界的基础上,基于下界解建立了以改进Karp-Steel补偿启发式方法构成的上界构造方法.发现了反映问题特性的两条优势规则.最后依托Ragatz提出的分枝定界算法框架,引入上界和下界方法,以及两条优势规则,形成了求解该问题的分枝定界枚举算法.通过计算实验证明了算法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王成恩	东北大学教育部暨辽宁省流程工业综合自动化重点实验室	60	1063	19.0	30.0
2	罗小川	东北大学教育部暨辽宁省流程工业综合自动化重点实验室	20	83	6.0	8.0
3	刘晓	东北大学工商管理学院	29	200	7.0	13.0
4	刘长勇	东北大学教育部暨辽宁省流程工业综合自动化重点实验室	1	1	1.0	1.0