Something went wrong. Try again.
A functional toolkit for authoring resource-leveling algorithms — compose constraint and scoring blocks, enumerate feasible schedules
Something went wrong. Try again.
13 kB · 346 lines
TypeScript
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347// Static run analysis — spaCy's `analyze_pipes` + `validate_attrs` for the// leveling pipeline. Constraints and scorers reference project data by id;// this walks those declared references against a ResolvedProject and reports// coded, attributed issues in milliseconds, instead of a search failing (or// silently mis-optimizing) after a long run. Run it before any search; it// never runs one itself.
import type { RunIssue } from "./errors.ts";import { type Constraint, type PrecedenceEdge, type ResolvedProject, type Scorer, type Search, constraintLabel,} from "./types.ts";
export interface AnalyzeRunOptions { readonly scorers?: readonly Scorer[] | undefined; /** When given (and it implements `supports`), constraint kinds the search * won't enforce are reported as LEVELSET_W201 warnings. */ readonly search?: Search | undefined;}
export interface RunAnalysis { /** True when no error-severity issues were found (warnings allowed). */ readonly ok: boolean; readonly issues: readonly RunIssue[];}
export function analyzeRun( resolved: ResolvedProject, constraints: readonly Constraint[], opts?: AnalyzeRunOptions,): RunAnalysis { const issues: RunIssue[] = []; const taskIds = new Set(resolved.tasks.map((t) => t.uniqueId)); const resourceIds = new Set(resolved.resources.map((r) => r.uniqueId)); const taskById = new Map(resolved.tasks.map((t) => [t.uniqueId, t]));
const checkResource = (source: string, resourceUniqueId: number): void => { if (resourceIds.has(resourceUniqueId)) return; issues.push({ code: "LEVELSET_E101", severity: "error", source, message: `references resourceUniqueId ${String(resourceUniqueId)} which is not in the project — was the resource removed or the id mistyped?`, }); }; const checkTask = (source: string, taskUniqueId: number): void => { if (taskIds.has(taskUniqueId)) return; issues.push({ code: "LEVELSET_E102", severity: "error", source, message: `references taskUniqueId ${String(taskUniqueId)} which is not in the project — was the task filtered out upstream?`, }); }; const checkUnit = (source: string, unitId: number): void => { if (resolved.workUnits.has(unitId)) return; issues.push({ code: "LEVELSET_E103", severity: "error", source, message: `references work unit ${String(unitId)} which is not in ResolvedProject.workUnits — was it omitted from ResolveOptions.workUnits?`, }); };
// Tightest deadline / latest release per task, for cross-constraint checks. const deadlines = new Map<number, { day: number; source: string }>(); const releases = new Map<number, { day: number; source: string }>(); const constraintEdges: PrecedenceEdge[] = []; const unitEdges: { from: number; to: number; source: string }[] = []; const seenNames = new Map<string, number>(); const modePolicyByTask = new Map<number, string>();
const claimModePolicy = (taskUniqueId: number, source: string): void => { const previous = modePolicyByTask.get(taskUniqueId); if (previous === undefined) { modePolicyByTask.set(taskUniqueId, source); return; } issues.push({ code: "LEVELSET_E111", severity: "error", source, message: `task ${String(taskUniqueId)} is already governed by mode policy "${previous}" — use exactly one ModeSelection or CrewBorrow policy per task.`, }); };
for (const c of constraints) { const source = constraintLabel(c); if (c.name !== undefined) seenNames.set(c.name, (seenNames.get(c.name) ?? 0) + 1);
// `enabled: false` constraints are carried in the run but not enforced — // searches skip them — so nothing about them can invalidate the run. // Reference, feasibility, and cycle checks all analyze only the enabled // set (the same set serialSGS preprocesses); a disabled constraint that // would be infeasible is exactly the what-if ablation case. if (c.enabled === false) continue;
switch (c.kind) { case "Precedence": for (const e of c.edges) { checkTask(source, e.predecessorUniqueId); checkTask(source, e.successorUniqueId); } if (c.edges.length === 0) warnEmpty(issues, source, "edges"); constraintEdges.push(...c.edges); break; case "Calendars": if (!resolved.calendars.has(c.calendarUniqueId)) { issues.push({ code: "LEVELSET_E109", severity: "error", source, message: `references calendarUniqueId ${String(c.calendarUniqueId)} which is not in the project's calendars.`, }); } break; case "MaxConcurrentResource": checkResource(source, c.resourceUniqueId); break; case "PeakCap": checkResource(source, c.resourceUniqueId); if (c.window && c.window.fromDay >= c.window.toDay) { issues.push({ code: "LEVELSET_E108", severity: "error", source, message: `window [${String(c.window.fromDay)}, ${String(c.window.toDay)}) is empty — fromDay must be strictly before toDay.`, }); } break; case "ConcurrentUnitsLimit": for (const unitId of c.unitIds) checkUnit(source, unitId); if (c.unitIds.length === 0) warnEmpty(issues, source, "unitIds"); if (c.discipline !== undefined) checkResource(source, c.discipline); break; case "UnitPrecedence": checkUnit(source, c.unitId); for (const after of c.afterUnitIds) { checkUnit(source, after); unitEdges.push({ from: after, to: c.unitId, source }); } if (c.afterUnitIds.length === 0) warnEmpty(issues, source, "afterUnitIds"); break; case "UnimodalProfile": checkResource(source, c.resourceUniqueId); break; case "ModeSelection": checkTask(source, c.taskUniqueId); claimModePolicy(c.taskUniqueId, source); for (const mode of c.modes) { for (const demand of mode.resourceDemand) checkResource(source, demand.resourceUniqueId); } if (c.modes.length === 0) warnEmpty(issues, source, "modes"); break; case "CrewBorrow": checkResource(source, c.homeResourceUniqueId); checkResource(source, c.borrowResourceUniqueId); for (const taskUniqueId of c.taskUniqueIds) { checkTask(source, taskUniqueId); claimModePolicy(taskUniqueId, source); if ( taskIds.has(taskUniqueId) && resourceIds.has(c.homeResourceUniqueId) && !resolved.assignments.some( (assignment) => assignment.taskUniqueId === taskUniqueId && assignment.resourceUniqueId === c.homeResourceUniqueId, ) ) { issues.push({ code: "LEVELSET_E110", severity: "error", source, message: `task ${String(taskUniqueId)} has no static assignment on homeResourceUniqueId ${String(c.homeResourceUniqueId)} — CrewBorrow has no home demand to substitute.`, }); } } if (c.taskUniqueIds.length === 0) warnEmpty(issues, source, "taskUniqueIds"); break; case "CrewFlowContinuity": checkResource(source, c.resourceUniqueId); for (const unitId of c.unitOrder) checkUnit(source, unitId); if (c.unitOrder.length === 0) warnEmpty(issues, source, "unitOrder"); break; case "Deadline": { checkTask(source, c.taskUniqueId); const prev = deadlines.get(c.taskUniqueId); if (!prev || c.latestFinish < prev.day) { deadlines.set(c.taskUniqueId, { day: c.latestFinish, source }); } break; } case "Release": { checkTask(source, c.taskUniqueId); const prev = releases.get(c.taskUniqueId); if (!prev || c.earliestStart > prev.day) { releases.set(c.taskUniqueId, { day: c.earliestStart, source }); } break; } }
if (opts?.search?.supports && !opts.search.supports(c.kind)) { issues.push({ code: "LEVELSET_W201", severity: "warning", source, message: `${c.kind} is not enforced by search "${opts.search.name}" — it will be recorded as an unsupportedConstraints annotation, not applied.`, }); } }
for (const [name, count] of seenNames) { if (count > 1) { issues.push({ code: "LEVELSET_W203", severity: "warning", source: name, message: `${String(count)} constraint instances share the name "${name}" — failures will be ambiguous to attribute. Give each instance a distinct name.`, }); } }
// Deadline vs release vs duration. Day indexes are calendar days and // durations are working days, so (deadline − release) < durationDays is a // safe (never false-positive) infeasibility bound. for (const [taskUniqueId, deadline] of deadlines) { const release = releases.get(taskUniqueId); const releaseDay = release?.day ?? 0; if (release && deadline.day < release.day) { issues.push({ code: "LEVELSET_E104", severity: "error", source: deadline.source, message: `task ${String(taskUniqueId)} has Deadline ${String(deadline.day)} earlier than Release ${String(release.day)} ("${release.source}") — no feasible placement exists.`, }); continue; } // Milestones are placed with zero span whatever their nominal duration // (serialSGS's `task.milestone || durationDays === 0` branch), so the // duration bound only applies to real tasks. const task = taskById.get(taskUniqueId); const duration = task === undefined || task.milestone ? undefined : task.durationDays; if (duration !== undefined && deadline.day - releaseDay < duration) { issues.push({ code: "LEVELSET_E105", severity: "error", source: deadline.source, message: `task ${String(taskUniqueId)} needs ${String(duration)} working days but only ${String(deadline.day - releaseDay)} calendar days fit between release ${String(releaseDay)} and deadline ${String(deadline.day)} — no feasible placement exists.`, }); } }
// Precedence cycle (project edges + constraint edges), restricted to known // tasks — the same graph serialSGS topo-sorts, checked before any search. const allEdges = [...resolved.precedences, ...constraintEdges].filter( (e) => taskIds.has(e.predecessorUniqueId) && taskIds.has(e.successorUniqueId), ); const taskCycle = findCycle( [...taskIds], allEdges.map((e) => [e.predecessorUniqueId, e.successorUniqueId]), ); if (taskCycle) { issues.push({ code: "LEVELSET_E107", severity: "error", source: "run", message: `precedence edges form a cycle through tasks ${taskCycle.map(String).join(" → ")} — the schedule graph must be acyclic.`, }); }
const unitCycle = findCycle( [...resolved.workUnits.keys()], unitEdges .filter( (e) => resolved.workUnits.has(e.from) && resolved.workUnits.has(e.to), ) .map((e) => [e.from, e.to]), ); if (unitCycle) { issues.push({ code: "LEVELSET_E106", severity: "error", source: "run", message: `UnitPrecedence constraints form a cycle through units ${unitCycle.map(String).join(" → ")}.`, }); }
// Scorer declared reads. for (const scorer of opts?.scorers ?? []) { const reads = scorer.reads; if (!reads) continue; for (const id of reads.resourceUniqueIds ?? []) checkResource(scorer.name, id); for (const id of reads.taskUniqueIds ?? []) checkTask(scorer.name, id); for (const id of reads.unitIds ?? []) checkUnit(scorer.name, id); }
return { ok: !issues.some((i) => i.severity === "error"), issues };}
function warnEmpty(issues: RunIssue[], source: string, field: string): void { issues.push({ code: "LEVELSET_W202", severity: "warning", source, message: `${field} is empty — the constraint can never bind. Remove it or fill in ${field}.`, });}
/** Kahn's algorithm; returns the node ids stuck in a cycle (unsorted * remainder) or null when acyclic. */function findCycle( nodes: readonly number[], edges: readonly [from: number, to: number][],): number[] | null { const indegree = new Map<number, number>(nodes.map((n) => [n, 0])); const successors = new Map<number, number[]>(nodes.map((n) => [n, []])); for (const [from, to] of edges) { indegree.set(to, (indegree.get(to) ?? 0) + 1); successors.get(from)!.push(to); } const queue = nodes.filter((n) => (indegree.get(n) ?? 0) === 0); let sorted = 0; while (queue.length > 0) { const n = queue.pop()!; sorted += 1; for (const s of successors.get(n) ?? []) { const next = (indegree.get(s) ?? 0) - 1; indegree.set(s, next); if (next === 0) queue.push(s); } } if (sorted === nodes.length) return null; return nodes.filter((n) => (indegree.get(n) ?? 0) > 0);}