Multi-Objective Scheduling of LLM-Based Multi-Agent Workflows in Cloud Computing

Multi-Objective Scheduling of LLM-Based Multi-Agent Workflows in Cloud Computing Goshgar Can Ismayilov Istanbul, Turkey goshgar.ismayilov@boun.edu.tr

arXiv:2611.13740v1 [cs.DC] 10 Nov 2026

Abstract Large language models (LLMs) have been increasingly composed into multi-agent workflows to accomplish complex and multi-step tasks. As the open-weight models continue to close the performance gap with the proprietary ones, model parameters are becoming a less significant source of competitive advantage in the artificial intelligence market. Yet how these models are efficiently scheduled onto distributed infrastructure such as the cloud, with respect to overall latency, monetary cost and resource utilization, remains largely unaddressed in the literature despite being an increasingly critical problem. Existing agentic workflow frameworks mostly focus on output quality and task success rates over popular benchmarks, rarely accounting for execution dynamics of LLM-based agents such as inference latency, computation power of heterogeneous resources, cloud-specific billing period and resource provisioning overheads. Therefore, this paper formulates multi-agent scheduling in cloud computing as a multi-objective optimization problem that jointly minimizes makespan and cost while maximizing resource utilization. Building on this formulation, we propose MO-SAIC (Multi-Objective Scheduling of Multi-Agent Workflows in Cloud Computing), a scheduling framework comprising four multi-objective schedulers with Non-Dominated Sorting Genetic Algorithm II (NSGA-II), Weighted-Sum Genetic Algorithm (W-GA), a multi-objective adaptation of Heterogeneous Earliest Finish Time (MO-HEFT) and a random baseline (RAND). We evaluate the schedulers from the workflow scheduling, multi-objective optimization and system perspectives to measure their overall performance, quality of their Pareto-optimal fronts and impacts of workflow topology, cloud resource composition and scalability parameters. We report the experimental results with their statistical significance via the Wilcoxon test. Lastly, we discuss the limitations of MO-SAIC as well as future research directions.

Keywords Large Language Models, Multi-Agent Workflows, Workflow Scheduling, Multi-Objective Optimization, Cloud Computing, Evolutionary Algorithms

1

Introduction

Consider an analogy from the history of cryptography. The field spent its early years as a state secret where advantage depended on which government could keep the cryptographic techniques hidden the longest through the mid-twentieth century. The decades since have reversed this trend, especially with the emergence of public-key cryptography. After that shift, security came to rest not on hiding the techniques but on protecting comparatively small secret keys. This transition follows the famous Kerckhoffs’s principle [1], stating that a cryptosystem should not rely on the secrecy

of the algorithm. We believe that large language models and agentic systems are currently heading toward an analogous transition. As open-weight models continue to close the performance gap with proprietary ones and model architectures are increasingly shared, model parameters are becoming a less significant source of competitive advantage. What increasingly differentiates is becoming not which models are used but how they are used at scale with respect to the efficient management of overall latency, cost and resource utilization. Rather than the model layer of artificial intelligence, the operational layer will be the harder challenge for large organizations, making the scheduling of agentic workflows on distributed infrastructures an increasingly critical research problem. LLMs have rapidly progressed from static text generators to autonomous agents with advanced capabilities of planning, reasoning, invoking external tools and acting on their own. Further techniques for LLMs including tool-augmented generation [2] and interleaving of reasoning and acting [3] have enabled these agents to actively query APIs, execute code and retrieve information to complete complex tasks. They often chain together many such steps instead of acting on a single request in isolation. This conceptual shift in LLMs has also been documented across a rapidly growing body of survey literature [4]. However, all these autonomous actions consume real computational resources in the background, incurring latency and cost. As agents are integrated into production systems at increasing scale, their total operational footprint has become a significant concern to address in its own right. A single LLM-based agent is rarely sufficient for complex and multi-step tasks, which has led to composing multiple specialized agents into multi-agent workflows. An increasing number of works in the literature address the automation and optimization of this multi-agent workflow composition. For instance, AFlow [5] employs a Monte Carlo tree search technique to iteratively sample, evaluate and refine different workflows. EvoFlow [6] instead evolves a diverse population of workflows based on an evolutionary algorithm with niching solution selection. However, once workflow topology has been fixed, no prior work has sufficiently addressed how its agents should be effectively assigned to and executed on physical cloud resources. In addition, while scheduling a singleagent system is relatively straightforward, the same is not true for multi-agent systems since such systems allow distinct agents to run on entirely separate resources. This gap motivates the problem of multi-agent workflow scheduling in distributed systems [7]. Scheduling traditional workflows across a pool of resources is not a new problem in the literature. Multi-objective evolutionary algorithms, most notably NSGA-II [8], have provided a technique to search for Pareto-optimal trade-offs when two or more objectives (e.g., makespan and cost) cannot be simultaneously minimized.

• Extensive experimental study. We extensively evaluate these four schedulers under various test scenarios to measure: (i) their overall performance relative to a random baseline scheduler; (ii) quality of their Pareto-optimal fronts; (iii) effects of workflow topology with changing size, depth and width; and (iv) effects of cloud resources with resource size and CPU/GPU pool composition. In our experiments, we use several performance measures from three distinct perspectives: (i) optimization objectives, resource load imbalance, distinct resource count for the workflow scheduling perspective; (ii) number of non-dominated solutions, Schott’s spacing, hypervolume and visual Pareto-optimal fronts for the multi-objective perspective and (iii) scheduling runtime for the system perspective. The statistical significance is shown via Wilcoxon rank-sum test across independent runs on distinct workflows. • A further discussion of limitations and future directions. We also discuss the current assumptions and limitations of MO-SAIC against the practical requirements for production deployments and the potential research directions to extend this research.

In this respect, NSGA-II has been applied extensively to workflow scheduling in cloud computing [9, 10] for the optimization of several objectives including makespan, cost, utilization, energy consumption, reliability and degree of imbalance. However, existing scheduling techniques are primarily designed for traditional workflows (e.g., Montage in astronomy [11]), not for agentic workflows where they do not consider the inherent characteristics of agents (e.g., inference time, tool calling time, output token size). Additionally, agents increasingly require heterogeneous CPU and GPU instances rather than a CPU-only pool. Figure 1 illustrates the distinction between the single-objective and multi-objective scheduling where the single-objective scheduler commits to a single solution purely via makespan without evaluating potential tradeoffs even when it is extremely costly. The multi-objective scheduler instead offers multiple solutions that minimize latency, minimize cost or maximize resource utilization. This clearly shows that multiagent workflow scheduling is inherently a multi-objective problem. Therefore, we position our work precisely at this intersection.

1.1

Contributions 1.2

This paper makes the following contributions to the literature:

Organization

The remainder of this paper is organized as follows. Section 2 reviews the literature of agentic workflows, traditional workflow scheduling and multi-objective optimization, by highlighting the current gap in the literature. Section 3 formally defines the problem as a multi-objective optimization problem, by specifying the optimization objectives and constraints as well as the agent, workflow, cloud and simulation models. Section 4 presents our multiobjective scheduling framework with four schedulers of NSGA-II, W-GA, MO-HEFT and RAND. Section 5 describes our experimental methodology for the benchmark workflows, performance measures and statistical methodology to compare the schedulers. Section 6 reports the experimental results and observations under various test scenarios. Section 7 discusses the current limitations and future directions while Section 8 concludes the paper.

• A formal model of multi-agent workflow scheduling in cloud computing. We formulate multi-agent workflow scheduling in cloud computing as a multi-objective optimization problem by considering the minimization of workflow makespan and monetary cost and the maximization of resource utilization. This problem abstracts four critical models: (i) a LLM-based agent model with inference latency, model-specific throughput, tool latency and output token size; (ii) a multi-agent workflow model through canonical agentic reasoning patterns including chain-of-thought, selfconsistency, tree-of-thought, debate and self-refine; (iii) a heterogeneous cloud resource model by unifying CPU and GPU computation capacity; and (iv) a workflow simulation model to execute workflows on resources by considering cloud-specific issues such as hourly-billing and resource (de)provisioning overheads. • MO-SAIC – a multi-objective scheduling framework. We propose a novel multi-objective multi-agent workflow scheduling framework for cloud computing, MO-SAIC, with the total of four schedulers: (i) a non-dominated sorting genetic algorithm scheduler (NSGA-II) as Pareto metaheuristic; (ii) a weighted-sum genetic algorithm scheduler (W-GA) as a scalarized metaheuristic; (iii) a multi-objective HEFT scheduler (MO-HEFT) as a classical list heuristic; and (iv) a random baseline scheduler (RAND) with no intelligence. • A controllable synthetic workflow generator. We employ a parametric and synthetic multi-agent workflow generator [12] to generate workflows with a diverse combination of canonical agentic reasoning patterns with given workflow size, depth and width. This generator allows controlled empirical study of how workflow topology affects scheduling decisions and quality.

2

Related Work

This section reviews the relevant works from the literature in three main perspectives including LLM-based agentic workflows, multiobjective workflow scheduling in cloud computing and agent scheduling for LLM serving.

2.1

LLM-Based Agentic Workflows

Many works in the literature have built LLM-based agentic workflows by composing multiple agents with heterogeneous roles and models. Wu et al. [13] present AutoGen, a general framework where multiple agents with different roles and tools communicate with one another to accomplish a common task collaboratively. Hong et al. [14] propose MetaGPT which employs standardized operating procedures from human software-engineering workflows for role-specialized agents. This enables agents to have human-like expertise and verify intermediate results to reduce error. Li et al. [15] design Camel to study how two agents autonomously and complementarily can cooperate toward a common goal with role-playing. 2

Single-Objective Scheduling

Makespan M(σ SO) Cost C(σ SO) Solution#1 (σ1SO): 32.4s $29.3 Solution#2 (σ2SO): 33.7s Solution#3 (σ3SO): 35.2s Solution#4 (σ4SO): 39.4s Solution#5 (σ5SO): 42.3s

Solution#1 (σ1SO)

Utilization U(σ SO) 15%

Population of Solutions

Agentic Work@low

Makespan M(σ MO) Cost C(σ MO) Solution#1 (σ1MO): 29.4s $5.1 Solution#2 (σ2MO): 40.9s $2.3 Solution#3 (σ3MO): 35.6s $4.4 Solution#4 (σ4MO): 45.9s $7.1 Solution#5 (σ5MO): 57.0s $6.1

Multi-Objective Scheduling

Solution#1 (σ1MO)

Utilization U(σ MO) 21% 18% 47% 13% 11%

Population of Solutions

Figure 1: Single-objective scheduling commits to a single solution purely via makespan (top) while multi-objective scheduling selects multiple solutions with distinct trade-offs across makespan, cost and utilization (bottom). Park et al. [16] populate an interactive sandbox environment with 25 generative agents that plan, act and reflect over time to produce emergent social behavior (e.g., planning their days, sharing news). For architectural characterization, construction techniques and application domains, Wang et al. [4] present broader perspectives. The multi-agent workflows all these frameworks orchestrate are mostly composed from a small set of canonical reasoning patterns. For instance, Wei et al. [17] show that eliciting intermediate reasoning states via chain-of-thought substantially improves LLM performance on complex tasks. Wang et al. [18] extend the concept by sampling multiple independent reasoning paths and aggregating into a single agent via self-consistency. Yao et al. [19] address explicit search over a tree of intermediate reasoning states rather than a linear reasoning. Du et al. [20] show that two agents debating and critiquing the answers of the other over several rounds improves factuality and reasoning. Madaan et al. [21] show that only a single agent iteratively critiquing its own response improves the response quality over several rounds. Finally, Yao et al. [3] propose ReAct, which interleaves reasoning traces with tool actions so that agents dynamically revise their reasoning based on their observations.

the search performance of NSGA-II [8] for workflow scheduling through a scoring criterion and a dynamic hierarchical population. Ismayilov et al. [10, 25] extend multi-objective workflow scheduling to a dynamic setting so that it reacts better to environmental changes such as resource failures by incorporating a neural network into NSGA-II. They consider makespan, cost, utilization, energy, reliability and degree of imbalance as objectives. To minimize energy consumption together with makespan and cost, Yassa et al. [26] combine a hybrid particle swarm optimization with the dynamic voltage and frequency scaling technique. This enables the underlying processors to operate in different voltage supply levels by changing their clock frequencies. Later, Verma et al. [27] hybridize particle swarm optimization with a budget and deadline-constrained HEFT especially for scientific workflows. Mohammadzadeh et al. [28] propose another hybrid algorithm based on the seagull and grasshopper optimization algorithms to jointly optimize makespan, cost, energy and throughput, now with resources from multiple cloud providers. Abazari et al. [29] broaden the set of objectives further to include the minimization of security risk in the cloud and the response time.

2.2

2.3

Multi-Objective Workflow Scheduling in Cloud Computing

Multi-objective optimization has been extensively applied to workflow scheduling in cloud computing, most commonly targeting the trade-off between makespan and monetary cost. Durillo et al. [9] adapt the classical HEFT heuristic [22] into MO-HEFT which is a Pareto-based list scheduling algorithm to maintain a set of partial scheduling solutions and measure its performance against synthetic and real-world workflows. Zhu et al. [23] instead propose a NSGAII-based evolutionary multi-objective metaheuristic for the joint optimization of the makespan and cost. Li et al. [24] later improve

Model and Agent Scheduling for LLM Serving

There exists a smaller and more recent group of works for scheduling of LLM executions across LLM engines. Luo et al. [30] propose Autellix which enriches schedulers with program-level statistics and minimizes end-to-end latency. Lin et al. [31] consider the data dependencies between consecutive LLM calls through semantic variables so that they can be co-scheduled. Jiang et al. [32] formally define the scheduling problem of LLM serving over a set of heterogeneous GPU resources as a constrained optimization problem. Griggs et al. [33] assign LLM calls to GPU resources with distinct 3

M. Every model 𝑚 ∈ M is characterized by a time-to-first-token (TTFT) latency 𝜙𝑚 (seconds) and a token generation throughput 𝜌𝑚 (tokens/second). Given an output size 𝑜 (𝛼) ∈ Z>0 (i.e., the number of tokens 𝛼 generates as response), its inference time 𝐿inf (𝛼) can be computed as:

