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.
6.8 kB · 210 lines
TypeScript
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211// PeakCap / Deadline / Release / ModeSelection constraint blocks, Makespan// scorer block, SerialSGS search block.
import { describe, expect, test } from "bun:test";
import { DeadlineBlock } from "../../src/level-blocks/deadline.ts";import { MakespanBlock } from "../../src/level-blocks/makespan.ts";import { MaxConcurrentResourceBlock } from "../../src/level-blocks/maxConcurrentResource.ts";import { ModeSelectionBlock } from "../../src/level-blocks/modeSelection.ts";import { PeakCapBlock } from "../../src/level-blocks/peakCap.ts";import { PhaseReleaseBlock } from "../../src/level-blocks/phaseRelease.ts";import { ReleaseBlock } from "../../src/level-blocks/release.ts";import { SerialSGSBlock } from "../../src/level-blocks/serialSgsSearch.ts";import { serialSGS } from "../../src/level-core/search/serialSGS.ts";import type { Schedule } from "../../src/level-core/types.ts";
import { MON_JAN_5, SAT_JAN_10, makeAssignment, makeProject, makeResource, makeTask, runOnce,} from "../level-core/fixtures.ts";
describe("constraint blocks", () => { test("PeakCap emits the constraint, with and without a window", () => { expect(PeakCapBlock.apply({ resourceUniqueId: 100, cap: 2.5 })).toEqual({ kind: "PeakCap", resourceUniqueId: 100, cap: 2.5, }); expect( PeakCapBlock.apply({ resourceUniqueId: 100, cap: 2, window: { fromDay: 0, toDay: 10 }, }), ).toEqual({ kind: "PeakCap", resourceUniqueId: 100, cap: 2, window: { fromDay: 0, toDay: 10 }, }); expect( PeakCapBlock.toMiniZinc({ resourceUniqueId: 100, cap: 2, window: { fromDay: 0, toDay: 10 }, }).text, ).toContain("d >= 0"); });
test("Deadline and Release emit their constraints and reject bad input", () => { expect(DeadlineBlock.apply({ taskUniqueId: 1, latestFinish: 30 })).toEqual({ kind: "Deadline", taskUniqueId: 1, latestFinish: 30, }); expect(ReleaseBlock.apply({ taskUniqueId: 1, earliestStart: 5 })).toEqual({ kind: "Release", taskUniqueId: 1, earliestStart: 5, }); expect( DeadlineBlock.schema.input.safeParse({ taskUniqueId: 1, latestFinish: -1, }).success, ).toBe(false); });
test("PhaseRelease expands a shared boundary into attributed Release constraints", () => { expect( PhaseReleaseBlock.apply({ taskUniqueIds: [1, 2], earliestStart: 5 }), ).toEqual([ { kind: "Release", taskUniqueId: 1, earliestStart: 5 }, { kind: "Release", taskUniqueId: 2, earliestStart: 5 }, ]); expect( PhaseReleaseBlock.toMiniZinc({ taskUniqueIds: [1, 2], earliestStart: 5 }) .text, ).toBe("constraint start_day[1] >= 5;\nconstraint start_day[2] >= 5;"); expect( PhaseReleaseBlock.schema.input.safeParse({ taskUniqueIds: [1, 1], earliestStart: 5, }).success, ).toBe(false); });});
describe("ModeSelection block", () => { const modes = [ { modeId: 1, durationDays: 2, resourceDemand: [{ resourceUniqueId: 100, units: 1 }], }, { modeId: 2, durationDays: 4, resourceDemand: [{ resourceUniqueId: 200, units: 0.5 }], }, ];
test("emits the constraint and pins the MiniZinc mode domain", () => { expect(ModeSelectionBlock.apply({ taskUniqueId: 7, modes })).toEqual({ kind: "ModeSelection", taskUniqueId: 7, modes, }); expect(ModeSelectionBlock.toMiniZinc({ taskUniqueId: 7, modes }).text).toBe( "constraint mode[7] in {1,2};", ); });
test("rejects empty modes, non-positive durations, duplicate mode ids, and duplicate resources", () => { expect( ModeSelectionBlock.schema.input.safeParse({ taskUniqueId: 7, modes: [], }).success, ).toBe(false); expect( ModeSelectionBlock.schema.input.safeParse({ taskUniqueId: 7, modes: [{ modeId: 1, durationDays: 0, resourceDemand: [] }], }).success, ).toBe(false); expect( ModeSelectionBlock.schema.input.safeParse({ taskUniqueId: 7, modes: [ { modeId: 1, durationDays: 1, resourceDemand: [] }, { modeId: 1, durationDays: 2, resourceDemand: [] }, ], }).success, ).toBe(false); expect( ModeSelectionBlock.schema.input.safeParse({ taskUniqueId: 7, modes: [ { modeId: 1, durationDays: 1, resourceDemand: [ { resourceUniqueId: 100, units: 1 }, { resourceUniqueId: 100, units: 2 }, ], }, ], }).success, ).toBe(false); });
test("the emitted constraint drives mode choice end-to-end in serialSGS", async () => { // Two tasks contend for home(100, max 1). Task 2's preferred mode is the // home crew, but borrowing 200 lets it start day 0 instead of waiting. const t1 = makeTask({ uniqueId: 1, start: MON_JAN_5, finish: SAT_JAN_10 }); const t2 = makeTask({ uniqueId: 2, start: MON_JAN_5, finish: SAT_JAN_10 }); const project = makeProject([t1, t2], { resources: [makeResource(100, "Home"), makeResource(200, "Borrow")], assignments: [makeAssignment(1, 100), makeAssignment(2, 100)], }); const modesFor = (taskUniqueId: number) => ModeSelectionBlock.apply({ taskUniqueId, modes: [ { modeId: 0, durationDays: 5, resourceDemand: [{ resourceUniqueId: 100, units: 1 }], }, { modeId: 1, durationDays: 5, resourceDemand: [{ resourceUniqueId: 200, units: 1 }], }, ], }); const schedule = await runOnce(project, [ modesFor(1), modesFor(2), MaxConcurrentResourceBlock.apply({ resourceUniqueId: 100, max: 1 }), MaxConcurrentResourceBlock.apply({ resourceUniqueId: 200, max: 1 }), ]); const by = new Map(schedule.tasks.map((t) => [t.uniqueId, t])); expect(by.get(1)!.modeId).toBe(0); // home crew, day 0 expect(by.get(2)!.modeId).toBe(1); // borrowed to start day 0 expect(by.get(2)!.startDay).toBe(0); });});
describe("Makespan block", () => { test("scores a schedule's makespan", async () => { const t1 = makeTask({ uniqueId: 1, start: MON_JAN_5, finish: SAT_JAN_10 }); const schedule: Schedule = await runOnce(makeProject([t1]), []); const scorer = MakespanBlock.apply({}); expect(scorer.direction).toBe("min"); expect(scorer.score(schedule)).toBe(schedule.makespan); });});
describe("SerialSGS block", () => { test("resolves to the serialSGS search singleton", () => { expect(SerialSGSBlock.apply({})).toBe(serialSGS); });});