%0 Journal Article
%T 独立多处理机任务静态调度问题的近似算法
%A 黄金贵？
%A 李荣珩？
%J 软件学报
%P 3211-3219
%D 2010
%X 研究独立多处理机任务静态调度问题pm|fix|cmax,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行.该问题应用广泛但早已证明为np难问题,而且也不存在常数近似算法.分析了问题pm|fix|cmax和其中所有任务都是单位处理机时间的特殊情形pm|fix,p=1|cmax的调度,并利用实例划分(splitscheduling,简称ss)、首次满足优先(firstfit,简称ff)和最大宽度优先(largewidefirst,简称lwf)等方法,构造了问题pm|fix,p=1|cmax的√2m+1近似算法和问题pm|fix|cmax的2√m近似算法,优于目前已有文献的最好结果.
%K 多处理机任务调度
%K 近似算法
%K 近似比
%K np难问题
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=3764&flag=1