A novel intelligent method for task scheduling in multiprocessor systems using genetic algorithm

In the multiprocessor systems, scheduling is a major issue in their operation, which is also an important problem in other area such as manufacturing, process control, economics, operation research and, etc. An efficient scheduling onto the processes that minimizes the entire run time and also average of response time is vital for achieving a high performance. Solving this problem is very hard and many attempts have been made to solve the problem, using classical algorithms and intelligent methods. In fact in all researches including intelligent methods, the classical algorithm is the basic part of the solution. Even in intelligent methods, which genetic algorithm has been used, when a final chromosome is produced after some generation, a classical algorithm is used to produce an optimal scheduling based on this chromosome. In this paper a novel intelligent solution has been proposed based on genetic algorithm and chromosome background tree without using any classical algorithm. In this method the genetic algorithm presents the optimal scheduling, directly from the produced chromosome in final generation. The time of transferring data between processes is considered, and also the method not only minimizes the entire run time, but also minimizes the average of the response time of all processes. (C) 2006 The Franklin Institute. Published by Elsevier Ltd. All rights reserved.