论文研究应用团划分方法改进多处理机任务近似调度.pdf

研究多处理机任务调度模型Pm|fix，pj=1|Cmax，即在m个处理机系统中调度n个时间长度都为1的多处理机任务，每个任务指派到所需一组处理机上不可剥夺地执行。这类问题在网络并行计算、多播系统及工程规划等领域都有广泛的应用，但早已被证明为NP难问题，而且也不存在常数近似算法。基于团划分方法构造了该问题的多项式时间近似算法，通过模拟实验进行了验证，和最大宽度优先（LWF）算法相比，该算法花费时间较长，近似比性能要好。