ADR 014 Scheduling Engine Architecture

ADR-014: Scheduling Engine Architecture

Status

Accepted

Context

EPIC-06 requires automatic scheduling that respects task dependencies, date constraints, and lead/lag times. When a homeowner adjusts a task's dates or a delay occurs, downstream dependent tasks should be reschedulable. The system must also identify the critical path -- the sequence of tasks that determines the minimum project duration.

Key requirements from the REQUIREMENTS.md:

• "Automatic scheduling based on dependencies" (Section 2.4)
• "Cascade updates when dates change" (Section 2.4)
• "See the critical path so I know which tasks cannot be delayed" (Section 4, User Stories)
• "Automatic rescheduling when a task is delayed" (Section 4, User Stories)

Constraints

• Small dataset: 50--200 work items typical for a home build project
• Single-user interaction model: Only 1--5 users, so concurrent scheduling conflicts are unlikely
• SQLite backend: All data in a single SQLite database; no distributed transaction concerns
• On-demand, not automatic: Scheduling should not run silently in the background. The user explicitly triggers it (clicks an "Auto-schedule" button), so they understand and can review the impact before saving.

Alternatives Considered

Approach	Description	Pros	Cons
Client-side scheduling	Run the algorithm in the browser	No server round-trip; instant feedback	Risks data inconsistency if browser state diverges from DB; complex to implement in React; harder to test
Server-side on-demand	POST endpoint runs scheduling, returns proposed changes	Data integrity guaranteed; single source of truth; easy to test; user reviews before committing	Requires server round-trip; slight latency (acceptable for 50--200 items)
Server-side automatic	Scheduling runs automatically on every work item save	Always up-to-date	Unexpected date changes surprise users; harder to debug; performance concern if triggered on every edit

Decision

Implement a server-side, on-demand scheduling engine using the Critical Path Method (CPM) algorithm.

Algorithm

The CPM algorithm operates in phases:

1. Build dependency graph from the work_item_dependencies table, including lead_lag_days offsets.
2. Topological sort using Kahn's algorithm to detect circular dependencies. If a cycle is found, the scheduling request fails with an error identifying the cycle.
3. Forward pass: Traverse items in topological order, computing the earliest start (ES) and earliest finish (EF) for each item.
   • For items with no predecessors: ES = start_after constraint (if set), otherwise the current date.
   • For items with predecessors: ES = max(all predecessor-derived dates + lead/lag) and must also respect start_after.
   • EF = ES + duration_days (if duration is set).
4. Backward pass: Traverse items in reverse topological order, computing the latest start (LS) and latest finish (LF) for each item.
   • For items with no successors: LF = EF (the latest finish equals the earliest finish for terminal items).
   • For items with successors: LF = min(all successor-derived dates - lead/lag).
   • LS = LF - duration_days.
5. Calculate float (slack): For each item, total float = LS - ES (or equivalently LF - EF).
6. Identify critical path: Items with zero float form the critical path. These tasks cannot be delayed without extending the overall project duration.

Dependency Type Handling

Each dependency type determines how predecessor and successor dates relate:

Type	Abbreviation	Forward Pass Rule	Backward Pass Rule
Finish-to-Start	FS	Successor ES >= Predecessor EF + lead/lag	Predecessor LF <= Successor LS - lead/lag
Start-to-Start	SS	Successor ES >= Predecessor ES + lead/lag	Predecessor LS <= Successor LS - lead/lag
Finish-to-Finish	FF	Successor EF >= Predecessor EF + lead/lag	Predecessor LF <= Successor LF - lead/lag
Start-to-Finish	SF	Successor EF >= Predecessor ES + lead/lag	Predecessor LS <= Successor LF - lead/lag

Lead/Lag Days

The lead_lag_days column on work_item_dependencies adds an offset to the dependency relationship:

• Positive values (lag): Adds waiting time. A FS dependency with lead_lag_days = 3 means the successor starts 3 days after the predecessor finishes.
• Negative values (lead): Allows overlap. A FS dependency with lead_lag_days = -2 means the successor can start 2 days before the predecessor finishes.

