独立多处理机任务静态调度问题的近似算法

研究独立多处理机任务静态调度问题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近似算法,优于目前已有文献的最好结果.