论文部分内容阅读
多处理机任务调度问题P4｜fix｜Cmax（m≥3）是典型的强NP难问题，由于其在并行环境中的实际意义而受到越来越多的关注．但在一般情形下，寻求该问题的较为理想的近似算法是极其困难的，通常从较少处理机数的系统着手研究．对于m=4的情形，文中研究了P4｜fix｜Cmax的规则调度算法，通过引入组调度技术，给出了该问题的一个线性时间的4／3-近似算法，并证明了该算法是4-处理机系统中的最优规则调度算法．