%0 Journal Article
%T Approximation Algorithm for Scheduling Independent Multiprocessor Jobs<br>独立多处理机任务静态调度问题的近似算法
%A HUANG Jin-Gui
%A LI Rong-Heng
%A <br>黄金贵
%A 李荣珩
%J 软件学报
%D 2010
%I 
%X 研究独立多处理机任务静态调度问题Pm|fix|Cmax,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行.该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法.分析了问题Pm|fix|Cmax和其中所有任务都是单位处理机时间的特殊情形Pm|fix,p=1|Cmax的调度,并利用实例划分(split scheduling,简称SS)、首次满足优先(first fit,简称FF)和最大宽度优先(large wide first,简称LWF)等方法,构造了问题Pm|fix,p=1|Cmax的√2m +1近似算法和问题Pm|fix|Cmax的2√m 近似算法,优于目前已有文献的最好结果.
%K multiprocessor job scheduling
%K approximation algorithm
%K approximation ratio
%K NP-hard problem<br>多处理机任务调度
%K 近似算法
%K 近似比
%K NP难问题
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=B356CD4BF408EB44D432A4CB1F7C28AE&yid=140ECF96957D60B2&vid=659D3B06EBF534A7&iid=59906B3B2830C2C5&sid=6C1B0E5BF8C72A6A&eid=06AED11AFE7C1F17&journal_id=1000-9825&journal_name=软件学报&referenced_num=0&reference_num=27