Task Scheduling Problem In Distributed Systems And Genetic Algorithms Applied Research

The distributed system recently received much attention as one of the hot topics in the research of Computer Science. The problem of task scheduling plays a key role in enhancing the parallel capability of system and keeping the balance of load. Task scheduling aims at scheduling a set of partially ordered computational tasks onto a multiprocessor system by a given strategy in order to obtain a better system performance. Because it can' t finish in polynomial time, the scheduling problem is known to be NP-hard.The genetic algorithm, which has received more attentions in solving the NP-hard problem, can make an efficient search in optimized problem for a better solution. Due to the advantage which other method can' t provide, in solving the large space, non-linear, global optimization and other complex problems, this algorithm has got amazing application in task scheduling and combinatorial optimization. At the same time, the genetic theoretical researches have made great development.This paper proposed a new genetic algorithm called quasi-genetic algorithm (QGA) to improve the efficiency of search and avoid precocity. By the makov modeling and the analysis for QGA, we drew the conclusion that the quasi-genetic algorithm has the global convergence.In order to validate the advantage of the quasi-genetic algorithm, we applied this algorithm in solving the task-scheduling problem in the distributed system. The simulation result showed that this algorithm has more obvious improvements than classical genetic algorithms in the efficiency of search and the best possible solutions.