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

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