Task Scheduling Genetic Algorithm-based Distributed Systems

Genetic algorithm(GA) is a new parallel optimized algorithm which can be used to solve many kinds of NP-hard problems. Some researchers have used GA on scheduling problems and this algorithm is turned out to be better than heuristic algorithm. In this paper we put forward an algorithm to solve task scheduling with general genetic algorithm.1. First we design math model for the task distribution and put forward a new coding scheme named "one dimension decimal separated coding". Each chromosome is composed of left string and right string. The left describes the distribution of task and the right describe the execution sequence of task. The left and right execute differently because the difference of task scheduling which can extend the search of optimized answer to the whole space. Besides the more optimized chromosome directly enter the next generation can accelerate the process of convergence.2. Second we design math model for the algorithm we propose and proved that it can reach optimized answer with standard generic algorithm and general generic algorithm.3. Third we build a simulated system LD with VC++ simulating local task scheduling. The simulated results show that our algorithm outperforms the algorithm using twodimensions coding and can produce much better results. Besides, 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.