Lp范数下2台机器并行工件在线排序问题研究

• 作者: 余金果 帅天平 李翠静
• 来源期刊: 软件
• 学科: 数学
• 关键词: 在线算法 排序 并行工件 lp范数 竞争比
• 年，卷（期）: 2014,（5）
• 所属期刊栏目: 基金项目
• 页码范围: 13-16
• 页数: 4页
• 分类号: O211
• 字数: 2743字
• 语种: 中文
• DOI: 10.3969/j.issn.1003-6970.2014.05.003

摘要

本文研究一类并行工件平行机在线排序问题。给定2台平行机和一组按列表到达的并行工件，对每一到达的工件进行机器指派和确定开工时间，使得机器完工时间的lp范数最小。本文首先分析了LS算法的竞争比，其值为2；其次证明了任何在线算法的竞争比不小于4/3。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	帅天平	北京邮电大学理学院	8	8	2.0	2.0
2	余金果	北京邮电大学理学院	2	4	1.0	2.0
3	李翠静	北京邮电大学理学院	2	1	1.0	1.0