arXiv CSopen access

Latency-Aware Service Placement using Neural Combinatorial Optimisers for Edge--Cloud Systems

EP-NCO: Latency-Aware Service Placement using Neural Combinatorial Optimisers for Edge–Cloud Systems Kimia Abedpoura,∗ , Mohammadsadeq Garshasbi Herabadb , Zheng Lia and Javid Taheria,b a School of Electronics, Electrical Engineering and Computer Science, Queen’s University Belfast , Belfast, BT7 1NN, UK

arXiv:2606.25553v1 [cs.DC] 24 Jun 2026

b Department of Mathematics and Computer Science, Karlstad University Karlstad, 651 88, Sweden

ARTICLE INFO

ABSTRACT

Keywords: Edge–cloud computing Service placement Neural combinatorial optimisation Graph neural networks Reinforcement learning Latency optimisation

The growth of Internet of Things (IoT) applications and latency-sensitive services has increased the demand for efficient service placement across compute continuum platforms, such as edge– cloud systems. Modern applications are decomposed into interdependent microservices deployed over heterogeneous infrastructures, making placement under resource and network constraints an intractable NP-hard combinatorial optimisation problem. This study proposes a latency-aware Edge Placement Neural Combinatorial Optimiser (EP-NCO), a learning-based framework for service placement in compute continuum platforms. EP-NCO employs a dual-graph model to capture resource relationships and service dependencies within both computing infrastructure and application structure. Graph neural networks (GNNs) learn structural embeddings of infrastructure nodes and servicecomponents, whereas reinforcement learning policies construct feasible placements that account for execution latency, communication link delays, and bandwidth-sharing effects. Extensive simulations across multiple system scales demonstrate that EP-NCO consistently achieves high-quality placement decisions, reducing the total service response time by 46%–50% compared with metaheuristics (genetic algorithm and particle swarm optimisation) and by 25%–35% compared with controlled RL ablation baselines. Once trained, EP-NCO enables fast online inference, making it a practical solution for dynamic large-scale edge–cloud environments with hundreds of computing nodes, hosting thousands of applications, which is significatly beyond the capability of current scheduling systems.

1. Introduction The advancement of Internet of Things (IoT) technologies has enabled latency-sensitive applications such as smart cities, industrial automation, and intelligent transportation systems. However, the resulting scale and heterogeneity introduce significant design and management challenges, making scalable and maintainable software architectures essential [1]. Microservice architectures address these challenges by decomposing applications into loosely coupled services, a trend accelerated by lightweight containerisation technologies that reduce resource overhead and simplify orchestration [2]. Cloud computing offers scalable computing and networking resources; however, it often suffers from high latency because of the physical distance between data centres and end edge-connected-devices. Edge computing mitigates this limitation by extending computation closer to data sources [3]. Consequently, edge–cloud infrastructures are highly distributed and heterogeneous in terms of computing capacity and network connectivity, making efficient and adaptive service placement a fundamental challenge under dynamic workloads and resource constraints. Service placement in edge-cloud environments is a combinatorial optimisation problem [4], where the goal is to ∗ Corresponding author

[email protected] (K. Abedpour); [email protected] (M.G. Herabad); [email protected] (Z. Li); [email protected] (J. Taheri) ORCID (s): 0009-0009-5961-4633 (K. Abedpour); 0000-0002-2336-2077 (M.G. Herabad); 0000-0002-9704-7651 (Z. Li); 0000-0001-9194-010X (J.

Taheri)

determine the optimal mapping between services and heterogeneous computing nodes while satisfying constraints such as resource availability, latency requirements, and costs. As microservice components and candidate nodes increase, the solution space grows exponentially, making exhaustive searches computationally infeasible. This problem is classified as NP-hard [5, 6, 7], implying that obtaining (computing) optimal solutions cannot be guaranteed in polynomial time. This mandates practical approaches [8] to rely on rulebased heuristics, meta-heuristics, or learning-based methods to explore the solution space and obtain (near-)optimal placement strategies within a reasonable time. Rule-based heuristic approaches [9, 10, 11] emphasise low computational overhead and fast decision-making; however, they often sacrifice solution quality. Meta-heuristic methods [12, 13, 14, 15] explore the search space more extensively and typically achieve higher-quality solutions, albeit at the cost of significant computational overhead, thereby limiting their applicability to offline optimisation. Learning-based approaches [16, 17, 18] shift this cost to an offline training phase and enable fast inference; however, they frequently suffer from high training complexity and limited generalisation under dynamic system conditions. Reinforcement learning (RL), particularly Q-learning, has been widely applied to dynamic decision-making in edge–cloud environments owing to its adaptability to workload and resource variations [19, 20]. However, the rapid growth of state–action spaces significantly limits its scalability and training efficiency in large-scale service placement scenarios [21, 22].

1

Abedpour et al.: Preprint submitted to Elsevier

Page 1 of 18

Latency-Aware Neural Service Placement

• Conducting extensive experiments to evaluate multiple solutions (rule-based heuristics, metaheuristics, RL-based, etc.), demonstrating their efficiency to solve the stated NP-hard service placement problem.

Figure 1: Conceptual comparison of solution quality versus execution time for greedy, rule-based heuristic, metaheuristic, exact, RL, Q-Learning, and NCO approaches.

Neural combinatorial optimisation (NCO) has recently emerged as an alternative paradigm for solving large-scale combinatorial problems using neural networks. By learning constructive heuristics directly, often through RL, NCO can efficiently generate high-quality solutions without an exhaustive search [23, 24]. This makes it particularly suitable for service placement problems with large and complex search spaces. Nevertheless, NCO-based solutions are still in their infancy and currently face multiple challenges, including generalisation across varying environments and the ability to handle strict constraints when solving multifaceted problems, such as the service placement problem for distributed systems [25]. Figure 1 shows a visual/conceptual comparison of the relative performances of different optimisation paradigms, clarifying the trade-off between their solution quality and execution time. To this end, in this study, we designed an NCO-based approach (EP-NCO: edge placement using NCO) to efficiently solve the service placement problem. In EP-NCO, the edgecloud infrastructure is represented as a graph, where nodes correspond to computing resources and edges represent network connectivity. Node attributes encode characteristics such as processing capacity, memory, and storage availability. Service requirements and constraints are incorporated to capture deployment dependencies and resource demands. EP-NCO uses Graph Neural Networks (GNNs) to capture the structural properties of the infrastructure graph and Reinforcement Learning (RL) to learn optimal sequential placement policies that map system states to deployment decisions. EP-NCO aims to optimise the response time and resource utilisation. The main contributions span from modelling to evaluation, as follows: • Developing a graph-based formulation of the service placement problem that captures infrastructure topology, heterogeneous node characteristics, and service requirements to provide a structured and scalable representation of edge-cloud systems. • Proposing an NCO-based approach (EP-NCO) that integrates GNNs with RLs to learn efficient service placement policies directly from system states. Abedpour et al.: Preprint submitted to Elsevier

The remainder of this paper is organised as follows. Section 2 presents a review of related work. Section 3 describes the proposed system model and formulates the optimisation objectives. Section 4 provides details on the design of the proposed solution (EP-NCO). Section 5 presents the experimental setup and implementation details. Section 6 evaluates the efficiency of all methods. Section 7 concludes the paper by summarising the main findings and outlining future research directions.

2. Related Work Existing research on latency-aware service placement in edge–cloud environments can be categorised into three main groups: heuristic approaches, metaheuristic solutions, and learning-based techniques. Each of these approaches proposes distinct strategies for assigning services to distributed resources under latency and resource constraints, leading to different scalability, computational overhead, and adaptability.

2.1. Exact Methods Exact methods typically formulate the service placement problem as an Integer Linear Programming (ILP) or MixedInteger Linear Programming (MILP) model, incorporating latency, resource, and routing constraints within a rigorous optimisation framework. Such approaches guarantee globally optimal solutions and offer a precise mathematical representation of the system [26]. However, their computational complexity increases exponentially with the size of the problem, rendering them impractical for large-scale or dynamic edge–cloud environments. Furthermore, these methods often depend on static assumptions and require complete knowledge of the system, which limits their applicability in real-world scenarios [27]. Therefore, exact optimisation methods are not suitable for the problem setting considered in this study and are not explored further.

2.2. Heuristics Heuristic methods are problem-specific strategies designed to obtain good-quality solutions at a low computational cost by exploiting simplified rules or local information rather than exhaustive search. In latency-aware service placement, heuristics typically prioritise proximity-aware or delay-aware decisions, such as placing services closer to edge-connected-devices or selecting nodes with lower communication delay; however, they often rely on handcrafted rules and simplified optimisation models. Several heuristic approaches have been proposed for service placement. Wu et al. [11] introduced a decentralised fuzzy-control heuristic for online resource allocation; however, its reliance on predefined scoring rules limits its adaptability under complex dynamics. Xu et al. [28] proposed a gravitational search Page 2 of 18

Latency-Aware Neural Service Placement

algorithm for DAG-structured task offloading, which incurs a high runtime overhead because of its population-based nature. Brogi and Forti [29] introduced a QoS-aware heuristicguided backtracking framework that prioritises feasibility over optimisation, resulting in exponential worst-case complexity. Other specialised heuristics target constrained scenarios, such as greedy graph colouring for virtual reality (VR) task allocation [30] and direct-to-device (D2D)assisted offloading [10]; however, these approaches often rely on static assumptions and manual tuning. Overall, heuristic methods offer fast and lightweight solutions suitable for real-time and large-scale deployments; however, they generally lack optimality guarantees and adaptability in complex and highly dynamic edge–cloud environments.

2.3. Metaheuristics Metaheuristic methods are high-level optimisation strategies that explore the search space using stochastic operators to escape local optima and typically achieve higher-quality solutions than simple heuristics, albeit at a significant computational cost. They have been widely applied to service placement and resource allocation in edge–cloud systems. Herabad et al. [31] proposed a multi-objective genetic algorithm (MOGA) for AR/VR service placement and demonstrated performance gains; however, it suffered from long convergence times because of its population-based nature. The same authors introduced E-PSOGA [12], a hybrid PSO– GA approach with improved reliability but similarly high runtime overhead. Souza et al. [32] applied an artificial bee colony algorithm for task offloading and achieved strong optimisation quality at the cost of a substantial computational demand. Other hybrid metaheuristic approaches, including GA-SA-PSO [13], quantum-inspired PSO [14], and the Whale Optimisation Algorithm with autonomic control [33], further improve placement quality but remain sensitive to parameter tuning, memory-intensive, and poorly scalable as the problem size increases. Overall, the iterative and population-based nature of metaheuristics limits their applicability to offline optimisation scenarios, making them less suitable for latencysensitive and large-scale edge–cloud environments.

