%0 Journal Article
%T Preemptive Scheduling Problem with Interrupted Time Cost on Identical Parallel Machines<br>有中断时间代价的一致并行机抢先调度问题
%A SUN Guang-zhong
%A CHEN Guo-liang
%A XU Yin-long
%A GU Jun
%A <br>孙广中
%A 陈国良
%A 许胤龙
%A 顾钧
%J 软件学报
%D 2002
%I 
%X 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.
%K scheduling problem
%K preemption
%K combinatorial optimization
%K time cost
%K NP-hard
%K approximation algorithm
%K approximation ratio<br>调度问题
%K 抢先允许
%K 组合优化
%K 时间代价
%K NP难
%K 近似算法
%K 近似比
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=035D08A79DA9DCF3&yid=C3ACC247184A22C1&vid=FC0714F8D2EB605D&iid=5D311CA918CA9A03&sid=C20D616EFC5754AE&eid=371466E036DA0FD9&journal_id=1000-9825&journal_name=软件学报&referenced_num=1&reference_num=11