Solving multi-processor task scheduling problem using a combinatorial evolutionary algorithm

Scheduling problem in multiprocessor, parallel and distributed systems are placed in NP-hard problems arena. These scheduling problems are employed in different important applications such as information processing, whether forecasting, image processing, database systems, process control, economics, operation research, and other areas. The data for these applications should be disseminated on different processors. Consequently efficient communication and well-organized assignments of jobs to processors are our concerns in solving multiprocessor task scheduling problems. This paper presents a new scheduling method which uses a local search technique. This local search algorithm is a combinatorial algorithm which combines Shuffled Frog Leaping (SFL), and Civilization and Society algorithms (CSA). This local search technique is a general algorithm which has been used to solve other problems such as the TSP before this. In addition to this combinatorial local search algorithm, a heuristic method is used to increase convergence speed of the genetic algorithm. Simulation results show that the proposed combinatorial method works better than other well known scheduling approaches