Scheduling a task dependency graph across AI coding agents

What does scheduling theory say about dispatching a dependency graph of tasks to a small pool of two to five AI coding agents? AR Labs researched that question in October 2026. The findings shape how Taskgraph picks the next step (the ready item heading the longest remaining chain) and why it treats an item with no dependency edges as not yet assessed. The report draws on the list-scheduling, critical-path and resource-constrained project scheduling literature, and on the scheduling practice of PMI, Microsoft Project, Primavera P6 and the DCMA 14-point schedule assessment.

The short answer

Scheduling theory treats "waves" as a display device, not as a dispatch policy. The standard way to run a dependency graph on a small fixed pool of workers is list scheduling: keep a ready set of items whose own blockers have all closed, rank it by a priority (most often the length of the longest remaining path to the end of the graph, which is the critical path), and start the highest-ranked ready item whenever a worker is free. Graham proved that any such greedy, never-idle dispatch finishes within a factor of (2 − 1/m) of the best possible schedule on m workers; a policy that holds wave N until every item in wave N-1 has closed loses that guarantee, because one slow item in a wave idles the whole pool.

Project-management practice agrees on the other three problems found in practice. Links on summary tasks (epics) are discouraged by PMI and unsupported by Primavera P6, and where tools do allow them, the link binds every descendant. "Can't run at the same time, either order works" is a resource or mutual-exclusion constraint, which the resource-constrained project scheduling literature models separately from precedence and resolves at dispatch time. A task with no links at all is flagged as a schedule-quality defect ("missing logic"), not read as deliberately parallel.

1. Layering a DAG into waves

A layering assigns each node a level such that every edge points from a lower level to a higher one. The literature on drawing and scheduling DAGs offers two standard algorithms that trade height (number of waves) against width (items per wave).

Longest-path layering puts each node on the level equal to the length of the longest chain of predecessors above it, which is the same as "as soon as possible" placement. It produces the minimum possible number of levels, and it is the exact solution of the static scheduling problem when the number of workers is unlimited (Healy and Nikolov, "How to Layer a Directed Acyclic Graph", Graph Drawing 2001). Its weakness is width: it piles every source node into level 1, so the first wave is typically far wider than the worker pool and later waves are thin. A task-graph viewer that layers this way shows every unlinked item crowded into wave 1.

Coffman–Graham layering was designed for multiprocessor scheduling with a width cap W. It orders nodes lexicographically by their successors and then fills levels no wider than W. The result has height at most (2 − 2/W) times the minimum height achievable at width W, and it is exactly optimal for W ≤ 2 (Healy and Nikolov; Nikolov, Tarassov and Branke, "In search for efficient heuristics for minimum-width graph layering with consideration of dummy nodes" / "Graph layering by promotion of nodes", Discrete Applied Mathematics). The underlying result is Coffman and Graham's 1972 paper "Optimal scheduling for two-processor systems" (Acta Informatica 1:200–213).

The practical difference: longest-path layering answers "what is the shortest possible sequence of rounds if workers were unlimited", while Coffman–Graham answers "what rounds of at most W items should I run". With a cap of 2-5 agents, only a width-bounded layering describes something a pool can actually execute, but both still impose the barrier problem described in section 2. Neither layering accounts for item duration; both treat every item as unit work.

2. Critical path and list scheduling on a bounded pool

The critical path method (CPM, Kelley and Walker, 1959) and PERT compute, for each activity, the earliest and latest start times consistent with the dependency graph; activities whose earliest and latest times coincide (zero float) form the critical path, which sets the minimum possible project duration when resources are unlimited. CPM alone ignores worker limits.

List scheduling adds the worker limit. Each node gets a priority, and whenever a worker becomes free the scheduler starts the highest-priority node whose predecessors are all finished. The classic priority is the node's "level" or "bottom level": the sum of durations along the longest path from that node to an exit node. Hu's 1961 algorithm (highest level first) is optimal for unit-time tasks on tree-shaped graphs, and HLFET (Highest Level First with Estimated Times) generalises it to arbitrary durations (Kwok and Ahmad, "Static scheduling algorithms for allocating directed task graphs to multiprocessors", ACM Computing Surveys 31(4), 1999). Kwok and Ahmad's benchmark of algorithms for a bounded number of processors ranked them, best first, MCP (Modified Critical Path), ISH, DLS, HLFET, ETF and LAST; all of the leaders are critical-path-priority list schedulers (Kwok and Ahmad, "Benchmarking and comparison of the task graph scheduling algorithms", JPDC 1999, via Springer citation). Their DCP algorithm recomputes the critical path as the schedule is built (Kwok and Ahmad, "Dynamic Critical-Path Scheduling").