prices and capabilities to reduce cost under a certain latency target. Ong et al. [34] focus on routing to two classes of models as strong models generating high-quality responses at a higher cost and weak models generating lower-quality responses but at a reduced cost. They present a training framework that dynamically select between these models during inference. Finally, the recent work [35] proposes HexAGenT as a workflow and heterogeneity-aware scheduling algorithm for the online workflow scheduling problem. Unlike these works, our focus is offline scheduling that assigns each agent to a cloud resource and executes the model on that instance while optimizing makespan, cost and utilization jointly.

3

𝐿inf (𝛼) = 𝜙𝑚 (𝛼 ) +

where it adds the time to stream the output after the initial token generation latency. During its execution, an agent might invoke external tool calls (e.g., for web search) from the finite set of tools Θ(𝛼) = {𝜃 1, . . . , 𝜃 𝑘 }. Each tool 𝜃 𝑖 is defined as:

Multi-Objective Multi-Agent Workflow Scheduling

𝜃 = (ℓ𝜃 , 𝑛𝜃 ) where ℓ𝜃 ∈ R>0 is the per-invocation latency and 𝑛𝜃 ∈ Z>0 is the number of times 𝛼 invokes it. Total tool latency is computed as: ∑︁ 𝐿tool (𝛼) = ℓ𝜃 · 𝑛𝜃

Formulating the multi-agent workflow scheduling problem requires the characterization of (i) the individual LLM-based agents, (ii) the agentic workflows as the composition of individual agents with a certain topology, (iii) the cloud computing as the infrastructure provider to run the workflows and (iv) the simulator to simulate the execution of the workflows in the cloud under certain conditions and constraints. Therefore, this section develops these models to culminate in a formal multi-objective optimization of the problem to be addressed. Refer to Table 1 for the mathematical notations used throughout this section and the remainder of the paper.

𝜃 ∈Θ(𝛼 )

where we assume the invocations as sequential and non-overlapping. In our experimental setting, tools are classified into two groups as the internal tools with low-latency and the external tools with relatively high-latency. Refer to Table 4 for the specifications of the models considered in this work. Note that this catalog serves solely to parameterize 𝜙𝑚 and 𝜌𝑚 with values for our simulation and our agent model itself remains independent of this particular set of models.

Table 1: Descriptions of common mathematical notations used throughout this paper.

3.2 Notation

Description

𝛼∈A 𝑟 ∈R cp(𝑟 )

An agent in the finite agent set A A cloud resource in the resource pool R Unified compute power of resource 𝑟

𝑋 𝜎 P 𝑀 (𝜎), 𝐶 (𝜎), 𝑈 (𝜎) 𝜎′ ≺ 𝜎 𝜎′ ⪯ 𝜎 𝐹 0 (P) 𝑅(𝜎)

Decision space of resource assignments A scheduling solution A population of candidate solutions Makespan, cost, utilization of 𝜎 𝜎 ′ Pareto-dominates 𝜎 𝜎 ′ weakly dominates 𝜎 Pareto-optimal front of P Set of cloud resources 𝜎 assigns agentic tasks

𝑓ˆ(𝜎) 𝑑𝑖 SS(𝐹 0 ) Λ(·) r = (𝑟 1, 𝑟 2, 𝑟 3 ) 𝜀 HV(𝐹 0 )

Min-max normalized objectives of 𝜎 in [0, 1] 3 Nearest-neighbor distance of front member 𝑖 Schott’s spacing of front 𝐹 0 Lebesgue measure (volume) Hypervolume reference point Hypervolume reference margin Hypervolume of front 𝐹 0

3.1

𝑜 (𝛼) 𝜌𝑚 (𝛼 )

Multi-Agent Workflow Model

A multi-agent workflow is a directed acyclic graph (DAG) 𝐺 = (A, 𝐸), where A is the finite set of agents and 𝐸 ⊆ A × A is a set of directed edges. Each edge (𝛼, 𝛼 ′ ) ∈ 𝐸 indicates that agent 𝛼 ′ depends on the output of agent 𝛼 and hence, 𝛼 must complete before 𝛼 ′ can start execution. For an agent 𝛼 ∈ A, we write pred(𝛼) = {𝛼 ′ ∈ A : (𝛼 ′, 𝛼) ∈ 𝐸} and succ(𝛼) = {𝛼 ′ ∈ A : (𝛼, 𝛼 ′ ) ∈ 𝐸} to define predecessors and successors, respectively. The workflows we generate are not arbitrary DAGs. Instead, they are composed of several canonical agentic reasoning patterns. A single-agent (SA) pattern is the simplest topology consisting of a single agent 𝛼 0 , serving as the atomic block for more complex pattern compositions. A chain-of-thought (CoT) pattern is a sequential chain of 𝑘 ≥ 2 agents 𝛼 0, . . . , 𝛼𝑘 −1 with (𝛼 𝑗 , 𝛼 𝑗+1 ) ∈ 𝐸 for 𝑗 ∈ {0, . . . , 𝑘 − 2}. In CoT, each agent refines the output of the previous agent. A self-consistency (SC) pattern is 𝑘 ≥ 2 agents 𝛼 0, . . . , 𝛼𝑘 −1 that execute in parallel and all merge into a single agent 𝛼𝑘 , with (𝛼 𝑗 , 𝛼𝑘 ) ∈ 𝐸 for 𝑗 ∈ {0, . . . , 𝑘 − 1}. A tree-of-thought (ToT) pattern introduces parallel exploration, with a single agent 𝛼 0 fanning out to 𝑘 ≥ 2 parallel agents, with (𝛼 0, 𝛼 𝑗 ) ∈ 𝐸 for 𝑗 ∈ {1, . . . , 𝑘 }. A debate (Db) pattern models adversarial multi-turn reasoning between two agents back-and-forth over 𝑟 ≥ 2 rounds. To achieve acyclicity, we unroll it into 2𝑟 distinct agent instances as 𝛼𝐴(1) , 𝛼 𝐵(1) , . . . , 𝛼𝐴(𝑟 ) , 𝛼 𝐵(𝑟 ) in sequence. Finally, a self-refine (SR) pattern is a chain of 𝑘 ≥ 2 agents that revises its own output over 𝑟 ≥ 2 rounds, which is similarly unrolled into 𝑟 copies of the 𝑘-agent chain. Figure 2 illustrates all these six patterns. A complete workflow is assembled by drawing multiple pattern instances and connecting them into a single weakly connected DAG

LLM-Based Agent Model

An agent is an LLM-driven computational system that acts autonomously through its own sequence of actions including inference and tool calling. Each agent in an agentic workflow 𝛼 ∈ A is assigned to a model 𝑚(𝛼) ∈ M from the space of available LLMs 4

3.3.1 CPU-Only Environment R ⊆ R cpu . This environment takes into account only the resources with no active GPU 𝑔𝑟 = 0. This deliberate limitation on resource heterogeneity naturally results in certain scheduling impacts. First, unlike the GPU-only environment, there is no hardware-driven improvement on latency and the schedulers cannot buy more speed for the critical-path agents and must instead rely more heavily on parallelizing agents across many resources. Second, per-hour prices of CPU-only resources are cheaper when compared to the resources with GPU, resulting in lower total resource costs at the end of the optimization. In addition, CPU-only resources span a finer-grained range of vCPU counts and prices, which gives the schedulers a more fine-grained makespan–cost trade-off. In Table 5, the specifications of the CPUonly instance families (M1, M3, M4, M5, M5D) considered are listed, spanning vCPU counts from 1 to 96, network bandwidth from 10 to 25 Gbps and hourly pricing from $0.044 to $5.424.

where the last agent of the previous pattern is linked to the first agent of the next pattern and additional edges are added between agents at random. The order in which the patterns are sequenced follows a first-order Markov chain with pattern-to-pattern transition probabilities. Therefore, the workflow is not said to be merely a disjoint union of isolated patterns. Each workflow is characterized by properties: size 𝑁 = |A| as the total number of agents; depth 𝑑 (𝐺) as the length of the longest path; and width 𝑤 (𝐺) as the largest number of agents at the same depth level. The construction of a workflow with given characteristics is feasible only when:
𝑤 (𝐺) + 𝑑 (𝐺) ≤ 𝑁 ≤ 𝑤 (𝐺) · 𝑑 (𝐺) + 1 where 𝑁 agents are distributed across 𝑑 (𝐺) + 1 depth levels and each agent in level ℓ > 0 is wired to at least one predecessor in level ℓ − 1 and each agent in level ℓ < 𝑑 (𝐺) to at least one successor in level ℓ + 1 and one level is sized to exactly 𝑤 (𝐺) agents.

3.3

3.3.2 GPU-Accelerated Environment R ⊆ R gpu . Every resource in this environment is GPU-accelerated 𝑔𝑟 > 0, offering more computational power per unit than a CPU-only environment. Here, agents complete their inference faster, compressing makespan toward the lower values. However, this compression is not free since GPUaccelerated resources incur considerably higher per-hour costs in return. Therefore, this environment challenges the schedulers to still find a meaningful cost–utilization trade-off once the makespan objective is largely satisfied by hardware alone. In Table 6, the specifications of the GPU-accelerated instance families (G4dn, G5, G6, G6e, G7, G7e, P4d, P4de, P5 and P5en) are listed, spanning several NVIDIA GPU generations, from the T4 through the H200.

Heterogeneous Cloud Model

A cloud resource is a virtualized and on-demand computation instance to which an agent can be assigned for execution. Each resource 𝑟 ∈ R is characterized by a tuple 𝑟 = (𝑣𝑟 , 𝑔𝑟 , 𝐵𝑟 , 𝑝𝑟 ), where 𝑣𝑟 ∈ Z ≥0 is the vCPU count, 𝑔𝑟 ∈ Z ≥0 is the vGPU count, 𝐵𝑟 ∈ R+ is the network bandwidth (Gbps) and 𝑝𝑟 ∈ R+ is the hourly ondemand price (USD/hour). For the total compute power of a resource, we unify CPU and GPU capacity into a single scalar via a weighted sum as: cp(𝑟 ) = 𝑤 𝑣 · 𝑣𝑟 + 𝑤𝑔 · 𝑔𝑟 where 𝑤 𝑣 , 𝑤𝑔 ∈ R+ are the weights for the relative contribution of a vCPU and a vGPU to inference. For instance, a CPU-only resource (𝑔𝑟 = 0) with 𝑤 𝑣 = 1 reduces cp(𝑟 ) to only its vCPU count exactly. From the available resources in the cloud, we compose three environments as CPU-only R cpu with 𝑔𝑟 = 0 for all 𝑟 , GPUaccelerated R gpu with 𝑔𝑟 > 0 for 𝑟 and CPU+GPU including all resources. When two dependent agents run on different resources, the output of the first agent must be transferred to the second over the network, subject to the available bandwidth. The bottleneck bandwidth between any two resources 𝑟𝑖 , 𝑟 𝑗 ∈ R is computed as:

3.3.3 CPU+GPU Environment R ⊆ R cpu ∪ R gpu . This environment considers both CPU-only and GPU-accelerated resources at the same time for agent assignment. This provides a broader scheduling since organizations generally provision elastic cloud capacity in practice and relax the schedulers to make workload-specific decisions about which agent runs on which resource. In return, this hardens the overall optimization since the schedulers now have to map an agent on a cheaper but moderate-throughput CPU resource or a more expensive but high-throughput GPU resource or their hybrid composition. For instance, an agent on the critical path might benefit more from a GPU to reduce latency for the agents immediately waiting on it. Consequently, achievable Pareto-fronts for this environment are likely to be more diverse, spanning the full range from all-CPU to all-GPU scheduling solutions and every combination in between.

𝐵(𝑟𝑖 , 𝑟 𝑗 ) = min(𝐵𝑟𝑖 , 𝐵𝑟 𝑗 ) where 𝐵(𝑟𝑖 , 𝑟 𝑗 ) is the bandwidth between 𝑟𝑖 and 𝑟 𝑗 . No network transfer occurs when two agents are hosted exactly on the same resource. In this work, we consider |R cpu | = 30 AWS EC2 CPU-only instances (see Table 5) and |R gpu | = 30 AWS EC2 GPU-accelerated instances (see Table 6). This resource catalog serves solely to parameterize 𝑣𝑟 , 𝑔𝑟 , 𝐵𝑟 and 𝑝𝑟 with concrete values for our simulation and our cloud model itself remains independent of this particular set of resources. Notably, our unified computation model treats CPU and GPU capacity as interchangeable, which is very straightforward. This might result in assigning large models to CPU-only resources. Although such assignments are impractical in real executions, they are admissible under our model which does not intend to capture real executions. For the sake of simplicity, no workflow-driven or cloud-driven uncertainty (e.g., fluctuation in inference latency, network congestion) is considered in this work.

3.4

Workflow Simulation Model in Cloud

Given a resource assignment 𝜎 : A → R, the simulation model executes that assignment by considering the characteristics of workflows and cloud computing to derive makespan, cost and utilization. In this paper, we assume a non-preemptive execution where an agent runs to completion without interruption once it starts on a resource. An agent must jointly satisfy two conditions to start: dependency readiness where all of its predecessors must finish and transfer their data and resource availability where the resource must be free of any execution. For every agent 𝛼, its ready time RT[𝛼] is 5

0

0

0

1

2

3

1

3

2

(a) Single-Agent (SA).

(b) Chain-of-Thought (CoT).

(c) Self-Consistency (SC). (1) 0

(1) 1

(1) 2

(2) 0

(2) 1

(2) 2

1 (1) 0 0

(2) 0

2 (1) 1

(2) 1

3

(d) Tree-of-Thought (ToT).

(e) Debate (Db).

(f) Self-Refine (SR).

Figure 2: Canonical agentic reasoning patterns: (a) single agent: atomic block; (b) chain-of-thought: sequential chain that refines output agent by agent; (c) self-consistency: parallel agents merged into a consensus agent; (d) tree-of-thought: one agent fanning out into multiple parallel agents; (e) debate: two agents debating back and forth over multiple rounds and (f) self-refine: chain of agents revising output over multiple rounds. is scalable by cp(𝑟 ). On the other hand, the tool term 𝐿tool (𝛼) is always a fixed floor that no resource can reduce. A scheduler can therefore compress the execution time of an individual agent only within a narrow band. The billing period of a resource starts when it is provisioned and closes whenever it is de-provisioned. Note that de-provisioning also consumes a Gaussian-distributed termination delay as TermTime(𝑟 ) before the period actually closes. Every billing period is charged in full hours, rounded up with an hourly on-demand price. The workflow completes when all exit agents Aexit = {𝛼 ∈ A : succ(𝛼) = ∅} have finished their executions.

