Journal of Computer Applications ›› 2005, Vol. 25 ›› Issue (08): 1829-1832.DOI: 10.3724/SP.J.1087.2005.01829
• Database and aritficial intelligence • Previous Articles Next Articles
LUO Xiao-chuan,WANG Cheng-en
Online:
Published:
罗小川,王成恩
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
摘要: 研究了一个具有序列相关Setup带交货期的单机调度NP问题,优化目标是最小化最大拖期。提出了一个求解该问题的分枝定界枚举算法,其中包括确定问题上界和下界的方法,以及两条优势规则。计算实验证明了本文提出算法的有效性。
关键词: 序列相关Setup, 交货期, 最大拖期, 分枝定界, 单机调度
CLC Number:
TP301
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.
罗小川,王成恩. 单机序列相关Setup最小化最大拖期算法[J]. 计算机应用, 2005, 25(08): 1829-1832.
0 / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: http://www.joca.cn/EN/10.3724/SP.J.1087.2005.01829
http://www.joca.cn/EN/Y2005/V25/I08/1829