# Specification: 038-deterministic-scheduling-solver

## Status

| Field | Value |
|-------|-------|
| **Created** | 2026-02-17 |
| **Current Phase** | PLAN Reviewed - Ready for Implementation |
| **Last Updated** | 2026-02-18 |

## Documents

| Document | Status | Notes |
|----------|--------|-------|
| product-requirements.md | completed | Codex reviewed. 3 blockers resolved, 5 important items fixed, 1 enhancement added. 8 Must Have, 3 Should Have, 2 Could Have features. |
| solution-design.md | completed | All 7 ADRs confirmed. Codex SDD review completed: 5 blockers resolved, 6 important items fixed, 3 enhancements noted. Full architecture: Python subprocess (single-threaded for determinism), shared storage, LLM explanation with chunking, data gatherer extraction, exponential weighting, priority fix, no rate limit, CP-SAT assumption-literal IIS, coverage hard-precedence, analytics instrumentation plan. |
| implementation-plan.md | completed | 10 phases (incl. 7.5 smoke test), ~195 tasks. TDD-structured with parallel work groups. Covers all 8 Must Have + Feature 9 Should Have. Features 10 & 11 explicitly deferred. Codex plan review completed 2026-02-18. |

**Status values**: `pending` | `in_progress` | `completed` | `skipped`

## Decisions Log

| Date | Decision | Rationale |
|------|----------|-----------|
| 2026-02-17 | User selects solver type (not side-by-side) | Manager chooses "Math Optimizer" or "AI Scheduler" before generating. Simpler UX, avoids double API costs. Can still compare by running both sequentially. |
| 2026-02-17 | Python subprocess (not microservice) | OR-Tools requires Python. subprocess call from PHP is simplest deployment - no extra Docker service. JSON I/O via stdin/stdout. |
| 2026-02-17 | Match existing 6 priorities | Same priorities as AI Scheduler enables fair comparison. Priorities: position_coverage, labor_cost, hours_fairness, seniority, minimize_overtime, employee_preferences. |
| 2026-02-17 | No rate limit for Math Optimizer | Zero API cost means no reason to limit runs. Only AI Scheduler keeps its 5/pay-week limit. |
| 2026-02-17 | OR-Tools CP-SAT chosen over LP/greedy | Research shows CP-SAT outperforms pure LP/MIP for scheduling. Proven optimal for 10-30 employees in under 60 seconds. Apache 2.0 licensed, free. |
| 2026-02-17 | LLM for explanation only, not generation | Solver provides structured constraint data. LLM translates to natural language. No LLM hallucination risk for the actual schedule. |
| 2026-02-17 | TaskEngine async execution (same as AI) | Reuses existing TaskEngine, Ably, and suggestion storage infrastructure. No new execution model needed. |
| 2026-02-17 | Fix AI Scheduler controller validation | Controller line 208 only accepts 4 of 6 defined priorities. Both solvers will use all 6 from AiDefaultPrefsService. |
| 2026-02-17 | LLM features gracefully degrade | When OpenAI is unavailable, structured constraint-based explanations shown instead. Suggestions hidden. Solver quality unaffected. |
| 2026-02-17 | Exponential priority weighting | weight = 10^(6-rank) ensures clear separation. Rank 1 = 100,000; Rank 6 = 1. |
| 2026-02-18 | ADR-1: OR-Tools CP-SAT via Python subprocess | proc_open() from PHP, JSON I/O via stdin/stdout. No microservice. |
| 2026-02-18 | ADR-2: Shared suggestion storage | solverType ENUM column on existing tables, not separate tables. |
| 2026-02-18 | ADR-3: LLM explanation only | Solver produces assignments, LLM generates text from constraint data. Never modifies schedule. |
| 2026-02-18 | ADR-4: Extract ScheduleDataGatherer | Shared data collection service for both solvers. Safe refactor of AiScheduleOptimizer. |
| 2026-02-18 | ADR-5: Exponential priority weighting confirmed | 10^(6-rank) formula approved. |
| 2026-02-18 | ADR-6: Fix priority validation bug | Controller line 208 to accept all 6 priorities. Part of this spec. |
| 2026-02-18 | ADR-7: No rate limit for Math Optimizer | Zero API cost = unlimited runs. AI keeps 5/pay-week limit. |
| 2026-02-17 | SDD Review: Single-threaded CP-SAT | num_search_workers=1 required for determinism. Multi-threading makes CP-SAT non-deterministic even with fixed seed. |
| 2026-02-17 | SDD Review: Assumption-literal IIS strategy | CP-SAT doesn't provide native IIS. Use assumption literals + unsat core extraction with 10s time budget. |
| 2026-02-17 | SDD Review: Coverage hard-precedence | Position coverage uses weight=10^7 (above user priorities) to ensure shifts are always filled first. |
| 2026-02-17 | SDD Review: LLM chunking (20 assignments/call) | Large stores need chunked LLM calls. Per-chunk fallback on failure. |
| 2026-02-17 | SDD Review: Overtime dual modeling | hoursMax = hard cap. OT penalty (40h weekly, 8h daily) = soft constraint with priority weighting. |
| 2026-02-17 | PLAN created with 9 phases | Sequential phases with parallel sub-components. Phase order: Migrations → Value Objects/Services → Python Solver → LLM Services → Orchestrator/Job → API Layer → Frontend UI → Advanced Features → Integration/E2E. |
| 2026-02-18 | PLAN Review: Features 10 & 11 deferred | PRD Should-Have Features 10 (Schedule Summary) and 11 (Override & Re-optimize) explicitly deferred from initial implementation. Can be added as follow-up phases. |
| 2026-02-18 | PLAN Review: Ably channel naming aligned | Math Optimizer uses `solver-schedule-{typeNum}-{jobId}` with `solver.completed`/`solver.failed` events. AI retains existing `ai-schedule-{typeNum}-{jobId}` channel. |
| 2026-02-18 | PLAN Review: Suggestion refresh added | PRD Feature 5 requires suggestions update on accept/reject. Added backend `refreshSuggestions()` method and frontend wiring. |
| 2026-02-18 | PLAN Review: Server-side health guard added | Controller rejects `solverType=math` if Python unavailable (not just UI hiding). |
| 2026-02-18 | PLAN Review: Phase 7.5 integration smoke test added | Early integration checkpoint for PHP↔Python bridge before advanced features. |
| 2026-02-18 | PLAN Review: Controller work consolidated | Phase 1 limited to priority validation fix only. All solverType routing moved to Phase 6. |