Scheduling Modes

The API endpoint (POST /api/schedule) supports two modes:

Mode	Description	Use Case
full	Schedules all work items from scratch based on dependencies, constraints, and the current date	Initial planning; major replanning after scope changes
cascade	Starting from an anchor work item, propagates date changes only to downstream successors	A single task was delayed; user wants to see the ripple effect

Constraints Respected

Constraint	Type	Behavior
start_after	Hard	Item cannot start before this date. The scheduling engine sets ES = max(dependency-derived ES, start_after).
start_before	Soft	Item should start before this date. If the scheduled start exceeds start_before, a warning is included in the response but the schedule is not rejected.
duration_days	Calculation	Used to compute end date from start date (EF = ES + duration_days). Items without duration_days are scheduled as zero-duration (milestones or unestimated items).

Response Shape

The scheduling endpoint is read-only — it returns the computed schedule without persisting any changes to the database. The client displays results for user review, then applies accepted changes via individual PATCH /api/work-items/:id calls.

interface ScheduleResponse {
  scheduledItems: ScheduledItem[];
  criticalPath: string[]; // Array of work item IDs on the critical path
  warnings: ScheduleWarning[];
}

interface ScheduledItem {
  workItemId: string;
  previousStartDate: string | null;
  previousEndDate: string | null;
  scheduledStartDate: string; // Earliest start (ES)
  scheduledEndDate: string; // Earliest finish (EF)
  latestStartDate: string; // Latest start (LS)
  latestFinishDate: string; // Latest finish (LF)
  totalFloat: number; // Days of slack: LS - ES
  isCritical: boolean;
}

interface ScheduleWarning {
  workItemId: string;
  type: 'start_before_violated' | 'no_duration' | 'already_completed';
  message: string;
}

The client receives the computed schedule and can display proposed changes for user review before applying them.

Interface Contract (for Backend Implementation)

The scheduling engine is a service module with this interface:

interface SchedulingEngine {
  schedule(params: {
    mode: 'full' | 'cascade';
    anchorWorkItemId?: string; // Required for cascade mode
  }): ScheduleResult;
}

interface ScheduleResult {
  scheduledItems: ScheduledItem[];
  criticalPath: string[];
  warnings: ScheduleWarning[];
}

The service reads all work items and dependencies from the database, runs the algorithm in memory, and returns the proposed schedule. It does not persist any changes -- the caller (route handler) decides whether to apply the results.

Consequences

What becomes easier

• Data integrity: Server-side scheduling with SQLite transactions ensures the dependency graph and dates are always consistent.
• Testability: The scheduling algorithm is a pure function (input: work items + dependencies; output: proposed schedule). It can be unit-tested without HTTP or database setup by passing in mock data.
• User control: On-demand scheduling means users always see and approve changes before they are applied. No surprises.
• Critical path visibility: The CPM algorithm naturally identifies the critical path as a byproduct of the forward/backward passes. No additional computation needed.
• Cascade mode efficiency: For single-task delays, only downstream items are recalculated, not the entire project.

What becomes harder

• Two-step user interaction: The user must trigger scheduling, review the proposed changes, and then accept them. This adds UI complexity compared to automatic rescheduling.
• No real-time updates: If one user triggers scheduling while another is editing dates, the second user's changes may conflict with the proposed schedule. However, with <5 users this is an acceptable trade-off.
• Algorithm complexity: Implementing CPM with four dependency types and lead/lag days is moderately complex. However, it is a well-documented algorithm with established reference implementations.

Future Extensibility

• Calendar integration: The scheduling engine could later account for non-working days (weekends, holidays) by adjusting duration calculations. This is not needed for the initial implementation.
• Resource leveling: If resource constraints are added in the future, the engine interface can be extended without changing the API contract.
• What-if analysis: The read-only nature of the scheduling response naturally supports scenario planning (run scheduling with different parameters without committing changes).