东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2005, Vol. 26 ›› Issue (10): 938-941.DOI: -

• 论著 • 上一篇    下一篇

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

罗小川;刘长勇;刘晓;王成恩   

  1. 东北大学教育部暨辽宁省流程工业综合自动化重点实验室;东北大学教育部暨辽宁省流程工业综合自动化重点实验室;东北大学工商管理学院;东北大学教育部暨辽宁省流程工业综合自动化重点实验室 辽宁沈阳110004
  • 收稿日期:2013-06-24 修回日期:2013-06-24 出版日期:2005-10-15 发布日期:2013-06-24
  • 通讯作者: Luo, X.-C.
  • 作者简介:-
  • 基金资助:
    国家自然科学基金资助项目(50205007);;

Branch-and-bound algorithm for scheduling on single processor with sequence-dependent setup times to minimize maximum tardiness

Luo, Xiao-Chuan (1); Liu, Chang-Yong (1); Liu, Xiao (2); Wang, Cheng-En (1)   

  1. (1) Laboratory of Process Industry Automation, Northeastern University, Shenyang 110004, China; (2) School of Business Administration, Northeastern University, Shenyang 110004, China
  • Received:2013-06-24 Revised:2013-06-24 Online:2005-10-15 Published:2013-06-24
  • Contact: Luo, X.-C.
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

748

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

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

Abstract: 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 rules. Computational experiments demonstrate the effectiveness of the algorithm.

中图分类号: