An improved genetic algorithm for load balance in multiprocessor systems

The allocating and scheduling of tasks in parallel and distributed systems has been considered to be an NP-Complete problem, which has received much attention. Although plentiful algorithms have been developed to obtain suboptimal solutions, many of them didn´t consider the total execution time and load balancing among processors simultaneously. To solve this problem efficiently, this paper presents an improved genetic algorithm based on the Critical Path Genetic Algorithm (CPGA) with some heuristic principles added to improve the performance. According to the evaluation results, our proposed algorithm could ensure the quality and efficiency of obtained solutions while avoiding the issues of CPGA algorithm, and always outperforms the CPGA algorithm in the respect of load balancing.