带两个服务等级约束的三台机排序问题

• 作者: 姚然 张安
• 来源期刊: 杭州电子科技大学学报（自然科学版）
• 关键词: 排序问题 服务等级 在线算法 竞争比
• 年，卷（期）: 2014,（1）
• 所属期刊栏目: 学术论文
• 页码范围: 54-56
• 页数: 3页
• 分类号: O22
• 语种: 中文
• DOI: 10.3969/j.issn.1001-9146.2014.01-012

摘要

研究带两个服务等级约束的3台同型机在线排序问题。工件和机器的服务等级为1或2，加工允许中断但不允许引入机器空闲时间，目标是最小化最大完工时间。该文首先证明任意在线算法的竞争比至少是3/2，接着对仅有1台机器等级为1的情形给出了竞争比为5/3的在线算法。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张安	杭州电子科技大学理学院	24	15	2.0	2.0
2	姚然	杭州电子科技大学理学院	3	2	1.0	1.0