## PRD Review Summary (Codex Review - 2026-02-17)

### Key Findings Addressed

| Category | Finding | Resolution |
|----------|---------|------------|
| **BLOCKER** | Priority set conflicts with Spec 026 (6 vs 4 in controller) | Documented: `AiDefaultPrefsService` defines all 6; controller validation at line 208 needs update. Both solvers will use all 6. |
| **BLOCKER** | "Same 11 constraints" not aligned with Spec 026 | Reconciled: enumerated exact constraint list matching `AiPromptBuilder` constraints 1-11 and `parseAndValidateAssignments`. Clarified hard vs soft (hoursRequested/Min are soft). |
| **BLOCKER** | Execution model undefined (sync vs async) | Defined: Uses TaskEngine async pattern same as AI Scheduler. Reuses Ably, suggestion storage, preview UI. |
| **IMPORTANT** | LLM features Must Have but "optional fallback" contradictory | Clarified: Solver standalone, LLM best-effort. Added graceful degradation acceptance criteria to Features 4 and 5. |
| **IMPORTANT** | Unmeasurable criteria (near-optimal, fairness thresholds) | Added explicit definitions: optimality gap formula, fairness CV thresholds (High < 0.15, Med 0.15-0.30, Low > 0.30), priority weight formula. |
| **IMPORTANT** | Weight sliders in primary journey but Could Have | Removed weight sliders from primary journey. Kept as Could Have Feature 12. |
| **IMPORTANT** | Evidence claims lack sources | Reframed as hypotheses with validation plan. Linked to existing code (`parseAndValidateAssignments` rejection logs). |
| **IMPORTANT** | Python deployment risk under-specified | Added explicit deployment requirements, failure modes, version pinning, and auto-hide behavior when Python missing. |
| **ENHANCEMENT** | Missing edge cases (overnight, overlapping, pay-period) | Added 7 new edge cases: overnight shifts, pay-period boundary, overlapping shifts, missing preference data, subprocess crash, large inputs. |

### Ready for SDD
- [x] All blockers resolved
- [x] User stories are clear and testable
- [x] Acceptance criteria are unambiguous with explicit formulas/thresholds
- [x] Scope well-defined with clear boundary from Spec 026
- [x] Execution model documented (TaskEngine async)
- [x] README updated with review notes

## SDD Review Summary (Codex Review - 2026-02-17)

### Key Findings Addressed

