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

研究多处理机任务调度模型PmfixCmax，即在m个处理机系统中调度n个多处理机任务，每个任务指派到所需一组处理机上不可剥夺地执行。该问题应用广泛但早已证明为NP难问题，而且也不存在常数近似算法。在E.Bampis等人提出的Split-Round技术基础上，提出了该问题的一个改进的多项式时间近似算法，并从理论上证明了该算法在最坏情况下的近似比为2(2m)-2，优于E.Bampis等人给出的3m-2的结果。