Constraint SatisfactionAI SearchSchedulingGenetic AlgorithmsAND/OR TreesOptimizationPenalty Functions

AI Scheduling for City Soccer Field Allocation

Python scheduling system for city-wide soccer games/practices under dense constraints and weighted preferences using a hybrid Genetic Algorithm + AND/OR-tree search that minimizes penalty to reach feasible, high-quality schedules.

Overview

AI scheduling system that assigns soccer games and practices across limited weekly field time slots. The problem includes capacity limits, incompatibilities, pre-assignments, multi-day linked slots, and division constraints, plus soft preferences like requested times, minimum slot usage, and paired-event requirements. The solver treats constraint violations as penalty and searches for schedules that minimize total cost (targeting 0 for feasibility) while improving preference satisfaction.

Build a practical optimizer for a real-world scheduling CSP/optimization problem, combining evolutionary exploration with symbolic search to escape local minima and drive penalty toward feasible solutions.

Your Role

What I Built

Team-built parser and internal data structures to load structured scheduling inputs
Hybrid solver combining Genetic Algorithm search with AND/OR-tree expansion to refine solutions
Penalty function encoding hard constraints (as penalty terms) and weighted soft constraints
Search operators to mutate/repair schedules while reducing penalty and improving preference fit

What I Owned End-to-End

Soft constraint modeling + weighting strategy (preference satisfaction, minimum slot use, paired events, etc.)
GA design (representation, mutation, selection pressure) and AND/OR-tree integration for schedule refinement
Scoring/optimization logic: penalty-driven objective and convergence behavior
Most of the solver logic end-to-end (everything except the parser and the hard-constraint definitions)

Technical Highlights

Architecture Decisions

Schedule represented as an assignment over games/practices → time slots across a weekly horizon
Objective function built around penalty minimization (hard constraints drive feasibility; soft constraints improve quality)
Hybrid pipeline: GA generates candidate schedules; AND/OR-tree search expands/repairs candidates to reduce penalty

Algorithms / Protocols / Constraints

Genetic Algorithm operating over full schedule assignments
AND/OR-tree search used to refine partial/poor assignments into lower-penalty schedules
Penalty-based evaluation combining capacity, incompatibility, preassignment, linked-slot constraints + soft preferences

Failure Handling

Penalty-driven validity: infeasible schedules receive large costs and are pushed out by selection pressure
Repair-oriented mutations to recover from high-penalty local minima during GA evolution

Optimization Strategies

Weighted penalties to prioritize feasibility first, then preference optimization
Hybrid search to balance global exploration (GA) with structured refinement (AND/OR-tree)

Tech Stack

Python

Results / Learnings

What Worked

Generated schedules that minimize constraint penalties toward feasible solutions while optimizing preference quality
Handled dense real-world constraints (capacity, incompatibility, pre-assignments, multi-day links, division rules)
Demonstrated that combining GA exploration with symbolic refinement improves convergence vs GA-only search

What I Learned

Penalty design and weighting dominate solver behavior; small weight changes can reshape convergence
Pure evolutionary search can stall under dense constraints without a structured repair/refinement mechanism
Hybridizing search methods is often worth the complexity when feasibility is hard to reach

Tradeoffs Considered

Penalty-based feasibility is flexible but requires careful tuning to avoid ‘almost-feasible’ plateaus
Hybrid GA + AND/OR increases implementation complexity and runtime cost
Optimization targets high-quality feasible schedules rather than provable global optimality

← View All Projects

← Genetic Algorithm Hyperparameter Tuning Framework Raspberry Pi Bare-Metal Systems Programming (AArch64) →