An efficient method for the multiprocessor scheduling problem using a genetic algorithm

Generally the Multiprocessor Scheduling (MPS) problem is difficult to solve because of the precedence of the tasks, and it takes a lot of time to obtain the optimal solution. Though a Genetic Algorithm (GA) does not guarantee the optimal solution, it is practical and effective for solving the MPS problem in a reasonable time. The algorithm developed in this research consists of an improved GA and CP/MISF (Critical Path/Most Immediate Successors First). An efficient genetic operator is derived to make the GA more efficient. It runs a parallel CP/MISF with GA to complement the faults of GA. The solution by the developed algorithm is compared with that of CP/MISF, and the better is taken as a final solution. As a result of comparative analysis using numerical examples, although this algorithm does not guarantee the optimal solution, it can obtain an approximate solution that is much closer to the optimal solution than existing GA’s. [In Korean.]