中文摘要：

随着网络并行计算技术的发展,多处理机任务调度问题已经成为研究热点之一。本项目研究了一类更复杂的多处理机任务调度问题，该问题一般都是强NP难的，只能寻求其性能较好的近似算法。项目主要进行了如下几方面的研究工作（1）研究了P4|fix|Cmax的规则调度算法，通过引入组调度技术，给出了该问题的一个线性时间的4/3-近似算法，并证明了该算法是4-处理机系统中的最优规则调度算法；（2）一般情况下不同参数条件的较好近似算法的研究。分析了问题Pm|fix|Cmax及其特殊情形Pm|fix, p=1|Cmax的调度，并利用实例划分、首次满足优先和最大宽度优先等方法，构造了问题Pm|fix, p=1|Cmax的(sqrt(2m)＋1)-近似算法和问题Pm|fix|Cmax的2sqrt(m)-近似算法，优于目前已有文献的最好结果；（3）该调度模型在网络服务计算环境中的实例化模型及其调度策略和调度算法的研究。本项目的研究，进一步明确网络服务计算环境中多处理机任务调度结构，并进行近似优化，为网络服务计算系统调度性能研究及其它相关领域研究打下了基础。