2.4. Learning-based Approaches Learning-based methods learn placement policies from historical or simulated interactions, shifting the computational complexity to an offline training phase while enabling fast inference at runtime (i.e., inference time). In latencyaware service placement, these approaches can capture the complex relationships between workloads, network conditions, and resource availability, leading to adaptive and context-aware decisions. Learning-based approaches can be categorised into three main classes of solutions. RL-based approaches: RL-based methods have been widely explored as alternatives to metaheuristics for service placement. Several studies integrate GNNs with RL to model service dependencies and heterogeneous infrastructure characteristics [34, 35, 36, 37]. While these approaches Abedpour et al.: Preprint submitted to Elsevier

improve placement quality, they typically rely on complex architectures, accurate global state information, or extensive interaction data, resulting in high training costs and limited scalability under dynamic system conditions [17, 38]. Q-learning-based approaches: Q-learning-based methods learn value functions through iterative interaction with the environment and benefit from their simplicity and modelfree nature. For example, Wang et al. [39] proposed a hierarchical Q-learning framework for multi-level service placement. However, the exponential growth of the state– action space severely limits the scalability of Q-learning in large-scale and highly dynamic edge–cloud systems. NCO-based approaches: NCO-based approaches employ neural architectures to learn constructive heuristics for solving large combinatorial optimisation problems. Xiao et al. [40] introduced an encoder–decoder NCO framework for task offloading under specific edge configurations. Despite promising results, existing NCO-based solutions still face challenges in generalisation across heterogeneous environments and in handling strict placement constraints. Overall, learning-based approaches enable fast inference and adaptive decision-making but often incur high training costs and exhibit limited robustness under variable workloads and large-scale deployment scenarios. In practice, RLbased methods are typically suitable for moderately dynamic environments, Q-learning for smaller problem instances, and NCO-based approaches for large-scale service placement tasks that require efficient online inferences.

2.5. Research Gap Despite extensive research on latency-aware service placement, existing approaches exhibit fundamental tradeoffs that limit their effectiveness in dynamic and large-scale edge–cloud environments. Heuristic and Exact methods provide fast and low-cost decisions but rely on handcrafted rules and local information, leading to suboptimal and poorly generalisable solutions. Metaheuristics improve solution quality through extensive search; however, their high computational overhead makes them unsuitable for real-time scenarios. Learningbased approaches, particularly RL and Q-learning, enable adaptive decision-making but suffer from scalability issues, large state–action spaces, and high training complexity. Recent neural combinatorial optimisation (NCO) methods offer fast inference and improved modelling capability, yet they still face challenges in generalisation across heterogeneous systems and in handling strict constraints. Therefore, a critical gap remains in designing a placement method that simultaneously achieves high solution quality, scalability, and efficient online decision-making without relying on restrictive assumptions or excessive computational cost. This motivates the need for a scalable and generalisable learning-based framework capable of capturing structural dependencies while maintaining practical efficiency.

Page 3 of 18

Latency-Aware Neural Service Placement

minimises the overall system cost, including execution link delay, communication overhead, and end-to-end response time: min

𝐗∈{0,1}𝐿×𝑀

𝑓 (𝐗)

(3)

Component dependencies are modelled as a directed acyclic graph (DAG)  = (, ). For each edge (𝑐𝑢 , 𝑐𝑣 ) ∈ , placing service-components on different nodes incurs communication cost and latency constraints. The placement problem must satisfy strict CPU and memory capacity constraints and execution dependencies while minimising performance costs, yielding an NP-hard optimisation problem with an exponentially large search space [41]. Figure 2: Multi-tier edge-to-cloud architecture including edgeconnected-devices, access point, edge, cloud, and cloudconnected layers.

3. Service Placement and System Model A multi-tier edge–cloud computing environment comprising heterogeneous computational and networking resources is considered to represent an edge-cloud system (the most common representation of compute continuum platforms) that spans from edge-connected-devices to centralised cloud servers. As illustrated in Figure 2, the architecture includes edge-connected-devices, access points, edge nodes, cloud servers, and cloud-connected-devices nodes. Collectively, they support the execution of distributed services to model a latency-aware service placement across the network.

