论文标题
在线列表计划算法的新竞争分析结果
New Competitive Analysis Results of Online List Scheduling Algorithm
论文作者
论文摘要
在线算法一直是计算机科学各个领域研究人员的新兴领域。格雷厄姆（Graham）引入的在线$ M $ - 机器列表调度问题在开发竞争分析的发展方面具有理论和实际意义，作为在线算法的绩效衡量标准。在本文中，我们研究和探讨了Graham在线\ textit {list Scheduling算法（LSA）}的性能。在文献中，\ textit {lsa}已经被证明为$ 2- \ frac {1} {m} {m} $竞争力，其中$ m $是机器的数量。我们在\ textIt {lsa}的竞争分析上提供了两个新的上限结果。我们以$ 2- \ frac {2} {m} $和$ 2- \ frac {m^2-m+1} {m^2} $的竞争比率获得上限。我们的分析结果可以激发从业者通过表征现实生活输入序列来设计改进的$ m $ $ MACHINE列表调度问题的竞争性在线算法。
Online algorithm has been an emerging area of interest for researchers in various domains of computer science. The online $m$-machine list scheduling problem introduced by Graham has gained theoretical as well as practical significance in the development of competitive analysis as a performance measure for online algorithms. In this paper, we study and explore the performance of Graham's online \textit{list scheduling algorithm(LSA)} for independent jobs. In the literature, \textit{LSA} has already been proved to be $2-\frac{1}{m}$ competitive, where $m$ is the number of machines. We present two new upper bound results on competitive analysis of \textit{LSA}. We obtain upper bounds on the competitive ratio of $2-\frac{2}{m}$ and $2-\frac{m^2-m+1}{m^2}$ respectively for practically significant two special classes of input job sequences. Our analytical results can motivate the practitioners to design improved competitive online algorithms for the $m$-machine list scheduling problem by characterization of real life input sequences.
