带单服务器的流水作业时间表问题

• 作者: 时凌
• 来源期刊: 华中科技大学学报（自然科学版）
• 学科: 数学
• 关键词: 流水作业时间表 单服务器 复杂性 启发式算法
• 年，卷（期）: 2005,（4）
• 页码范围: 121-124
• 页数: 4页
• 分类号: O223
• 字数: 4521字
• 语种: 中文
• DOI: 10.3321/j.issn:1671-4512.2005.04.037

摘要

研究带单服务器的流水作业时间表问题,目标是使加工时间达到最小,该问题是强NP-困难的.证明即使对于所有安装时间等于1或者所有加工时间等于1的情况下,该问题仍然是强NP-困难的,所以不存在多项式时间的最优解.在只有两台机器的情况下,引入了一人新的启发式算法,并证明该算法的紧界为3/2.

作者信息

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