基于遗传算法的分布式系统任务调度问题研究

【作者】 贺晓丽；

【导师】 许曰滨；

【作者基本信息】 青岛大学 ， 计算机软件与理论， 2003， 硕士

【摘要】 分布式系统作为计算机领域的研究热点之一，近年来受到了广泛的关注。其中的任务调度问题，对发挥系统的并行性能和保持负载平衡具有非常重要的意义。该问题已被证明是一个NPC问题，无法在多项式时间内找到最优解，所以促使人们不懈地研究如何设计调度算法，用有限的代价获得更好的解。现有的启发式算法虽然能够得到满意解，但是计算的时间复杂度较高，当问题规模很大时，求解效率不高。 遗传算法是近年兴起的一种用于解决优化问题的并行寻优算法，已被广泛用于解决各类NP问题。目前已有学者将遗传算法用于调度算法的研究，并用仿真实验说明，在处理调度问题时，遗传算法与启发式算法相比具有较大的优越性。 但这些算法仍然存在一些缺陷。为了克服这些缺陷，针对任务调度问题的特性，本文设计了一个全新的遗传算法。这一算法在编码、选择、杂交、变异方法上都与传统遗传算法明显不同。在编码方法上，设计了十进制分离编码方式，从而杂交和变异也分离同时进行。在选择方法上，采用了广义遗传算法四分之二择优选择的方式。 在本文中，首先用马尔可夫链的有关知识对我们采用的算法进行了数学分析，然后将这一算法应用到任务调度问题上。仿真结果表明，与在这一问题上常采用的二维编码的遗传算法相比，本算法能得到更好的解；与不采用广义遗传算法而代之以精英策略的遗传算法相比，本算法具有更快的收敛速度。所以本算法具有较大的优越性，适合处理大规模的调度问题。更多还原

【Abstract】 The distributed system recently got much attentions as one of the hot topics in the research of Computer Science.The task scheduling algorithm plays a very important role in enhancing this system’s parallel performance and maintaining it’s load equation.The scheduling problem has turned out to be a NPC problem and optimal solutions can not be found in polynomial time.So,many people make great efforts on finding a better algorithm which can produce a better solution within limited cost.Some algorithms which have been thought out can find satisfactory solutions.but incur high time complexity.which tend to exacerbate in more complex environments.The genetic algorithm(GA) is a new parallel optimize algorithm,which can be used to solve many kinds of NP-hard problems.Some researchers have used GA on scheduling problem,and this algorithm is turned out to be better than heuristic algorithms.But all of these algorithms have some faults.In order to overcome these faults,we designed a new GA.This GA is different from statistic GA in coding, select crossover mutation. A decimal separated coding is used so crossover and mutation is separated also. Our select method is selecting two from four instead of elite select.In this paper,first, we use Markov modeling to analysis our GA, than apply this algorithm in task scheduling problem.The simulated results show that our algorithm outperforms the algorithm using two dimensions coding and can produce much better results.Besides this, our algorithm has faster convergence speed than elite select method.The conclusion is that our algorithm is much better than other algorithms and can be used to solve large scheduling problems.更多还原