Track: Optimization

Abstract

The University Class Scheduling Problem (UCSP), or the process of building a
class schedule for a university, has been a difficult problem in computer science due to its
combinatorial complexity and multi-objective nature. As a result, several heuristic-based
approaches have been tested, one being the genetic algorithm (GA). The application of GAs
to this problem has presented its own difficulties due to the generation of infeasible solutions.
Thus, this article presents novel methods of decoding random-key genetic representations
such that only feasible solutions are generated. It is then demonstrated empirically that these
modifications still constitute a viable algorithm, and analytically that these changes affect no
additional bias on the otherwise unmodified GA. Going forward, similar, more generalized
methods can be developed and applied to a wider range of problems.