自由作业稠密时间表的性质研究

摘要：

稠密时间表作为自由作业问题的近似解,其加工总长与最优值之比具有上界2-1/m(m为机器数),是一个尚未证明的猜想.利用组合方法证明了稠密时问表性能比猜想成立的一个充分条件.利用该条件及有关文献的结果.给出了机器数不超过7的自由作业稠密时间表性能比猜想的证明.

关键词：自由作业、加工总长、稠密时间表、性能比

所属期刊栏目：39

分类号：O22;O29

资助基金：国家自然科学基金重大国际地区合作研究项目70731160015;江苏省教育厅项目yw06037;江苏省"青蓝"工程资助

在线出版日期：2009-06-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：166-173