带两个服务等级的三台机最优在线算法

• 作者: 周昊 王玉艳 蒋义伟
• 来源期刊: 高校应用数学学报A辑
• 学科: 数学
• 关键词: 在线排序 服务等级 总完工时间 竞争比
• 年，卷（期）: 2017,（2）
• 页码范围: 207-216
• 页数: 10页
• 分类号: O175.14
• 字数: 7125字
• 语种: 中文

摘要

研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	蒋义伟	浙江工商大学管理工程与电子商务学院	4	0	0.0	0.0
2	周昊	浙江树人大学基础部	12	7	1.0	2.0
3	王玉艳	浙江理工大学理学院	1	0	0.0	0.0