论文研究单位处理时间的多处理机任务调度近似算法.pdf

研究多处理机任务调度模型Pm|fix，pj=1|Cmax，即在m个处理机系统中调度n个时间长度都为1的多处理机任务，每个任务指派到所需一组处理机上不可剥夺地执行。其更一般的问题是Pm|fix|Cmax，在网络并行计算、多播系统及工程规划等领域都有广泛的应用。该问题早已证明为NP难问题，而且也不存在常数近似算法。基于部分调度和宽度优先原则构造了该问题的一个多项式时间近似算法，并从理论上证明了该算法在最坏情况下的近似比为2m1，优于已有文献中2m的目前最好结果。