文档介绍：不能在多项式时间内求得最优解,因而被公认为一个完全问题。广优化方面取得了较好的应用。有关的理论研究也随之得到了较快的发展。厂摘要壬务调度问题是指根据一定的调度策略,把一组并行处理的任务按规定的时序个较好的解决方案,即在较短的时间内能找到较好的解。虼诵矶嘌芯糠植际算法——类遗传算法,对于完全问题,近年来兴起的遗传算法珿系统的专家开始关注遗传算法的研究。该算法在解决大空间、非线性、全局寻优等复杂问题时具有传统方法所不具备的独特优势,使在任务调度与组合本文从提高算法搜索效率和避免过早收敛的角度,提出了一种新型的遗传。通过建立类遗传算法的马氏链模型,对其收敛性进行分析,得出了类遗传算法具有全局收敛性的结论。为了验证挠旁叫裕颐怯τ酶盟惴ɡ唇饩鲆旃够合低车娜挝竦度问题。仿真实验结果表明,该算法在搜索效率和搜索较优解方面与经典遗传任务调度,分布式系统作为计算机领域的研究热点之一,近年来受到了广泛的关注。其中的任务调度问题,对发挥系统的并行性能和保持负载平衡具有重大意义。分配到系统的多个处理机节点上,以期获得较好的系统执行性能。由于该问题算法相比都有明显的改善。关键词:遗传算法,马尔可夫链,收敛性是一/\,、
瑆琲甌.,—.瑆—,,.猤—.,,瑃瓸篏痶
言引间内找到问题的最优解。针对不同的分布式系统,已提出了许多启发式的算法本文从提高遗传算法搜索效率和避免过早收敛的角度出发,设计了一种类避免了过早收敛现象的发生。由于跟传统遗传算法的杂交算子选取两个父本不况;第二章介绍了遗传算法的基本机理及其相关的理论;第三章是本文的重点,首先描述了本文提出的类遗传算法,定义其采用的杂交算子和变异算子;随后介绍了马尔可夫链的相关内容,包括其基本概念和各种不同马氏链的基本性质。近年来,随着分布式系统的应用日趋广泛,对其任务调度和管理的研究也越来越深入。任务调度问题已经被证明是一个完全问题,不可能在多项式时用于解决该问题,但是这些算法有些复杂性太高难以实现,有些实现起来太费时。所以有必要寻求更好的算法来解决这个问题。遗传算法作为一种新的全局搜索算法,越来越多地受到国内外学者的关注。由于遗传算法在解决大空间、非线性、全局寻优等复杂问题时具有传统方法所不具备的优越性,目前已在组合优化、机器学****优化控制、图像处理等领域得到了广泛的应用。采用遗传算法解决任务分配问题还是一个较新的领域,本文就是在这一领域所做的一些探讨和尝试。遗传算法。该算法的主要改进是杂交算子的设计。算法选取三个父本进行轮转杂交,使遗传算法每一代的搜索范围扩大,从而提高了算法的搜索效率,同时同,所以将本算法命名为类遗传算法。通过建立类遗传算法的马氏链模型,对其收敛性进行分析,得出了类遗传算法具有全局收敛性的结论。本文内容安排如下:第一章概述了分布式系统及其任务调度问题的研究情再通过建立类遗传算法的马氏链模型,分析了其全局收敛性,得出了其能收敛到全局最优解的结论。最后一章叙述了用类遗传算法来解决任务分配问题的具体实现。仿真试验将该算法用于解决异构分布式系统的任务调度问题,通过与其它遗传算法相比较,证明了类遗传算法有较好的性能。
篁三童坌童垄墨丝丝苎堡叁堡堡旦璧——第一章分布式系统及其任务调度问题分布式系统概述分布式系统是二十世纪九十年代以来计算机领域的研究热点之一。作为网络一体化和并行处理分布化的产物,分布式系统解决了系统透明性及处理机动态分配等问题,表现出比计算机网络更强的生命力和更大的吸引力。一个被大家公认的分布式系统的定义是:“分布式系统是一些独立的计算采用不同的操作系统。分布式系统按照硬件结构的不同可分为四类:总线型多处理机、交换型多处理机、总线型多计算机、交换型多计算机。分类图如下:分布式系统与集中式系统相比,有其自身的优点。分布式系统有较高的性能价格比,它还可能具有任何价位上的大型机都无法达到的性能。随着计算机的发展,其应用领域越来越广,其中许多应用本身就是分布式的。与集中式系控制核反应堆或飞机,使用分布式系统来达到高可靠性是最主要的考虑因素。机的集合。但在用户看来却是一台计算机⋯。”在硬件结构上,尽管所有的分布式系统都是由多个钩傻模ǹ梢杂不同的方法将硬件组织起来,形成不同的系统,并且不同类别的计算机系统应统相比,分布式系统能更好地处理分布式应用。分布式系统的另一个优点是它有更高的可靠性,通过将任务交由多个机器共同承担,单个芯片的故障只会让一台机器停下来,而其他的机器将继续工作。对于一些关键性应用来说,例如图分布式系统分类图
分布式系统中的任务调度问题并且在负载增加时分布式系统较集中系统更容易扩展。中,与之对应的是任务调度。它是并行处理的关键。其处理过程要求根据一定分布式操作系统中的任务调度问题对发挥系统的并行性能和保持负载平举过一个假设具有多层并发度计算需求的计算实例”>扑