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