Scheduling Problem With Genetic Algorithm-based Distributed System Tasks

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.