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.
5.8 kB · 151 lines
TypeScript
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152// Gate — Collector block (hard feasibility gate).//// Keeps only the schedules that satisfy *every* limit; a limit bounds one// scorer's value by `max` and/or `min` (an absent bound is unbounded on that// side — never ±Infinity). This is the feasibility-filter shape: "keep the// schedules whose makespan and peak headcount both stay under their caps",// generalized to N scorer-referencing limits with two-sided bounds.//// When at least one schedule passes, the passing set (order-preserving) is// the result. When none pass, `fallback` decides:// • "none" — the empty set (a strict gate: nothing feasible, nothing out).// • "leastBad" — the single least-bad schedule (the "closest" fallback).//// The least-bad measure is the interesting part. Violations of different// scorers are not commensurable (a day past a duration cap is not a person// past a headcount cap), so we do NOT sum them. Instead we compare schedules// *lexicographically* over the limits in declared order — the first limit is// the binding one. Ties (equal violation on every limit) keep first-seen// order.//// The `scorer` entries are instanceIds from the same pipeline, not Scorer// closures: they resolve to compiled scorers only at run-wiring time (as// `objective.lexicographic` does), so the emitted spec stays plain JSON.//// Collectors are a selection layer above the solver, so `toMiniZinc` emits an// explanatory comment rather than a constraint fragment.
import { z } from "zod";
import type { GateCollector, Schedule, Scorer } from "../level-core/types.ts";
import type { CollectorBlock, MiniZincFragment } from "./types.ts";
const GateLimitInputSchema = z .object({ /** Scorer instanceId this limit bounds. */ scorer: z.string(), /** Upper bound (value must be <= max). Absent = unbounded above. */ max: z.number().optional(), /** Lower bound (value must be >= min). Absent = unbounded below. */ min: z.number().optional(), }) .refine((l) => l.max !== undefined || l.min !== undefined, { message: "a gate limit needs at least one of max or min (an unbounded side is simply absent)", });
export const GateInputSchema = z.object({ limits: z.array(GateLimitInputSchema).min(1), /** What to return when no schedule passes every limit. */ fallback: z.enum(["leastBad", "none"]),});
export type GateInput = z.infer<typeof GateInputSchema>;
const GateOutputSchema: z.ZodType<GateCollector> = z.object({ kind: z.literal("Gate"), limits: z.array( z.object({ scorer: z.string(), max: z.number().optional(), min: z.number().optional(), }), ), fallback: z.enum(["leastBad", "none"]),});
export const GateBlock: CollectorBlock<GateInput> = { id: "Gate", schema: { input: GateInputSchema, output: GateOutputSchema }, apply: ({ limits, fallback }): GateCollector => ({ kind: "Gate", limits, fallback, }), toMiniZinc: (): MiniZincFragment => ({ text: `% Gate — selection layer; keeps schedules satisfying every limit, emits no solver constraint.`, }), doc: { nl: "Keeps only schedules that satisfy every limit; when none pass, returns nothing or the single least-bad schedule.", pseudocode: "pass = candidates.filter(within all limits); pass.length ? pass : (fallback == 'leastBad' ? [leastViolating(candidates)] : [])", },};
/** A Gate limit with its scorer instanceId already resolved to the compiled * Scorer — what `selectGate` evaluates against. */export interface ResolvedGateLimit { readonly scorer: Scorer; readonly max?: number | undefined; readonly min?: number | undefined;}
function withinBounds(value: number, limit: ResolvedGateLimit): boolean { return ( (limit.max === undefined || value <= limit.max) && (limit.min === undefined || value >= limit.min) );}
// Per-limit violation: how far the scorer value lies outside [min, max], 0// when within. The two one-sided terms are the SAME scorer's units, so adding// them here is legitimate (and min <= max means at most one is ever nonzero).function limitViolation(value: number, limit: ResolvedGateLimit): number { let out = 0; if (limit.max !== undefined && value > limit.max) out += value - limit.max; if (limit.min !== undefined && value < limit.min) out += limit.min - value; return out;}
// `a` is less bad than `b` iff its violation vector is lexicographically// smaller: at the first limit where they differ, `a` violates less. Equal on// every limit is not less bad (first-seen wins, keeping selection stable).function lexLessBad(a: readonly number[], b: readonly number[]): boolean { for (let i = 0; i < a.length; i++) { if (a[i]! < b[i]!) return true; if (a[i]! > b[i]!) return false; } return false;}
/** * Execute a Gate over a materialized candidate set. Returns the schedules * passing every limit (order-preserving) when any pass; otherwise applies the * fallback — the empty set ("none") or the single least-bad schedule * ("leastBad", lexicographic over per-limit violation in declared order). */export function selectGate( schedules: readonly Schedule[], limits: readonly ResolvedGateLimit[], fallback: "leastBad" | "none",): readonly Schedule[] { const passing = schedules.filter((s) => limits.every((l) => withinBounds(l.scorer.score(s), l)), ); if (passing.length > 0) return passing; if (fallback === "none" || schedules.length === 0) return [];
let best = schedules[0]!; let bestViol = limits.map((l) => limitViolation(l.scorer.score(best), l)); for (let i = 1; i < schedules.length; i++) { const viol = limits.map((l) => limitViolation(l.scorer.score(schedules[i]!), l), ); if (lexLessBad(viol, bestViol)) { best = schedules[i]!; bestViol = viol; } } return [best];}