Schedule Assistant

A Python package for generating and optimizing academic course schedules using genetic algorithms. This system handles various constraints such as faculty availability, room capacity, and course credit requirements.

Features

• Flexible data model for courses, faculty, rooms, and time slots
• Support for both 7W1/7W2 and full-term scheduling
• Hard constraint enforcement (room conflicts, faculty scheduling, etc.)
• Soft constraint optimization (faculty preferences, room utilization)
• Genetic algorithm-based optimization
• Benchmarking tools for performance analysis
• Schedule export functionality
• Random data generation for testing

Structure

• data_model.py - Core data structures
• constraints.py - Constraint checking functions
• genetic_algorithm.py - Schedule optimization engine
• input_handler.py - Data loading utilities
• utils.py - Benchmarking and testing utilities

Poster

Constraints

The system enforces several types of constraints to ensure valid and optimized schedules:

Hard Constraints

These are strict rules that must be met:

• No Conflicts: Prevents scheduling the same room or instructor for multiple courses simultaneously.
• Room Capacity: Ensures the assigned room can accommodate the number of enrolled students for each course.
• Credit Hour Requirements: Allocates the appropriate number of time blocks based on course credits (e.g., 4-credit courses require two blocks).
• Term-Specific Scheduling: Enforces rules such as 1-credit courses being scheduled exclusively in the 7W1 term.
• Faculty Availability: Respects and incorporates periods when faculty members are marked as unavailable.

Soft Constraints (Preferences)

These are desirable conditions that the system attempts to optimize:

• Faculty Time Preferences: Aims to schedule courses according to the preferred teaching times of faculty members.
• Efficient Room Utilization: Strives to match room capacity closely with course enrollment to avoid using overly large or small rooms.

Genetic Algorithm

The core of the schedule generation process is a genetic algorithm. This optimization technique mimics the process of natural selection to find high-quality schedules. It works by:

1. Initialization: Creating an initial population of random (often invalid) schedules.
2. Evaluation (Fitness Function): Assessing each schedule based on how well it satisfies the defined hard and soft constraints. Schedules that violate fewer hard constraints and meet more soft constraints are considered "fitter."
3. Selection: Favoring fitter schedules to be "parents" for the next generation.
4. Crossover & Mutation: Combining parts of parent schedules (crossover) and introducing small random changes (mutation) to create new offspring schedules. This explores new possibilities in the solution space.
5. Iteration: Repeating the evaluation, selection, and reproduction steps for a number of generations.

This iterative process allows the algorithm to progressively refine schedules, moving towards solutions that satisfy all hard constraints and optimally address soft constraints. The system is designed to find valid schedules for typical academic scenarios, as noted in the performance section.

Performance

The genetic algorithm typically finds valid schedules within 100 generations for small to medium-sized problems (10-30 courses). Runtime scales with problem complexity, particularly with the number of courses.

Heuristic for determening when to schedule a class based on student preference:

• Observe historical data
• Determine which classes historically have low enrollment and observe their timeslots
• Generate embedding of that historical class if it doesn't exist today or has a different code (to be used as a metric of comparison), and use that embedding for comparison. When deciding to schedule a particular class (depending on what the historical information says) add a check to see whether that class had a historically low enrollment in that timeslot (give some more input on fitness). That way, without direct student input on each class, we can at least approximate if a particular 'type' of class (type meaning if the embeddings are close) should be scheduler earlier or later in the day to try and maximize. Determining the threshold here would be the difficult part.

2 4-credit or 3 4-credit or 1 4-credit 2 2-credit // 2 4-credits 2-credits 2 4 credits and 1 2 credits

Spread courses across curiculum (if any discipline has too many courses in 1-teaching block, because of the classroom contstrains, we work to ship them to other places/other).