Research on Improvement of B&B Algorithm Performance of Single Machine Total Tardiness Schedule

摘要：

This paper addresses the schemes to improve B&B algorithm performance for the NP-hard problem of scheduling N jobs on a single machine with due dates,sequence-dependent setup times, and no preemption, where the objective is to minimize the total tardiness. Some dominance rules are proposed to reduce the expanded nodes and explored nodes. A comparison with Ragatzs B&B approaches indicates that the algorithm, which adopts our schemes, is competitive and has a certain advantage for larger problems.

关键词： Dominance Rule Algorithm Performance B&B Algorithm Total Tardiness Single Machine Scheduling

作者: Xiaochuan Luo Dancheng LI Hang Song

作者单位: Key Laboratory of Process Industry Automation Northeastern University Shenyang, Liaoning 110004, Chi Software College, Northeastern University Shenyang, Liaoning 110004, China

会议类型: 国际会议

会议名称: 2006 International Symposium on Distributed Computing and Applications to Business,Engineering and Science(2006年国际电子、工程及科学领域的分布式计算应用学术研讨会)

会议地点: 杭州

会议语种:英文

页码: 1368-1371

在线出版日期: 2006-10-12（万方平台首次上网日期，不代表论文的发表时间）