Genetic Algorithm for Solving 3 Dimensional Time Table Problem Based on Traveling Salesman Problem (TSP) Method

Abstract

Scheduling problems are problems that are often faced by educational institutions, especially at the university level. This is because there are several obstacles in the preparation of the schedule, namely first, there should be no duplication of space, day, and hour. Second, there should be no duplication of lecturers on the same day and time, even though in different rooms and in different subjects. Third, there should be no duplication of group classes (study groups). Therefore, the purpose of this study is to obtain a genetic algorithm as a solution in overcoming the three constraints of preparing the schedule by using the Traveling Salesman Problem (TSP) method in the crossover process. To make it easier to organize the schedule, a 3-dimensional matrix is used with the x-axis representing (space, day, hour), the y-axis representing (courses, lecturers, credits) and the z-axis representing (classes). This study simulates the scheduling of 20 courses, 50 credits, 8 lecturers, and 19 classes. Chromosomes in this study are permutations of integers 1-20. Each gene in a chromosome represents a course package. From the scheduling results, the fitness function is 0.96 for 48 schedule slots (2 rooms x 3 days x 8 hours). For schedule slots greater than 50 (3 rooms x 3 days x 8 hours, 2 rooms x 4 days x 8 hours, and 2 rooms x 3 days x 9 hours), this algorithm is successful in getting fitness function 1. ©2018 JNSMR UIN Walisongo. All rights reserved.