Algorithms
Constraint-Based Soccer Scheduling
A Python scheduling prototype that combines backtracking and genetic search to assign recurring soccer games and practices under capacity and placement constraints.
- Constraint Satisfaction
- AI Search
- Scheduling
- Genetic Algorithms
- OR-Tree Search
- Python
Constructing schedules that can evolve
The scheduler assigns recurring games and practices while tracking the capacity left in each time interval.
I combined incremental backtracking with population search, using the same schedule-construction routine to create initial candidates and complete crossover children. The original project name is Gengar.
Time capacity and candidate schedules
Tracking placements and capacity
Soccer games and practices compete for recurring time slots, with different capacity limits and placement restrictions. I built a Python scheduling prototype, Gengar, that combines backtracking construction with a genetic search over candidate schedules.
The input describes events, available slots, incompatible pairings, unwanted times, and preferences. Internally, half-hour intervals make it possible to account for bookings that span multiple slots. Assigning an event reduces the remaining capacity in each interval it occupies; removing it restores that capacity. Games and practices keep separate capacity records.
Building a schedule by branching
Construction starts with a partial schedule and chooses the next unassigned event. Each allowed placement creates a new branch with its own copied state. If a branch runs out of placements, search returns to an earlier choice; otherwise it continues until it finds a complete assignment.
This is an OR-tree search: any one successful branch can supply the result. Cost and randomized ordering guide which children are explored first. The same construction routine creates the initial population and fills gaps in crossover children, reusing placement checks across both parts of the algorithm.
Combining candidate schedules
Crossover starts from the two lowest-cost parents, favors assignments they share, and uses their remaining choices as guidance for constructive completion. Survivor selection keeps low-cost candidates. A mutation routine attempts to move events in proportion to their contribution to the schedule penalty.
The prototype connects these search mechanisms, but its objective remains incomplete: preference and section-difference terms are placeholders, and minimum-fill accounting needs correction. Parser, mutation, and constraint-integration defects also remain unresolved, so the work does not establish a validated final schedule.
A central implementation challenge was keeping event identity and capacity updates consistent across the parser, placement checks, and genetic operators. Copying states simplifies backtracking, at the cost of additional memory and copying during search.
Tools and technologies
- Python
- argparse
- Standard-library collections / copying / random
Python implements the scheduling representation, parser, recursive construction, and genetic operators directly. The command-line interface uses argparse; small scenario files and diagnostic output support investigation of placement behavior.