三台机并行工件排序问题的改进的下界

• 作者: 余国松 徐刚
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 排序 并行工件 在线算法 竞争比
• 年，卷（期）: 2015,（10）
• 所属期刊栏目: 博士论坛
• 页码范围: 26-29
• 页数: 4页
• 分类号: O221.7|TP301.6
• 字数: 2080字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1501-0113

摘要

与经典的排序问题不同的是，并行工件排序指的是在加工某些工件时，需要多个机器同时并行工作。竞争比是评价在线算法好坏的一个重要指标，而竞争比的下界则是算法设计的一个重要参考。利用反证法，通过构造一个特殊的反例，分析了由此产生的全部9种可能的情形，建立了它们对应的9种线性规划模型，借助计算软件证明了前8种情形是不可能的，然后详细分析了第9种情形也是不可能的，从而给出了三台机并行工件排序问题的竞争比的一个改进的下界2.07。这个结果优于已知的最好的下界1.999。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐刚	南昌大学数学系	23	206	8.0	14.0
2	余国松	南昌大学数学系	7	25	2.0	5.0