Exploring the Potential of a Genetic Algorithm on a Real-World Complex Scheduling Problem

Genetic algorithms for NP-complete problems are widespread since it is easy to obtain a solution to the problem. However, its optimality gives the real issue and is not guaranteed to be achievable. In our research, we address a special subproblem of scheduling problems, the final exam scheduling, in which special requirements restrict the state space, which often contradicts each other. The task's difficulty is the massive size of the state space. Genetic algorithm-based solutions were considered since a MILP solver could not find a solution in a reasonable time. A model was built to solve this problem using the genetic algorithm. Most of the possibilities were seen in the different mutation procedures, so we investigated them in more detail. A question for genetic algorithms is what parameters and probabilities to run the model with since the more freedom we give to the run, the larger the runtime. Finding the threshold between the two is essential. Therefore, our experiments measured sizeable real data sets to find the optimal values for this complex problem. The resulting algorithm can significantly facilitate the lengthy manual scheduling processes carried out so far in our university.