3.1. Service Placement Problem Service placement is a combinatorial optimisation problem in which service-components are mapped to heterogeneous computing nodes under resource and performance constraints. Let  = {𝑐1 , … , 𝑐𝐿 } and  = {𝑣1 , … , 𝑣𝑀 } denote the service-components and available nodes, respectively. Equation (1) defines the binary decision variable 𝑥𝑖𝑗 , which indicates whether component 𝑐𝑖 is assigned to node 𝑣𝑗 : { 𝑥𝑖𝑗 =

1, 0,

if 𝑐𝑖 is assigned to 𝑣𝑗 otherwise.

(1)

Equation (2) enforces the resource capacity constraint on each node, ensuring that the total resource demand of assigned components does not exceed the available capacity: 𝐿 ∑

𝑥𝑖𝑗 𝐝𝑖 ≤ 𝐫𝑗 ,

∀𝑣𝑗 ∈ 

(2)

𝑖=1

Equation (3) defines the optimisation objective of the service placement problem, which seeks an assignment 𝐗 that Abedpour et al.: Preprint submitted to Elsevier

3.2. Computing Nodes Model The computing infrastructure is modelled as a directed graph representing a heterogeneous set of computational resources. Let  = {1, … , 𝑁} denote the set of computing nodes, which includes cloud nodes, edge nodes, cloudconnected nodes, and edge-connected-devices. Each node 𝑛 ∈  is characterised by its limited computational resources, namely its CPU capacity cpuCap𝑛 and memory capacity memCap𝑛 . Network Model: Network connectivity between nodes is represented as a directed graph 𝐺𝑛𝑒𝑡 = ( ,  𝑛𝑒𝑡 ) where (𝑖, 𝑗) ∈  𝑛𝑒𝑡 indicates the existence of a communication link from node 𝑖 to node 𝑗. Each link is associated with a bandwidth bw𝑖𝑗 > 0 and a propagation link delay delay𝑖𝑗 . Service Model: Let  = {1, … , 𝑆} denote the set of services, where each service 𝑠 ∈  consists of a set of service-components 𝑠 . Equation (4) represents the internal dependency structure of each service as a directed acyclic graph: 𝐺𝑠 = (𝑠 , 𝑠 )

(4)

where an edge (𝑢, 𝑣) ∈ 𝑠 indicates that component 𝑣 depends on the output produced by component 𝑢 (i.e., 𝑣 can be executed after 𝑢 finishes). Each component 𝑐 ∈ 𝑠 requires cpuReq𝑐 units of CPU, memReq𝑐 units of memory, and generates output data of size dataSize𝑐 .

3.3. Sequential Placement Model In this study, the service placement problem is solved using sequential service placement decisions, wherein servicecomponents are assigned to computing nodes one-by-one. Equation (5) defines the binary placement decision variable indicating whether component 𝑐 is assigned to node 𝑛: { 𝑥𝑐,𝑛 =

1, 0,

if component 𝑐 is assigned to node 𝑛 (5) otherwise.

Each component 𝑐 must be assigned to exactly one computing node 𝑎(𝑐) (𝑎(𝑐) = 𝑛 if 𝑥𝑐,𝑛 = 1). During the Page 4 of 18

Latency-Aware Neural Service Placement

placement process, service-components are deployed sequentially according to the service dependency structure. At each decision step, a placement action selects a node for the next service-component, considering resource availability and network feasibility constraints.

3.4. Objective Function The objective function Equation (6) minimises the total response time of the deployed services, which is defined as the sum of the execution and communication link delays. This additive formulation models the overall system latency and serves as a tractable surrogate for end-to-end service performance. min 𝑇total = 𝑇exec + 𝑇trans

{𝑥𝑐,𝑛 }

(6)

Execution Time: The execution time in Equation (7) depends on the computational demand of each component and the processing capacity of the node on which it is deployed. 𝑇exec =

∑∑ ∑ 𝑠∈ 𝑐∈𝑠 𝑛∈

𝑥𝑐,𝑛

cpuReq𝑐 cpuCap𝑛

(7)

Transmission Delay: Communication link delays occur when dependent servicecomponents are deployed on different nodes. For each dependency (𝑢, 𝑣) ∈ 𝑠 , the data generated by component 𝑢 must be transferred to the node hosting component 𝑣. To model bandwidth contention, let 𝑠𝑖𝑗 denote the number of concurrent data flows traversing link (𝑖, 𝑗). Communication is restricted to direct network links, and multi-hop routing is not considered to maintain model tractability in large-scale settings. Accordingly, 𝑠𝑖𝑗 denotes the number of service dependencies directly using link (𝑖, 𝑗). Equation (8) computes the effective bandwidth under bandwidth sharing among concurrent flows: ef f Bw𝑖𝑗 =

bw𝑖𝑗 𝑠𝑖𝑗

(8)

Equation (9) is to calculate the total transmission link delay considering data transfer time and propagation link delay. If no direct network link exists between the selected nodes, the placement is considered infeasible and excluded from the decision process. ( ) ∑ ∑ dataSize𝑢 𝑇trans = + delay𝑎(𝑢),𝑎(𝑣) . (9) ef f Bw𝑎(𝑢),𝑎(𝑣) 𝑠∈ (𝑢,𝑣)∈ 𝑠

3.5. Constraints Resource Capacity Constraints: Constraints (10) and (11) ensure that the total resource consumption of service-components deployed on each node does not exceed the available node capacities. ∑∑ 𝑥𝑐,𝑛 memReq𝑐 ≤ memCap𝑛 , ∀𝑛 ∈  (10) 𝑠∈ 𝑐∈𝑠

Abedpour et al.: Preprint submitted to Elsevier

Table 1 System model-related notation. Notation 

 𝑛𝑒𝑡 𝐺𝑛𝑒𝑡 = ( ,  𝑛𝑒𝑡 ) bw𝑖𝑗 delay𝑖𝑗 𝑠𝑖𝑗 ef fBw𝑖𝑗  𝑠 𝐺𝑠 = (𝑠 , 𝑠 ) (𝑢, 𝑣) ∈ 𝑠 cpuReq𝑐 memReq𝑐 dataSize𝑐 cpuCap𝑛 memCap𝑛 𝑥𝑐,𝑛 𝑎(𝑐) 𝑇total 𝑇exec 𝑇trans

∑∑

Description Set of computing nodes (cloud, edge, cloud-connected-devices, edge-connecteddevices-layer) Set of directed network links between nodes Network connectivity graph Bandwidth of link (𝑖, 𝑗) Propagation delay of link (𝑖, 𝑗) Number of concurrent flows sharing link (𝑖, 𝑗) Effective bandwidth of link (𝑖, 𝑗) (shared) Set of services Set of service-components in service 𝑠 DAG representing service structure Dependency: component 𝑣 depends on output of 𝑢 CPU requirement of component 𝑐 Memory requirement of component 𝑐 Output data size of component 𝑐 CPU capacity of node 𝑛 Memory capacity of node 𝑛 Binary placement variable (1 if component 𝑐 is placed on node 𝑛) Node to which component 𝑐 is assigned Total response time Execution time of all service-components Transmission link delay due to data transfers

𝑥𝑐,𝑛 cpuReq𝑐 ≤ cpuCap𝑛 ,

∀𝑛 ∈ 

(11)

𝑠∈ 𝑐∈𝑠

Bandwidth Sharing Constraint: When multiple dependency flows are mapped onto the same network link, the available bandwidth is shared among them according to the effective bandwidth definition in Equation( 8).

4. EP-NCO: Proposed Solution To solve the stated service placement problem, we designed EP-NCO, a learning-based NCO framework to learn scalable placement policies that generate high-quality, feasible solutions for edge-cloud systems. EP-NCO aims to address the inefficiency of exact solvers in relation to their exponentially growing execution time. Problem Statement(Service Placement): The service placement problem is modelled as a combinatorial optimisation problem  = (𝑋, 𝑓 , ), where 𝑋 ⊆ {0, 1}𝑛 represents the discrete solution space, 𝑓 ∶ 𝑋 → ℝ denotes the objective function to be minimised or maximised, and  ensures that all constraints are satisfied, expressed as 𝑔𝑖 (𝑥) ≤ 0 or ℎ𝑗 (𝑥) = 0. The optimal solution 𝑥∗ = arg min𝑥∈𝑋 𝑓 (𝑥) is subject to these constraints. Page 5 of 18

Latency-Aware Neural Service Placement

Figure 3: Proposed dual-graph encoder–decoder architecture based on GNN encoding and autoregressive decoding with multi-head attention.

Neural Combinatorial Optimisation: The EP-NCO solver/model learns solution construction policies for discrete optimisation problems using existing solutions or procedures. EP-NCO uses a neural model to map problem instances to high-quality solutions. Given a search space 𝑋 and objective 𝑓 ∶ 𝑋 → ℝ, an NCO model then learns a parameterised policy 𝜋𝜃 ∶ 𝑋 →  that generates solutions 𝑥𝜃 such that 𝑓 (𝑥𝜃 ) ≈ 𝑓 (𝑥∗ ). Architectures such as GNNs are used to encode structural constraints, thereby enabling near-instantaneous decisions in large-scale optimisation settings. Graph neural networks (GNNs): GNNs operate on graph-structured data  = (, ), where (a) each node 𝑣𝑖 has features 𝐡(0) 𝑖 and (b) each edge encodes a communication or dependency relation. In this context, nodes correspond to either infrastructure graph nodes or service graph nodes, depending on the graph type. GNNs are used to capture multi-hop structural dependencies for downstream tasks to solve the service placement problem. Equation (12) defines the node representation update at layer 𝑙 in EP-NCO, where neighbour messages are aggregated: ⎛

⨁

⎝

𝑣𝑗 ∈ (𝑖)

𝐡(𝑙+1) = 𝜙(𝑙) ⎜𝐡(𝑙) , 𝑖 ⎜ 𝑖

𝜓

(𝑙)

⎞

(𝑙) ⎟ (𝐡(𝑙) 𝑖 , 𝐡𝑗 , 𝐞𝑖𝑗 )⎟

(12)

⎠

4.1. Dual-Graph Representation and State Encoding Figure 3 illustrates the NCO architecture of EP-NCO. The framework adopts a dual-graph representation that jointly models the computing infrastructure and the internal structure of services. The encoder employs GNNs to extract structural embeddings from both graphs, whereas the decoder sequentially constructs a placement solution using an Abedpour et al.: Preprint submitted to Elsevier

autoregressive policy guided by multi-head attention. This design enables the model to simultaneously reason about resource availability, network connectivity, and service-level dependencies. Network Graph Encoding: The computing infrastructure is represented as a directed graph 𝐺𝑛𝑒𝑡 = ( ,  𝑛𝑒𝑡 ), where infrastructure graph nodes correspond to heterogeneous computing entities across the compute (cloud–edge–edge-connected-devices) continuum, and infrastructure graph edges denote communication links. Each infrastructure graph node 𝑛 ∈  is associated with a feature vector describing its available computational resources (CPU and memory capacities), whereas each infrastructure graph edge (𝑖, 𝑗) ∈  𝑛𝑒𝑡 captures link attributes between nodes (bandwidth and propagation link delay). A GNN (NodeGNN) encodes the infrastructure state. The infrastructure graph nodes are updated through a messagepassing procedure in which each node aggregates information from its neighbouring infrastructure graph nodes. Equation (13) updates node 𝑛 at layer 𝑘 (𝐡(𝑘) 𝑛 ) after each iteration. ( ( )) 𝐡(𝑘+1) = 𝜎 𝑊 (𝑘) ⋅ AGG {𝐡(𝑘) (13) 𝑛 𝑢 ∶ 𝑢 ∈  (𝑛)} Here,  (𝑛) denotes the neighbourhood of node 𝑛, 𝑊 (𝑘) is a trainable weight matrix at layer 𝑘, AGG(⋅) represents an aggregation function (e.g., mean aggregation), and 𝜎(⋅) denotes a nonlinear activation function. In EP-NCO, the NodeGNN comprises four messagepassing layers and generates infrastructure graph node embeddings with a dimension of 32 to capture both local resource availability and global network connectivity patterns. This provides a compact representation of the infrastructure state for the placement policy. Service Graph Encoding:

Page 6 of 18

Latency-Aware Neural Service Placement

Each service is modelled as a DAG 𝐺𝑠 = (𝑠 , 𝑠 ), where the service graph nodes represent service-components and service graph edges capture their data dependencies. Each service graph node is associated with a feature vector describing its computational requirements, including CPU demand, memory usage, and output data size. In harmony with NodeGNN, another GNN (ServiceGNN) encodes service DAGs to compute embeddings for all service graph nodes. Similar to NodeGNN, ServiceGNN performs iterative message passing along the service graph edges. Equation (14) defines the embedding update for a service graph node 𝑐 at layer 𝑘: ( ( )) 𝐡(𝑘+1) = 𝜎 𝑊𝑠(𝑘) ⋅ AGG {𝐡(𝑘) (14) 𝑐 𝑢 ∶ (𝑢, 𝑐) ∈ 𝑠 }

search space by considering only feasible placements when generating decisions. Despite its restrictive behaviour, this constraint-aware decoding strategy significantly reduces the effective search space and prevents the generation of invalid placements. Moreover, by updating the infrastructure node capacities and network states after each assignment, the hard-decoder maintains an incremental representation of the system state, thereby enabling subsequent decisions to account for previously allocated resources. In summary, each decoder has its own pros. and cons. The hard-decoder provides a more structured and constraintcompliant decision-making process by restricting the action space to feasible solutions and improving decision stability. However, this restriction may limit exploration and increase the risk of suboptimal policies. In contrast, the softdecoder allows for a broader exploration of the solution (𝑘) where 𝑊𝑠 denotes the trainable parameters of the Serspace and may discover better placements; however, it reviceGNN at layer 𝑘. This message-passing mechanism allies on penalty-based learning and may generate infeasible lows the encoder to capture the structural dependencies and intermediate solutions, leading to slower convergence. precedence relations between service graph nodes. Autoregressive Decision Process: The resulting embeddings summarise both the resource Let {𝑐1 , 𝑐2 , … , 𝑐𝐶 } denote the ordered sequence of requirements and the structural role of each service graph service-components to be placed, following the dependency node within the overall service workflow. constraints of the service graph. At each step 𝑡, the policy selects a hosting infrastructure node for service-component 4.2. Autoregressive Placement Policy and 𝑐𝑡 conditioned on the current system representation and the Constraint Handling assignments made in previous steps. Given the encoded dual-graph representation, EP-NCO conEquation (15) defines the factorisation of the joint asstructs placement solutions using an autoregressive decision signment distribution under the placement policy: process. Instead of optimising all service-components to 𝐶 infrastructure nodes simultaneously, the model sequentially ∏ ) ( (𝑡) assigns one service-component to one infrastructure node, (15) 𝜋(𝐱) = 𝜋 𝑎(𝑐𝑡 ) ∣ 𝐡(𝑡) 𝑐 , 𝐇𝑛 thereby decomposing the original combinatorial problem 𝑡=1 into a series of conditional decision-making problems. where 𝐡(𝑡) Hard and Soft Decoding Strategies: 𝑐 denotes the embedding of the current servicecomponent obtained from ServiceGNN, and 𝐇(𝑡) To satisfy the system constraints during the sequential 𝑛 represents the set of infrastructure graph node embeddings in placement process, EP-NCO employs two decoding strateNodeGNN. gies: soft-decoding and hard-decoding. To evaluate the candidate placements, the decoder comIn the soft-decoder strategy, the autoregressive policy putes the compatibility scores between the service-component generates placement decisions without explicitly enforcing embedding and the embeddings of all candidate infrastrucfeasibility constraints during the decoding process. The polture graph nodes using a multi-head attention mechanism. icy assigns probabilities to all candidate infrastructure graph These scores are then transformed into a probability distrinodes, thereby allowing the model to explore a broader bution via a softmax function, enabling stochastic sampling action space during training. Constraint violations, such as during training and greedy selection during inference. insufficient resource capacity or infeasible network connecFeasibility Masking for Constraint Enforcement: tions, are not prevented during decision-making. Instead, The hard constraints defined in Section 3 are enforced they are incorporated into the optimisation objective through during decoding through feasibility masking, which removes penalty terms added to the overall cost function. Conseinfeasible assignments from the action space at each decision quently, infeasible solutions incur higher costs and are disstep. couraged during learning. Resource Capacity Constraints: A service-component In the hard-decoder strategy, the autoregressive policy can only be assigned to an infrastructure node if sufficient explicitly incorporates problem constraints into the decodresidual CPU and memory resources are available. Infrasing phase. At each decision step, feasibility checks were tructure graph nodes that violate Constraint (10) are masked performed to ensure that the candidate infrastructure graph and assigned a zero probability. nodes satisfied the resource capacity and connectivity conConnectivity Constraints: For each dependency graphstraints defined in the problem formulation. Infrastructure edge (𝑢, 𝑣) where service-component 𝑢 has already been asgraph nodes that violate these constraints are masked and signed to infrastructure node 𝑖, assigning service-component removed from the action space before computing the prob𝑣 to infrastructure node 𝑗 is allowed only if a corresponding ability distribution. Consequently, the policy restricts the Abedpour et al.: Preprint submitted to Elsevier

Page 7 of 18

Latency-Aware Neural Service Placement

communication link (𝑖, 𝑗) ∈  𝑛𝑒𝑡 exists. This ensures that the data transfer requirements remain feasible during placement construction. Incremental State Updates: After each assignment, the system state is updated to reflect the consumed computational resources and induced network traffic. The residual infrastructure node capacities are reduced accordingly, and the link utilisation levels are updated, allowing subsequent decisions to account for the evolving infrastructure state. Penalty-Based Handling of Residual Violations: Certain global effects, such as bandwidth sharing among multiple simultaneous data transfers, can only be fully evaluated once a complete placement has been constructed. To capture these effects, EP-NCO incorporates a penalty mechanism into its optimisation objective. Placements that induce severe congestion or zero effective bandwidth are penalised by adding a weighted violation term to the overall response time. This encourages the learned policy to generate placements that satisfy local feasibility constraints and achieve efficient global utilisation of network resources. Exploration and Inference Modes: During training, the autoregressive policy samples node assignments according to the learned probability distribution, with temperature and entropy regularisation applied to promote exploration. During evaluation and deployment, the policy operates in a deterministic greedy mode, selecting the highest probability feasible node at each step to generate a stable and reproducible placement solution. Combined with explicit feasibility masking and penaltybased refinement, the autoregressive decoding process enables EP-NCO to effectively bridge the gap between the formal optimisation problem and a scalable, learning-driven placement strategy.

4.3. Reinforcement learning (RL) in EP-NCO In RL models, sequential decision-making is formulated as a Markov Decision Process (MDP) ⟨, , 𝑃 , 𝑅, 𝛾⟩, where a policy 𝜋(𝑎𝑡 ∣ 𝑠𝑡 ) selects[ actions to maximise the expected ] ∑ 𝑘𝑟 . By interacting with discounted return 𝐺𝑡 = 𝔼 ∞ 𝛾 𝑡+𝑘 𝑘=0 the environment, in this context, the agent learns placement policies that map states to actions without explicit searching. This makes RL suitable for large dynamic edge–cloud settings. The service placement problem formulated in Section 3 does not provide an explicit optimal supervision signal because the objective function depends on complex interactions between service-component placements, resource contention, and network congestion effects. Moreover, exact optimisation is computationally infeasible for realistic systemscale applications. Consequently, EP-NCO adopts the RL framework to learn an effective placement policy through direct interaction with the optimisation objective. Markov Decision Process Formulation: The placement procedure is modelled as a finite-horizon MDP. At each decision step 𝑡, the agent observes the current system state, represented by the dual-graph embeddings described in Section 4.1, and the residual resource and Abedpour et al.: Preprint submitted to Elsevier

network states induced by previous assignments. This action corresponds to selecting a feasible infrastructure node for the current service-component 𝑐𝑡 , as detailed in Section 4.2. Environmental transition is deterministic and is defined by the state update rules following each assignment, including reductions in available infrastructure node resources and updates to link-level bandwidth usage. An episode terminates once all service-components across all services are assigned. In EP-NCO, an ’episode’ corresponds to constructing a complete placement solution for a given problem instance, whereas an ’epoch’ denotes a full pass over the training dataset comprising multiple episodes. In other words, each epoch consists of multiple episodes. Reward Design and Objective Alignment: A reward signal is provided only after a complete placement solution is constructed. This episodic reward formulation directly reflects the global optimisation objective while avoiding biased intermediate signals that could distort the optimisation landscape. The reward signal was derived directly from the optimisation objective. After the completion of a placement episode, the total response time is computed according to Equations (7) and (9), incorporating both execution and transmission link delays, as well as bandwidthsharing effects. Equation (16) defines the episode-level reward as the negative total cost, thereby aligning the RL objective with the minimisation of the total response time: ( ) 𝑅 = − 𝑇exec + 𝑇trans + 𝜆 𝑉 (16) where 𝑉 denotes the number of residual constraint violations, such as zero effective bandwidth induced by concurrent flows, and 𝜆 is a penalty weight that controls the severity of these violations. This formulation ensures that the placement policy is explicitly discouraged from producing infeasible or highly congested placements while still allowing gradients to propagate during training. Policy Gradient Optimisation: Equation (17) defines the optimisation objective for the placement policy with parameters 𝜃, including those of NodeGNN, ServiceGNN, and the autoregressive decoder. The objective of the learning process is to maximise the expected return obtained from the placement policies: (17)

𝐽 (𝜃) = 𝔼𝜋𝜃 [𝑅]

where 𝑅 denotes the episode-level reward, as defined in Equation (16). The gradient of this objective is estimated using the REINFORCE policy gradient estimator. Let {𝑎1 , 𝑎2 , … , 𝑎𝐶 } denote the sequence of node selections generated by an autoregressive decoder. Equation (18) defines the policy gradient of the objective: [ 𝐶 ] ∑ ∇𝜃 𝐽 (𝜃) = 𝔼𝜋𝜃 𝑅 ∇𝜃 log 𝜋𝜃 (𝑎𝑡 |𝑠𝑡 ) (18) 𝑡=1

Page 8 of 18

Latency-Aware Neural Service Placement

where 𝑠𝑡 represents the system state at decision step 𝑡. This gradient encourages action sequences that lead to lower response times and fewer constraint violations. Equation (19) defines the entropy-regularised optimisation objective, where entropy regularisation is incorporated to improve training stability: 𝐽 ′ (𝜃) = 𝔼𝜋𝜃 [𝑅] + 𝛽(𝜋𝜃 )

(19)

where (𝜋𝜃 ) denotes the policy entropy and 𝛽 controls the strength of the exploration regularisation. Exploration Strategy and Regularisation: Effective exploration is critical because of the large and structured action space. During training, stochastic action selection was employed by sampling the policy distribution at each decision step. A temperature parameter is applied to the action logits to control the sharpness of the distribution, thereby enabling a smooth transition from exploration to exploitation as the training progresses. In addition, entropy regularisation is incorporated into the optimisation objective to prevent premature convergence to suboptimal policies. The entropy coefficient is gradually annealed during training, allowing the policy to initially explore diverse placement patterns before focusing on highquality solutions. Training Procedure: EP-NCO training was conducted using a dataset of synthetically generated service placement instances spanning multiple system scales [42, 43]. At each training iteration, batches of problem instances were processed in parallel. For each instance, the policy constructs a complete placement through an autoregressive decoding process, after which the episode-level reward is computed. The policy parameters were updated using stochastic gradient descent based on the estimated policy gradients. To monitor the learning progress and mitigate overfitting, periodic evaluations were performed using a greedy inference mode, in which the highest-probability feasible action was selected at each step. Early stopping was performed based on the stability of the evaluation performance across epochs. Inference and Generalisation: At inference time, the learned policy operates deterministically in a greedy mode, generating a placement solution through sequential node selection without stochastic sampling. This ensures reproducible and stable deployments. Importantly, the learned policy is not tied to any specific problem instance (or a specific collection of them); instead, it generalises across varying numbers of services, servicecomponents, and network configurations. This enables EPNCO to scale effectively to large and previously unseen system scenarios, thereby addressing the limitations of exact and rule-based heuristic optimisation approaches. Overall, the proposed optimisation framework incorporated into the EP-NCO enables it to directly approximate the solution of a complex combinatorial optimisation problem, producing high-quality and feasible service placement decisions with practical computational efficiency [42, 43]. Abedpour et al.: Preprint submitted to Elsevier

Algorithm 1 EP-NCO : Dual-Graph Encoder–Decoder with RL Optimisation Input: Network graph 𝐺𝑛𝑒𝑡 = ( ,  𝑛𝑒𝑡 ) with node capacities and link attributes Service DAGs {𝐺𝑠 = (𝑠 , 𝑠 )}𝑠∈ Penalty weight 𝜆, epochs 𝐸, batch size 𝐵 Temperature schedule 𝜏(⋅), entropy schedule 𝛽(⋅) Output: Trained policy parameters 𝜃 1: Initialise policy parameters 𝜃 (ServiceGNN, NodeGNN, AR-Decoder) 2: for epoch = 1 to 𝐸 do 3: Sample a minibatch of 𝐵 placement instances 4: for all instances in minibatch (parallel) do 5: Initialise residual infrastructure node resources and link flow counters 6: ←∅ 7: 𝐇𝑐 ← ServiceGNN𝜃 ({𝐺𝑠 }) 8: 𝐇𝑛 ← NodeGNN𝜃 (𝐺𝑛𝑒𝑡 ) 9: Determine service-component order {𝑐1 , … , 𝑐𝐶 } 10: for 𝑡 = 1 to 𝐶 do 11: 𝑐 ← 𝑐𝑡 12: Construct feasibility mask 𝐦 ∈ {0, 1}| | 13: 𝐦[𝑛] = 1 iff infrastructure node 𝑛 satisfies resource and connectivity constraints 14: 𝓵 ← 𝑓𝜃 (𝐡𝑐 , 𝐇𝑛 ) 15: 𝓵[𝑛] ← −∞ for all 𝑛 with 𝐦[𝑛] = 0 16: if training then 17: problem instance 𝑎(𝑐) ∼ sof tmax(𝓵∕𝜏) 18: else 19: 𝑎(𝑐) ← arg max𝑛 𝓵[𝑛] 20: end if 21:  ←  ∪ {(𝑐, 𝑎(𝑐))} 22: Update infrastructure node resources and link flow counters 23: end for 24: Compute 𝑇exec , 𝑇trans with bandwidth sharing 25: 𝑅 ← −(𝑇exec + 𝑇trans + 𝜆𝑉 ) 26: Store log-probabilities and entropy 27: end for 28: Update 𝜃 using policy gradient with entropy regularisation 29: end for 30: Inference: run greedy decoding to obtain 

5. Experimental Setup Simulation Environment: All experimental problem instances were generated using the edge-to-cloud simulation framework, which was designed and introduced in [8, 31]. This comprehensive simulator allows the modelling of heterogeneous infrastructures with varying service-based workloads. To provide controlled heterogeneity, stochasticity, and reproducibility,

Page 9 of 18

Latency-Aware Neural Service Placement

or an exponential moving average otherwise. The gradients are clipped to a maximum norm of 1.0. The temperature and entropy coefficients are annealed during training. Early CloudEdgeservice stopping is based on greedy validation performance. All Scale Computing connected- connected- Services components devices devices results were obtained using a fixed random seed and evalS: Small 30 15 15 15 8 uated on a held-out test set. During training, batches of M: Medium 60 30 30 30 8 512 placement instances were processed in parallel. These L: Large 100 50 50 50 8 configurations were selected empirically to balance training XL: XLarge 145 75 75 75 8 stability and computational efficiency on the available CPUbased hardware. all simulator parameters (including compute-node capaciTo evaluate EP-NCO, its performance was directly comties, network bandwidth, latency, component resource depared with several baseline approaches grouped into three mands, and data-transfer sizes) were sampled from predecategories according to their nature. First RL baselines, . fined ranges derived from prior studies and industrial specSecond, two widely used metaheuristic methods, namely, ifications. This enables the realistic modelling of dynamic the genetic algorithm (GA) and particle swarm optimisation edge-cloud conditions and supports diverse deployment sce(PSO), were considered. Third, a set of rule-based heuristic narios for both training and evaluation. The implementation strategies: Task Continuation Affinity (TCA), Most Powof the proposed EP-NCO framework, including training and erful Heuristic (MP), Most Data Size (MDS), and Leastevaluation scripts, is publicly available at [44]. Powerful (LP) [8, 31]. A detailed comparative analysis of Problem Instances: these approaches is presented in Section 5). Three instance scales (S:Small, M:Medium, L:Large) RL Baselines: The RL approach was evaluated under were created to assess performance under increasing strucboth hard- and soft-decoder settings. The hard-decoder tural complexity, with an additional XL:XLarge instance enforces feasibility during action selection, whereas the generated exclusively for scalability analysis. Each sersoft-decoder addresses constraint violations through penalty vice comprised eight service-components presented as a terms. RL-based ablation variants implemented within the DAG. The instance topologies included computing, edgeproposed framework were considered. These variants are inconnected-devices, and cloud-connected-devices nodes. All spired by prior RL-based service placement studies [42, 43] simulations were executed in Python using PyTorch 2.9.0 and models customised for the service placement problem. (CPU) on Ubuntu 24.04.2 LTS with 14 CPU cores, and These RL-based solutions were inspired by prior RL-based training and evaluation were conducted using a fixed random service placement/deployment studies but were substanseed. tially adapted to our problem setting; that is, introducing a dual-graph state representation, sequential autoregressive 5.1. Placement Algorithms placement, feasibility masking, and a latency-aware episodic EP-NCO Setup and Training Details: Three EP-NCO mod- reward. els (EP-NCO-S, EP-NCO-M, and EP-NCO-L) were trained Genetic Algorithm (GA): The Genetic Algorithm (GA) on Small-, Medium-, and Large-scale instances, respecis a population-based metaheuristic that iteratively evolves tively, to learn the structural and statistical characteristics of candidate placement solutions using selection, crossover, their respective target scales. Table 3summarised the naming and mutation operators. It is particularly effective for multiconvention for all evaluated EP-NCO and RL variants , objective optimisation problems, such as minimising service which indicates both the training scale and decoder type response time while maximising system reliability. How(hard or soft). ever, its iterative nature leads to a high computational overThe training instances included three categories of input head, and its runtime increases significantly with problem features: (i) network-level attributes (bandwidth and link scale, limiting its suitability for real-time deployment [8, 31]. latency), (ii) node-level capacities (CPU and memory), and Particle Swarm Optimisation (PSO): Particle Swarm (iii) service-level requirements (CPU, memory, and output Optimisation (PSO) is a swarm intelligence-based metasize). These features were encoded using NodeGNN and heuristic in which candidate solutions are updated based ServiceGNN encoders, and the model was trained using a on both individual and global best experiences. PSO can policy gradient (REINFORCE) approach; EP-NCO employs achieve fast convergence toward high-quality solutions. graph embeddings of dimension 32 and a four-layer GNN However, its performance is sensitive to parameter tuning, architecture for both the infrastructure and service encoders. and it suffers from scalability issues in large and complex The hyperparameters were kept fixed across all experiments. search spaces [8, 31]. The data loader used batch_size=1, whereas policy gradients Task Continuation Affinity (TCA): Task Continuation were accumulated over 16 trajectories per update (four in Affinity (TCA) is a rule-based heuristic that reduces comCPU-only runs). The learning rates were 2 × 10−4 for the munication overhead by placing dependent microservice encoders and 2 × 10−3 for the decoder. components on the same or nearby nodes. It is computaThe reward is defined as the negative response time with tionally efficient and well-suited for online decision-making. a violation penalty. Variance reduction is achieved using a baseline equal to the GA response time when available, Table 2 Problem Instance Specifications at Different System Scales

Abedpour et al.: Preprint submitted to Elsevier

Page 10 of 18

Latency-Aware Neural Service Placement Table 3 Explanation of Algorithm Names Name Description EP-NCO_SH EP-NCO trained on Small scale with hard-decoder EP-NCO_MH EP-NCO trained on Medium scale with hard-decoder EP-NCO_LH EP-NCO trained on Large scale with hard-decoder EP-NCO_SS EP-NCO trained on Small scale with soft-decoder EP-NCO_MS EP-NCO trained on Medium scale with soft-decoder EP-NCO_LS EP-NCO trained on Large scale with soft-decoder RL_SH [42, 43] RL trained on Small scale with hard-decoder RL_MH [42, 43] RL trained on Medium scale with hard-decoder RL_LH [42, 43] RL trained on Large scale with hard-decoder RL_SS [42, 43] RL trained on Small scale with soft-decoder RL_MS [42, 43] RL trained on Medium scale with soft-decoder RL_LS [42, 43] RL trained on Large scale with soft-decoder GA [8, 31] Genetic Algorithm baseline PSO [8, 31] Particle Swarm Optimisation baseline TCA [8, 31] Task Continuation Affinity heuristic MP [8, 31] Most Powerful heuristic LP [8, 31] Least-Powerful heuristic MDS [8, 31] Most Data Size heuristic

However, despite these advantages, it relies on local optimisation and often fails to achieve globally optimal placements [8, 31]. Most Powerful (MP): The Most Powerful (MP) heuristic assigns microservice components to nodes with the highest available computational capacity to reduce execution time. However, it ignores network-related factors, such as communication link delay, which can lead to inefficient overall placements in distributed edge-cloud environments [8, 31]. Least-Powerful (LP): The Least-Powerful (LP) heuristic selects nodes with the minimum sufficient resources required to host each component, aiming to improve resource utilisation. It is simple and effective in enhancing resource efficiency. However, despite these advantages, this approach can increase execution and communication link delays, often resulting in suboptimal performance for complex problem instances [8, 31]. Most Data Size (MDS): The Most Data Size (MDS) heuristic prioritises placing components that generate large output data on nodes with favourable network conditions to reduce transmission link delay. It is effective in minimising data transfer latency by considering communication patterns. However, despite its effectiveness in reducing transmission delay, its strong emphasis on data size often leads to poor performance in complex, large-scale placement scenarios [8, 31].

6. Experimental Results & Analyses In this study, we evaluated the performance of EPNCO with the primary objective of reducing the service response time while maintaining a low runtime, particularly in environments with limited resources. EP-NCO performs initial training followed by inference, ensuring that it efficiently adapts to different operational conditions.

Abedpour et al.: Preprint submitted to Elsevier

Figure 4: service placement response time of algorithms across different scales

6.1. Overall Performance Analysis The results in Figure 4 demonstrate a clear performance differentiation among the evaluated placement strategies in terms of the average service response time across all infrastructure scales. Different EP-NCO variants (LH, MH, and SH) exhibited consistently superior behaviour, delivering the lowest service response times throughout the evaluation, with EP-NCO_SH achieving the most stable and efficient performance as the system size increased. The controlled RL ablation variants showed moderate effectiveness but degraded gradually with scale, indicating limitations in generalisation under higher system complexity. Classical metaheuristics, including GA and PSO, maintained acceptable performance at small scales but experienced noticeable service response time increases on larger infrastructures, reflecting reduced optimisation capability in high-dimensional placement spaces. The remaining EPNCO variants (LS, MS, and SS) achieved mid-range performance, outperforming the heuristic baselines but falling short of the primary EP-NCO configurations. Rule-based heuristics (TCA, MP, LP) incurred substantially higher link delays, revealing limited adaptability to large-scale serviceplacement conditions. Finally, MDS consistently yielded the highest response times across all scales, underscoring its inefficiency in handling dense and complex service topologies. Collectively, the results confirm the strong scalability and optimisation robustness of the EP-NCO family, particularly EP-NCO_SH, relative to both metaheuristic and rule-based baselines.

6.2. Aggregate Response Time Analysis The bar chart representation in Figure 5 provides a complementary perspective on the comparative behaviour of the placement strategies by highlighting their aggregate response time trends across all infrastructure scales. The visual grouping of algorithms makes the relative performance gaps more explicit, revealing a clear stratification between the EPNCO family, controlled RL ablation variants, metaheuristics Page 11 of 18

Latency-Aware Neural Service Placement

Figure 5: Average response time per service across infrastructure scales.

and rule-based heuristics. In particular, the consistently low bars associated with the EP-NCO configurations underscore their overall efficiency, whereas the progressively larger bars observed for rule-based heuristics emphasise their limited applicability. This aggregated view reinforces the general performance hierarchy identified earlier while enabling a more direct comparison of inter-algorithm disparities that may be less visually pronounced in the heatmap.

6.4. Algorithm Computational Time and Complexity Analysis

Table 4 summarises the computational characteristics of each algorithm by reporting their training cost, inference latency, and cumulative CPU usage on the XL topology. The learning-based families (EP-NCO and RL) incur substantial one-off training overheads, with larger decoder variants requiring significantly more computation owing to their increased model capacity. 6.3. Per-Service Performance Analysis Despite these differences in the training cost, all learning Figure 6 illustrates the response time distribution of models achieved sub-second inference times, indicating that the first inference problem instances across all 75 services, once trained, they provide highly efficient per-request exeallowing examination of the algorithmic behaviour at the cution. Metaheuristics (GA and PSO) avoid training costs granularity of individual services. Although the other scales but exhibit considerably higher inference times. Rule-based exhibit broadly similar characteristics, we present only the heuristics (TCA, MP, LP, and MDS) remain computationally XL case owing to its higher structural complexity, which minimal but have proven inefficient for complex large-scale provides the most informative visual contrast. problem instances. The EP-NCO family demonstrated markedly low mediOverall, the table highlights a fundamental trade-off: ans and narrow variability ranges, reflecting strong servicelearning-based approaches (i.e., EP-NCO and RL) pay a high level stability. This behaviour is largely attributable to the upfront cost in exchange for extremely low inference latency, use of GNN within the EP-NCO architecture, which enables whereas non-learning-based methods (GA, PSO, TCA, MP, the model to capture relational dependencies in service LP, and MDS) avoid training but incur higher per-execution DAGs, thereby maintaining consistent performance across runtimes with substantially lower solution quality for largeheterogeneous service demands. scale problem instances. A clear separation is also visible between the EP-NCO variExecution Time Analysis: ants with hard- and sof-decoders. The hard-decoder conIn Figure 7, the runtime-based crossover curves illustrate figurations achieve tighter distributions and more reliable the point at which the amortised cost of training a learningservice-wise behaviour. An analogous pattern emerges within based method becomes favourable relative to the repeated the controlled RL ablation variants, where the hard-decoder execution of non-learning-based approaches. For each learn∗ RL models exhibit reduced dispersion compared with their ing algorithm, 𝑁𝑒𝑥𝑒𝑡𝑖𝑚𝑒 represents the number of problem soft-decoder counterparts, suggesting that deterministic deinstances that the algorithm must solve to compensate for its coding enhances service-level consistency under highlengthy training time (as compared with another algorithm). dimensional placement conditions. Equation (20) is calculated by comparing the TotalExecu∗ In contrast, metaheuristics exhibit wider spreads and tionTime (TAET) for solving 𝑁𝑡𝑖𝑚𝑒 problem instances using more frequent outliers, whereas rule-based heuristics display algorithm 𝑎𝑙𝑔. For example, both EP-NCO_SH and GA take ∗ = 95 problem the largest variability and several extreme response time valalmost the same amount of time to solve 𝑁𝑒𝑥𝑒 ∗ ) = TAET(EP-NCO_SH, ues. Overall, these per-service distributions highlight that, instances because TAET(GA, 𝑁𝑒𝑥𝑒 ∗ ). beyond achieving superior averages, EP-NCO models de𝑁𝑒𝑥𝑒 liver significantly more predictable performance across indialg alg TAET (𝑎𝑙𝑔, 𝑁) = 𝑇train + 𝑁 × 𝑇infer (20) vidual services in dense, large-scale environments. Furthermore, EP-NCO models with hard-decoders performed better where 𝑇train denotes the one-time training time, and than their counterparts with soft-decoders. 𝑇 represents the per-problem-instance inference time. infer

For the metaheuristics (GA and PSO), 𝑇train = 0.

Abedpour et al.: Preprint submitted to Elsevier

Page 12 of 18

Latency-Aware Neural Service Placement

Figure 6: Distribution of service response time per service in different training scales and inference of XLarge scale

Table 4 Algorithm RunTimes + CPU Cost per Algorithm (x-large scale) Method

Train Time (sec) Cores Inference (s)

EP-NCO _SH 9072 (2.52 h) EP-NCO_MH 30672 (8.52 h) EP-NCO_LH 95004 (26.39 h) EP-NCO_SS 10512 (2.92 h) EP-NCO_MS 37800 (10.50 h) EP-NCO_LS 87480 (24.30 h) RL_SH 11052 (3.07 h) RL_MH 60120 (16.70 h) RL_LH 117324 (32.59 h) RL_SS 4212 (1.17 h) RL_MS 24120 (6.70 h) RL_LS 50760 (14.10 h) GA 0 PSO 0 TCA 0 MP 0 LP 0 MDS 0

14 14 14 14 14 14 14 14 14 14 14 14 1 1 1 1 1 1

CPU Cost (sec)

0.92 127009 (35.28 h) 1.03 429409 (119.28 h) 0.97 1330056 (369.46 h) 0.88 147168 (40.88 h) 0.90 529200 (147.00 h) 0.90 1224720 (340.20 h) 0.80 154728 (42.98 h) 0.82 841680 (233.80 h) 0.89 1642536 (456.26 h) 0.88 58968 (16.38 h) 0.89 337680 (93.80 h) 0.78 710640 (197.40 h) 96.574 96.57 85.217 85.21 0.016 0.016 0.017 0.017 0.033 0.033 0.015 0.015

Because the inference costs of the EP-NCO and RL models remain nearly constant across additional problem instances, their cumulative runtime grows slowly, whereas GA and PSO exhibit strictly linear growth driven by their expensive per-run optimisation cycles. The crossover numbers are related to the nature of the algorithms. For example, EP-NCO_SH surpasses GA after approximately 95 problem instances and PSO after 108 problem instances, whereas EP-NCO_MH surpasses them after 321 and 364 problem instances, respectively. For the RL models, RL_SH crosses GA at approximately 115 problem instances and PSO at 131 problem instances. This rapid amortisation of training costs highlights the efficiency of compact learning-based strategies for repeated largescale placement decisions. Larger decoder variants (e.g., EP-NCO_LH and RL_LH) require higher crossover points owing to longer training times but ultimately achieve the same asymptotic advantage as the number of placements increases. Overall, this analysis confirms that learning-based strategies become increasingly favourable in terms of the total wall-clock execution runtime when deployment decisions are repeatedly required. Core-Hour Analysis: Abedpour et al.: Preprint submitted to Elsevier

Core-hour analysis complements the runtime perspective by explicitly accounting for core utilisation and revealing how the total compute expenditure evolves using different algorithms. For each learning-based method, the ∗ ) at which the crossover number of problem instances (𝑁𝑐𝑝𝑢 total cumulative CPU consumption surpasses that of another algorithm. Equation 21 shows the TotalAlgorithmCpuTime (TACT) is computed, and used to find the cross-over point ∗ ) where the total core-hour of one algorithm surpasses (𝑁𝑐𝑝𝑢 another one. ∑ alg alg ∗ × 𝐶𝑇 (𝑇infer ) (21) TACT(𝑎𝑙𝑔) = 𝐶𝑇 (𝑇train + 𝑁𝑐𝑝𝑢 where 𝐶𝑇 denotes the number of CPU core-hours, 𝑇train is the one-time training time, and 𝑇infer is the inference time for each problem instance. In our experiments, all learning-based approaches used 14 cores during training and inference, resulting in substantial initial core-hour consumption; however, their total core-hour grows slowly when solving problem instances, owing to nearly constant per-instance inference time. In contrast, metaheuristics (GA and PSO) operated on a single core; however, their cumulative CPU time increased rapidly because their optimisation procedures required a large number of core-hours (even if they could be embarrassingly parallelised over 14 cores). The selected crossover examples illustrate this behaviour: EP-NCO_SH reaches parity with GA at approximately 2040 problem instances (total core-seconds ≈ 146500s ≈ 40.69 hours) and with PSO at approximately 3640 problem instances (total core-seconds ≈ 149600s ≈ 41.56 hours). Similarly, RL_SH crosses GA at approximately 1800 problem instances (total core-seconds ≈ 174800 s ≈ 48.56 hours) and PSO at 2087 problem instances (total core-seconds ≈ 177900s ≈ 49.42 hours). Larger decoder models exhibited proportionally higher crossover points, reflecting longer training times. Overall, these results demonstrate that despite their higher initial computing investment, learning-based methods become increasingly efficient in core-hours under a fixed compute-budget constraint when repeated large-scale placement decisions are required. Table 5 shows EP-NCO models employ a GNN encoder combined with a RL policy and decoder to learn effective service placement strategies. During training, these models Page 13 of 18

Latency-Aware Neural Service Placement

Figure 7: Cross-over number of XL runs after which a learning method becomes faster end-to-end (training + N × inference), and cross-over points by compute budget (CPU-hours). The learning methods are adjusted to accommodate the difference between 14 cores used in EP-NCO vs. one core used in GA/PSO.

Table 5 Comparison of training and inference time complexities of algorithms. Algorithms EP-NCO RL Metaheuristics Heuristics

Training Time Complexity (Offline) 𝑂(𝐸 × 𝑇 × 𝑀) 𝑂(𝐸 × 𝑇 × 𝐾) None None

Inference Time Complexity (Online) 𝑂(𝑇 × 𝑀) 𝑂(𝑇 × 𝐾) 𝑂(𝐺 × 𝑁 × 𝐶𝑜𝑠𝑡) 𝑂(𝐶 × 𝑉 × 𝐾)

perform multiple RL episodes, resulting in a time complexity of 𝑂(𝐸 × 𝑇 × 𝑀), where 𝐸 denotes the number of training episodes, 𝑇 represents the number of placement decisions, and 𝑀 is the number of edges in the underlying graph. During inference, the trained model generates placement decisions through a single forward pass, resulting in a complexity of 𝑂(𝑇 × 𝑀). In contrast, controlled RL ablation variants models use an MLP-based encoder to evaluate the action space across the available computing nodes at each decision step. Consequently, their training complexity is 𝑂(𝐸 × 𝑇 × 𝐾). Their inference complexity is 𝑂(𝑇 × 𝐾), where 𝐾 denotes the number of candidate nodes. Metaheuristic algorithms do not require an explicit training phase; however, they typically rely on iterative population-based search procedures, resulting in an inference complexity of 𝑂(𝐺 × 𝑁 × 𝐶𝑜𝑠𝑡). Similarly, rule-based heuristics directly evaluate candidate placements without training, leading to a complexity of 𝑂(𝐶 × 𝑉 × 𝐾), where 𝐶 represents the number of service-components, and 𝑉 denotes the number of candidate versions for each component. These results confirm that although learning-based approaches incur a one-time training overhead, the resulting models can generate placement decisions in sub-second time frames. EP-NCO outperformed RL approached in this regard, enabling making near-instantaneous service placement decisions once the policy has been trained.

Abedpour et al.: Preprint submitted to Elsevier

6.5. Training Analysis Figure 8 illustrates the reward progression of all learningbased algorithms throughout training, providing insight into their optimisation dynamics and convergence characteristics. A consistent upward trend was observed across the EPNCO family, with rewards steadily improving as training progressed. The hard-decoder variants (EP-NCO_SH, EPNCO_MH, and EP-NCO_LH) converge more rapidly and exhibit smoother reward trajectories, reflecting the stability introduced by deterministic decoding. In contrast, the softdecoder versions (EP-NCO_SS, EP-NCO_MS, and EPNCO_LS) show slightly noisier learning curves but eventually achieve competitive reward levels. This behaviour is expected because the GNN encoder in the EP-NCO captures the structural dependencies between services and resources, enabling more globally coherent policy updates during training. A similar pattern was observed in the controlled RL ablation variants. The RL models employing hard-decoders (RL_SH, RL_MH, and RL_LH) displayed faster and more stable convergence, whereas the soft-decoder variants (RL_SS, RL_MS, and RL_LS) demonstrated higher variance in reward progression, particularly in the early epochs. Because RL relies solely on an MLP decoder without graph-level reasoning, its learning curves tend to exhibit more pronounced fluctuations, particularly for large-decoder configurations, where the policy search space becomes substantially wider. Nonetheless, all RL models followed a generally monotonic reward increase, indicating successful training (optimisation), despite their less expressive representations compared to the EP-NCO -based models. A comparison of the two families reveals the distinctive role of GNN-based representation learning in accelerating and stabilising optimisation. In particular, EP-NCO models consistently achieve higher reward levels within fewer epochs, especially when trained with smaller and mediumscale decoders (i.e., models trained on Small and Medium problem instances). This behaviour demonstrates their ability to leverage graph structures for more effective credit

Page 14 of 18

Latency-Aware Neural Service Placement

Figure 8: Training reward progression of learning-based placement models. The curves illustrate the convergence behaviour of EP-NCO and RL variants across training epochs, highlighting the faster and more stable optimisation achieved by EP-NCO due to its GNN-based representation.

assignment. RL models, while computationally lighter during training, require more epochs to attain similar reward magnitudes and are more sensitive to the decoder scale. Overall, the training curves confirm that EP-NCO achieves superior convergence behaviour and reward quality, primarily because of its structured GNN encoders (NodeGNN and ServiceGNN) and the more efficient propagation of service– infrastructure dependencies during policy optimisation. Ablation Insight. To further assess the contribution of the proposed architecture, we compared EP-NCO with RL ablation variants that replace the GNN encoder with an MLP-based representation and remove explicit dual-graph modelling. The observed performance gap across all evaluations (Figures 4–8) indicates that removing structured graph encoding leads to degraded solution quality and less stable training dynamics, highlighting the importance of the relational inductive bias in capturing service–infrastructure dependencies.

6.6. Inference Analysis To evaluate the generalisation capability of the algorithms, we tested each method on 200 previously unseen problem instances for each scale. For clearer visual interpretation, Figure 9 presents the first 50 test instances from the XL configuration, wherein the complexity of the infrastructure renders the performance differences more pronounced. This subset allowed for a detailed comparison of per-problem instance behaviour while remaining representative of the broader testing distribution, as the overall trends remained consistent across the entire set (200 instances) and across other scales. Among the learning-based methods, the EP-NCO family consistently achieved the lowest inference cost with minimal fluctuations between problem instances. Among them, EP-NCO_SH and EP-NCO_LH exhibited the most stable trajectories, remaining tightly bounded between approximately 35 and 45 service response times. This predictable behaviour stems from the structured GNN encoder within

Abedpour et al.: Preprint submitted to Elsevier

Figure 9: Inference performance on previously unseen XL problem instances. The first 50 test instances are zoomed-in to illustrate the per-instance behaviour of the EP-NCO and RL variants compared with the metaheuristic and heuristic baselines. Hard-decoder EP-NCO models consistently achieve the lowest and most stable service response time trajectories.

the EP-NCO , which captures service–infrastructure interactions and yields highly coherent decisions, even for unseen inputs. The soft-decoder variants (EP-NCO_SS, EPNCO_MS, and EP-NCO_LS) maintained competitive but slightly more variable performance, reflecting the stochasticity introduced by probabilistic decoding. The zoomed-in view further highlights this separation: hard-decoder EPNCO models form the lowest-service response time cluster with minimal oscillations across the 50 tests. The controlled RL ablation variants demonstrated moderate performance, with consistently higher service response times and greater variability than their EP-NCO counterparts. RL with hard-decoder variants (RL_SH, RL_MH, and RL_LH) shows smoother curves and improved inference robustness relative to their soft-decoder versions; however, they remain noticeably less stable than EP-NCO, owing to the absence of a graph-structured inductive bias. RL with soft-decoder models (RL_SS, RL_MS, and RL_LS) exhibited larger fluctuations across problem instances, particularly in the early segments of the curve, indicating less consistent generalisation under high-dimensional input conditions. Rule-base heuristics exhibited the highest overall inference Page 15 of 18

Latency-Aware Neural Service Placement Table 6 Performance Comparison Across Different Scales Algorithm EP-NCO_SH EP-NCO_MH EP-NCO_LH EP-NCO_SS EP-NCO_MS EP-NCO_LS RL_SH RL_MH RL_LH RL_SS RL_MS RL_LS GA PSO TCA MP LP MDS

Small

Medium

Large

XLarge

Mean

Rank

Mean

Rank

Mean

Rank

Mean

Rank

0.2964 0.4456 0.2903 0.7500 0.7820 0.7530 0.3980 0.5100 0.3890 0.7630 0.7900 0.7650 0.5838 0.6448 0.8716 0.8527 0.9056 1.1826

1.97 4.97 1.03 9.17 13.33 10.18 4.03 6.03 3.02 11.23 14.39 12.24 6.96 8.01 15.25 14.58 16.64 18.00

0.3169 0.4491 0.3150 0.7590 0.8030 0.7610 0.4500 0.5350 0.4370 0.7880 0.8300 0.7800 0.5845 0.6480 1.0189 0.9716 1.0181 1.3983

1.73 4.13 1.27 9.00 13.02 10.00 4.55 6.10 3.33 12.00 14.04 11.00 6.91 8.00 16.34 15.11 16.51 18.00

0.2992 0.3814 0.2972 0.7800 0.7890 0.7800 0.4610 0.5090 0.4500 0.7640 0.7990 0.7650 0.5963 0.6542 0.8703 0.8664 0.9055 1.1909

1.86 3.00 1.14 11.72 13.25 11.64 5.00 6.01 4.00 9.14 14.33 10.14 6.99 8.00 15.22 14.78 16.80 18.00

0.3206 0.3031 0.3198 0.7530 0.8130 0.7550 0.4000 0.4820 0.3960 0.7540 0.8100 0.7540 0.6054 0.6598 1.0663 1.0109 1.0475 1.4661

2.58 1.17 2.26 9.00 14.00 12.00 5.00 6.00 4.00 10.53 13.00 10.47 7.00 8.01 16.52 15.18 16.31 18.00

service response times. Metaheuristics such as GA and PSO produced significantly larger and noisier curves, reflecting their lack of learning-based adaptation, where optimisation must be repeated from scratch for each test instance. This resulted in broad variability in solution quality. Rule-based heuristics (TCA, MP, LP, and MDS) remained the least competitive, with MDS consistently producing the highest service response time range, often exceeding 100–130 service response times across the 50 test instances. These results align with earlier observations: while heuristics are computationally inexpensive, they fail to deliver meaningful optimisation performance for large-scale placements. Overall, the inference results clearly demonstrate that learning-based methods (particularly EP-NCO with harddecoders) generalise effectively to unseen inputs, providing low service response times and stable decisions across diverse service-placement scenarios. The performance gap between EP-NCO and all baseline methods widens further under XL conditions, highlighting the advantage of combining GNN representations with learned decision policies during inference.

6.7. Ranking (Based on Friedman Mean Rank) To provide a statistically robust comparison, each algorithm was evaluated for over 200 independent problem instances per scale. Performance was analysed using the non-parametric Friedman test, which is appropriate for multiple-algorithm comparisons without assuming normality and provides a scale-consistent comparative ordering of the evaluated methods [45]. For each instance, algorithms were ranked according to service response time (lower is better), and the average rank across all instances yielded the Friedman mean rank. The Friedman test indicates statistically significant differences among the algorithms across all scales (all 𝑝 < 0.001), rejecting the null hypothesis of equivalent performance and motivating post-hoc comparisons. The Nemenyi post-hoc analysis confirmed that the EP-NCO variants significantly outperformed heuristic and RL baselines, whereas Abedpour et al.: Preprint submitted to Elsevier

Table 7 Train–test cross-scale evaluation matrix for EP-NCO. Test Small Medium Large XLarge Train Small ✓ ✓ ✓ ✓ Medium ✓ ✓ ✓ ✓ Large ✓ ✓ ✓ ✓

the differences with metaheuristics were less consistent across scales. As reported in Table 6, the EP-NCO variants consistently achieved the lowest mean ranks across all problem scales, with EP-NCO_LH performing best in the Small, Medium, and Large settings, and EP-NCO_MH emerging as the top performer in the XLarge setting. In contrast, metaheuristic and rule-based approaches exhibit They had substantially higher mean ranks, highlighting the consistent performance advantages and robust scalability of the proposed framework as system complexity increased. Table 7 shows further analyse cross-scale generalisation behaviour, we explicitly summarise the The train–test evaluation protocol. The table highlights whether an EPNCO model trained on a given scale is evaluated on In other scales, making the cross-scale analysis explicit. These comparisons implicitly serve as ablation analyses. In particular, the performance gap between the EP-NCO and RL baselines highlights the importance of graph-based encoding, whereas the difference between hard and soft decoders demonstrates the impact of feasibility-aware decision making.

7. Conclusion This study presents EP-NCO, an NCO-based solution for latency-aware microservice placement in heterogeneous edge-cloud infrastructures. By combining a dual-graph representation with GNN-based encoding and autoregressive reinforcement learning, EP-NCO models execution, communication, and bandwidth-sharing effects for reasoning over resources and dependencies. Experimental evaluations across four infrastructure scales showed that EP-NCO with hard decoding significantly outperformed other approaches. Compared with metaheuristic baselines, such as GA and PSO, EP-NCO reduces response time by 46%–55% across scales and outperforms controlled RL ablation variants by 25%–35%. EP-NCO shows strong per-service performance with lower median response times and reduced variance across 75 services in XLarge deployment, indicating stable optimization under dense dependencies. It delivers near-instantaneous inference (0.9–1.0s), achieving 90× speedup over GA and PSO, reaching break-even after solving about 100 problem instances. The model assumes static topology and directlink communication, relying on synthetic workloads, which may limit applicability in dynamic real-world environments. These findings suggest EP-NCO can be a scalable, efficient solution for latency-sensitive applications like IoT services,

Page 16 of 18

Latency-Aware Neural Service Placement

smart city infrastructures, online video games, and edgeassisted AI systems, where efficient placement is crucial. Future work will investigate dynamic workloads, multiobjective optimisation (e.g., security or reliability), and federated training for decentralised edge systems.

Acknowledgements This research is supported in part by the Engineering and Physical Sciences Research Council (EPSRC), UK Research and Innovation (UKRI), under Grant EP/Y028813/1. Additional support is provided by the Knowledge Foundation of Sweden (KKS).

CRediT authorship contribution statement Kimia Abedpour: Conceptualization, Methodology, Software, Formal analysis, Investigation, Writing – original draft. Mohammadsadeq Garshasbi Herabad: Formal analysis, Validation, Writing – review & editing. Zheng Li: Supervision, Writing – review & editing. Javid Taheri: Supervision, Methodology, Writing – review & editing.

Declaration of Generative AI and AI-assisted Technologies in the Writing Process During the preparation of this work, the authors used ChatGPT (OpenAI) for language refinement, proofreading, and editorial assistance. After using this tool, the authors reviewed and edited the content as needed and take full responsibility for the content of the published article.

References [1] Thatikonda Supraja, Priyanka Chawla, and Sukhpal Singh Gill. Aidriven service placement in fog and edge computing environments: a systematic review, taxonomy and future directions. Cluster Computing, 28(16):1–39, 2025. [2] Imane Taleb, Jean-Loup Guillaume, and Benjamin Duthil. A survey on services placement algorithms in integrated cloud-fog/edge computing. ACM Computing Surveys, 57(11):1–36, 2025. [3] Linghe Kong, Jinlin Tan, Junqin Huang, Guihai Chen, Shuaitian Wang, Xi Jin, Peng Zeng, Muhammad Khan, and Sajal K Das. Edgecomputing-driven internet of things: A survey. ACM Computing Surveys, 55(8):1–41, 2022. [4] Qingmiao Jiang, Yuan Zhang, and Jinyao Yan. Neural combinatorial optimization for energy-efficient offloading in mobile edge computing. IEEE Access, 8:35077–35089, 2020. [5] Farah Ait Salaht, Frédéric Desprez, and Adrien Lebre. An overview of service placement problem in fog and edge computing. ACM Computing Surveys (CSUR), 53(3):1–35, 2020. [6] Hadi Tabatabaee Malazi, Saqib Rasool Chaudhry, Aqeel Kazmi, Andrei Palade, Christian Cabrera, Gary White, and Siobhán Clarke. Dynamic service placement in multi-access edge computing: A systematic literature review. IEEE Access, 10:32639–32688, 2022. [7] Balázs Sonkoly, János Czentye, Márk Szalay, Balázs Németh, and László Toka. Survey on placement methods in the edge and beyond. IEEE Communications Surveys & Tutorials, 23(4):2590–2629, 2021. [8] Mohammadsadeq Garshasbi Herabad, Javid Taheri, Bestoun S. Ahmed, and Calin Curescu. A lightweight learning-based approach for online edge-to-cloud service placement. Electronics, 15(1), 2026. ISSN 2079-9292.

Abedpour et al.: Preprint submitted to Elsevier

[9] Ayeh Mahjoubi, Javid Taheri, Karl-Johan Grinnemo, and Shuiguang Deng. Optimal placement of recurrent service chains on distributed edge-cloud infrastructures. In 2021 IEEE 46th Conference on Local Computer Networks (LCN), pages 495–502. IEEE, 2021. [10] Muhammad Asif Khan, Emna Baccour, Aiman Erbad, Ridha Hamila, and Mounir Hamdi. Code: Computation offloading in d2d-edge system for video streaming. IEEE Systems Journal, 17(3):4014–4025, 2022. [11] Chunrong Wu, Qinglan Peng, Yunni Xia, Yong Ma, Wangbo Zheng, Hong Xie, Shanchen Pang, Fan Li, Xiaodong Fu, Xiaobo Li, et al. Online user allocation in mobile edge computing environments: A decentralized reactive approach. Journal of Systems Architecture, 113:101904, 2021. [12] Mohammadsadeq G Herabad, Javid Taheri, Bestoun S Ahmed, and Calin Curescu. E-psoga: An enhanced hybrid metaheuristic for optimal edge-to-cloud placement of services with multi-version components. IEEE Access, 2025. [13] Hemant Kumar Apat, Bibhudutta Sahoo, Veena Goswami, and Rabindra K Barik. A hybrid meta-heuristic algorithm for multi-objective iot service placement in fog computing environments. Decision Analytics Journal, 10:100379, 2024. [14] Marlom Bey, Pratyay Kuila, Banavath Balaji Naik, and Santanu Ghosh. Quantum-inspired particle swarm optimization for efficient iot service placement in edge computing systems. Expert Systems with Applications, 236:121270, 2024. [15] Tiansheng Huang, Weiwei Lin, Chennian Xiong, Rui Pan, and Jingxuan Huang. An ant colony optimization-based multiobjective service replicas placement strategy for fog computing. IEEE Transactions on Cybernetics, 51(11):5595–5608, 2020. [16] Muhammad Fahimullah, Shohreh Ahvar, Mihir Agarwal, and Maria Trocan. Machine learning-based solutions for resource management in fog computing. Multimedia Tools and Applications, 83(8):23019– 23045, 2024. [17] Ankur Sharma and Veni Thangaraj. Intelligent service placement algorithm based on ddqn and prioritized experience replay in iot-fog computing environment. Internet of Things, 25:101112, 2024. [18] Sadananda Lingayya, Sathyendra Bhat Jodumutt, Sanjay Rangrao Pawar, Anoop Vylala, and Senthilkumar Chandrasekaran. Dynamic task offloading for resource allocation and privacy-preserving framework in kubeedge-based edge computing using machine learning. Cluster Computing, 27(7):9415–9431, 2024. [19] Jesse Clifton and Eric Laber. Q-learning: Theory and applications. Annual Review of Statistics and Its Application, 7:279–301, 2020. doi: 10.1146/annurev-statistics-031219-041220. [20] Byungjin Jang, Minho Kim, Gaspard Harerimana, and Jae Wook Kim. Q-learning algorithms: A comprehensive classification and applications. IEEE Access, 7:133653–133667, 2019. doi: 10.1109/ ACCESS.2019.2941229. [21] Tao Liu, Shuai Ni, Xiang Li, Yan Zhu, and Linghe Kong. Deep reinforcement learning based approach for online service placement and computation resource allocation in edge computing. IEEE Transactions on Mobile Computing, 2022. doi: 10.1109/TMC.2022. 3141230. [22] Yao Chen, Yang Sun, Bo Yang, and Tarik Taleb. Joint caching and computing service placement for edge-enabled iot based on deep reinforcement learning. IEEE Internet of Things Journal, 9(20): 20006–20017, 2022. doi: 10.1109/JIOT.2022.3159913. [23] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: A methodological tour d’horizon. European Journal of Operational Research, 290(2):405–421, 2021. doi: 10.1016/j.ejor.2018.10.063. [24] Natalia Vesselinova, Rebecca Steinert, Daniel F. Pérez-Ramírez, and Magnus Boman. Learning combinatorial optimization on graphs: A survey with applications to networking. IEEE Access, 8:120388– 120416, 2020. doi: 10.1109/ACCESS.2020.3005682. [25] Ka Tai Chung, C. K. M. Lee, and Y. P. Tsang. Neural combinatorial optimization with reinforcement learning in industrial engineering: A survey. Artificial Intelligence Review, 2025. doi: 10.1007/

Page 17 of 18

Latency-Aware Neural Service Placement s10462-024-11045-1. [26] Farah Aït Salaht, Frédéric Desprez, and Adrien Lebre. An overview of service placement problem in fog and edge computing. ACM Comput. Surv., 53(3), June 2020. ISSN 0360-0300. doi: 10.1145/3391196. URL https://doi.org/10.1145/3391196. [27] Hadi Tabatabaee Malazi, Saqib Rasool Chaudhry, Aqeel Kazmi, Andrei Palade, Christian Cabrera, Gary White, and Siobhán Clarke. Dynamic service placement in multi-access edge computing: A systematic literature review. IEEE Access, 10:32639–32688, 2022. doi: 10.1109/ACCESS.2022.3160738. [28] Ling Xu, Yunpeng Liu, Bing Fan, Xiaorong Xu, Yiguo Mei, and Wei Feng. An improved gravitational search algorithm for task offloading in a mobile edge computing network with task priority. Electronics, 13(3):540, 2024. [29] Antonio Brogi and Stefano Forti. Qos-aware deployment of iot applications through the fog. IEEE internet of Things Journal, 4(5): 1185–1192, 2017. [30] Shiqi Li, Peng Lin, Jing Song, and Qingyang Song. Computingassisted task offloading and resource allocation for wireless vr systems. In 2020 IEEE 6th International Conference on Computer and Communications (ICCC), pages 368–372. IEEE, 2020. [31] Mohammadsadeq Garshasbi Herabad, Javid Taheri, Bestoun S Ahmed, and Calin Curescu. Optimizing service placement in edge-tocloud ar/vr systems using a multi-objective genetic algorithm. arXiv preprint arXiv:2403.12849, 2024. [32] Alisson Barbosa de Souza, Paulo Antonio Leal Rego, Vinay Chamola, Tiago Carneiro, Paulo Henrique Gonçalves Rocha, and José Neuman de Souza. A bee colony-based algorithm for task offloading in vehicular edge computing. IEEE systems journal, 17(3):4165–4176, 2023. [33] Mostafa Ghobaei-Arani and Ali Shahidinejad. A cost-efficient iot service placement approach using whale optimization algorithm in fog computing environment. Expert Systems with Applications, 200: 117012, 2022. [34] Wenkai Lv, Pengfei Yang, Tianyang Zheng, Chengmin Lin, Zhenyi Wang, Minwen Deng, and Quan Wang. Graph-reinforcementlearning-based dependency-aware microservice deployment in edge computing. IEEE Internet of Things Journal, 11(1):1604–1615, 2023. [35] Shuangwu Chen, Qifeng Yuan, Jiangming Li, Huasen He, Sen Li, Xiaofeng Jiang, and Jian Yang. Graph neural network aided deep reinforcement learning for microservice deployment in cooperative edge computing. IEEE Transactions on Services Computing, 17(6): 3742–3757, 2024. [36] Kevin Afachao, Adnan M Abu-Mahfouz, and Gerhard P Hanke. Efficient microservice deployment in the edge-cloud networks with policy-gradient reinforcement learning. IEEE Access, 2024. [37] Lixing Chen, Yang Bai, Pan Zhou, Youqi Li, Zhe Qu, and Jie Xu. On adaptive edge microservice placement: A reinforcement learning approach endowed with graph comprehension. IEEE Transactions on Mobile Computing, 23(12):11144–11158, 2024. [38] Shanchen Pang, Teng Wang, Haiyuan Gui, Xiao He, and Lili Hou. An intelligent task offloading method based on multi-agent deep reinforcement learning in ultra-dense heterogeneous network with mobile edge computing. Computer Networks, 250:110555, 2024. [39] Yimeng Wang, Yongbo Li, Tian Lan, and Nakjung Choi. A reinforcement learning approach for online service tree placement in edge computing. In 2019 IEEE 27th International Conference on Network Protocols (ICNP), pages 1–6. IEEE, 2019. [40] Xiang-Jie Xiao, Yong Wang, Pei-Qiu Huang, and Kezhi Wang. Neural combinatorial optimization for multiobjective task offloading in mobile edge computing. IEEE Transactions on Vehicular Technology, 2025. [41] Imane Taleb, Jean-Loup Guillaume, and Benjamin Duthil. A survey on services placement algorithms in integrated cloud-fog / edge computing. ACM Comput. Surv., 57(11), June 2025. ISSN 03600300. doi: 10.1145/3729214. URL https://doi.org/10.1145/3729214.

Abedpour et al.: Preprint submitted to Elsevier

[42] Dhruv Garg, Nanjangud C. Narendra, and Selome Tesfatsion. Heuristic and reinforcement learning algorithms for dynamic service placement on mobile edge cloud, 2021. URL https://arxiv.org/abs/2111. 00240. [43] Kevin Afachao, Adnan M. Abu-Mahfouz, and Gerhard P. Hanke. Efficient microservice deployment in the edge-cloud networks with policy-gradient reinforcement learning. IEEE Access, 12:133110– 133124, 2024. doi: 10.1109/ACCESS.2024.3461149. [44] Kimia Abedpour. Ep-nco: Latency-aware service placement using neural combinatorial optimisation (code). https://github.com/ kimiaa45-ab/EP-NCO, 2026. Available online; accessed May 2026. [45] Janez Demšar. Statistical comparisons of classifiers over multiple data sets. Journal of Machine learning research, 7(Jan):1–30, 2006. Kimia Abedpour received her B.Sc. and M.Sc. degrees in Computer Engineering (Software) from Marlik Nowshahr Institute and Tabarestan Chalus Institute, Iran, in 2019 and 2021, respectively. She is currently pursuing her Ph.D. in Computer Science at Queen’s University Belfast, United Kingdom. Her research interests include cloud and edge/fog computing, service placement, and AIbased optimisation techniques.

Mohammadsadeq Garshasbi Herabad is a PhD researcher in Computer Science at Karlstad University, Sweden. His research focuses on intelligent and adaptive systems for distributed and dynamic computing environments. His work investigates the use of machine learning and optimisation techniques to improve system performance and reliability under dynamic conditions. He has authored multiple peer-reviewed publications in international venues. His research interests include distributed systems, edge computing, and AI-driven optimisation.

Zheng Li received his Ph.D. and M.Phil. degrees from the Australian National University (ANU) and the University of New South Wales (UNSW), respectively. He was a graduate researcher with the Software Systems Research Group at National ICT Australia (NICTA). He is currently a Lecturer at the School of Electronics, Electrical Engineering, and Computer Science, Queen’s University Belfast, UK. His research interests include big data analytics, edge/cloud computing, empirical software engineering, and performance engineering.

Javid Taheri is a full Professor with School of Electronics, Electrical Engineering, and Computer Science, Queen’s University Belfast (UK), and with the Department of Mathematics and Computer Science, Karlstad University (Sweden). He was also a visiting professor at Ericsson HQ (Sweden) in 2022–2025. He received his Ph.D. in Mobile Computing from the University of Sydney, Australia. His research interests include cloud and edge computing, network virtualisation, softwaredefined networking, and AI-based optimisation.

Page 18 of 18