The Teacher Placement using K-Means Clustering and Genetic Algorithm
Keywords:Clustering, K-means, genetic, crossover, mutation
The problem of teacher placement in a school is a problem faced by Magelang Regency. The success of teacher placement is determined by the minimum total distance between the teacher and the school, with the aim that teacher performance is maintained. In computer science this problem is an NP-hard problem that takes a very long time to achieve optimal results when done with conventional methods. Another approach to solve this problem is to use heuristic algorithms, one of which is by using genetic algorithms. To further improve the performance of genetic algorithms, one way is to narrow the search space. In this study, the problem will be broken down first through a clustering process so that the search space becomes narrower, before being subjected to genetic algorithm processes. This study will cluster the original data, before being subjected to a genetic algorithm to solve the problem of teacher placement. The clustering method used is the K-Means clustering method while the Genetic Algorithm uses the Ordered Crossover (OX) operator and the Partial Shuffle Mutation (PSM) mutation operator. From this study, it was found that by performing K-Means clustering before the optimization process using the Genetic Algorithm turned out to get better results than without using clustering. The total distance without clustering is 11751 km while with clustering it 9259 km. Also the total running time to execute this program turned out to be much shorter (from the order of hours to the order of minutes).