带两个服务等级的3台机半在线算法

• 作者: 丁璐 张怡 肖满
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 排序 服务等级 3台机器 半在线算法 竞争比
• 年，卷（期）: 2020,（12）
• 所属期刊栏目: 人工智能与数据挖掘
• 页码范围: 2252-2258
• 页数: 7页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2020.12.019

摘要

研究了3台机上带有2个服务等级的半在线排序问题,其中等级为1的机器只有1台,等级为2的机器有2台,目标为极小化机器最大完工时间.在已知等级为1的工件加工时间之和时,给出一个下界为3/2和一个竞争比为5/3的在线算法;在已知等级为2的工件加工时间之和时,给出一个下界为3/2和一个竞争比为9/5的在线算法;在分别已知2个等级的工件加工时间之和时,给出一个下界为4/3和一个竞争比为3/2的在线算法;在已知工件总的加工时间时,给出一个竞争比为3/2的最优在线算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张怡		4	0	0.0	0.0
2	肖满		1	0	0.0	0.0
3	丁璐		2	5	1.0	2.0