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

Branch-and-Bound Algorithm for Scheduling on Single Processor with Sequence-Dependent Setup Times to Minimize Maximum Tardiness

作　　者：罗小川[1] 刘长勇[1] 刘晓[2] 王成恩[1] 

机构地区：[1]东北大学教育部暨辽宁省流程工业综合自动化重点实验室,辽宁沈阳110004 [2]东北大学工商管理学院,辽宁沈阳110004

出　　处：《东北大学学报（自然科学版）》2005年第10期938-941,共4页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金资助项目(50205007);东北大学'十五'学科建设项目

摘　　要：研究了具有序列相关Setup带交货期的单机调度NP问题,优化目标是最小化最大拖期.通过松弛子路径连通约束,提出了基于AP算法的下界方法.在算法下界的基础上,基于下界解建立了以改进Karp-Steel补偿启发式方法构成的上界构造方法.发现了反映问题特性的两条优势规则.最后依托Ragatz提出的分枝定界算法框架,引入上界和下界方法,以及两条优势规则,形成了求解该问题的分枝定界枚举算法.通过计算实验证明了算法的有效性.The NP-hard problem of scheduling N jobs on a single processor with due dates and sequence-dependent setup times is studied, where the objective is to minimize the maximum tardiness. By relaxing the connectivity constraints to eliminate subtours the lower bound methods are proposed. Then, the upper bound methods are constructed by the modified Karp-Steel patching heuristic method based on the solution of lower bound problem. Two dominance rules are proved according to the natural features of the problem. An algorithm based on Ragatz＇s branch-and-bound permutation schemes is thus developed including the implementation of lower and upper bounding procedures and dominance roles. Computational experiments demonstrate the effectiveness of the algorithm.

关 键 词：序列相关Setup 交货期 最大拖期 单机调度 分枝定界 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]