Preemptive Scheduling Problem with Interrupted Time Cost on Identical Parallel Machines
有中断时间代价的一致并行机抢先调度问题

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.