The key guarantee is Graham's (Bell System Technical Journal 1966; SIAM J. Applied Math 1969): any list schedule that never leaves a worker idle while a ready task exists finishes within (2 − 1/m) of the optimal makespan on m workers, whatever the priority order. The proof works because at every instant either all m workers are busy or some task on the critical chain is running, so the makespan is at most total work / m plus the critical path length. Priority choice (critical-path-first) then improves typical results well beyond the bound.

Waves as barriers break that argument. Under a barrier policy, a worker can sit idle while a ready task exists, because the task belongs to wave N and one item of wave N-1 is still running. The makespan becomes the sum, over waves, of that wave's slowest batch, rather than roughly the larger of the critical path and total work / m. This is the bulk-synchronous parallel (BSP) trade-off in parallel computing: supersteps separated by global barriers are easy to reason about, but every processor waits for the slowest one at each barrier (Papp et al., "DAG Scheduling in the BSP Model", 2023; Bender and Phillips, "Scheduling DAGs on Asynchronous Processors", SPAA 2007). How much worse it is depends on how uneven durations are within a wave, so the literature gives no single ratio. A worked illustration (constructed for this report, not from a source): with two workers, wave 1 = {A: 10 units, B: 1 unit}, wave 2 = {C: 1, D: 1, E: 1} where only C depends on A. Streaming dispatch runs B, D, E on the second worker while A runs and finishes C at time 11. The barrier policy finishes at 10 + 2 = 12, and the gap grows with every additional wave containing one long item; in the limit the barrier schedule approaches the number of waves times the longest item, while the streaming schedule stays bounded by Graham's inequality.

For coding agents, durations are unknown and highly variable, which is exactly the regime where barriers waste the most capacity. Graham's bound needs no duration estimates, so streaming dispatch keeps its guarantee even when the priority is computed on unit weights (longest chain of remaining items).

3. Hierarchical precedence: links on summary tasks and epics

Tools disagree on whether a dependency can attach to a summary task, and practice guidance converges on "don't".

Microsoft Project allows links on summary tasks and enforces them on every descendant: if Summary 1 is a predecessor of Summary 2, no subtask of Summary 2 can start before Summary 1 (all of its subtasks) finishes, and Project refuses links that would then form a cycle, for instance a subtask under Summary 2 feeding a subtask under Summary 1 (Stakeholdermap, "Why you shouldn't link summary tasks"). The same page quotes the PMI Practice Standard for Scheduling: "It generally is not recommended to use links on summary activities because the logic can be difficult to follow and the practice may not be supported by all scheduling tools." MPUG lists the consequences as false gaps, circular-reference errors and the loss of overlap between phases, and identifies the root error as linking phases when the real dependency is between specific activities: "it isn't phase 1 that is needed for phase 2. It's the approved PID that is needed for the starting task" (MPUG, "7 Incorrect Ways to Use Microsoft Project: Using Predecessors in Summary Tasks"). A common accidental source is promoting a task to a summary by indenting work under it and leaving its old links in place (Tensix, "Microsoft Project Summary Tasks Dependencies").

Primavera P6 has no logic on WBS nodes at all. Its WBS Summary activity derives its start and finish from the activities sharing its WBS code and is "the only activity type in Primavera P6 that works sans logic" (Primavera Scheduling, "WBS Summary"). P6 users who need a phase-level link model it with start and finish milestones inside the phase, which every child then links to explicitly.

