期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

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

A NOVEL WAY TO ANALYZE COMPETITIVE PERFORMANCE OF ONLINE ALGORITHMS——INSTANCE TRANSFORMATION BASED METHOD
原文传递
导出
摘要 针对工件动态到达的在线调度模型提出了一种基于实例转换的竞争分析方法,该方法从问题的一个任意实例出发,逐步沿着性能比增加的方向修改工件的各种参数而得到结构更加简单特殊的实例,最后所导出的简单实例的性能比可以直接计算,且是算法竞争比的一个上界.该方法为在线调度算法的竞争比分析提供了一种新颖的、规律性的思路,以最小化总加权完工时间的单机在线调度问题为例,使用提出的分析方法为该问题一个已有的竞争分析结论提供了更加简洁明了的替代性证明. 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.
作者 陶继平 席裕庚
机构地区 上海交通大学自动化系
出处 《系统科学与数学》 CSCD 北大核心 2009年第10期1381-1389,共9页 Journal of Systems Science and Mathematical Sciences
基金 国家自然科学基金(60674041) 高等学校博士学科点专项科研基金(20070248004)资助项目
关键词 实例转换 在线调度 竞争分析 单机调度 总加权完工时间 Instance transformation chine scheduling, total weighted completion online algorithm, competitive analysis, single matime.
分类号 O223 [理学—运筹学与控制论] TP391 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献18

  • 1赵传立 唐恒水.排序引论[M].北京：科学出版社,2002..
  • 2Rachamadugu R and Morton T. Myopic heuristics for the single machine weighted tardiness problem. Carnegie Mellon University, Pittsburgh, 1982.
  • 3Baker K. Sequencing rules and due-date assignments in a job shop. Management Science, 1984, 30(9): 1093-1104.
  • 4Singer M and Pinedo M. A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops. Institute of Industrial Engineers Transactions, 1998, 30(2): 109-118.
  • 5Raman N and Talbot F. The job shop tardiness problem: A decomposition approach. European Journal of Operational Research, 1993, 69(2): 187-199.
  • 6Pinedo M and Singer M. A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. Naval Research Logistics, 1999, 46(1): 1-17.
  • 7Kreipl S. A large step random walk for minimizing total weighted tardiness in a job shop. Journal of Scheduling, 2000, 3(3): 125-138.
  • 8Vails V, Angeles Perez M and Sacramento Quintanilla M. A tabu search approach to machine scheduling. European Journal of Operational Research, 1998, 106(2 3): 277-300.
  • 9Borodin A and El Yaniv R. Online Computation and Competitive Analysis. New York: Cambridge University Press, 1998.
  • 10Fiat A and Woeginger G J. Competitive analysis of algorithms. Lecture Notes in Computer Science, 1998, 1442:1-12.

共引文献1

同被引文献20

  • 1Chowdhury N M M K,BoutabaR.A survey of network virtualization[J].Computer Networks,2010,54 (5):862-876.
  • 2Fischer A,Botero J F,Beck M T,et al.Virtual Network Embedding:A Survey[J].IEEE Communications Surveys and Tutorials,2013,15(4):1888-1906.
  • 3Yu M,Yi Y,Rexford J,et al.Rethinking virtual network embedding:Substrate Support for path splitting and migration[J].ACM SIGCOMM on Computer Communication Review,2008,38(2):17-29.
  • 4Andersen D.Theoretical approaches to node assignment[EB/OL].http://www.cs.cmu.edu/～ dga/papers/andersen-assign.ps,2002.
  • 5Zhu Y,Ammar M.Algorithms for assigning substrate network resources to virtual network components[C]// IEEE International Conference on Computer Communications (INFOCOM).Spain,2006:1-12.
  • 6Lu J,Turner J.Efficient mapping of virtual networks onto a shared substrate[R].Louis:Washington University Washington University,2006.
  • 7Ricci R,Alffld C,Lepreau J.A Solver for the Network Testbed Mapping Problem[J].ACM SIGCOMM Computer Communications Review,2003,33 (2):65-81.
  • 8Mosharaf Kablr Chowdhury N M,Muntasir R R,Raouf B.ViNEYard:Virtual network embedding algorithms with coordinated node and link mapping[J].IEEE/ACM Transactions on Networking,2012,20 (1):206-219.
  • 9Jens L,Holger K.A virtual network mapping algorithm based on subgraph isomorphism detection[C]// Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures.Spain,2009:81-88.
  • 10Cheng X,Su S,Zhang Z B.Virtual Network Embedding Through Topology-Aware Node Ranking[J].ACM SIGCOMM Computer Communication Review,2011,41 (2):39-47.

引证文献3

二级引证文献17

系统科学与数学
2009年 第10期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部