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

有中断时间代价的一致并行机抢先调度问题 被引量：1

Preemptive Scheduling Problem with Interrupted Time Cost on Identical Parallel Machines
下载PDF
导出
摘要 提出了一种具有中断时间代价的抢先调度问题(P|ptmn(d)|Cmax):在抢先调度中,一个任务发生一次中断,其总的执行时间会增加一个d.该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景.证明了这是一个NP-hard问题,给出了一个时间复杂度为O(nlogn+m)的脱线近似算法LPT-Wrap,其近似比小于等于1.40825,并分析了P|ptmn(d)|Cmax的在线特性,给出一个线性时间复杂度的在线近似算法,其竞争比为2. A preemptive scheduling problem P|ptmn(d)|Cmax is proposed in this paper, in which an additional time cost is needed if a job is interrupted once. The problem has wide applications such as job allocation in projects, distributed computing and communication in networks. It is proved that P|ptmn(d)|Cmax is an NP-hard problem. An off-line approximation algorithm LPT-Wrap with time complexity of O(nlogn+m) and a performance ratio no more than 1.408 25 is presented. The on-line property of P|ptmn(d)|Cmax is also studied and an on-line algorithm with linearity time complexity and a competitive ratio of 2 is proposed.
作者 孙广中 陈国良 许胤龙 顾钧
机构地区 国家高性能计算中心(合肥) 香港科技大学计算机科学系
出处 《软件学报》 EI CSCD 北大核心 2002年第8期1606-1611,共6页 Journal of Software
基金 ~~ 国家重点基础研究发展规划973资助项目(G1998030403)
关键词 调度问题 组合优化 时间代价 并行计算机 NP问题 scheduling problem preemption combinatorial optimization time cost NP-hard approximation algorithm approximation ratio
分类号 O224 [理学—运筹学与控制论] TP301.6 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献11

  • 1[1]Hall, L.A. Approximation algorithms for scheduling. In: Hochbaum, D., ed., Approximation Algorithms for NP-Hard Problems. Boston: PWS, 1996. 1～45.
  • 2[2]Karger, D., Stein, C., Wein, J. Scheduling algorithms. In: Atallah, M.J., ed., Handbook on Algorithms and Theory of Computation. CRC Press, 1998.
  • 3[3]Graham, R.L. Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 1966,45:1563～1581.
  • 4[4]Engels, D.W., Feldman, J., Karger, D.R. Parallel processor schedluing with delay constraints. In: Proceeding of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM Press, 2001. 577～585.
  • 5[5]Pressman, R.S. Software Engineering: a Practitioner's Approach. McGraw-Hill, 1997.
  • 6[6]Attiya, H., Welch, J. Distributed Computing: Fundamentals, Simulations and Advanced Topics. London: McGraw-Hill, 1998.
  • 7[7]Green, P.E. Fiber-Optic Networks. Cambridge, MA: Prentice-Hall, 1992.
  • 8[8]Deng, Xiao-tie, Gu, Nian, Brecht, T., et al. Preemptive scheduling of parallel jobs on multiprocessors. In: Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM Press, 1996. 159～167.
  • 9[9]Goemans, M., Wein, J., Williamson, D.P. A 1.47-approximation algorithm for a preemptive single-machine scheduling problem. Operations Research Letters, 2000,26:149～154.
  • 10[10]Garey, M.R., Johnson, D.S. Computers and Intractability: A Guild to the Theory of NP-Completeness. New York: W.H. Freeman and Company, 1979.

同被引文献5

  • 1L. A. Hall. Approximation algorithms for scheduling. In: D.Hochbaum, ed.. Approximation Algorithms for NP-Hard Problems. Boston: PWS Publishing, 1996. 1-45.
  • 2R. L. Graham. Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 1966, 45 : 1563-1581.
  • 3M. R. Garey, D. S. Johnson. Computers and Intractability: A Guild to the Theory of NP-Completeness. New York: W.H.Freeman and Company, 1979.
  • 4Cormen H. Thomas, Leiserson E. Charles, Rivest L. Ronald,et al. Introduction to Algorithms. 2nd Edition. Cambridge,MA: The MIT Press, 2002.
  • 5Lewis R. Harry, Papadimitriou H. Christos. Elements of the Theory of Computation. 2nd Edition. New Jersey: Prentice-Hall,1998.

引证文献1

二级引证文献2

软件学报
2002年 第8期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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