A scheduling method on parallel computation models with limited number of processors using genetic algorithms

In parallel processing systems, a compiler partitions a loaded program into tasks, allocates the tasks on multiple processors and schedules the tasks on each processor. In this paper we suggest a Genetic Algorithm based scheduling method to find an optimal allocation and sequence of tasks on each processor. The suggested method uses a chromosome which consists of task sequence and binary string that represent the number and order of tasks on each processor respectively. Two correction algorithms are used to maintain precedency constraints of the tasks in the chromosome. This scheduling method determines the optimal number of processors within limited numbers, and then finds the optimal schedule for each processor. A result from computational experiment of the suggested method is given.