the earliest moment the dependency readiness is satisfied:   RT[𝛼] = ′ max FT[𝛼 ′ ] + 𝑜˜ (𝛼 ′ )/𝐵(𝜎 (𝛼 ′ ), 𝜎 (𝛼)) 𝛼 ∈pred(𝛼 )

where FT is the finish time and RT is zero if 𝛼 has no predecessors and the transfer term is zero when 𝛼 ′ and 𝛼 share the same resource. Here, 𝑜˜ (𝛼 ′ ) is the data size of the output of 𝛼 ′ , obtained as 𝑜˜ (𝛼 ′ ) = 4 · 𝑜 (𝛼 ′ ) bytes. Here, we assume that one token corresponds to four single-byte characters of English text. Resource availability needs some exclusive cases to be properly managed. If the resource 𝑟 has never been used before, it must first be provisioned with a Gaussian-distributed initialization delay InitTime(𝑟 ) before 𝛼 can start. If 𝑟 has been used before but its billing period is closed, it must be re-provisioned exactly as if it were new, by incurring InitTime(𝑟 ) again. Lastly, if 𝑟 is still actively provisioned and free, 𝑟 can start a new agent task with no additional delay. Once the start time ST[𝛼] of 𝛼 is set with these cases, its execution time can be computed as:

3.5

Multi-Agent Workflow Scheduling as Multi-Objective Optimization

A multi-objective optimization problem (MOP) is a problem with two or more objectives where at least two objectives are in conflict. Without loss of generality, a MOP over a decision space 𝑋 can be formally defined in the following way:
𝑇 min 𝐹 (𝑥) = 𝑓1 (𝑥), . . . , 𝑓𝑘 (𝑥) ,

ET[𝛼] = 𝐿inf (𝛼)/cp(𝑟 ) + 𝐿tool (𝛼) where the inference time is scaled by the resource computation power. Its finish time is FT[𝛼] = ST[𝛼] + ET[𝛼]. Figure 3 shows this decomposition for the maximum single-agent budget. Only the inference term 𝐿inf (𝛼)/cp(𝑟 ) depends on the resource an agent runs on. Even for the highest TTFT in the model catalog together with the maximum output length, only about 30% of the budget at cp(𝑟 ) = 1

𝑥 ∈𝑋

s.t. 𝑔𝑖 (𝑥) ≤ 0, 𝑖 = 1, . . . , 𝑝, ℎ 𝑗 (𝑥) = 0, 𝑗 = 1, . . . , 𝑞, where 𝐹 : 𝑋 → R𝑘 , 𝑘 ≥ 2, maps each solution 𝑥 in decision space into a point in objective space R𝑘 under the inequality and equality 6

Maximum single-agent execution time (s)

800

Time to first token (scales with cp(r)) Output token generation (scales with cp(r)) Tool-call latency (fixed, independent of cp(r))

719 s (30% scalable)

700

610 s (18% scalable)

600

527 s s (5% scalable) (3% 514 scalable)

500

505 s 502 s 501 s (<1% scalable) (<1% scalable) (<1% scalable)

irreducible tool-latency floor = 500 s

400 300 200 100 0

scalable budget 219 s of 719 s 1 m1.small

2 m1.large

8 m5.2xlarge

16 m5.4xlarge

48 96 256 m5.12xlarge m5.24xlarge p5en.48xlarge

Resource compute power cp(r)

Figure 3: Single-agent execution time against resource computation power cp(𝑟 ). The TTFT and the output-token generation time scale with cp(𝑟 ) while the total tool-call latency does not. Even with the highest catalog TTFT, 5000 output tokens and five tools issuing ten calls of ten seconds each, only about 30% of the budget is scalable. where the makespan objective 𝑀 (𝜎) is the completion time of the last agent to finish:

constraint functions 𝑔𝑖 and ℎ 𝑗 . Because of the conflicting objectives (i.e., improving an objective comes at the expense of another), there is typically no single 𝑥 ∗ ∈ 𝑋 that simultaneously optimizes every 𝑓𝑖 . Therefore, a MOP represents such trade-offs via the concept of Pareto-domination. For a minimization problem, a solution 𝑥 Paretodominates 𝑥 ′ (𝑥 ≺ 𝑥 ′ ) if 𝑓𝑖 (𝑥) ≤ 𝑓𝑖 (𝑥 ′ ) for every 𝑖 ∈ {1, . . . , 𝑘 } and 𝑓𝑖 (𝑥) < 𝑓𝑖 (𝑥 ′ ) for at least one 𝑖. In other words, 𝑥 is at least as good as 𝑥 ′ on every objective and strictly better on at least one. A solution 𝑥 ∗ ∈ 𝑋 is Pareto-optimal if no solution in 𝑋 dominates it, š 𝑥 ∈ 𝑋 : 𝑥 ≺ 𝑥 ∗ where the set of every such solution is the Pareto-optimal set (POS) in decision space and its projection under 𝐹 in objective space is the Pareto-optimal front (POF).

𝑀 (𝜎) = max FT[𝛼] 𝛼∈A

FT[𝛼] is the finish time of agent task 𝛼. The cost objective is the total monetary cost across the billing periods of all resources: l𝑡 − 𝑡 m ∑︁ ∑︁ 𝑒 𝑠 𝐶 (𝜎) = · 𝑝𝑟 3600 𝑟 ∈R (𝑡𝑠 ,𝑡𝑒 ) ∈billing[𝑟 ]

where each billing period is rounded up to the nearest full hour and charged at its hourly on-demand price 𝑝𝑟 . Note that the inner sum counts the number of cycles the resource 𝑟 is provisioned and deprovisioned. The utilization objective refers to the average resource busy time as: Í ∑︁ 1 𝛼 : 𝜎 (𝛼 )=𝑟 ET[𝛼] Í 𝑈 (𝜎) = |𝑅(𝜎)| (𝑡𝑠 ,𝑡𝑒 ) ∈billing[𝑟 ] (𝑡𝑒 − 𝑡𝑠 )

3.5.1 Decision Variables. The decision space for our agentic workflow scheduling problem is the set of all the resource assignment solutions as: 𝑋 = {𝜎 : A → R } where the function maps every agent in the workflow to exactly one resource in the cloud. The schedulers search over the entire decision space to seek such a feasible assignment solution 𝜎. For the sake of simplicity, we assume that each resource can execute at most one agent at a time, without considering the resource-level parallelism at the moment.

𝑟 ∈𝑅 (𝜎 )

where ET[𝛼] is the execution time of agent 𝛼 and 𝑅(𝜎) is the set of resources to which 𝜎 assigns at least one agent. In this regard, 𝑀 (𝜎) and 𝐶 (𝜎) are in conflict since faster resources incur higher ondemand prices. 𝑈 (𝜎) is also in conflict with 𝑀 (𝜎) since maximizing busy times favors using fewer and heavily-loaded resources, which lowers parallelism.

3.5.2 Objective Functions. Every 𝜎 ∈ 𝑋 is evaluated by simulating its execution (see Algorithm 1) and collecting the resulting makespan, cost and utilization values. This lets us state the multiagent workflow scheduling problem as the multi-objective optimization problem: min 𝜎 ∈𝑋

3.5.3 Optimization Constraints. The feasible region of a MOP is limited through the inequality and equality constraints 𝑔𝑖 (𝑥) ≤ 0 and ℎ 𝑗 (𝑥) = 0. Our agentic workflow scheduling problem involves four such constraints. The precedence constraint asks that no agent begin execution before all its predecessor agents have finished and

𝐹 (𝜎) = (𝑀 (𝜎), 𝐶 (𝜎), −𝑈 (𝜎))𝑇 : 𝑋 → R3 7

Algorithm 1 Workflow Simulation in Cloud. Require: Workflow DAG 𝐺 = (A, 𝐸); resource assignment 𝜎 : A → R Ensure: Schedule; makespan 𝑀; cost 𝐶; utilization 𝑈 1: order ← topological order of 𝐺 (ties broken uniformly at random) 2: FT[·], lastFT[·], billingStart[·], billing[·] ← ∅ 3: for 𝛼 ∈ order do 4: 𝑟 ← 𝜎 (𝛼)
5: RT[𝛼] ← max𝛼 ′ ∈pred(𝛼 ) FT[𝛼 ′ ] + 𝑜˜ (𝛼 ′ )/𝐵(𝜎 (𝛼 ′ ), 𝑟 ) ⊲ 0 if pred(𝛼) = ∅ 6: if 𝑟 not yet used then 7: ST[𝛼] ← RT[𝛼] + InitTime(𝑟 ) ⊲ Gaussian provisioning delay 8: billingStart[𝑟 ] ← RT[𝛼] 9: else if lastFT[𝑟 ] ≤ RT[𝛼] then ⊲ 𝑟 has gone idle: close its billing period, re-provision 10: billing[𝑟 ] ← billing[𝑟 ] ∪ {(billingStart[𝑟 ], lastFT[𝑟 ] + TermTime(𝑟 ))} 11: ST[𝛼] ← RT[𝛼] + InitTime(𝑟 ) 12: billingStart[𝑟 ] ← RT[𝛼] 13: else ⊲ 𝑟 is still running from a previous agent 14: ST[𝛼] ← lastFT[𝑟 ] 15: end if 16: ET[𝛼] ← 𝐿inf (𝛼)/cp(𝑟 ) + 𝐿tool (𝛼) 17: FT[𝛼] ← ST[𝛼] + ET[𝛼] 18: lastFT[𝑟 ] ← FT[𝛼] 19: end for 20: for 𝑟 with an open billing period do 21: billing[𝑟 ] ← billing[𝑟 ] ∪ {(billingStart[𝑟 ], lastFT[𝑟 ] + TermTime(𝑟 ))} ⊲ close out 22: end for 23: 𝑀 ← max𝛼 ∈ A FT[𝛼] Í Í 24: 𝐶 ← 𝑟 ∈ R (𝑡𝑠 ,𝑡𝑒 ) ∈billing[𝑟 ] ⌈(𝑡𝑒 − 𝑡𝑠 )/3600⌉ · 𝑝𝑟 Í ∑︁ 1 𝛼 : 𝜎 (𝛼 )=𝑟 ET[𝛼] Í 25: 𝑈 ← ⊲ busy time over billed time, averaged over the resources 𝜎 actually uses |𝑅(𝜎)| (𝑡𝑠 ,𝑡𝑒 ) ∈billing[𝑟 ] (𝑡𝑒 − 𝑡𝑠 ) 𝑟 ∈𝑅 (𝜎 )

26: return schedule, 𝑀, 𝐶, 𝑈

3.5.4 Pareto-Optimality. A scheduling solution 𝜎 is said to weakly dominate 𝜎 ′ (𝜎 ⪯ 𝜎 ′ ) if:

all data has fully arrived: ST[𝛼] ≥ FT[𝛼 ′ ] + 𝑜˜ (𝛼 ′ )/𝐵(𝜎 (𝛼 ′ ), 𝜎 (𝛼)),

∀ (𝛼 ′, 𝛼) ∈ 𝐸

𝑀 (𝜎) ≤ 𝑀 (𝜎 ′ ) 𝐶 (𝜎) ≤ 𝐶 (𝜎 ′ )

The resource serialization constraint requires that no resource execute two agents concurrently. For any two distinct agents 𝛼, 𝛼 ′ ∈ A sharing a resource, 𝜎 (𝛼) = 𝜎 (𝛼 ′ ) = 𝑟 , their execution intervals should not overlap: ST[𝛼] ≥ FT[𝛼 ′ ]

or

𝑈 (𝜎) ≥ 𝑈 (𝜎 ′ ) and 𝜎 Pareto-dominates 𝜎 ′ (𝜎 ≺ 𝜎 ′ ) if additionally at least one of these three holds strictly. A schedule 𝜎 ∗ ∈ 𝑋 is Pareto-optimal if no 𝜎 ∈ 𝑋 dominates it where the resulting POS is:

ST[𝛼 ′ ] ≥ FT[𝛼]

𝑋 ∗ = { 𝜎 ∗ ∈ 𝑋 : š 𝜎 ∈ 𝑋, 𝜎 ≺ 𝜎 ∗ } and its projection 𝐹 (𝑋 ∗ ) in objective space is the POF. However, the decision space of the problem we define is far too large to search exhaustively in the complexity level of |R| | A | . In other words, 𝑋 ∗ is intractable to compute exactly. This is why we should employ a strong metaheuristic to solve the problem or, more precisely, to approximate the non-dominated front. Figure 4 illustrates Paretodomination in two-dimensional objective space by distinguishing non-dominated solutions from the dominated solutions.

The assignment completeness constraint requires that every agent be assigned to exactly one resource: ∀ 𝛼 ∈ A, ∃! 𝑟 ∈ R : 𝜎 (𝛼) = 𝑟 and finally the non-negativity constraint requires that no agent start before the workflow itself begins: ST[𝛼] ≥ 0,

∀𝛼 ∈ A

4

The schedulers in MO-SAIC are designed to satisfy all these optimization constraints by construction, so no explicit constraint check or repair mechanism is necessary during solution construction.

MO-SAIC Framework

This section presents MO-SAIC, our multi-objective multi-agent workflow scheduling framework. Every scheduler in MO-SAIC searches over the same decision space 𝑋 and is evaluated through 8

14

better Objective 2 (e.g., Cost)

12

10

8

into several ranks; and (ii) crowding distance to preserve diversity in the same ranks. In this subsection, we customize NSGA-II to work with the solution representation and optimization objectives of our multi-objective agentic workflow scheduling problem. Refer to Algorithm 2 for the complete algorithm.

Pareto-optimal (front) Dominated Ideal point Reference point Reference point r S1

