含有批处理机的三机流水作业加工总长问题的计算复杂性

• 作者: 成岗 鲁习文
• 来源期刊: 高校应用数学学报A辑
• 学科: 数学
• 关键词: 流水作业 批处理机 加工总长 NP困难性
• 年，卷（期）: 2005,（4）
• 页码范围: 417-423
• 页数: 7页
• 分类号: O223
• 字数: 3789字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-4424.2005.04.005

摘要

研究含有批处理机的三台机器流水作业加工总长问题的计算复杂性.不仅考虑了批处理机容量有限的情形,还考虑了批处理机容量无限的情形.证明了当第二台机器是批处理机、其余两台机器是单机时,该问题是NP困难的.至此,含有批处理机的三台机器流水作业加工总长问题在所有情形下的计算复杂性得到了解决.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	鲁习文	华东理工大学理学院数学系	29	71	6.0	6.0
2	成岗	华东理工大学理学院数学系	3	5	1.0	2.0