case-studies/chore-scheduler
One scheduling problem, solved six ways and cross-checked
- type
- Personal project, Aug 2026
- size
- About 2,000 lines of Python across optimizer, scheduler and orchestration
- stack
- Python, NumPy, SciPy (milp/HiGHS, linear_sum_assignment, sparse), PyYAML
- code
- github.com/Subhash-269/chore-scheduler
Five roommates, four chores on different rhythms: dishes daily, sweeping every 3 days, the stove every 10 days, and mopping on every second sweep day. The hard rules: one chore per person per day, nobody works on a day off, and each chore happens exactly once per window. On top of that sit competing fairness goals (total workload, each chore type, rest between tasks), and the schedule should continue smoothly from last month instead of resetting.
Hard rules plus several competing fairness goals plus state that carries across runs: no single algorithm is obviously right, which made it a good testbed for comparing them.
| solver | how it works here | why it's in the mix |
|---|---|---|
| MILP | Constraint matrix built by hand as a scipy.sparse matrix, solved with HiGHS. Variables decide who does each slot and which day a flexible chore fires. | The only one of the six with an optimality guarantee. |
| Greedy | One forward pass, ranking people by most rested, then fewest of this chore, then fewest tasks overall. | Fast baseline, and the starting point for the three search methods. |
| Simulated annealing | Swap moves with validity checks; temperature decays from 5.0 to near zero over 8,000 iterations; returns the best schedule seen. | Escapes local optima the greedy pass gets stuck in. |
| Tabu search | Same moves and scoring as annealing, so only the acceptance rule differs. Tenure of 15 iterations, with an aspiration rule for record-beating moves. | A controlled comparison against annealing. |
| Genetic algorithm | Population of 30 over 150 generations: uniform crossover with conflict repair, tournament selection of 4, mutation, and elitism of 2. | Explores many schedules at once; elitism means the best never regresses. |
| Daily Hungarian | Each day becomes a task-by-person cost matrix solved as an exact bipartite matching, modeling the mop-after-sweep link explicitly. | Better joint picks on busy days than one-at-a-time choices. |
- aTwo phases instead of one blended objective. The MILP first minimizes how many soft rules have to bend, locks that minimum in, then optimizes fairness among the schedules that achieve it. That avoids weighting rest against fairness on mismatched scales.
- bFix rest without trading away correctness. A beam-search repair layer (width 6, patience 10) runs on every solver's output and only accepts changes that fix rest gaps without making correctness or fairness worse.
- cRank, don't average. The winner is chosen lexicographically: structural violations first, then rest violations, then rest balance, then fairness per chore, then overall fairness. The ranking is a recommendation; any of the six can be picked.
- dNever trust the solver's own word. Every winning schedule is re-validated from scratch: frequency windows, cadence, the mop-after-sweep placement, and days off.
A state file carries three things between runs: rest still owed, where each chore is in its cycle, and cumulative fairness counts, so fairness is judged across the whole history. Rest owed is a soft constraint, so it can never make a schedule impossible. If the MILP does turn infeasible on a continuation run, a diagnostic re-solves with each carry-over isolated and reports which one caused it.
Mobile UI mockups from the repo's mobile-app branch. iOS and Android release planned.
