有中断时间代价的一致并行机抢先调度问题
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家重点基础研究发展规划973资助项目(G1998030403)


Preemptive Scheduling Problem with Interrupted Time Cost on Identical Parallel Machines
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    提出了一种具有中断时间代价的抢先调度问题(P|ptmn(δ)|Cmax):在抢先调度中,一个任务发生一次中断,其总的执行时间会增加一个δ.该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景.证明了这是一个NP-hard问题,给出了一个时间复杂度为O(nlogn+m)的脱线近似算法LPT-Wrap,其近似比小于等于1.40825,并分析了P|ptmn(δ)|Cmax的在线特性,给出一个线性时间复杂度的在线近似算法,其竞争比为2.

    Abstract:

    A preemptive scheduling problem P|ptmn(δ)|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(δ)|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 ofP|ptmn(δ)|Cmax is also studied and an on-line algorithm with linearitu time complexity and a competitive ratio of 2 is proposed.

    参考文献
    相似文献
    引证文献
引用本文

孙广中,陈国良,许胤龙,顾钧.有中断时间代价的一致并行机抢先调度问题.软件学报,2002,13(8):1606-1611

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2001-04-29
  • 最后修改日期:2001-07-12
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号