H.M. Naimi, H.S. Shahhoseini, and M. Naderi (Iran)
: Task graph scheduling, Genetic algorithm, Initial population, Multiprocessing.
Task graph scheduling is a complex optimization problem, and different approaches have been used to solve it. It has been shown that most forms of the problem are NP-Hard. The genetic algorithm has been widely used for solving the task graph scheduling problem. The uniform distribution of the initial population has a key role in the performance of this approach. With non uniform distributed initial population, the GA may search only a part of the domain and some other parts remain unexplored, or in a long time the mutations may produce the chromosome in the lost area of the search space. Unfortunately, the initial population in almost all of the previous proposed genetic algorithms for task graph scheduling has a non-uniform distribution in the search domain. In this paper the domain of the problem is analyzed and an exact algorithm for constructing a uniformly distributed initial population is proposed for graph with tree topology. It is called Uniformly Distributed Sampling, UDS.
Important Links:
Go Back
