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

作     者：陶继平 席裕庚 

作者机构：上海交通大学自动化系上海200240 

出 版 物：《系统科学与数学》 (Journal of Systems Science and Mathematical Sciences)

年 卷 期：2009年第29卷第10期

页      面：1381-1389页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 081203[工学-计算机应用技术] 08[工学] 070105[理学-运筹学与控制论] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金(60674041) 高等学校博士学科点专项科研基金(20070248004)资助项目 

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

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