| Category | Finding | Resolution |
|----------|---------|------------|
| **BLOCKER** | CP-SAT `num_search_workers=4` breaks determinism | Fixed: set to 1 worker. CP-SAT is non-deterministic with multi-threading even with fixed seed. Single-threaded is required for the determinism guarantee. Performance impact documented. |
| **BLOCKER** | IIS detection not natively supported by CP-SAT | Fixed: specified assumption-literal + unsat core extraction strategy with 10-second time budget. Falls back to "unable to determine" if timeout. |
| **BLOCKER** | Missing Feature 5 (Improvement Suggestions) design | Fixed: added `SolverImprovementSuggestionService` component, storage schema, LLM prompt pattern, and graceful degradation behavior. |
| **BLOCKER** | Missing Feature 6 (Infeasibility Resolution) design | Fixed: added `InfeasibilityResolutionService` with resolution options, re-run-with-adjustments flow, 2 new API endpoints, and error handling. |
| **BLOCKER** | Missing Feature 8 (Solver Comparison) design | Fixed: added `SolverComparisonService` with comparison endpoint, `ComparisonResult` entity, LLM summary generation, and frontend comparison tab. |
| **IMPORTANT** | Overtime handling ambiguity (hard vs soft) | Clarified: hoursMax is hard constraint (never exceeded). Overtime penalty (hours between 40 and hoursMax) is soft constraint. Daily OT (>8h/day) modeling added to solver. |
| **IMPORTANT** | LLM batch call could exceed context for 150 shifts | Fixed: added chunking strategy (max 20 assignments per call), partial failure handling, and structured fallback per chunk. |
| **IMPORTANT** | Analytics tracking events not addressed in SDD | Fixed: added `ScheduleAnalyticsService` with implementation plan for all 10 PRD tracking events. |
| **IMPORTANT** | Last-used solver type persistence not specified | Fixed: stored as `lastSolverType` key in existing `aiScheduleDefaultPrefs` JSON column. No migration needed. |
| **IMPORTANT** | Position coverage precedence not enforced | Fixed: coverage modeled as hard-precedence penalty (weight=10^7) added before user-ranked priorities. Solver always tries to fill shifts first. |
| **IMPORTANT** | Owner inclusion and locked costing unclear | Fixed: added explicit documentation of owner exclusion default, owner recurring schedules as locked shifts for costing. |
| **ENHANCEMENT** | Scorecard CV with zero/absent requested hours | Documented edge case handling: exclude zero-hours employees from CV, handle single employee and identical hours. |
| **ENHANCEMENT** | Security on new endpoints | Confirmed: all new endpoints enforce `checkAccess('uri_schedule_ai')` and `checkStoreGroup($typeNum)`. POST endpoints require CSRF. |
| **ENHANCEMENT** | Worker concurrency risk | Noted: TaskEngine queue backpressure + single-threaded solver mitigate CPU saturation risk. |

### Codebase Verification (9/9 Files Verified)

| File | Status | Notes |
|------|--------|-------|
| `AiSchedulingApiController.php` line 208 | Confirmed bug | Only validates 4 of 6 priorities (missing `minimize_overtime`, `employee_preferences`) |
| `AiDefaultPrefsService.php` AVAILABLE_PRIORITIES | Verified | All 6 priorities correctly defined |
| `AiScheduleOptimizer.php` data gathering methods | Verified | All 5 methods exist: getOpenShiftsForWeek, getSchedulableEmployees, getAvailabilityForWeek, getTimeOffForWeek, getCurrentPeriodHours |
| `AiScheduleGenerationJob.php` | Verified | Extends BaseJob, 660s timeout, proper dispatch flow |
| `AiSuggestion.php` | Verified | Full model with fromRow/fromCacheArray factories |
| `AiSuggestionRepository.php` | Verified | Repository pattern with save/findById/findPendingByWeek |
| `ConflictDetectionService.php` lines 264-294 | Verified | Overnight shift logic with two-day availability checking |
| `ai-scheduling.js` | Verified | AiScheduling class with Ably subscription |
| `BaseJob.php` | Verified | Abstract base class with lifecycle hooks |

### Architectural Decisions Confirmed/Updated

| Decision | Status |
|----------|--------|
| ADR-1: CP-SAT via Python subprocess | Confirmed (updated: single-threaded for determinism) |
| ADR-2: Shared suggestion storage | Confirmed (added improvementSuggestions column) |
| ADR-3: LLM explanation only | Confirmed (added chunking strategy) |
| ADR-4: Extract ScheduleDataGatherer | Confirmed |
| ADR-5: Exponential priority weighting | Confirmed (added coverage hard-precedence at 10^7) |
| ADR-6: Fix priority validation | Confirmed (codebase verification confirms bug) |
| ADR-7: No rate limit for Math Optimizer | Confirmed |

### Ready for Implementation Plan
- [x] All blockers resolved (5/5)
- [x] All important items fixed (6/6)
- [x] Design covers all PRD Must Have requirements (Features 1-8)
- [x] Design covers PRD Should Have Feature 9 (Why Not query)
- [x] Architecture is sound with determinism guarantee
- [x] All interfaces clearly defined (5 new endpoints added)
- [x] Security and error handling addressed for all new endpoints
- [x] Analytics instrumentation plan matches all 10 PRD tracking events
- [x] Codebase references verified (9/9 files confirmed)
- [x] README updated with review notes

