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

• 作者: 时凌
• 来源期刊: 西南民族大学学报(自然科学版)
• 学科: 数学
• 关键词: 流水作业时间表 延迟时间 准备时间 3-划分 NP-困难
• 年，卷（期）: 2003,（3）
• 页码范围: 258-263
• 页数: 6页
• 分类号: O223
• 字数: 2001字
• 语种: 中文
• DOI: 10.3969/j.issn.1003-2843.2003.03.002

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	时凌	湖北民族学院理学院	24	20	3.0	3.0