4.2.1 Solution Representation. Each solution chromosome 𝜎 ∈ 𝑋 is represented as a string of decision variables with the length of the number of available agents in workflow |A|. Each gene in a chromosome encodes the resource to which the agent on that position is assigned. During the execution of that agent (see Section 3.4), each gene is decoded to assign the agent to its corresponding resource.

6

4

2

4.2.2 Population Initialization. The initial population of NSGAII P0 = {𝜎0, . . . , 𝜎𝜆−1 } is drawn by assigning every agent to an independent and uniformly random resource as:

S6 Ideal point

0

𝜎𝑖 (𝛼) ∼ Uniform(R), 0

2

4

6

8

Objective 1 (e.g., Makespan)

10

better

12

14

16

where 𝜆 is the number of solutions in the population. All the schedulers in this framework are randomly initialized, which implies they all start from statistically indistinguishable initial populations. Therefore, every improvement reported in the experimental study can be directly attributed to the search space exploration capabilities of the schedulers themselves.

Figure 4: An illustrative Pareto front over two minimization objectives with non-dominated solutions (in blue) and dominated solutions (in gray). The shading shows the region both objectives are simultaneously worse than the front solutions. The ideal point is the best-possible solution while the reference point is the anchor for hypervolume calculations [36].

4.2.3 Fitness Evaluation. Every chromosome is evaluated at every generation with respect to the makespan, cost and utilization objectives of the simulation in cloud. The resulting objective vector 𝐹 (𝜎) = (𝑀 (𝜎), 𝐶 (𝜎), −𝑈 (𝜎)) is preserved alongside the solution for the rest of its lifetime across the generations. Refer to Section 3.5 for the calculations of these objectives.

the same workflow simulation environment against the same three objectives of makespan, cost and utilization. The schedulers differ only in how they explore 𝑋 without any control over how their solutions are evaluated, so their results are comparable.

4.1

4.2.4 Non-Dominated Sorting. Given the population P with 2𝜆 individuals during environmental selection, the non-dominated sorting partitions it into successive fronts 𝐹 0 (P), 𝐹 1 (P), . . . by using Pareto-domination to select the best 𝜆 solutions. 𝐹 0 (P) represents the Pareto-optimal front, having the solutions 𝜎 ∈ P that are not dominated by any other solution in P. The next front 𝐹 1 (P) has every remaining solution that is not dominated by any other solution where it goes until the entire population is exhausted.

Framework Architecture

MO-SAIC is composed of five components: (i) workflow generator, generating individual agentic workflows with given size, depth and width parameters; (ii) cloud, providing the heterogeneous CPU and GPU resource pool to which the agents can be assigned; (iii) schedulers, searching the resulting decision space for the optimal scheduling solutions; (iv) simulator, executing candidate scheduling solutions to reveal the objective vector; and (v) evaluator, ranking the population of scheduling solutions by non-dominated sorting and crowding distance to reveal the Pareto-optimal front. For the fair comparison of the schedulers, we keep all other components identical across the framework. As a pipeline, the workflow generator first generates a single workflow instance. Secondly, the schedulers take this instance and the available cloud resources to generate a population of scheduling solutions. Thirdly, regardless of which scheduler produced them, the simulator evaluates all solutions in the same way. Lastly, evaluator ranks the solutions to feed back to the schedulers until the maximum generation Γmax is reached and later to select the Pareto-optimal solutions.

4.2

∀ 𝛼 ∈ A, 𝑖 = 0, . . . , 𝜆 − 1

4.2.5 Crowding Distance. Within a single front 𝐹𝑘 (P), the crowding distance cd(𝜎) calculates how isolated 𝜎 is from its neighbors in the same front to push evolution to sparsely-explored regions. For each objective, the front is first sorted and the two solutions sitting at the two ends of that objective are assigned cd = ∞ to always preserve the front boundaries. Every interior solution 𝜎 accumulates its value as: 𝑓 (𝜎𝑖+1 ) − 𝑓 (𝜎𝑖 −1 ) cd(𝜎) += 𝑓max − 𝑓min where 𝑓min, 𝑓max are the range of that objective and cd(𝜎) are summed over all objectives. A solution in a more empty neighborhood has a larger cd(𝜎). 4.2.6 Parent Selection. Parents are drawn via tournament selection where a certain number of chromosomes are first randomly sampled from the population and the best chromosome with respect to the rank and crowding distance wins the tournament. Every child needs two independently drawn parents from two independent

NSGA-II Scheduler

NSGA-II [8] is an elitist multi-objective genetic algorithm that evolves a population of solutions across generations by using: (i) non-dominated sorting to rank solutions via Pareto-domination 9

