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

摘要：

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

关键词：排序、并行工件、在线算法、竞争比

分类号：O221.7;TP301.6(运筹学)

资助基金：国家自然科学基金No.61175127；江西省自然科学基金No.20142BAB211021。

在线出版日期：2015-06-01（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：26-29