序列相关Setup单机调度的最小化最大拖期分枝定界算法
来源期刊：东北大学学报(自然科学版)2005年第10期
论文作者：罗小川 刘长勇 刘晓 王成恩
文章页码：938 - 941
关键词：序列相关Setup;交货期;最大拖期;单机调度;分枝定界;
摘 要：研究了具有序列相关Setup带交货期的单机调度NP问题,优化目标是最小化最大拖期.通过松弛子路径连通约束,提出了基于AP算法的下界方法.在算法下界的基础上,基于下界解建立了以改进Karp-Steel补偿启发式方法构成的上界构造方法.发现了反映问题特性的两条优势规则.最后依托Ragatz提出的分枝定界算法框架,引入上界和下界方法,以及两条优势规则,形成了求解该问题的分枝定界枚举算法.通过计算实验证明了算法的有效性.
罗小川，刘长勇，刘晓，王成恩
摘 要：研究了具有序列相关Setup带交货期的单机调度NP问题,优化目标是最小化最大拖期.通过松弛子路径连通约束,提出了基于AP算法的下界方法.在算法下界的基础上,基于下界解建立了以改进Karp-Steel补偿启发式方法构成的上界构造方法.发现了反映问题特性的两条优势规则.最后依托Ragatz提出的分枝定界算法框架,引入上界和下界方法,以及两条优势规则,形成了求解该问题的分枝定界枚举算法.通过计算实验证明了算法的有效性.
关键词：序列相关Setup;交货期;最大拖期;单机调度;分枝定界;