## PLAN Review Summary (Codex Review - 2026-02-18)

### Key Findings Addressed

| Category | Finding | Resolution |
|----------|---------|------------|
| **BLOCKER** | PRD Should-Have Features 10 & 11 not planned | Explicitly deferred with rationale. Both can be added post-launch as follow-up phases without modifying core code. |
| **BLOCKER** | PRD Feature 5 requires suggestions to refresh on accept/reject | Added `refreshSuggestions()` backend method (T4.2.2.6, T4.2.3.1), API endpoint (T6.3.8), and frontend wiring (T7.3.11, T7.4.5). |
| **BLOCKER** | Ably channel naming mismatch between plan context and SDD | Fixed: plan now specifies `solver-schedule-{typeNum}-{jobId}` + `solver.completed`/`solver.failed` for Math Optimizer. AI retains existing pattern. Frontend Ably subscription updated (T7.3.10). |
| **IMPORTANT** | Controller work duplicated across Phase 1 and Phase 6 | Consolidated: Phase 1 T1.5.2 moved to Phase 6 T6.3.1. Phase 1 only touches priority validation fix. |
| **IMPORTANT** | Email notifications for solver jobs missing (SDD CON-2) | Added test T5.2.10 and implementation note in T5.3.2 to reuse existing email flow. |
| **IMPORTANT** | Math usage tracking not sourced | Added T6.2.12 test and updated T6.3.3 to derive count from `aiScheduleJobs WHERE solverType='math'`. |
| **IMPORTANT** | No server-side guard when Python unavailable | Added T6.2.11 test and updated T6.3.1 to call `PythonSolverBridge::checkHealth()` before dispatching math solver job. |
| **ENHANCEMENT** | `solver_comparison_viewed.chosenSolver` not wired | Added T8.5.1-T8.5.2 for frontend capture and backend logging. |
| **ENHANCEMENT** | No explicit Definition of Done per phase | Added "Definition of Done" section before Implementation Phases with 6 universal criteria. |
| **ENHANCEMENT** | No risk checklist in plan | Added "Risk Checklist" table with 8 risks, affected phases, and mitigations. |
| **ENHANCEMENT** | No mid-plan integration checkpoints | Added Phase 7.5 (Integration Smoke Test) with 4 PHP↔Python bridge verification tasks. |

### Ready for Implementation
- [x] All 3 blockers resolved
- [x] All 4 important items fixed
- [x] All 4 enhancements addressed
- [x] Plan covers all 8 PRD Must Have features + Should Have Feature 9
- [x] Features 10 & 11 explicitly deferred with rationale
- [x] Definition of Done defined per phase
- [x] Risk checklist with mitigations
- [x] Integration smoke test added (Phase 7.5)
- [x] ~195 tasks across 10 phases (including 7.5)
- [x] README updated with review notes

## Context

**Feature Overview:** Add a deterministic constraint-based scheduling solver alongside the existing AI (OpenAI) scheduling engine from Spec 026. The goal is to provide a reliable, explainable, and fast scheduling algorithm that uses mathematical optimization (constraint solving / linear programming / greedy+repair) to generate schedules, while using LLM only for human-facing explanation and improvement suggestions.

**Key Goals:**
1. **Deterministic solver** using OR-Tools CP-SAT, linear programming, or greedy+repair algorithm
2. **Side-by-side comparison** with existing AI-generated schedules (Spec 026)
3. **LLM for explanation only** - AI explains WHY shifts were assigned, suggests improvements, handles edge cases conversationally
4. **Same constraints** as current AI system: role qualification, availability, time-off, hours limits, overtime, etc.
5. **Provably optimal** or near-optimal solutions with measurable quality metrics

### Related Specifications
- `026-ai-smart-scheduling` - Existing AI-only scheduling (Phase 4 complete)
- `025-schedule-templates-overlays` - Template system
- `035-premium-scheduling-module` - Premium gating (fully implemented)
- `013-employee-scheduling` - Core scheduling engine
- `010-employee-schedule-panel` - Schedule panel UI

### Existing AI System Architecture
The current system (Spec 026) uses:
- `AiScheduleOptimizer` - 8-step algorithm with OpenAI structured outputs
- `AiPromptBuilder` - Builds system/user prompts with constraints 1-11
- `OpenAIClient` - Model fallback chain (gpt-5-mini → gpt-5 → gpt-4o-mini)
- `AiSuggestionRepository` - Stores suggestions in `aiScheduleSuggestions`
- TaskEngine async processing via `AiScheduleGenerationJob`
- Ably real-time notifications on completion

The deterministic solver will integrate alongside this system, sharing the same data gathering, constraint definitions, and suggestion storage patterns.

---
*This file is managed by the specification-management skill.*