使总完工时间达到最小的流水作业排序问题

• 作者: 张琼 时凌 龙彩燕
• 来源期刊: 西南民族大学学报（自然科学版）
• 学科: 数学
• 关键词: 总完工时间 流水作业排序问题 最坏性能比 单服务器
• 年，卷（期）: 2020,（6）
• 所属期刊栏目: 数学与物理学
• 页码范围: 638-642
• 页数: 5页
• 分类号: O223
• 语种: 中文
• DOI: 10.11920/xnmdzk.2020.06.013

摘要

研究带单服务器且服务时间相等的流水作业排序问题,该流水作业排序问题的目标函数是使总完工时间达到最小.利用目标和的数字匹配这个强NP-困难问题到带单服务器且服务时间相等的流水作业排序问题的归约,证明带单服务器且服务时间相等的流水作业排序问题问题也是强NP-困难的.引入加工顺序为最小加工时间优先的新启发式算法,并证明该启发式算法的上界是6/5,且该上界是紧的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	龙彩燕		5	0	0.0	0.0
2	时凌		10	9	2.0	2.0
3	张琼		12	7	1.0	1.0