【作者】 马伟明；

【导师】 王占杰；

【作者基本信息】 大连理工大学 ， 计算机应用技术， 2008， 硕士

【摘要】 任务调度是分布式计算系统研究的核心内容之一。如何合理的将作业分配给不同的资源,以使整个系统达到最佳的性能,这就是任务调度要解决的问题。由于分布式计算系统的异构性和动态性,以及运行于系统之中的应用程序对于资源的不同需求,使得任务调度变得极其复杂,不好的任务分配策略,将会增加任务的执行时间、降低整个系统的吞吐量。本论文首先介绍了分布式系统的概况,分析了分布式环境下任务调度的问题,并且设计了分布式计算任务调度系统中针对机器资源特性的收集模块,针对任务调度的NP完全问题,遗传算法具有很好的处理能力,但是传统的遗传算法有着过早收敛等缺陷,本文针对传统遗传算法的缺点,结合遗传算法操作过程中对各项参数的要求提出了一种对分布式异构计算系统进行任务分配与调度的改进的遗传算法,根据分布式计算系统各服务节点的计算能力、负载及网络状态进行动态调度,从而能够向用户提供最优性能,提高任务完成的效率。本论文的改进遗传算法,在传统遗传算法的基础上,针对分布式计算任务调度的动态特性,首先对任务分配调度问题做出定义,然后提出了新的编码机制和适应度函数,根据新的编码机制,重新设计了选择算子、交叉算子和变异算子。最后给出算法的仿真实验结果分析与结论等。任务调度问题是一个典型的NP问题,将遗传算法应用于任务调度中,利用遗传算法所具有的并行性和全局解空间搜索的特点,可以有效地缩短任务的完成时间,提高分布式系统资源的使用效率。更多还原

【Abstract】 Task Scheduling is one core of the Distributed Computing System Research. In order to make the system have the best performance, it imports to distribute the reasonable resource to execute the task, this is the problem which the task scheduling will solve. The Task Scheduling is very complex, because the Heterogeneity and dynamic of the Grid System and the different need of the resources of the application program. Bad Task Scheduling will increase the Running time and reduce the throughput of the whole Distributed System.In this paper it introduces the current development state of the Distributed Computing System first, then it analyzes the basic functions of the Task Scheduling and designs the resource collection model in the System. Genetic Algorithm has good performance when it is used to solve the NP Complete Problem of the Task Scheduling, but the traditional Genetic Algorithms have precocious defect. This paper provides an improved Genetic Algorithm according the defect of the traditional Genetic Algorithm. It can provide the user the best performance and increase the efficiency of the task to schedule dynamically according the computing capacity load and network state of the node. In this paper, first it defines the Task Scheduling Problem, then re-designs the selection, crossover and mutation operator according the dynamic characteristic of the Distributed Computing Task Scheduling System in the basis of the basic Genetic Algorithm. At last, it provides the simulation results and the conclusions.The Task Scheduling Problem is NP-Complete Problem,it can shorten the complete time and improve the efficiency of the Distributed System with the characteristics of parallelism and global solution space of the Genetic Algorithm when using the Genetic Algorithm to solve the Task Scheduling Problem.更多还原