| 三台机并行工件排序问题的改进的下界 |
| |
| 引用本文： | 余国松,徐刚. 三台机并行工件排序问题的改进的下界[J]. 计算机工程与应用, 2015, 51(10): 26-29 |
| |
| 作者姓名： | 余国松 徐刚 |
| |
| 作者单位： | 南昌大学 数学系，南昌 330031 |
| |
| 基金项目： | 国家自然科学基金(No.61175127)；江西省自然科学基金(No.20142BAB211021)。 |
| |
| 摘 要： | 与经典的排序问题不同的是，并行工件排序指的是在加工某些工件时，需要多个机器同时并行工作。竞争比是评价在线算法好坏的一个重要指标，而竞争比的下界则是算法设计的一个重要参考。利用反证法，通过构造一个特殊的反例，分析了由此产生的全部9种可能的情形，建立了它们对应的9种线性规划模型，借助计算软件证明了前8种情形是不可能的，然后详细分析了第9种情形也是不可能的，从而给出了三台机并行工件排序问题的竞争比的一个改进的下界2.07。这个结果优于已知的最好的下界1.999。
|
| 关 键 词： | 排序 并行工件 在线算法 竞争比 |
Improved lower bound for online scheduling of parallel jobs on three machines |
| |
| YU Guosong,XU Gang. Improved lower bound for online scheduling of parallel jobs on three machines[J]. Computer Engineering and Applications, 2015, 51(10): 26-29 |
| |
| Authors: | YU Guosong XU Gang |
| |
| Affiliation: | Department of Mathematics, Nanchang University, Nanchang 330031, China |
| |
| 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. |
| |
| Keywords: | scheduling parallel job online algorithm competitive ratio |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
