一种新的在线调度算法竞争比分析方法---基于实例转换的方法

陶继平;席裕庚

系统科学与数学 ›› 2009, Vol. 29 ›› Issue (10) : 1381-1389.

PDF(555 KB)
中国科学院数学与系统科学研究院期刊网
PDF(555 KB)
系统科学与数学 ›› 2009, Vol. 29 ›› Issue (10) : 1381-1389. DOI: 10.12341/jssms08461
论文

一种新的在线调度算法竞争比分析方法---基于实例转换的方法

    陶继平, 席裕庚
作者信息 +

A Novel Way to Analyze Competitive Performance of Online Algorithms-Instance Transformation Based Method

    TAO Jiping, XI Yugeng
Author information +
文章历史 +

摘要

针对工件动态到达的在线调度模型提出了一种基于实例转换的竞争分析方法,该方法从问题
的一个任意实例出发,逐步沿着性能比增加的方向修改工件的各种参数而得到结构更加简单特殊的实例,最后所导出的简单实例的性能比可以直接计算,且是算法竞争比的一个上界.该方法为在线调度算法的竞争比分析提供了一种新颖的、规律性的思路,以最小化总加权完工时间的单机在线调度问题为例,使用提出的分析方法为该问题一个已有的竞争分析结论提供了更加简洁明了的替代
性证明.

Abstract

A competitive analysis method for online algorithms is developed based on the idea of instance transformation. The method begins with an arbitrary instance, and transforms the instance along the direction of its performance ratio increasing, moreover the eventual instance after transformation shows a more special structure of which we can take advantage to analyze its performance ratio. This presented method is applied on a single machine online scheduling problem of minimizing the total weighted completion time. We give an alternative proof of an existing conclusion about the competitive performance.

关键词

实例转换 / 在线调度 / 竞争分析 / 单机调度 / 总加权完工时间.

Key words

Instance transformation / online algorithm / competitive analysis / single machine scheduling / total weighted completion time.

引用本文

EndNote

Ris (Procite)

Bibtex

导出引用
陶继平 , 席裕庚. 一种新的在线调度算法竞争比分析方法---基于实例转换的方法. 系统科学与数学, 2009, 29(10): 1381-1389. https://doi.org/10.12341/jssms08461
TAO Jiping , XI Yugeng. A Novel Way to Analyze Competitive Performance of Online Algorithms-Instance Transformation Based Method. Journal of Systems Science and Mathematical Sciences, 2009, 29(10): 1381-1389 https://doi.org/10.12341/jssms08461
中图分类号： 90B35   
PDF(555 KB)

Accesses

Citation

Detail
段落导航
相关文章

/

〈 〉