The resulting semantics, where a tool honours container links at all, are: "X is blocked by epic E" means X waits for every descendant of E; "epic E is blocked by Y" means every descendant of E waits for Y (children inherit the container's blockers). Both are expansions to leaf-level edges. The recommended practice is to perform that expansion explicitly, or better, to replace the container link with links to the specific leaf or milestone actually needed, because blanket expansion over-constrains the schedule. We could not confirm OmniPlan's group-dependency semantics from primary documentation (its documentation URL now redirects to a generic support index); treat that as an open gap.

4. Mutual exclusion versus precedence

Scheduling theory separates two kinds of constraint. A precedence constraint (conjunctive arc) says j cannot start until i finishes. A resource constraint says certain activities cannot overlap because together they exceed a capacity; for a capacity-1 resource this reduces to a disjunctive pair, "i before j or j before i, scheduler's choice". The resource-constrained project scheduling problem (RCPSP) is the general model (Brucker, Drexl, Möhring, Neumann and Pesch, "Resource-constrained project scheduling: Notation, classification, models, and methods", EJOR 112, 1999; Hartmann and Briskorn, "A survey of variants and extensions of the RCPSP", EJOR 207, 2010).

The literature's terminology fits the file-conflict case (two items that must not edit the same files at once) directly. A "minimal forbidden set" is a set of activities with no precedence between them that cannot all run at once because of a resource limit. Disjunctive-arc methods resolve forbidden sets by adding an arc in one direction, and the choice of direction is the scheduling decision; committing to it in advance, before durations and progress are known, throws away the option (Brucker et al. 1999). The job-shop disjunctive graph (Roy and Sussmann, 1964) uses the same two-arc-type structure. In a list scheduler, the standard way to handle a resource is the serial or parallel schedule-generation scheme: a ready task starts only if the resource it needs is free, otherwise it waits, and whichever of the conflicting pair becomes ready first goes first (Hartmann, "Heuristic Algorithms for Solving the RCPSP").

For a pool of coding agents this means a write conflict on shared files should be recorded as a lock (a named resource of capacity 1, such as a file or module path) rather than a blocks edge. Forcing a precedence edge lengthens the critical path artificially, can create a false chain in the wave view, and removes the scheduler's ability to start whichever item is ready first.

5. Unknown versus known-independent edges

Schedule-quality standards treat an activity with no predecessor or no successor as a defect to be fixed, not as evidence of independence. The DCMA 14-Point Assessment, the US Defense Contract Management Agency's schedule health check, makes "missing logic" its first check: activities without a predecessor (other than the project start) or without a successor (other than the project finish) are "open ends" and should be under 5% of incomplete activities (Tensix, "Primavera P6 EPPM and the DCMA 14-Point Assessment"; ScheduleLens, "DCMA 14-Point Assessment"). Primavera's built-in Check Schedule report flags the same condition (Taradigm, "Check Schedule Report in Primavera P6").

The convention behind the check is that every real activity connects to a start milestone and an end milestone, so "no dependencies" is always stated explicitly as "depends only on project start". A missing link therefore always means "not yet assessed". Scheduling tools have no separate flag for "assessed and independent"; the explicit start-milestone link plays that role. We found no primary source that models unassessed edges probabilistically for dispatch; the practical answer in the literature is to block on assessment.

Implications

The findings imply the following rules for a tool that builds waves and dispatch queues from a dependency graph of agent tasks.

Dispatch by ready set, not by wave. An item becomes eligible the moment all of its own effective blockers close and its locks are free; a free agent slot takes the highest-priority eligible item. Keep waves only as a display of graph depth.

Rank eligible items by critical-path priority. Compute each item's bottom level as the length of the longest chain of open items that depend on it, counting each item as one unit unless a size estimate exists, and dispatch the highest first. Break ties by number of direct dependents. Show the critical path (the longest chain) in the task-graph viewer.

When showing waves, use a width-capped layering. Coffman–Graham with W equal to the agent cap gives rounds the pool can actually run, while longest-path layering gives the theoretical minimum depth. Label which one is shown.

Expand container edges to leaves before computing anything. "X blocked by epic E" becomes "X blocked by every open descendant of E"; "epic E blocked by Y" becomes "every descendant of E blocked by Y". Then lint each container edge as a smell and suggest replacing it with an edge to the specific leaf actually needed, following PMI and P6 practice. Reject any expansion that creates a cycle and report the offending pair.

Model file conflicts as locks, not edges. Give each item a declared write set (files or module paths); two items whose write sets overlap may not run concurrently, and whichever is ready first takes the lock. Keep blocks edges for real precedence only, and offer a migration that converts existing conflict-only edges to locks.

Treat no edges as unassessed. Do not place an item with no edges into the dispatchable set by default. Require an explicit "independent" assertion (the equivalent of linking to the project start milestone) before an unlinked item is eligible, and report the share of open items without assessed logic as a health metric, with the DCMA 5% threshold as a reference point.

Re-plan on every close. Recompute eligibility and priorities when any item closes, reopens or gains an edge, as in dynamic critical-path scheduling, rather than freezing a plan at the start of a run.

Sources not reached

OmniPlan's handling of group dependencies was not verified from primary documentation. Graham (1966/1969), Hu (1961), Coffman and Graham (1972), Kelley and Walker (1959) and Roy and Sussmann (1964) are cited from standard knowledge of the field and through the secondary sources linked above; their original papers were not fetched in this pass.