有中断时间代价的一致并行机抢先调度问题  

Preemptive Scheduling Problem with Interrupted Time Cost on Identical Parallel Machines

作　　者：孙广中[1] 陈国良[1] 许胤龙[1] 顾钧[2] 

机构地区：[1]国家高性能计算中心(合肥) [2]香港科技大学计算机科学系

出　　处：《软件学报》2002年第8期1606-1611,共6页Journal of Software

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

摘　　要：提出了一种具有中断时间代价的抢先调度问题(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.

关 键 词：调度问题 组合优化 时间代价 并行计算机 NP问题 

分 类 号：O224[理学—运筹学与控制论] TP301.6[理学—数学]