| 有中断时间代价的一致并行机抢先调度问题 |
| |
| 引用本文： | 孙广中,陈国良,许胤龙,顾钧.有中断时间代价的一致并行机抢先调度问题[J].软件学报,2002,13(8):1606-1611. |
| |
| 作者姓名： | 孙广中 陈国良 许胤龙 顾钧 |
| |
| 作者单位： | 1. 国家高性能计算中心,合肥,安徽,合肥,230027;中国科学技术大学,计算机科学与技术系,安徽,合肥,230027
2. 香港科技大学,计算机科学系,香港 |
| |
| 基金项目： | 国家重点基础研究发展规划973资助项目(G1998030403) |
| |
| 摘 要： | 提出了一种具有中断时间代价的抢先调度问题(P|ptmn(δ)|Cmax):在抢先调度中,一个任务发生一次中断,其总的执行时间会增加一个δ.该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景.证明了这是一个NP-hard问题,给出了一个时间复杂度为O(nlogn+m)的脱线近似算法LPT-Wrap,其近似比小于等于1.40825,并分析了P|ptmn(δ)|Cmax的在线特性,给出一个线性时间复杂度的在线近似算法,其竞争比为2.
|
| 关 键 词： | 调度问题 抢先允许 组合优化 时间代价 NP难 近似算法 近似比 |
| 文章编号： | 1000-9825/2002/13(08)1606-06 |
| 收稿时间： | 2001/4/29 0:00:00 |
| 修稿时间： | 2001年4月29日 |
Preemptive Scheduling Problem with Interrupted Time Cost on Identical Parallel Machines |
| |
| SUN Guang-zhong,CHEN Guo-liang,XU Yin-long and GU Jun.Preemptive Scheduling Problem with Interrupted Time Cost on Identical Parallel Machines[J].Journal of Software,2002,13(8):1606-1611. |
| |
| Authors: | SUN Guang-zhong CHEN Guo-liang XU Yin-long and GU Jun |
| |
| Abstract: | 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. |
| |
| Keywords: | scheduling problem preemption combinatorial optimization time cost NP-hard approximation algorithm approximation ratio |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
