Once the affected set of projects is known, how do build tools schedule the resulting build/test/lint tasks — what determines which tasks run in parallel versus which must wait, and how does this scale across multiple CI machines?

## From affected set to task graph Once the affected set of projects is fixed, the next problem is ordering and parallelizing the actual work — building, testing, and linting each affected project. This is governed by a **task graph**, which is a finer-grained structure than the project dependency graph used for affected detection, though it's derived from it. The task graph has two sources of ordering constraint: - The first is **inter-project**: if project A depends on project B, then A's build task can't start until B's build task (or at least B's build artifact) is available, because A needs to compile against B's output. - The second is **intra-project**: within a single project, a test task typically depends on that project's own build task completing, and a lint task might run independently of both. Combining these constraints across every affected project produces a single task-level **directed acyclic graph**, where nodes are individual tasks (not projects) and edges are 'must complete before.' ## Topological execution and DAG width Given this DAG, the scheduler's job is a topological execution: at any moment, every task whose predecessors have all completed is eligible to run, and eligible tasks are dispatched to whatever workers are free. This means parallelism isn't just 'run N tasks per core' — it's bounded by the **DAG's width**, i.e., how many tasks are simultaneously eligible at each point in the execution. - Early in a run, if many affected projects have no inter-dependencies, dozens of build tasks can start at once. - Later, if several projects all depend on one shared library, execution narrows to a bottleneck until that library's task finishes, then fans back out. ## The critical path The key trade-off scheduling has to manage is the **critical path**: the longest chain of sequentially-dependent tasks through the graph. No matter how many workers are available, total wall-clock time can't drop below the critical path's cumulative duration, because those tasks are strictly ordered. A monorepo where every project transitively depends on one 'core' library has a critical path that funnels through core's build/test every single run, capping the benefit of adding more parallel workers — this is a common real bottleneck teams hit and a reason for splitting overly-central libraries or optimizing their build/test time specifically, since shaving time off the critical path helps every downstream run, while shaving time off a parallel branch only helps if it was itself the local bottleneck. ## Scaling out to a fleet At CI-fleet scale, this scheduling problem extends beyond a single machine's cores to distributing tasks across many CI agents or a remote-execution cluster. Tools like Bazel's remote execution API, or cloud task-distribution services (Nx Cloud, BuildBuddy, or custom sharding built on top of GitHub Actions/Buildkite matrix jobs), take the eligible-task set and dispatch it to a pool of workers rather than local cores, so the effective parallelism scales with fleet size rather than one machine's CPU count. This introduces its own scheduling concerns: - workers need the right toolchain/environment; - task dispatch has network and queueing latency; - load balancing matters — a naive round-robin dispatch can leave one worker with a string of slow tasks while others sit idle, so production schedulers often use estimated task duration (from historical run data) to bin-pack tasks more evenly, a technique sometimes called 'historical timing-based sharding.' ## What the tools actually do A concrete real-world pattern: Nx Cloud's distributed task execution splits the affected task graph across a pool of agent machines, respecting the same dependency-ordering constraints, and uses prior run durations to balance the split so no single agent becomes the long pole. Bazel's remote execution similarly fans build/test actions out to a worker pool while enforcing the action graph's ordering via input/output artifact dependencies. In both cases, the underlying discipline is identical to single-machine scheduling — topological ordering plus eligible-task dispatch — just with network-distributed workers substituting for local threads, and the critical path remaining the hard floor on total pipeline time regardless of how many workers you add.