Day 19: Scheduling with DNA: Using GAs for Class and Work Timetables
Scheduling is a classic example of a constraint satisfaction problem that often becomes too complex for brute-force or greedy solutions. Whether you’re designing class timetables for a university or shift schedules for employees, the number of constraints quickly increases, making traditional methods inefficient. Genetic Algorithms provide a flexible and powerful approach to finding feasible and optimized schedules by evolving solutions that balance multiple constraints over time.
In a scheduling problem, the chromosome represents a potential timetable. Each gene can represent a time-slot assignment for a course, instructor, room, or shift. Unlike simple optimization problems, scheduling must respect both hard constraints (such as no double-booking of rooms or overlapping classes for a teacher) and soft constraints (such as preferring certain time blocks).