计算机工程与应用Issue(10)：26-29,4.DOI:10.3778/j.issn.1002-8331.1501-0113
三台机并行工件排序问题的改进的下界
Improved lower bound for online scheduling of parallel jobs on three machines
摘要
Abstract
The online scheduling of parallel jobs on parallel machines is considered in this paper. Contrary to classical parallel machine scheduling problems, jobs may require processing on several machines in parallel. The standard metric for worst-case performance is the competitive ratio. By constructing certain adversary sequence, all the nine kinds of cases are analyzed. It is shown that 2.07 is a new lower bound on the competitive ratio of any online algorithm, which is better than the previous lower bound of 1.999.关键词
排序/并行工件/在线算法/竞争比Key words
scheduling/parallel job/online algorithm/competitive ratio分类
数理科学引用本文复制引用
余国松,徐刚..三台机并行工件排序问题的改进的下界[J].计算机工程与应用,2015,(10):26-29,4.基金项目
国家自然科学基金（No.61175127）；江西省自然科学基金（No.20142BAB211021）。 （）
