Build Scheduler: Plans, Worker Pools, Resource Limits and Critical Paths

Build Scheduler: Plans, Worker Pools, Resource Limits and Critical Paths

You've joined the developer-productivity team that owns the build scheduler: the service that takes a pipeline of tasks with dependencies and works out the order to run them and how long the pipeline will take on a given number of workers. The planner has two known bugs, and three capabilities are queued behind them. All times are whole seconds.

Codebase

How your code is run

run(operations: list[list]) -> list executes the operations in order against a fresh scheduler and returns one result per operation. Every operation is [name, *args]. Errors are returned as "error: <code>" strings, never raised.

• An unknown operation returns "error: unknown operation"; a wrong number of arguments returns "error: invalid arguments".
• A task has an id (non-empty string, case-sensitive, compared as plain strings so "t10" sorts before "t2"), an integer duration >= 1, an integer priority (a larger number is more urgent, may be negative) and deps, a list of ids. invalid arguments means a wrong type (priority, deps not a list of non-empty strings, etc.); a duration that is not an integer >= 1 is invalid duration.
• A task may only depend on tasks that were added earlier (otherwise unknown dependency, which also covers depending on itself), so the graph never has a cycle. A dependency listed more than once counts once.
• plan returns every task exactly once, dependencies first. Among tasks that are ready at the same time, the one with the larger priority goes first; equal priorities are ordered by task id. ("Ready" means all of its dependencies are already in the plan.)

Worked example

[["add_task", "compile", 5, 1, []],
 ["add_task", "lint", 2, 5, []],
 ["add_task", "test", 8, 3, ["compile"]],
 ["add_task", "package", 3, 3, ["compile", "lint"]],
 ["plan"]]

returns

[true, true, true, true, ["lint", "compile", "package", "test"]]

lint (priority 5) beats compile (priority 1). After compile, both test and package are ready with priority 3, and package sorts before test.

Part 1 — Fix the planner (SCHED-190, SCHED-203)

Goal: plan must include every task and honor priorities.

Reports:

1. "A task that lists the same dependency twice (our YAML generator sometimes does that) is missing from the plan entirely, and so is everything that depends on it."
2. "Low-priority work is being scheduled ahead of urgent work when both are ready."

Rules

1. plan contains every task exactly once, whatever way its dependencies were written.
2. Among simultaneously ready tasks, larger priority first, then smaller task id.

tests/test_planner.py::test_more_urgent_ready_task_goes_first and ::test_task_with_a_repeated_dependency_is_still_planned currently fail.

Part 2 — Simulate a worker pool (SCHED-214)

Goal: simulate(workers) predicts when each task starts and finishes if workers identical workers execute the pipeline.

Rules

1. workers must be an integer >= 1, else error: invalid workers.
2. Time starts at 0. A worker runs one task at a time, without interruption, for exactly its duration. A task may start only when all of its dependencies have finished (a task starting at the moment its last dependency finishes is fine).
3. At every moment, in this order: (a) all tasks finishing at that moment complete and release their dependents; (b) each idle worker, one after another, takes the most urgent ready task (same order as plan: larger priority, then smaller id). A worker never waits while a task is ready.
4. The result is {"makespan": int, "start": {task_id: int}, "finish": {task_id: int}} covering every task. makespan is the latest finish (0 for an empty graph, with empty start and finish).

Example (the pipeline above)

["simulate", 2]

returns

{"makespan": 13,
 "start":  {"lint": 0, "compile": 0, "package": 5, "test": 5},
 "finish": {"lint": 2, "compile": 5, "package": 8, "test": 13}}

With one worker the makespan is 18 (lint, compile, package, test back to back).

Part 3 — Resource groups with concurrency limits (SCHED-298)

Goal: some tasks share a scarce resource (a GPU, a license server). A group can be limited so only a few of its tasks run at once.

Rules

1. add_task takes an optional fifth argument group: a non-empty string or null. The existing four-argument form keeps working and means no group (invalid arguments for any other value).
2. set_limit(group, limit) sets the maximum number of tasks of that group running at the same moment. limit must be an integer >= 1, else error: invalid limit; a non-string or empty group is invalid arguments. Setting it again replaces the limit. A group with no limit, and tasks with no group, are unlimited. Limits can be set before or after tasks are added; they apply to every later simulate.
3. In simulate, when an idle worker picks the next task (rule 3b of Part 2), tasks whose group is already at its limit are skipped, not dropped: the worker takes the next most urgent ready task instead, and the skipped task stays ready for later. A task started earlier in the same moment counts toward its group, and a task finishing at that moment has already freed its slot.
4. plan and Part 2 behavior for tasks without limits do not change.

Example

[["add_task", "compile", 5, 1, []],
 ["add_task", "unit", 4, 3, ["compile"], "gpu"],
 ["add_task", "integ", 6, 2, ["compile"], "gpu"],
 ["add_task", "docs", 2, 1, ["compile"]],
 ["set_limit", "gpu", 1],
 ["simulate", 3]]

returns true five times (four add_task, one set_limit), then

{"makespan": 15,
 "start":  {"compile": 0, "unit": 5, "docs": 5, "integ": 9},
 "finish": {"compile": 5, "unit": 9, "docs": 7, "integ": 15}}

At time 5 integ is more urgent than docs but its group is full, so docs takes the third worker.

Part 4 (stretch) — Critical path queries on large pipelines (SCHED-377)

Goal: capacity planning needs the theoretical minimum time for any task, instantly, while pipelines with thousands of tasks keep growing.

Rules

1. earliest_finish(task_id) is the earliest time the task can finish with unlimited workers and ignoring group limits: its duration plus the largest earliest_finish among its dependencies (0 if it has none). Unknown id: error: task not found.
2. critical_path() returns the longest chain of tasks (sum of durations) as ids, first to last. It ends at the task with the greatest earliest_finish (ties: smaller id) and walks backwards, at each step choosing the dependency with the greatest earliest_finish (ties: smaller id). An empty graph returns [].
3. Queries can be interleaved with add_task and asked many times; hidden inputs contain pipelines where recomputing every path per query is far too slow.

Example (the pipeline above): earliest_finish("test") is 13, earliest_finish("package") is 8, and critical_path() is ["compile", "test"].

Notes

• graph.py, queueing.py and validation.py are known-good, and stats.py is unused by the operations.
• You may use the AI assistant freely. Later parts must not break earlier ones; the hidden tests re-check earlier behavior as well.
• Parts 1-3 done well is a strong result; Part 4 is a stretch.