计算机应用 ›› 2005, Vol. 25 ›› Issue (08): 1829-1832.DOI: 10.3724/SP.J.1087.2005.01829
• 数据库与人工智能 • 上一篇 下一篇
罗小川，王成恩
发布日期:
出版日期:
LUO Xiao-chuan,WANG Cheng-en
Online:
Published:
摘要： 研究了一个具有序列相关Setup带交货期的单机调度NP问题,优化目标是最小化最大拖期。提出了一个求解该问题的分枝定界枚举算法,其中包括确定问题上界和下界的方法,以及两条优势规则。计算实验证明了本文提出算法的有效性。
关键词: 序列相关Setup, 交货期, 最大拖期, 分枝定界, 单机调度
Abstract: The NP-hard problem of scheduling N jobs on a single machine with due dates, sequence-dependent setup was addressed, where the objective was to minimize the maximum tardiness. An algorithm based on branchand-bound permutation schemes was developed including the implementation of lower and upper bounding procedures, and two dominance rules. Computational experiments demonstrate the effectiveness of the algorithm.
Key words: sequence dependent setup, due date, maximum tardiness, branch and bound, single machine schedule
中图分类号:
TP301
罗小川，王成恩. 单机序列相关Setup最小化最大拖期算法[J]. 计算机应用, 2005, 25(08): 1829-1832.
LUO Xiao-chuan,WANG Cheng-en. Algorithm for single machne schedule with sequence dependent setup to minimize maximum tardiness[J]. Journal of Computer Applications, 2005, 25(08): 1829-1832.
0 / 推荐
导出引用管理器 EndNote|Ris|BibTeX
链接本文: http://www.joca.cn/CN/10.3724/SP.J.1087.2005.01829
http://www.joca.cn/CN/Y2005/V25/I08/1829
