A Hybrid Genetic Algorithm for Highly Constrained Timetabling Problems

Abstract

In this paper, we present a powerful hybrid genetic algorithm based around a heuristic timetabling framework. This combines a direct representation of the timetable with heuristic crossover operators to ensure that the most fundamental constraints are never violated. We explain how the population is seeded so as to produce a solution which cannot be outperformed by the heuristic method alone. We also see how the algorithm is guaranteed to always produce a feasible solution by hard coding constraints which must not be broken. Hybrid crossover operators are used, which propagate the most desirable features of the timetable to produce good quality solutions, even for large and highly constrained problems. Finally, we present the results from applying the algorithm to a particularly difficult problem, and demonstrate the variety of possible timetables that can be generated, depending upon the requirements of the user. 1 INTRODUCTION Recently, there has been a lot of attention paid to the...

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 117 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.