多处理机任务调度及其在网络服务计算中的应用研究

项目名称： 多处理机任务调度及其在网络服务计算中的应用研究

项目编号： No.60872039

项目类型： 面上项目

立项/批准年度： 2009

项目学科： 金属学与金属工艺

项目作者： 黄金贵

作者单位： 湖南师范大学

项目金额： 28万元

中文摘要： 随着网络并行计算技术的发展,多处理机任务调度问题已经成为研究热点之一。本项目研究了一类更复杂的多处理机任务调度问题，该问题一般都是强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）该调度模型在网络服务计算环境中的实例化模型及其调度策略和调度算法的研究。本项目的研究，进一步明确网络服务计算环境中多处理机任务调度结构，并进行近似优化，为网络服务计算系统调度性能研究及其它相关领域研究打下了基础。

中文关键词： 多处理机任务调度;NP难问题;网络服务;近似算法

英文摘要： With the development of the network parallel computing technology, multiprocessor job scheduling problem has become increasingly interesting, which, however, seems not to imply practical algorithms. Mainly the following aspects of this research: (1)With introduced the Normal scheduling, and Group scheduling, we develop a linear time algorithm with the 4/3 approximation ratio for the problem P4|fix|Cmax. It is proved to be the optimal normal scheduling in 4-processor systems.(2) For the problems of the offline version both Pm|fix|Cmax of the scheduling with arbitrary process time jobs and Pm|fix, p=1|Cmax of the scheduling with unit processing time jobs. constructed a (sqrt(2m)+1)-approximation algorithm and 2sqrt(m)-approximation algorithm respectively by using the Split Scheduling, the First Fit and the Large Wide First technique. That is better than the best results in the literature at present. (3) the scheduling model in the network computing environment, service model and its instantiation in the scheduling policy and scheduling algorithm. These researchs will further clarify the multiprocessor task scheduling structure, better performance for practical and feasible approximation algorithm, lay the foundation for the improvement of the network service performance and other related areas.

英文关键词： Multiprocessor job scheduling; NP hard; Network service; Apprixmation Algorithm