where 𝑇 (𝛼) refers to average transfer time. The upward rank is then defined recursively backward: ( 0, succ(𝛼) = ∅ rank𝑢 (𝛼) = 𝐿(𝛼) + 𝑇 (𝛼) + max𝛼 ′ ∈succ(𝛼 ) rank𝑢 (𝛼 ′ ), otherwise

tournaments. Pressure through rank and crowding distance naturally pushes parent selection toward a better Pareto-optimal front with less-crowded regions. 4.2.7 Crossover and Mutation. Once two parents 𝜎𝑎 , 𝜎𝑏 are selected, the two-point crossover is applied by partitioning each chromosome into three contiguous segments. Then, the child inherits the outer two segments from 𝜎𝑎 and the middle segment from 𝜎𝑏 . Every gene of the resulting child is then independently mutated with the prespecified mutation rate (see Table 2), which reassigns that agent to a new uniformly random resource in R.

where rank𝑢 (𝛼) is the rank of agent 𝛼. Once all ranks are computed, agents are ordered by decreasing rank𝑢 with always a valid topological order. Before the actual assignment, a single baseline solution 𝜎base : A → R is computed with a single-objective HEFT for the minimization of makespan. This baseline solution is never part of the population to be measured. MO-HEFT then processes agents one at a time in priority order by maintaining a front of 𝜆 partial assignments. It extends every partial assignment for each agent 𝛼 on the front with every resource choice in R, eventually producing 𝜆|R| candidate solutions. These 𝜆|R| candidates are then reduced back down to 𝜆 solutions with the non-dominated sorting and crowding distance operators, as in NSGA-II. Once every agent is visited, the partial assignments turn into the full assignments 𝜎 ∈ 𝑋 , which MO-HEFT returns as its final population.

4.2.8 Elitism. NSGA-II maintains the elitism (i.e., preserving the best solutions ever found across generations) by default. Once 𝐹 0 (P) is found, the population for the next generation is filled from 𝐹 0 (P) first before any lower-ranked front is even considered. Hence, no non-dominated solution the population has ever found is discarded by a worse solution.

4.3

Weighted-Sum Genetic Algorithm Scheduler

4.5

W-GA [37], shares the same solution representation, population initialization, crossover and mutation operators with NSGA-II. The difference from NSGA-II is that W-GA replaces the non-dominated sorting and crowding distance operators with a single scalar fitness score operator with respect to a dynamic weight vector of 𝑤 (𝜎) = (𝑤 𝑀 , 𝑤𝐶 , 𝑤𝑈 ). At every generation, every individual 𝜎 is assigned its own independently drawn random weight vector 𝑤 (𝜎) with 𝑤 𝑀 + 𝑤𝐶 + 𝑤𝑈 = 1. In other words, no two individuals and no two generations are scored against the same weights, which pushes the population toward different regions of search space for more front diversity. The fitness score function is defined in the following way: 𝑤𝑀 ·

𝜎 (𝛼) ∼ Uniform(R),

  𝑀 (𝜎) − 𝑀min 𝐶 (𝜎) − 𝐶 min 𝑈 (𝜎) − 𝑈 min + 𝑤𝐶 · + 𝑤𝑈 · 1 − 𝑀max − 𝑀min 𝐶 max − 𝐶 min 𝑈 max − 𝑈 min

5

5.1

MO-HEFT [9] is a multi-objective adaptation of the classical HEFT heuristic [22]. In this technique, the mean execution time of each agent over all resources in R is computed as:

where 𝐿(𝛼) refers to average execution time. The average transfer time as averaged over every ordered pair of resources is: 1 ∑︁ ∑︁ 𝑜˜ (𝛼) |R| 2 𝑟 ∈ R 𝑟 ∈ R 𝐵(𝑟𝑖 , 𝑟 𝑗 ) 𝑖

Benchmark Workflows

Every workflow used in our experiments is generated by the parametric and synthetic workflow generator [12] so that the workflow structure can be varied systematically and independently. Given a target size 𝑁 , depth 𝑑 (𝐺) and width 𝑤 (𝐺) satisfying the feasibility inequality in Section 3.2, the generator constructs a layered DAG with exactly 𝑑 (𝐺) + 1 depth levels with the widest level of 𝑤 (𝐺) agents and wires every agent in an interior level to at least one predecessor in the level above and at least one successor in the level below (see Figure 5). In-degree and out-degree of each agent are drawn uniformly from [1, 5]. Each agent is additionally injected with up to five tool invocations. Every tool 𝜃 ∈ Θ(𝛼) an

  1 ∑︁ 𝐿inf (𝛼) + 𝐿tool (𝛼) |R| 𝑟 ∈ R cp(𝑟 )

𝑇 (𝛼) =

Experimental Setup

This section describes the experimental setup and methodology to compare the four schedulers in Section 4. We present (i) the synthetic benchmark workflow generation for evaluation; (ii) the performance measures to inspect scheduling quality from the workflow scheduling, multi-objective and system perspectives; and (iii) the Wilcoxon rank-sum statistical significance test.

MO-HEFT Scheduler

𝐿(𝛼) =

∀𝛼 ∈ A

where the scheduler returns a population P = {𝜎0, . . . , 𝜎𝜆−1 } and 𝜆 is the number of solutions in the population. All four schedulers are compared on the same number of solutions 𝜆. The random scheduler also follows the problem constraints given in Section 3. Hence, before the resource assignment, it first performs dependency-aware ordering through a topological sort where agents at the same dependency level are selected and randomly shuffled.

where 𝑀min, 𝑀max are the smallest and largest makespan in a generation; and 𝐶 min, 𝐶 max and 𝑈 min, 𝑈 max are defined analogously for cost and utilization, respectively. To maintain elitism across generations, two individuals with the best fitness scores are moved unmodified into the next generation while the remainder of the next population is filled through the tournament selection, crossover and mutation operators, as in NSGA-II.

4.4

Random Scheduler

We include the random scheduler in the framework as the baseline algorithm to evaluate the algorithmic value of the other schedulers. Given the set of agents A in the workflow and the set of resources in the cloud R, each solution is a random mapping 𝜎 : A → R with drawing uniformly-random resource for every agent:

𝑗

10

Algorithm 2 NSGA-II Scheduler. Require: Agent set A; resource set R; population size 𝜆; generation count Γmax ; mutation rate 𝑝𝑚 ; tournament size 𝜏 Ensure: Final population P of 𝜆 resource assignments 1: P ← {𝜎0 , . . . , 𝜎𝜆−1 }, each 𝜎𝑖 (𝛼) ∼ Uniform(R) ∀ 𝛼 ∈ A ⊲ population initialization 2: Sim ← {Simulate(𝜎) : 𝜎 ∈ P} ⊲ Algorithm 1, cached per individual 3: for gen = 1 to Γmax do 4: 𝐹 0 (P), 𝐹 1 (P), . . . ← NonDominatedSort(Sim)
5: cd(·) ← CrowdingDistance 𝐹 0 (P), 𝐹 1 (P), . . . 6: rank(𝜎) ← 𝑘 such that 𝜎 ∈ 𝐹𝑘 (P), for every 𝜎 ∈ P 7: Children ← ∅ 8: while |Children| < 𝜆 do 9: for 𝑖 ∈ {𝑎, 𝑏} do ⊲ two independently drawn parents 10: 𝑆 ← TournamentSelect(P)
11: parent𝑖 ← arg min𝜎 ∈𝑆 rank(𝜎), −cd(𝜎) ⊲ crowded-comparison 12: end for 13: 𝜎child ← Crossover(parent𝑎 , parent𝑏 ) ⊲ two-point over fixed agent order 14: Mutate(𝜎child, 𝑝𝑚 ) ⊲ per-gene reassignment 15: Children ← Children ∪ {𝜎child } 16: end while 17: Simchildren ← {Simulate(𝜎) : 𝜎 ∈ Children} 18: Pool ← P ∪ Children 19: PoolResults ← Sim ∪ Simchildren 20: P ← SelectBest(Pool, PoolResults, 𝜆) ⊲ elitist replacement 21: end for 22: return P

1

1 4

2

7 6

5 3

1 4

7

2 8

6

2

5

8

3

(a) Workflow Size, 𝑁 = 8.

4

7 6

5

8

3

(b) Workflow Depth, 𝑑 (𝐺 ) = 3.

(c) Workflow Width, 𝑤 (𝐺 ) = 3.

Figure 5: An illustrative workflow with 𝑁 = 8, 𝑑 (𝐺) = 3, 𝑤 (𝐺) = 3 with each figure highlighting one structural property: (a) size, (b) depth, the longest entry-to-exit path and (c) width, the widest depth level.

5.2

agent invokes can be an internal tool with per-invocation latency ℓ𝜃 ∈ [0.05, 2] seconds or an external tool with ℓ𝜃 ∈ [0.5, 10] seconds, each invoked 𝑛𝜃 ∈ [1, 5] times. This topology construction lets three parameters 𝑁 , 𝑑 (𝐺) and 𝑤 (𝐺) be set directly and independently. The generator also supports composing a workflow directly from the six canonical reasoning patterns of single-agent, chain-ofthought, self-consistency, tree-of-thought, debate and self-refine, ordered by the pattern-transition Markov chain [12] to generate more semantically realistic agentic workflows (see Figure 6 for exact probabilities). Unless otherwise stated, experiments use the workflow size 𝑁 = 50, depth 𝑑 (𝐺) = 15 and width 𝑤 (𝐺) = 8. Refer to Figure 7 in Appendix C for an illustrative workflow JSON.

Performance Metrics

We evaluate the schedulers with two levels of granularity as the solution-level metrics for the quality of a single scheduling solution and the population-level metrics for the quality of an entire population of solutions. These metrics are outlined as follows: 5.2.1 Objectives. All scheduling solutions are primarily evaluated and analyzed on three optimization objectives of makespan, cost and utilization, as described in Section 3. 5.2.2 Resource Load Imbalance. For a solution 𝜎, let 𝑅(𝜎) be the set of cloud resources it uses and let 𝑇busy (𝜎, 𝑟 ) denote the total busy time of resource 𝑟 ∈ 𝑅(𝜎) under 𝜎. Then, the resource load 11

SA 0.35

0.20

0.15

0.15

0.10

0.05

distance of a solution 𝜎 is:

0.40

𝑑𝑖 = min 𝑓ˆ(𝜎𝑖 ) − 𝑓ˆ(𝜎 𝑗 ) 1 𝑗≠𝑖

CoT 0.30

0.10

0.25

0.20

0.10

0.05

SC 0.35

0.25

0.10

0.15

0.10

0.05

Then, spacing is the sample standard deviation of these distances: v u t |𝐹 0 | |𝐹 0 | ∑︁
2 1 ∑︁ 1 𝑑𝑖 − 𝑑¯ , 𝑑¯ = 𝑑𝑖 SS(𝐹 0 ) = |𝐹 0 | − 1 𝑖=1 |𝐹 0 | 𝑖=1

0.30

Transition probability

From

0.35

0.25

where lower values indicate a more uniformly spread front. SS(𝐹 0 ) = 0 means every solution in the front stays exactly 𝑑¯ away from its nearest neighbor.

0.20

ToT 0.30

0.25

0.20

0.10

0.10

0.05

Db 0.40

0.20

0.15

0.15

0.05

0.05

SR 0.40

0.20

0.15

0.15

0.08

0.02

SA

CoT

SC

ToT

Db

SR

To

0.15

5.2.6 Hypervolume (HV). The hypervolume [36] measures the volume of objective space a front dominates. Using the same normalization factors as 𝑓ˆ(·) ∈ [0, 1] 3 as spacing, let a reference point r = (1 + 𝜀, 1 + 𝜀, 1 + 𝜀) with a margin 𝜀 on every axis so that even the worst solution still contributes positive volume. Hypervolume can be formally defined in the following way: ! Ø      HV(𝐹 0 ) = Λ 𝑓ˆ𝑀 (𝜎), 𝑟 1 × 𝑓ˆ𝐶 (𝜎), 𝑟 2 × 𝑓ˆ𝑈 (𝜎), 𝑟 3

0.10 0.05 0.00

𝜎 ∈𝐹 0

Figure 6: Transition-probability heatmap of the first-order Markov chain where rows are the current pattern and columns are the next. SA is the most likely next pattern regardless of the current.

where Λ(·) denotes three-dimensional Lebesgue measure (i.e., volume); and 𝑓ˆ𝑀 (𝜎), 𝑓ˆ𝐶 (𝜎), 𝑓ˆ𝑈 (𝜎) ∈ [0, 1] are the normalized objectives. For this metric, larger values indicate a front that dominates more objective space and lies closer to the ideal point. 5.2.7 Pareto-Optimal Fronts. Solutions are projected onto three two-dimensional objective spaces as makespan–cost, makespan– utilization and cost–utilization; and one three-dimensional objective space as makespan–cost–utilization. These projections enable the achievable optimization surface to be visually inspected.

imbalance can be defined as: max 𝑇busy (𝜎, 𝑟 ) − min 𝑇busy (𝜎, 𝑟 ) 𝑟 ∈𝑅 (𝜎 )

𝑟 ∈𝑅 (𝜎 )

∑︁ 1 𝑇busy (𝜎, 𝑟 ) |𝑅(𝜎)|

5.2.8 Scheduling Runtime. The wall-clock computational cost of running a scheduler is the elapsed time between the start and end times. It counts from the invocation of the scheduler to the return of the final solutions. Note that the scheduling runtime is distinct from the makespan of the scheduling solution the scheduler produces.

𝑟 ∈𝑅 (𝜎 )

where zero imbalance indicates every resource carries an equal share of the workload. In this regard, larger imbalances imply that the total load is concentrated on a small subset of resources while other resources remain comparatively idle.

5.3

5.2.3 Distinct Resource Count. Using 𝑅(𝜎) as the set of cloud resources 𝜎 uses, this metric counts the number of distinct cloud resources in 𝑅(𝜎) as:

Statistical Analysis

All experiments are conducted on a single machine of MacBook Air with Apple M2 chip, 8 GB memory and 8 CPU cores. We run every scheduler independently 20 times with freshly generated workflow instance and random seed for every run. Once a workflow is generated, all schedulers are evaluated on this workflow. We collect the performance metrics per run and report their results with their mean and standard deviations across these 20 runs. With independent measures, our goal is to eliminate the impact of randomness available in evolutionary computation and catch the typical behaviors of schedulers across distinct workflow instances, rather than a single specific draw. The RAND scheduler is just used as the baseline algorithm. The percentage improvements of the other schedulers with respect to RAND are reported where the positive percentage means better than the baseline and vice versa. We perform the statistical significance test via the Wilcoxon rank-sum test and report significance at the conventional 𝑝 < 0.05 threshold. Refer to Table 2 for the list of the important parameters with their corresponding values used throughout the experimental setup.

|𝑅(𝜎)| where it reveals the cloud footprint of a solution since every additional resource brings its own provisioning and deprovisioning overheads. Spreading the existing workload evenly on very few resources might improve cost and utilization. 5.2.4 Number of Non-Dominated Solutions (NS). This metric simply counts the number of non-dominated solutions in the front of a given population as |𝐹 0 (P)|. Larger values mean the scheduler finds a wider set of optimal solutions. However, interpretation of that metric might be occasionally misleading, especially when a better solution comes and dominates the existing ones in the front. 5.2.5 Schott’s Spacing (SS). Schott’s spacing quantifies how evenly a front is spread [38]. Let 𝑓ˆ(𝜎) ∈ [0, 1] 3 be the min-max normalization of three objectives. For a front 𝐹 0 , the nearest-neighbor 12

Table 2: Default experimental parameters and their corresponding values used across all the experiments unless otherwise stated.

6

Parameter

Value

Workflow size, 𝑁 Workflow depth, 𝑑 (𝐺) Workflow width, 𝑤 (𝐺)

50 15 8

Cloud resource pool size, |R| Resource-pool composition vCPU weight, 𝑤 𝑣 vGPU weight, 𝑤𝑔 Provisioning delay (mean / std) Deprovisioning delay (mean / std)

60 CPU + GPU 1.0 8.0 100 s / 10 s 10 s / 2 s

Population size, 𝜆 Generation count Mutation rate Tournament size

50 5000 0.1 10

Independent runs, 𝑛

20

utilization but narrows the front. It reduces cost by 59.1% and raises utilization by 18.4%, but its count of non-dominated solutions falls to 8.50 with a Schott’s spacing of 0.03. 6.1.1 Generation Count. Figure 10 in Appendix E traces the best makespan, cost and utilization found by W-GA and NSGA-II over 5000 generations of a single run. Cost improves earliest and most sharply for both schedulers. W-GA reduces the best cost from about $123.00 to about $33.00 within the first thirty generations and NSGA-II reduces it from about $146.00 to about $25.00 within the first two hundred. The initial population assigns every agent to an independent uniformly-random resource and therefore contains many expensive instances that need to be removed. After that, both schedulers continue to lower cost slowly where W-GA reaches $23.70 and NSGA-II reaches $4.88 at generation 5000. Makespan converges early and improves little afterwards. W-GA settles around 2575 seconds by generation 600 and improves only to 2570 seconds for the remaining 4400 generations. NSGA-II settles around 2735 seconds by generation 1100 and later brings it to 2707 seconds. Utilization is the slowest objective to converge for NSGA-II. W-GA raises utilization from about 34% to about 42% by generation 1350 and then remains flat. NSGA-II instead climbs continuously, passing 50% near generation 750, reaching 55% near generation 2350 and completing at 56.5%. NSGA-II keeps discovering improvements later than W-GA. The utilization of W-GA stops changing after roughly generation 1350 while its cost and makespan improve intermittently where the last of which occurs near generation 3750. By contrast, NSGA-II records a makespan step near generation 4200 and utilization gains past generation 4600. Selection of generation cut point forms a trade-off between scheduling quality and runtime.

Experimental Results

This section reports the experimental results and the key findings. We discuss (i) the overall scheduling performance of the schedulers; (ii) their resulting Pareto-optimal fronts; (iii) the effects of workflow topology; and (iv) effects of heterogeneous cloud resources.

6.1

Overall Scheduling Performance 6.1.2 Temporal Scheduling Overhead. Figure 8 in Appendix D reports the wall-clock scheduling time of the four schedulers in MOSAIC while Figure 9 specifically focuses on NSGA-II for the growing population and workflow size. RAND is trivially fast with 0.0007 seconds in total. This is well expected since RAND performs only a single dependency-aware topological sort followed by a random resource draw. On the other hand, MO-HEFT, W-GA and NSGA-II take 203.53, 73.56 and 96.26 seconds, respectively. MO-HEFT is the most computationally expensive scheduler. For each of the 𝑁 = 50 agents, it extends every 𝜆 = 50 solution with every |R| = 60 default resource choice, producing 𝜆|R| = 3000 candidate extensions that must be reduced back down to 𝜆 solutions through the non-dominated sorting and crowding-distance operators. The heaviest computational overhead of MO-HEFT does not mean consistently superior scheduling quality. According to Table 3, MO-HEFT delivers a 7.0% makespan gain over RAND and a worse cost of $125.49 in return for significant gains in utilization. In contrast, NSGA-II achieves significant improvements over RAND, making it favorable for the balance between computational overhead and scheduling quality. Applying non-dominated sorting of NSGA-II has a measurable overhead over weightedsum of W-GA. This is especially visible between W-GA’s 73.5614 seconds and NSGA-II’s 96.2599 seconds while they both run the identical population size and generation count. While W-GA employs a single weighted-sum fitness for solutions, NSGA-II performs non-dominated sorting and crowding distance at every generation.

Table 3 reports the makespan, cost, utilization and Pareto-optimal front quality of all four schedulers at the default configuration of Table 2 as the average of 20 independent runs and Wilcoxon rank-sum significance. The first and most critical observation is that NSGA-II is the strongest scheduler that outperforms the other schedulers on most metrics by improving every objective. It lowers makespan by 8.5% to 2663.27 seconds, lowers cost by 94.6% from $113.60 to $6.17 and raises utilization by 66.8% from 30.39% to 50.69% while also improving resource imbalance by 35.4%, the number of non-dominated solutions by 104.9% and hypervolume by 185.1%. No other scheduler except W-GA improves makespan, cost and utilization at the same time. Cost is the objective that the schedulers separate most and makespan the least. Cost spans over twenty-fold across the four schedulers from NSGA-II’s $6.17 to MO-HEFT’s $125.49. On the other hand, the schedulers except RAND stay within about 3% of each other on makespan from 2663.27 to 2731.46 seconds. Figure 3 shows that the inference part of each agent scaling with the resource it runs on is narrower than the tool latency, which leaves little room to minimize makespan. The hourly price of a resource, by contrast, varies widely across Table 5 and Table 6. Hence, the search moves cost and utilization the most. MO-HEFT reaches a high utilization, but without reaching it economically. Its utilization of 49.84% is close to NSGA-II’s 50.69% and it has the lowest resource imbalance at 1.49. However, its cost of $125.49 is the worst of all four schedulers. W-GA improves cost and 13

Table 3: Overall scheduling performance of the four schedulers, averaged over 20 independent runs with the improvement over RAND and statistical significance of * 𝑝 < 0.05.

6.2

Metric

RAND

MO-HEFT

W-GA

NSGA-II

Makespan (s) ↓ Cost ($) ↓ Utilization ↑ Resource Imbalance ↓ Non-dominated Solutions ↑ Spacing (Schott’s) ↓ Hypervolume ↑

2911.37 113.60 30.39% 2.52 12.30 0.06 0.30

2706.69 (+7.0%*) 125.49 (-10.5%) 49.84% (+64.0%*) 1.49 (+40.6%*) 21.95 (+78.5%*) 0.07 (-12.0%) 0.77 (+154.8%*)

2731.46 (+6.2%*) 46.46 (+59.1%*) 35.97% (+18.4%*) 1.97 (+21.7%*) 8.50 (-30.9%*) 0.03 (+47.7%*) 0.56 (+85.7%*)

2663.27 (+8.5%*) 6.17 (+94.6%*) 50.69% (+66.8%*) 1.63 (+35.4%*) 25.20 (+104.9%*) 0.10 (-59.9%*) 0.86 (+185.1%*)

Computation Time (s)

0.0007

203.5308

73.5614

96.2599

Pareto Frontier Analysis

6.3.1 Workflow Size. Table 7 reports mean experimental results over 20 independent runs as the workflow size 𝑁 grows from 25 to 120 agents. Cost grows faster than makespan as workflow size increases. From 𝑁 = 25 to 𝑁 = 120, makespan rises by only about a third from 2292.91 to 3057.72 seconds while cost shows a dramatic rise of 44-fold from $1.2469 to $55.2051. Since workflow depth is fixed, the additional agents are included within the existing dependency levels rather than lengthening the critical path. Hence, the growing workload is executed largely in parallel, not affecting makespan to a great degree. In contrast, cost, as the sum of billing durations, accumulates roughly with each agent added and grows correspondingly faster than makespan. NSGA-II absorbs the growing workload by recruiting more distinct resources at the expense of utilization and load imbalance. The number of distinct resources grows more than threefold from 13.39 at 𝑁 = 25 to 44.01 at 𝑁 = 120 while utilization gradually falls from 56.93% to 40.20% and resource imbalance worsens from 1.3891 to 2.1362. A larger 𝑁 causes more agents at the same dependency levels to be ready at once and NSGA-II spreads them across a wider set of resources to avoid delays and keep makespan small. However, each resource comes with its hourly-rounded cycle that rarely aligns with how long that agent is actually busy, which lowers the average busy-time per resource as the total amount of work grows. Therefore, workflow size trades utilization and resource imbalance for bounded makespan growth. Increase in hypervolume does not necessarily reflect improvement with a stronger front. Hypervolume climbs from 0.7466 at 𝑁 = 25 to 0.9979 at 𝑁 = 100, which would suggest an improvement on its own at the first glance. However, a larger workflow also widens the achievable range for makespan, cost and utilization, which can raise the hypervolume without an actual improvement. At the same time, the number of non-dominated solutions declines from 32.50 at 𝑁 = 25 to roughly 21 to 24 for 𝑁 ≥ 75 and Schott’s spacing worsens from 0.0843 to 0.1093. This suggests that NSGA-II yields a sparser and less evenly-distributed front. Workflow size also inflates the computational cost of scheduling itself. Figure 9 in Appendix D reports the wall-clock computation time with the increasing workflow size. As shown, the runtime grows with 𝑁 since every additional agent lengthens the solution length and adds to the simulation complexity for every candidate solution at every generation. When evaluated together with the degrading multi-objective performance, workflow size

This section presents three two-dimensional space projections of makespan–cost, makespan–utilization and cost–utilization from the three-dimensional objective space in Figure 11 for visual inspection. 6.2.1 Makespan–Cost Frontier. The scheduling solutions in Table 3 are distributed more widely along the cost axis than along the makespan axis. Cost ranges over twenty-fold across the four schedulers, from NSGA-II’s $6.17 to MO-HEFT’s $125.49. However, makespan varies within about 3% across the schedulers except RAND, from NSGA-II’s 2663.27 to W-GA’s 2731.46 seconds, with RAND higher at 2911.37 seconds. Notably, NSGA-II dominates the other schedulers by finding the lowest cost and the lowest makespan. A spacing pattern is also visible in Figure 11d where solutions are clustered toward the low-cost and low-makespan corner, unlike those in Figure 11a in Appendix F. 6.2.2 Cost–Utilization Frontier. Two most utilization-optimal schedulers act differently on the cost axis. MO-HEFT and NSGA-II reach roughly the same utilization levels of 49.84% and 50.69%, respectively. However, MO-HEFT’s cost of $125.49 is twenty times higher than NSGA-II’s $6.17, showing that MO-HEFT does not use resources economically. It suggests that reaching a utilization level offers no guarantee of reaching it economically, as seen in Figure 11b and Figure 11d in Appendix F. Moreover, W-GA improves on RAND by raising utilization from 30.39% to 35.97% while reducing cost from $113.60 to $46.46. 6.2.3 Makespan–Utilization Frontier. A richer front does not necessarily mean a more evenly-distributed trade-off for makespan–utilization. NSGA-II carries the most non-dominated solutions of the four schedulers with 25.20 against RAND’s 12.30. However, its Schott’s spacing of 0.10 is worse than RAND’s 0.06, indicating that its larger front is not uniformly distributed, as seen in Figure 11d. W-GA shows the opposite pattern where it has fewer non-dominated solutions than even RAND, 8.50 against 12.30 while it has the tightest spacing of all four schedulers at 0.03. Its weightedsum fitness directs solutions toward a narrow and tightly-clustered region of the makespan–utilization space.

6.3

Influence of Workflow Topology on NSGA-II

This section evaluates the influence of workflow topology including size, depth and width on NSGA-II scheduling performance. 14

is the most influential topology parameter by placing the heaviest demand on both scheduling quality and scheduling runtime scalability, among the three topology parameters considered.

billing cycle. This differs from the effect of workflow size where extra agents are spread across more resources. However, here, the agent count does not change and consequently increasing parallelism is absorbed by denser packing. The Pareto-front contracts at high width. Hypervolume falls from 0.9025 at 𝑤 (𝐺) = 5 to 0.7647 at 𝑤 (𝐺) = 25 while the number of non-dominated solutions holds near 25 to 28 and Schott’s spacing stays near 0.09 to 0.10.

6.3.2 Workflow Depth. Table 8 reports how NSGA-II scheduling performance changes as depth 𝑑 (𝐺) grows from 15 to 42 while workflow size 𝑁 = 50 and width 𝑤 (𝐺) = 8 stay fixed. Note that 𝑑 (𝐺) = 42 is the boundary value 𝑤 (𝐺) + 𝑑 (𝐺) = 𝑁 where it forces almost the entire workflow into a single chain with only one level with the full width 𝑤 (𝐺) = 8. Makespan grows while cost declines as workflow depth increases. Makespan more than doubles from 2663.27 seconds at 𝑑 (𝐺) = 15 to 6220.51 seconds at 𝑑 (𝐺) = 42 while cost falls from $6.17 to $4.82 in the same range. In contrast to workflow size, depth lengthens the critical path where every additional level is a sequential dependency that cannot be parallelized regardless of how many resources are available. Hence, makespan scales with the number of levels. Cost falls since a narrower workflow needs less concurrency with fixed amount of work at any one time and schedulers can reuse already-active resources across consecutive levels of agents, rather than opening new billing cycles for additional resources. There is a small decline in both distinct resource count and utilization. Distinct resources slightly fall from 27.00 at 𝑑 (𝐺) = 15 to 25.77 at 𝑑 (𝐺) = 42 while utilization declines from 50.69% to 45.94%. Resource imbalance rises correspondingly from 1.6284 at 𝑑 (𝐺) = 15 to a peak of 1.9855 at 𝑑 (𝐺) = 35 since the wide 𝑤 (𝐺) = 8 level of agents is spread across several resources while the remaining narrow levels are serialized onto a small set of heavilyreused resources. Finally, it settles at 1.9307 at 𝑑 (𝐺) = 42 as the workflow approaches a single chain. Hypervolume also falls as depth grows. Hypervolume declines from 0.8634 at 𝑑 (𝐺) = 15 to a low of 0.7482 at 𝑑 (𝐺) = 35, contrary to the increasing hypervolume observed for growing workflow size. Here, workflow size 𝑁 stays constant regardless of depth, so it does not enlarge achievable range of makespan, cost and utilization. In addition, heavily-serialized dependencies leave less freedom for a solution to trade makespan against cost and utilization, which compresses non-dominated solutions into a smaller region of objective space. This compression is also visible in Schott’s spacing that decreases from 0.0998 to 0.0724 between 𝑑 (𝐺) = 15 and 𝑑 (𝐺) = 35.

6.4

Influence of Cloud Resources on NSGA-II

This section evaluates the influence of cloud resources including resource size and CPU/GPU composition on NSGA-II scheduling performance. 6.4.1 Resource Size. Table 10 in Appendix H reports the way NSGAII scheduling performance changes as the cloud resource pool grows from |R| = 60 to 180 and 300 while the workflow topology stays fixed. Makespan is insensitive to the size of the resource pool. It moves from 2663.27 seconds at |R| = 60 to 2676.70 at |R| = 180 and 2591.85 at |R| = 300 without a visible trend. For the workflow size of 𝑁 = 50, available resources are sufficient and adding more does not reduce makespan. However, resource size might be a bottleneck for larger workflows. A larger pool inflates cost and lowers utilization. Cost rises from $6.1716 at |R| = 60 to $17.8053 at |R| = 180 and $25.7325 at |R| = 300 while utilization falls from 50.69% to 45.67% and resource imbalance worsens from 1.6284 to 1.8114. The number of distinct resources also grows from 27.00 to 39.88. The Pareto-front does not improve with a larger pool. The number of non-dominated solutions rises only slightly from 25.20 to 28.50, Schott’s spacing improves marginally from 0.0998 to 0.0839 and hypervolume stays near 0.86 with no clear trend. Overall, enlarging the resource pool beyond the concurrency the workflow requires brings no benefit to makespan or to front quality while it measurably worsens cost and utilization. 6.4.2 Environment Heterogeneity. Table 11 in Appendix H reports NSGA-II scheduling performance when the resource pool is restricted to CPU-only or GPU-only instances against the default CPU+GPU environment. The GPU-only pool gives the lowest makespan. Makespan falls to 2620.16 seconds against 2774.33 for CPU-only and 2663.27 for CPU+GPU, about 6% below the CPU-only setting. GPU acceleration raises cp(𝑟 ) and shortens the inference term of every agent. The GPU-only pool costs roughly ten times more. Cost reaches $64.7780 against $6.7696 for CPU-only and $6.1716 for CPU+GPU. GPU instances carry much higher hourly prices and an all-GPU pool leaves no cheap fallback. CPU+GPU reaches the lowest cost of the three because it can place most agents on cheap CPU instances and use GPUs only where they help, under our simplified computation power model. CPU-only reaches the highest utilization and CPU+GPU has the most non-dominated solutions. Utilization is 53.86% for CPU-only, 50.69% for CPU+GPU and 46.84% for GPU-only since fast GPU execution leaves resources idle within their billing hour. The number of non-dominated solutions is 25.20 for CPU+GPU against 23.00 for CPU-only and 15.60 for GPU-only and Schott’s spacing is best for CPU+GPU at 0.0998. Both resource classes together give NSGA-II the widest set of makespan–cost trade-offs to populate. The GPU-only front collapses once makespan is satisfied by hardware

6.3.3 Workflow Parallelism. Table 9 in Appendix G reports how NSGA-II scheduling performance changes as width 𝑤 (𝐺) grows. Width sets the largest number of agents that can share a single dependency level. A wider workflow packs the same 50 agents into fewer and wider levels of simultaneous agents. Makespan decreases slowly at the widest settings. It stays near 2650 seconds for 𝑤 (𝐺) up to 15 and falls to 2491.95 and 2347.12 seconds at 𝑤 (𝐺) = 25 and 35. Since the depth is fixed, the critical path spans fifteen dependency levels and the achievable makespan is limited. Cost shows no trend with width. It fluctuates between $4.7648 and $6.5181 with a variance that overlaps for all five settings. Utilization rises overall as the workflow becomes wider. It grows from 48.15% at 𝑤 (𝐺) = 5 to 59.09% at 𝑤 (𝐺) = 35 while resource imbalance improves from 1.7168 to 1.5288 and the distinct resource count falls from 26.73 to 24.19. A larger width lets more agents be ready at the same moment and NSGA-II packs onto a compact set of resources that then accumulate more busy time per 15

alone. Overall, the mixed CPU+GPU environment delivers near the GPU-only makespan at the CPU-only cost with the most nondominated solutions.

7

capable of reacting to these scenarios effectively. Therefore, extending our work to a dynamic multi-objective problem would be beneficial for more adaptive multi-objective scheduling. (6) Set of optimization objectives. MO-SAIC optimizes makespan, cost and utilization objectives by remaining entirely agnostic to the correctness of model responses. However, scheduling depending on smaller models might degrade the quality of that agent contribution even if it reduces cost and latency. This tradeoff is not addressed where introducing task success probability or response quality as a further objective might be taken into consideration. In addition, energy consumption might be also studied in the future together with the existing objectives.

Further Discussions

MO-SAIC makes a number of design and implementation assumptions to keep the problem tractable. In this section, we discuss such further issues as well as potential future research directions: (1) Synthetic workflows rather than realistic agentic traces. The workflows in this paper are generated through our synthetic and parametric workflow generator [12] by compiling several agentic reasoning patterns under a Markovian transition matrix. Admittedly, this generator enables us to vary workflow size, depth and width independently and study their impacts in isolation. However, it might not fully reflect how real-world organizations compose their workflows in practice. In the future, we aim to collect realistic agentic workflow traces and re-evaluate our schedulers against them. (2) A simulated but not measured execution environment. Agent and cloud characteristics including inference latency, tool latency, provisioning and deprovisioning delays and network bandwidth are modeled in this work, by using static AWS pricing and LLM catalogs and Gaussian noise, rather than realworld measurements taken from cloud providers. However, real environment execution might show variability from network congestion, cold-start delays and interference, which can affect makespan. Deploying and simulating the MO-SAIC schedulers on an actual cloud environment is a promising direction. (3) A simplified computation power unification for CPUs and GPUs. Our computation power model combines vCPU and vGPU counts through a single fixed-weighted sum cp(𝑟 ) = 𝑤 𝑣 𝑣𝑟 +𝑤𝑔𝑔𝑟 where it treats every vGPU unit as equally powerful regardless of GPU generation. However, in reality, a T4 and an H200 differ for the same workload. A natural next step is to replace this linear abstraction with per-generation throughput multipliers for more realistic workflow simulations. (4) Abstracting away hardware compatibility. MO-SAIC permits any agent to be assigned to any cloud resource, so a scheduler might place a large model onto a CPU-only instance whose memory could not actually hold the model weights. However, in practice, model weights impose minimum memory footprint that only certain resources can satisfy. Some models might require multiple GPUs together, rather than a single resource. Consequently, some of the solutions our schedulers generate as optimal might not be deployed on real infrastructure. Therefore, incorporating per-model memory requirements into the assignment constraints might be a critical future direction for a production-ready MO-SAIC. (5) A static and offline scheduling formulation. This paper considers the multi-objective optimization problem as timeinvariant over fixed workflows and fixed cloud resources. However, real deployments might face changes over time, such as software and hardware failures. In addition, agents might fail and retry in tool calling. The schedulers in this paper are not

8

Conclusion

In this paper, we formulate LLM-based multi-agent workflow scheduling in cloud computing as a multi-objective optimization problem, jointly considering the minimization of makespan and cost and the maximization of resource utilization. For the given problem, we propose MO-SAIC, a multi-objective scheduling framework with a total of four schedulers. To evaluate the schedulers in MO-SAIC, we employ a parametric and synthetic multi-agent workflow generator to systematically vary workflow topology with respect to size, depth and width. We measure performance under the extensive test scenarios as: (i) their overall performance improvements relative to RAND; (ii) quality of their fronts; (iii) impacts of workflow topology; and (iv) impacts of cloud resources. The performance metrics we use span three main perspectives as: (i) objective functions, resource load imbalance, distinct resource count for the workflow scheduling perspective; (ii) number of non-dominated solutions, Schott’s spacing, hypervolume and visual Pareto-optimal fronts for the multi-objective perspective; and (iii) scheduling runtime for the system perspective. Lastly, we identify the current limitations of MO-SAIC and the potential future research directions. We expect that, rather than the model layer, the operational layer of artificial intelligence will be increasingly important in the future as the open-weight models close the performance gap with the proprietary ones, making the multi-objective multi-agent workflow scheduling a critical problem to address for large organizations.

16

A

LLM Model Performance Reference

This appendix lists the performance characteristics of the agent models in terms of throughput and TTFT. Table 4: Large language models with reference performance characteristics of throughput and TTFT [39], assumed to be measured at a single-vCPU configuration. In this work, we deliberately treat the models as open-source and self-hosted on cloud resources so that they can be scheduled onto cloud resources. Model OpenAI Models gpt-5.4-pro gpt-5.4 gpt-5.4-mini gpt-5.4-nano gpt-5.3-codex gpt-5.2-codex gpt-5.2 gpt-5.1 gpt-5 gpt-5-nano gpt-5-mini gpt-4.1 gpt-4.1-nano gpt-4.1-mini gpt-4o gpt-4o-mini gpt-4-turbo gpt-oss-120b gpt-oss-20b Google Gemini gemini-2.5-pro gemini-2.5-flash Meta Llama llama-4-scout llama-4-maverick llama-3.1-405b Mistral Models ministral-3-3b ministral-3-8b ministral-3-14b xAI Grok grok-code-fast-1 Other Models nemotron-3-super-100b nemotron-3-nano-30b deepseek-v3.2 deepseek-r1-distill-qwen-32b mercury-2-inception ling-2.6-flash nova-pro mimo-v2-flash qwen-3.5-397b

Tput (t/s)

TTFT (s)

74 74 201 191 79 123 73 111 83 137 86 108 181 80 131 33 30 262 313

151.79 151.79 3.85 3.64 88.26 87.34 130.34 57.47 36.28 83.30 65.32 1.02 0.63 0.76 0.81 3.16 2.84 0.79 0.65

117 221

21.19 0.50

128 121 29

0.70 0.95 2.19

274 182 110

0.42 0.52 0.60

172

2.81

367 152 35 60 789 210 141 129 96

0.71 1.90 3.75 0.84 3.88 1.07 0.81 2.14 2.44

Model OpenAI Models o1 o3 o3-mini o3-pro o4-mini Anthropic Claude claude-4.1-opus claude-4.1-opus-thinking claude-4-sonnet claude-4.6-sonnet claude-4.5-opus claude-4.6-opus claude-3-haiku Google Gemini gemini-3.1-pro gemini-3.1-flash-lite gemini-3-pro gemini-3-flash

Mistral Models mistral-small-4 mistral-medium-3 mistral-large-3 mistral-large-2 xAI Grok grok-4.20 grok-4.3 grok-4.1-fast grok-4 grok-3-mini Other Models glm-5 glm-4.7 glm-4.7-flash glm-4.5 glm-4.5-air lfm2-24b-a2b step-3.5-flash minimax-m2.7 minimax-m2.5 kimi-k2.5 kimi-k2 phi-4 gemma-3-27b

17

Tput (t/s)

TTFT (s)

98 118 160 27 161

32.29 5.38 7.12 84.93 21.94

29 29 40 44 46 40 138

1.66 15.00 1.33 1.48 1.01 1.78 1.16

109 205 109 159

29.71 7.50 32.65 1.19

175 57 48 38

0.64 1.20 1.04 1.45

233 209 138 54 190

10.33 12.36 0.54 15.60 0.54

74 82 95 51 106 92 87 45 46 45 43 35 31

1.64 1.10 0.91 1.45 1.18 0.42 3.03 2.53 2.12 2.38 1.51 2.02 2.04

B

Cloud Resource Specifications

This appendix presents the specifications of CPU-only and GPU-accelerated cloud resources on which agents are deployed and executed. Table 5: AWS EC2 CPU-Only instance specifications including virtual CPU count, network bandwidth and hourly on-demand pricing for five resource families (M1, M3, M4, M5, M5D) [40]. Instance Type

vCPUs

Network (Gbps)

Price ($/hour)

1 1 2 4

10 10 10 10

0.044 0.087 0.175 0.35

M1 Family m1.small m1.medium m1.large m1.xlarge M3 Family m3.medium m3.large m3.xlarge m3.2xlarge M5 Family m5.4xlarge m5.12xlarge m5.24xlarge

1 2 4 8

10 10 10 10

0.067 0.133 0.266 0.532

16 48 96

10 12 25

0.768 2.304 4.608

M5D Family m5d.large m5d.2xlarge m5d.8xlarge m5d.16xlarge

2 8 32 64

10 10 10 20

0.113 0.452 1.808 3.616

Instance Type M4 Family m4.large m4.xlarge m4.2xlarge m4.4xlarge m4.10xlarge m4.16xlarge M5 Family m5.large m5.xlarge m5.2xlarge m5.8xlarge m5.16xlarge

M5D Family m5d.xlarge m5d.4xlarge m5d.12xlarge m5d.24xlarge

vCPUs

Network (Gbps)

Price ($/hour)

2 4 8 16 40 64

10 10 10 10 10 25

0.1 0.2 0.4 0.8 2.0 3.2

2 4 8 32 64

10 10 10 10 20

0.096 0.192 0.384 1.536 3.072

4 16 48 96

10 10 12 25

0.226 0.904 2.712 5.424

Table 6: AWS EC2 GPU-accelerated instance specifications including virtual CPU count, virtual GPU count, network bandwidth and hourly on-demand pricing for ten NVIDIA GPU instance families from T4 through H200 (G4dn, G5, G6, G6e, G7, G7e, P4d, P4de, P5 and P5en) [40]. Instance Type

vCPUs

NVIDIA T4 – 16 GB/GPU g4dn.xlarge 4 g4dn.2xlarge 8 NVIDIA A10G – 24 GB/GPU g5.xlarge 4 g5.2xlarge 8 g5.4xlarge 16 g5.12xlarge 48 g5.16xlarge 64 g5.24xlarge 96 NVIDIA L4 – 24 GB/GPU g6.xlarge 4 g6.2xlarge 8 g6.4xlarge 16 g6.8xlarge 32 g6.12xlarge 48 g6.16xlarge 64 g6.24xlarge 96 g6.48xlarge 192

vGPUs

Network (Gbps)

Price ($/hour)

1 1

25 25

0.526 0.752

1 1 1 4 1 4

10 10 25 40 25 50

1.006 1.212 1.624 5.672 4.096 8.144

1 1 1 1 4 1 4 8

10 10 25 25 40 25 50 100

0.805 0.978 1.323 2.014 4.602 3.397 6.675 13.350

Instance Type

vCPUs

vGPUs

NVIDIA L40S – 48 GB/GPU g6e.xlarge 4 g6e.2xlarge 8 NVIDIA RTX PRO – 32 GB/GPU g7.2xlarge 8 g7.4xlarge 16 g7.8xlarge 32 g7.24xlarge 96 g7.48xlarge 192 NVIDIA RTX PRO – 96 GB/GPU g7e.2xlarge 8 g7e.4xlarge 16 NVIDIA A100 – 40 GB/GPU p4d.24xlarge 96 NVIDIA A100 – 80 GB/GPU p4de.24xlarge 96 NVIDIA H100 – 80 GB/GPU p5.4xlarge 16 p5.48xlarge 192 NVIDIA H200 – 141 GB/GPU p5en.48xlarge 192

18

Network (Gbps)

Price ($/hour)

1 1

20 20

1.861 2.242

1 1 1 4 8

60 100 100 350 700

2.520 3.042 4.086 14.257 28.513

1 1

50 50

3.363 3.998

8

400

21.958

8

400

27.447

1 8

100 3200

6.880 55.040

8

3200

63.296

C

A Workflow JSON

This appendix lists the per-agent attributes for the agentic workflow in Figure 5 in the format of JSON. [

{ {

" id " : " 5 " , " model " : " grok -3 - mini " , " ttft " : 0.54 , " tokens_per_sec " : 190 , " output_size " : 187 , " successors " : [ " 6 " ] , " tools " : [ { " is_internal " : false , " latency " : 3.48 , " number_of_requests " : 4 } , ... ]

" id " : " 1 " , " model " : " gemini -2.5 - pro " , " ttft " : 21.19 , " tokens_per_sec " : 117 , " output_size " : 175 , " successors " : [ " 4 " ] , " tools " : [ { " is_internal " : true , " latency " : 1.49 , " number_of_requests " : 5 } , ... ]

}, {

}, {

" id " : " 6 " , " model " : " gemma -3 -27 b " , " ttft " : 2.04 , " tokens_per_sec " : 31 , " output_size " : 254 , " successors " : [ " 7 " , " 8 " ] , " tools " : [ { " is_internal " : false , " latency " : 1.36 , " number_of_requests " : 1 } , ... ]

" id " : " 2 " , " model " : " gpt -5.4 - pro " , " ttft " : 151.79 , " tokens_per_sec " : 74 , " output_size " : 438 , " successors " : [ " 4 " , " 5 " ] , " tools " : [ { " is_internal " : true , " latency " : 0.59 , " number_of_requests " : 2 } , ... ]

}, {

}, {

" id " : " 7 " , " model " : " gpt -4 o " , " ttft " : 0.81 , " tokens_per_sec " : 131 , " output_size " : 128 , " successors " : [ ] , " tools " : [ { " is_internal " : true , " latency " : 0.17 , " number_of_requests " : 4 } , ... ]

" id " : " 3 " , " model " : " gpt -5 - mini " , " ttft " : 65.32 , " tokens_per_sec " : 86 , " output_size " : 332 , " successors " : [ " 4 " , " 5 " ] , " tools " : [ { " is_internal " : false , " latency " : 8.68 , " number_of_requests " : 5 } , ... ]

}, {

}, {

" id " : " 8 " , " model " : " gpt -4 o " , " ttft " : 0.81 , " tokens_per_sec " : 131 , " output_size " : 200 , " successors " : [ ] , " tools " : [ { " is_internal " : true , " latency " : 1.45 , " number_of_requests " : 3 } , ... ]

" id " : " 4 " , " model " : " mistral - large -3 " , " ttft " : 1.04 , " tokens_per_sec " : 48 , " output_size " : 157 , " successors " : [ " 6 " ] , " tools " : [ { " is_internal " : false , " latency " : 6.65 , " number_of_requests " : 5 } , ... ]

}

},

]

Figure 7: Attributes of all eight agents for the workflow in Figure 5. MO-SAIC schedulers consider these attributes while scheduling the agents onto the cloud resources.

19

D

Wall-Clock Computation Time

This appendix provides wall-clock scheduling overheads of schedulers in MO-SAIC. 103

203.5s

Computation Time (s), log scale

102

73.6s

96.3s

W-GA

NSGA-II

101 100 10 1 10 2 10 3 10 4

0.0007s

RAND

MO-HEFT

Figure 8: Computation time of the schedulers (mean ± std over 20 runs) at default configuration, shown on a log scale.

150 96.3s

100

222.0s

Computation Time (s)

Computation Time (s)

200

50

250

238.2s

250

200

185.2s

150

137.1s 96.3s

100 58.4s

15.9s

50

0 10

50

Population size

100

25

50

75

Workflow size N

100

120

Figure 9: NSGA-II computation time (mean ± std over 20 independent workflows) as population size 𝜆 (left) and workflow size 𝑁 (right) grow.

20

E

Convergence of Genetic Algorithms

This appendix shows variations of the best makespan, cost and utilization values across all 5000 generations of a single run. This is only applicable to the generational schedulers including W-GA and NSGA-II.

(a) Convergence of W-GA over 5000 generations.

(b) Convergence of NSGA-II over 5000 generations.

Figure 10: Convergence of the W-GA and NSGA-II schedulers over 5000 generations on makespan, cost and utilization.

21

F

Two-Dimensional Pareto Frontiers

This appendix shows the Pareto frontiers of the schedulers based on their final populations for a single run in two-dimensional projections.

(a) RAND: makespan–cost, makespan–utilization and cost–utilization projections.

(b) MO-HEFT: makespan–cost, makespan–utilization and cost–utilization projections.

(c) W-GA: makespan–cost, makespan–utilization and cost–utilization projections.

(d) NSGA-II: makespan–cost, makespan–utilization and cost–utilization projections.

Figure 11: Non-dominated (blue) and dominated (gray) solutions from the final populations of schedulers. Solutions are projected onto the three two-dimensional objective spaces.

22

G

Workflow Topology

This appendix provides tables for the impacts of workflow topology such as size, depth and width on the NSGA-II performance. Table 7: Impact of workflow size 𝑁 on NSGA-II scheduling quality (mean ± std over 20 independent workflows), 𝑑 (𝐺) = 15, 𝑤 (𝐺) = 8 and all other parameters at their defaults. Workflow size 𝑁 Makespan (s) ↓ Cost ($) ↓ Utilization ↑ Resource Imbalance ↓ Distinct Resources Non-dominated Solutions ↑ Spacing (Schott’s) ↓ Hypervolume ↑

25

50

75

100

120

2292.91 ± 132.04 1.2469 ± 0.1909 56.93% ± 4.69% 1.3891 ± 0.3748 13.39 ± 0.93 32.50 ± 3.64 0.0843 ± 0.0255 0.7466 ± 0.0531

2663.27 ± 148.18 6.1716 ± 1.3416 50.69% ± 2.65% 1.6284 ± 0.2536 27.00 ± 1.29 25.20 ± 5.00 0.0998 ± 0.0391 0.8634 ± 0.1177

2871.44 ± 180.93 17.0122 ± 2.4709 45.20% ± 2.62% 2.0353 ± 0.2155 34.86 ± 1.27 22.10 ± 4.16 0.0905 ± 0.0241 0.9648 ± 0.0769

3035.66 ± 120.95 39.0057 ± 3.5187 41.93% ± 1.81% 2.0404 ± 0.1813 40.27 ± 1.35 23.80 ± 2.48 0.1029 ± 0.0302 0.9979 ± 0.0713

3057.72 ± 152.35 55.2051 ± 6.0904 40.20% ± 1.79% 2.1362 ± 0.2180 44.01 ± 1.94 21.20 ± 4.38 0.1093 ± 0.0258 0.9978 ± 0.0826

Table 8: Impact of workflow depth 𝑑 (𝐺) on NSGA-II scheduling quality (mean ± std over 20 independent workflows), 𝑁 = 50, 𝑤 (𝐺) = 8 and all other parameters at their defaults. Workflow depth 𝑑 (𝐺) Makespan (s) ↓ Cost ($) ↓ Utilization ↑ Resource Imbalance ↓ Distinct Resources Non-dominated Solutions ↑ Spacing (Schott’s) ↓ Hypervolume ↑

15

25

35

42

2663.27 ± 148.18 6.1716 ± 1.3416 50.69% ± 2.65% 1.6284 ± 0.2536 27.00 ± 1.29 25.20 ± 5.00 0.0998 ± 0.0391 0.8634 ± 0.1177

4039.80 ± 163.21 5.5210 ± 1.0050 47.99% ± 2.07% 1.7264 ± 0.2538 26.43 ± 1.16 28.00 ± 5.08 0.0781 ± 0.0301 0.8083 ± 0.0588

5244.33 ± 286.58 4.8848 ± 0.8934 45.98% ± 3.59% 1.9855 ± 0.2214 26.36 ± 1.03 32.30 ± 4.15 0.0724 ± 0.0220 0.7482 ± 0.0612

6220.51 ± 171.11 4.8246 ± 0.5016 45.94% ± 1.85% 1.9307 ± 0.2897 25.77 ± 1.50 33.50 ± 3.23 0.0800 ± 0.0276 0.7902 ± 0.0967

Table 9: Impact of workflow width 𝑤 (𝐺) on NSGA-II scheduling quality (mean ± std over 20 independent workflows), 𝑁 = 50, 𝑑 (𝐺) = 15 and all other parameters at their defaults. Workflow width 𝑤 (𝐺) Makespan (s) ↓ Cost ($) ↓ Utilization ↑ Resource Imbalance ↓ Distinct Resources Non-dominated Solutions ↑ Spacing (Schott’s) ↓ Hypervolume ↑

5

8

15

25

35

2639.93 ± 199.52 6.2573 ± 1.3518 48.15% ± 4.27% 1.7168 ± 0.2508 26.73 ± 1.87 24.80 ± 5.00 0.0871 ± 0.0266 0.9025 ± 0.0924

2663.27 ± 148.18 6.1716 ± 1.3416 50.69% ± 2.65% 1.6284 ± 0.2536 27.00 ± 1.29 25.20 ± 5.00 0.0998 ± 0.0391 0.8634 ± 0.1177

2640.81 ± 208.65 4.7648 ± 0.8270 50.09% ± 2.48% 1.6345 ± 0.2434 25.24 ± 1.78 21.80 ± 3.06 0.1030 ± 0.0334 0.8864 ± 0.0909

2491.95 ± 164.24 5.8199 ± 2.4837 55.94% ± 2.22% 1.6301 ± 0.2838 25.06 ± 1.38 27.60 ± 3.64 0.0927 ± 0.0452 0.7647 ± 0.1183

2347.12 ± 185.45 6.5181 ± 1.4381 59.09% ± 2.90% 1.5288 ± 0.2007 24.19 ± 2.27 28.10 ± 4.53 0.0998 ± 0.0379 0.7734 ± 0.1053

23

H

Cloud Resource Pool

This appendix provides tables for the impacts of cloud size and composition on the NSGA-II performance. Table 10: Impact of cloud resource pool size on NSGA-II scheduling quality (mean ± std over 20 independent workflows). Cloud size | R | Makespan (s) ↓ Cost ($) ↓ Utilization ↑ Resource Imbalance ↓ Distinct Resources Non-dominated Solutions ↑ Spacing (Schott’s) ↓ Hypervolume ↑

60

180

300

2663.27 ± 148.18 6.1716 ± 1.3416 50.69% ± 2.65% 1.6284 ± 0.2536 27.00 ± 1.29 25.20 ± 5.00 0.0998 ± 0.0391 0.8634 ± 0.1177

2676.70 ± 65.61 17.8053 ± 4.1071 47.87% ± 1.95% 1.7417 ± 0.1790 36.39 ± 1.40 27.00 ± 4.60 0.0900 ± 0.0292 0.8727 ± 0.1149

2591.85 ± 142.67 25.7325 ± 3.6668 45.67% ± 2.15% 1.8114 ± 0.2025 39.88 ± 0.77 28.50 ± 3.07 0.0839 ± 0.0265 0.8284 ± 0.1009

Table 11: Impact of cloud resource pool composition on NSGA-II scheduling quality (mean ± std over 20 independent workflows). Resource pool Makespan (s) ↓ Cost ($) ↓ Utilization ↑ Resource Imbalance ↓ Distinct Resources Non-dominated Solutions ↑ Spacing (Schott’s) ↓ Hypervolume ↑

CPU-only

GPU-only

CPU+GPU

2774.33 ± 157.20 6.7696 ± 1.4037 53.86% ± 3.33% 1.4666 ± 0.1971 27.57 ± 1.43 23.00 ± 4.80 0.1003 ± 0.0369 0.8166 ± 0.1199

2620.16 ± 124.50 64.7780 ± 7.7081 46.84% ± 3.13% 1.0554 ± 0.1541 22.25 ± 1.37 15.60 ± 2.76 0.1254 ± 0.0423 1.0291 ± 0.0481

2663.27 ± 148.18 6.1716 ± 1.3416 50.69% ± 2.65% 1.6284 ± 0.2536 27.00 ± 1.29 25.20 ± 5.00 0.0998 ± 0.0391 0.8634 ± 0.1177

24

References [1] Auguste Kerckhoffs. La cryptographie militaire. Journal des Sciences Militaires, IX:5–38, 161–191, 1883. [2] Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. Advances in neural information processing systems, 36:68539–68551, 2023. [3] Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629, 2022. [4] Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, et al. A survey on large language model based autonomous agents. Frontiers of computer science, 18(6):186345, 2024. [5] Jiayi Zhang, Jinyu Xiang, Zhaoyang Yu, Fengwei Teng, Xionghui Chen, Jiaqi Chen, Mingchen Zhuge, Xin Cheng, Sirui Hong, Jinlin Wang, et al. Aflow: Automating agentic workflow generation. In International Conference on Learning Representations, volume 2025, pages 34040–34077, 2025. [6] Guibin Zhang, Kaijie Chen, Guancheng Wan, Heng Chang, Hong Cheng, Kun Wang, Shuyue Hu, and Lei Bai. Evoflow: Evolving diverse agentic workflows on the fly. arXiv preprint arXiv:2502.07373, 2025. [7] Goshgar Can Ismayilov. MAWCS: A multi-agent workflow scheduling framework for heterogeneous models and cloud resources. In Joint Proceedings of the SEMANTiCS 2026 Workshops UKG, SAGE, Sem4Tra, SKGi, and SymGenAI4Sci, volume 4292 of CEUR Workshop Proceedings, 2026. [8] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE transactions on evolutionary computation, 6(2):182–197, 2002. [9] Juan J Durillo, Hamid Mohammadi Fard, and Radu Prodan. Moheft: A multi-objective list-based method for workflow scheduling. In 4th IEEE International Conference on Cloud Computing Technology and Science Proceedings, pages 185–192. IEEE, 2012. [10] Goshgar Ismayilov and Haluk Rahmi Topcuoglu. Neural network based multi-objective evolutionary algorithm for dynamic workflow scheduling in cloud computing. Future Generation computer systems, 102:307–322, 2020. [11] Ewa Deelman, Karan Vahi, Gideon Juve, Mats Rynge, Scott Callaghan, Philip J Maechling, Rajiv Mayani, Weiwei Chen, Rafael Ferreira Da Silva, Miron Livny, et al. Pegasus, a workflow management system for science automation. Future Generation Computer Systems, 46:17–35, 2015. [12] Goshgar C. Ismayilov. MAWGE: A parametric and synthetic multi-agentic workflow generator library. In Proceedings of the Ninth Workshop on Natural Language for Artificial Intelligence, volume 4315 of CEUR Workshop Proceedings, 2026. [13] Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Beibin Li, Erkang Zhu, Li Jiang, Xiaoyun Zhang, Shaokun Zhang, Jiale Liu, et al. Autogen: Enabling next-gen llm applications via multi-agent conversation. arXiv preprint arXiv:2308.08155, 2023. [14] Sirui Hong, Mingchen Zhuge, Jonathan Chen, Xiawu Zheng, Yuheng Cheng, Jinlin Wang, Ceyao Zhang, Steven Yau, Zijuan Lin, Liyang Zhou, et al. Metagpt: Meta programming for a multi-agent collaborative framework. In International Conference on Learning Representations, volume 2024, pages 23247–23275, 2024. [15] Guohao Li, Hasan Hammoud, Hani Itani, Dmitrii Khizbullin, and Bernard Ghanem. Camel: Communicative agents for" mind" exploration of large language model society. Advances in neural information processing systems, 36:51991–52008, 2023. [16] Joon Sung Park, Joseph O’Brien, Carrie Jun Cai, Meredith Ringel Morris, Percy Liang, and Michael S Bernstein. Generative agents: Interactive simulacra of human behavior. In Proceedings of the 36th annual acm symposium on user interface software and technology, pages 1–22, 2023. [17] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824–24837, 2022. [18] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171, 2022. [19] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Advances in neural information processing systems, 36:11809–11822, 2023. [20] Yilun Du, Shuang Li, Antonio Torralba, Joshua B Tenenbaum, and Igor Mordatch. Improving factuality and reasoning in language models through multiagent debate. arXiv preprint arXiv:2305.14325, 2023. [21] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. Advances in neural information processing systems, 36:46534–46594, 2023. [22] Haluk Topcuoglu, Salim Hariri, and Min-You Wu. Task scheduling algorithms for heterogeneous processors. In Proceedings. Eighth Heterogeneous Computing Workshop (HCW’99), pages 3–14. IEEE, 1999. [23] Zhaomeng Zhu, Gongxuan Zhang, Miqing Li, and Xiaohui Liu. Evolutionary multi-objective workflow scheduling in cloud. IEEE Transactions on parallel and distributed Systems, 27(5):1344–1357, 2015. [24] Huifang Li, Binyang Wang, Yan Yuan, Mengchu Zhou, Yushun Fan, and Yuanqing Xia. Scoring and dynamic hierarchy-based nsga-ii for multiobjective workflow scheduling in the cloud. IEEE Transactions on Automation Science and Engineering, 19(2):982–993, 2021. [25] Goshgar Ismayilov and Haluk Rahmi Topcuoglu. Dynamic multi-objective workflow scheduling for cloud computing based on evolutionary algorithms. In 2018 IEEE/ACM International Conference on Utility and Cloud Computing Companion (UCC Companion), pages 103–108. IEEE, 2018. [26] Sonia Yassa, Rachid Chelouah, Hubert Kadima, and Bertrand Granado. Multi-objective approach for energy-aware workflow scheduling in cloud computing environments. The Scientific World Journal, 2013(1):350934, 2013. [27] Amandeep Verma and Sakshi Kaushal. A hybrid multi-objective particle swarm optimization for scientific workflow scheduling. Parallel Computing, 62:1–19, 2017. [28] Ali Mohammadzadeh and Mohammad Masdari. Scientific workflow scheduling in multi-cloud computing using a hybrid multi-objective optimization algorithm. Journal of Ambient Intelligence and Humanized Computing, 14(4):3509–3529, 2023. [29] Farzaneh Abazari, Morteza Analoui, Hassan Takabi, and Song Fu. Mows: multi-objective workflow scheduling in cloud computing based on heuristic algorithm. Simulation Modelling Practice and Theory, 93:119–132, 2019. [30] Michael Luo, Xiaoxiang Shi, Colin Cai, Tianjun Zhang, Justin Wong, Yichuan Wang, Chi Wang, Yanping Huang, Zhifeng Chen, Joseph E Gonzalez, et al. Autellix: An efficient serving engine for llm agents as general programs. arXiv preprint arXiv:2502.13965, 2025. [31] Chaofan Lin, Zhenhua Han, Chengruidong Zhang, Yuqing Yang, Fan Yang, Chen Chen, and Lili Qiu. Parrot: Efficient serving of { LLM-based } applications with semantic variable. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), pages 929–945, 2024. [32] Youhe Jiang, Ran Yan, Xiaozhe Yao, Yang Zhou, Beidi Chen, and Binhang Yuan. Hexgen: Generative inference of large language model over heterogeneous environment. arXiv preprint arXiv:2311.11514, 2023. [33] Tyler Griggs, Xiaoxuan Liu, Jiaxiang Yu, Doyoung Kim, Wei-Lin Chiang, Alvin Cheung, and Ion Stoica. M\’elange: Cost efficient large language model serving by exploiting gpu heterogeneity. arXiv preprint arXiv:2404.14527, 2024. [34] Isaac Ong, Amjad Almahairi, Vincent Wu, Wei-Lin Chiang, Tianhao Wu, Joseph E Gonzalez, Mohammed Kadous, and Ion Stoica. Routellm: Learning to route llms from preference data. In International Conference on Learning Representations, volume 2025, pages 34433–34448, 2025. [35] You Peng, Youhe Jiang, Wenshuang Li, Xu Xu, Ke Zhou, Jiawei Jiang, Chen Wang, and Binhang Yuan. Hexagent: Efficient agentic llm serving via workflow-and heterogeneityaware scheduling. arXiv preprint arXiv:2605.16637, 2026. [36] Eckart Zitzler and Lothar Thiele. Multiobjective optimization using evolutionary algorithms—a comparative case study. In International conference on parallel problem solving from nature, pages 292–301. Springer, 1998. [37] Tadahiko Murata, Hisao Ishibuchi, et al. Moga: multi-objective genetic algorithms. In IEEE international conference on evolutionary computation, volume 1, pages 289–294. IEEE Piscataway, 1995. [38] Jason Ramon Schott. Fault tolerant design using single and multicriteria genetic algorithm optimization. PhD thesis, Massachusetts Institute of Technology, 1995. [39] BenchLM.AI. LLM speed benchmarks. https://benchlm.ai/llm-speed, 2026. [40] Vantage. Amazon EC2 instance comparison. https://instances.vantage.sh, 2026.

25

Related documents

• Semantics, Workflows, and Infrastructure: Understanding Agent Serving at Production Scale#1128702
• Semantics, Workflows, and Infrastructure: Understanding Agent Serving at Production Scale#1108711
• Scepsy: Serving Agentic Workflows Using Aggregate LLM Pipelines#1105012
• Designing LLM-based Multi-Agent Systems for Software Engineering Tasks: Quality Attributes, Design Patterns and Rationale#1633717
• You're Hired: Strategic Model Selection for LLM Collaboration#1143417