%0 Journal Article
%T 有中断时间代价的一致并行机抢先调度问题
%A 孙广中
%A 许胤龙
%A 陈国良
%A 顾钧
%J -
%D 2002
%X 提出了一种具有中断时间代价的抢先调度问题(P|ptmn(δ)|Cmax):在抢先调度中,一个任务发生一次中断,其总的执行时间会增加一个δ.该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景.证明了这是一个NP-hard问题,给出了一个时间复杂度为O(nlogn+m)的脱线近似算法LPT-Wrap,其近似比小于等于1.40825,并分析了P|ptmn(δ)|Cmax的在线特性,给出一个线性时间复杂度的在线近似算法,其竞争比为2
%K 调度问题 抢先允许 组合优化 时间代价 NP难 近似算法 近似比
%U http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?file_no=20020837&flag=1