Scheduling Complex Workflows with Directed Acyclic Graph Dependencies

This direction is split into other directions: precedence-constrained scheduling. Its last version stays readable and citable here.

Version 1 of 1301 papers339 conceptsfrozen 2026-10-04

Most modern computing systems—from cloud schedulers to Large Language Model (LLM) orchestrators—treat tasks as independent units of work. In this "bag of tasks" model, a scheduler simply picks an available job and assigns it to an idle resource. However, real-world applications rarely work this way. Whether it is a scientific simulation, a multi-stage machine learning pipeline, or an autonomous agent calling multiple APIs, tasks are almost always linked by data and logic.

The research direction emerging across these fields is the shift toward dependency-aware orchestration, where workflows are modeled as Directed Acyclic Graphs (DAGs). In a DAG, nodes represent individual tasks, and edges represent the dependencies between them: Task B cannot start until Task A provides its output.

The Failure of the Independence Assumption

When a system assumes tasks are independent, it ignores the "cascading" nature of real-world workflows. This leads to several critical failures:

  1. Propagation of Latency: In "agentic" workflows, such as Text-to-SQL systems, a single user query triggers a chain of dependent LLM calls. As You Peng and colleagues demonstrate with HEXGEN-TEXT2SQL, standard inference systems like vLLM fail to account for these sequences. A delay in an early "planning" stage propagates through the entire pipeline, causing the final response to miss its deadline.
  2. The "Graph Gap" in Reasoning: Even advanced LLMs struggle to move from listing subtasks to correctly mapping their dependencies. Shuofei Qiao and the team behind WORFBENCH identified a significant "graph gap": models often fail to distinguish between tasks that can run in parallel and those that must remain sequential.
  3. Inefficient Resource Allocation: In heterogeneous clusters, simple heuristics like "min-min" or "shortest job first" often fail because they don't account for the communication costs of moving data between dependent tasks. Qi Qi 0001 and Zhanyu Ma highlight that in vehicular edge computing, optimizing for immediate task latency without considering the subsequent cost of moving data to the next node in the DAG results in poor end-to-end performance.

Modeling Workflows as Graphs

To solve these issues, researchers are moving toward models that explicitly represent the structure of the work. This involves two primary components: Task Graphs and Tool Graphs.

In scientific computing, César O. Díaz and Samee U. Khan argue that modeling inter-task dependencies as DAGs is essential for energy-aware scheduling. Without this structure, a scheduler might power down a node that is actually a critical bottleneck for a dozen downstream tasks.

For autonomous agents, the challenge is "tool-use" logic. Keyan Ding and the SciToolAgent team use Knowledge Graphs to navigate tool dependencies. Similarly, Yongliang Shen introduced TaskBench, which uses a "Tool Graph" to ensure that the output of one specialized scientific tool is correctly formatted and passed as the input to the next.

Intelligent Scheduling Mechanisms

Once a workflow is modeled as a DAG, the problem becomes one of global optimization rather than greedy local decisions. Several strategies have emerged:

  • Attentive Reinforcement Learning: Mukoe Cheong and Honguk Woo developed SCARL, which uses attentive embeddings to capture job-machine interdependencies. By "attending" to the structure of the DAG, the scheduler can prioritize tasks that sit on the "critical path"—the longest sequence of dependent tasks that determines the total execution time.
  • Graph Neural Networks (GNNs): Aditya Paliwal and researchers at Google/DeepMind introduced REGAL, which uses GNNs to optimize computation graphs. Unlike traditional methods that take hours to optimize a single model, REGAL learns the underlying patterns of graph dependencies, allowing it to generalize to new, unseen workflows in seconds.
  • Space-Time Planning: Timothy Zhu proposed TetriSched, which uses a "Space-Time Request Language" to plan ahead. Instead of reacting to tasks as they arrive, it treats the cluster's future capacity as a resource to be reserved, ensuring that multi-stage pipelines have the necessary hardware available exactly when their preceding stages finish.

The Intuition: From Queues to Pipelines

The core intuition behind this research is that scheduling is not about managing tasks; it is about managing the flow of data.

In a traditional system, a task is like a person waiting in a single-file line. In a dependency-aware system, a task is like a component on an assembly line. If the person at Station A is slow, Station B sits idle regardless of how many "resources" are available. By modeling these dependencies as DAGs, systems can finally "see" the assembly line, allowing them to pre-allocate resources, parallelize independent branches (as explored in PARALLELPROMPT by Keshav Santhanam), and ensure that the entire workflow—not just the individual task—reaches completion as efficiently as possible.

Papers in this version

Showing 60 of 301 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_scheduling_complex_workflows_with_direct_808ffe66,
  title = {Scheduling Complex Workflows with Directed Acyclic Graph Dependencies},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scheduling-complex-workflows-with-directed-acyclic-graph-dependencies/rdr_808ffe66f6a94ea1909f3a600c42dce1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_scheduling_complex_workflows_with_direct_808ffe66_v1,
  title = {Scheduling Complex Workflows with Directed Acyclic Graph Dependencies},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scheduling-complex-workflows-with-directed-acyclic-graph-dependencies/rdr_808ffe66f6a94ea1909f3a600c42dce1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}