m台机器上流水作业时间表问题的复杂性及一种新的启发式算法

摘要：

研究流水作业时间表问题,在具有延迟时间的条件下证明该问题是强NP-困难的.给出一种新的启发式算法,并证明该算法的最坏性能比是(m+1)/2,且上界是紧的.

关键词：流水作业时间表、延迟时间、准备时间、3-划分、NP-困难

所属期刊栏目：29

分类号：O223(运筹学)

资助基金：Supported by Educational Department of Hubei Province2002x13

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

页数：共6页

页码：258-263