arXiv CSopen access

Exact, Efficient, and Reliable Multi-Objective and Multi-Constrained IoT Workflow Scheduling in Edge-Hub-Cloud Cyber-Physical Systems

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

cloud distributed-computing parallel-computing

distributed computing, parallel computing, cloud

arXiv:2604.24340v1 [cs.DC] 27 Apr 2026

Andreas Kouloumpris, Georgios L. Stavrinides, Member, IEEE, Maria K. Michael, Member, IEEE, and Theocharis Theocharides, Senior Member, IEEE

Abstract—Emerging Internet of Things (IoT)-enabled cyberphysical applications, such as autonomous critical infrastructure inspection, demand low-latency, energy-efficient, and reliable execution across resource-constrained edge devices with heterogeneous multicore processors and diverse sensing and actuating capabilities, in collaboration with a hub device and a cloud server. These workflow-based applications comprise interdependent tasks that must be executed under stringent deadline, reliability, capability, memory, storage, and energy constraints. Given their critical nature, exact optimization is necessary to obtain optimal schedules that ensure dependable operation. Existing scheduling approaches, both exact and heuristic, fail to jointly address all these objectives and constraints. To this end, we propose an exact multi-objective and multi-constrained workflow scheduling approach for edge-hub-cloud cyber-physical systems, based on continuous-time mixed integer linear programming. The proposed formulation jointly optimizes latency, energy, and reliability, while holistically addressing timing and resource constraints. To enhance reliability while avoiding the overhead of unnecessary task replicas, it selectively employs task duplication. We evaluate our approach against a widely used heuristic, which we extend to ensure a fair and meaningful comparison, using a real-world IoT workflow and synthetic task graphs of varying sizes, across different system configurations and objective trade-offs. The proposed method consistently outperforms the heuristic, achieving up to 29.83%, 33.96%, and 28.49% average improvements in latency, energy, and reliability, respectively, while attaining practical runtimes. Overall, the experimental results demonstrate the effectiveness of our approach under various system configurations and objective trade-offs, and show its practical scalability to task graphs of sizes relevant to the targeted applications and system architecture. Index Terms—Task scheduling, IoT workflows, exact multiobjective optimization, cyber-physical systems, latency, energy efficiency, reliability. Received 27 October 2025; revised 11 January 2026; accepted 12 February 2026. This work has been supported by the European Union’s Horizon 2020 research and innovation programme under grant agreement No. 739551 (KIOS CoE) and from the Government of the Republic of Cyprus through the Cyprus Deputy Ministry of Research, Innovation and Digital Policy. (Andreas Kouloumpris and Georgios L. Stavrinides are co-first authors.) (Corresponding author: Andreas Kouloumpris.) Andreas Kouloumpris, Maria K. Michael, and Theocharis Theocharides are with the KIOS Research and Innovation Center of Excellence and the Department of Electrical and Computer Engineering, University of Cyprus, 1678 Nicosia, Cyprus (e-mail: [email protected]; [email protected]; [email protected]). Georgios L. Stavrinides is with the KIOS Research and Innovation Center of Excellence, University of Cyprus, 1678 Nicosia, Cyprus (e-mail: [email protected]). This article has supplementary downloadable material available at https://doi.org/10.1109/JIOT.2026.3665298, provided by the authors. Digital Object Identifier 10.1109/JIOT.2026.3665298

I. I NTRODUCTION

HE rapid growth of the Internet of Things (IoT) has driven the development of critical cyber-physical applications that demand real-time, energy-efficient, and reliable execution at the network edge [1], [2]. Such IoT-enabled applications often follow the edge-hub-cloud paradigm, which deviates from the conventional edge computing model that comprises three distinct layers (edge devices, edge servers, and cloud servers). In this paradigm, edge and hub devices may be battery-powered and form the bottom layer, while cloud servers form the top layer [3]. Edge devices equipped with sensors collect data and process them locally or transmit them to a hub device for aggregation and further processing. The hub device may also interact with a cloud server to execute more demanding tasks, while the final results often drive actuators on edge devices that interact with the physical environment. Hub devices, such as smartphones or laptops, offer higher computational capacity than edge devices, such as wearables or single-board computers. Although less capable than edge servers, hub devices are physically closer to edge devices, facilitating their coordination and communication with remote cloud servers. Cyber-physical IoT applications based on this paradigm often involve deadline- and precedence-constrained tasks that require specialized device capabilities, such as sensors, actuators, or specific software/hardware modules. These applications, commonly referred to as workflows [4], encompass a wide range of latency-critical, energy-restricted, and reliability-sensitive scenarios. Prominent examples include the use of biomedical edge devices for remote patient monitoring and support (Fig. 1a) [5], [6], and the use of unmanned aerial vehicles (UAVs) for autonomous critical infrastructure inspection or search-and-rescue missions (Fig. 1b) [7], [8]. In these use cases, multiple edge devices with diverse sensing and actuating capabilities cooperate with each other and a hub device, which in turn communicates with a cloud server, to execute the application tasks in a timely, energy-efficient, and reliable manner. The hub device and the cloud server may also feature specialized software or hardware, such as libraries or accelerators for machine learning inference. Moving from the cloud towards the network edge, the heterogeneity of devices increases, as they encompass different multicore processors and varied sensing and actuating capabilities [9]–[11]. Meanwhile, their computational, communication,

Cloud Server

Smartphone (Hub Device)

UAVs (Edge Devices) Critical Infrastructure

Wearable Heart Rate Monitor (Edge Device)

(a)

IoT Workflow

Implantable Smart Pacemaker (Edge Device)

Disaster Area

IoT Workflow

Laptop (Hub Device)

Cloud Server

(b)

Fig. 1. Examples of critical IoT-enabled cyber-physical applications following the edge-hub-cloud paradigm: (a) remote patient monitoring and support, and (b) autonomous critical infrastructure inspection or search-and-rescue missions. Edge devices equipped with various sensors (e.g., heart rate sensors or thermal cameras) and actuators (e.g., heart stimulators or payload release mechanisms) collaborate with each other and a hub device, which also interacts with a cloud server to jointly execute the IoT workflow.

memory, storage, and energy capacities become more limited, posing additional challenges. These challenges are further amplified by the operating setting, as environmental factors such as temperature, humidity, and cosmic rays can affect reliability, often leading to transient errors [12], [13]. Edge devices, due to their higher integration and operating conditions, are typically more vulnerable to these threats than hub devices, which are in turn less reliable than cloud servers. These reliability issues are often mitigated through task replication, where the same task is executed more than once to enhance reliability [14]. However, task replication introduces additional overhead that can degrade performance and increase energy consumption. Therefore, it should be applied selectively. Hence, minimizing latency and energy while maximizing reliability are inherently conflicting objectives. Given the criticality of applications such as those in [5]–[8], an optimized balance between latency, energy, and reliability is essential. This can be achieved through an exact scheduling technique that optimally determines where to allocate and when to execute each task, based on the relative importance of each objective, ensuring dependable execution. In contrast to heuristic approaches, which typically yield approximate solutions without guaranteeing global optimality or full constraint satisfaction, exact methods such as mixed integer linear programming (MILP) can provide globally optimal schedules that satisfy all formulated constraints [15]. Although exact methods are computationally intensive, the pre-programmed and deterministic nature of the targeted applications allows their offline use, provided that solutions are obtained within a reasonable time frame. An additional challenge of exact methods is the representation of time, which can be modeled as discrete or continuous. Discrete-time models simplify problems by assuming that events occur only at predefined intervals. On the the other hand, continuous-time models provide higher accuracy by allowing events to occur at any time. However, this leads to additional complexity, especially when modeling time-dependent cumulative constraints for the concurrent use of limited resources by multiple tasks, such as main memory, storage, or specific device capabilities [16]. Existing exact and heuristic scheduling approaches do not holistically address all objectives and constraints of the tar-

geted applications and overlook the specific multi-tier architecture. Therefore, we propose a continuous-time MILP method for the multi-objective and multi-constrained scheduling of IoT workflows in an edge-hub-cloud cyber-physical system (CPS) comprising multiple edge devices, a hub device, and a cloud server. The proposed exact approach jointly minimizes latency and energy while maximizing reliability under application and system constraints. Building on our preliminary research in [17], our main contributions are as follows: • We propose a comprehensive multi-objective and multiconstrained continuous-time MILP formulation to optimally schedule an IoT workflow in an edge-hub-cloud CPS. The formulation is enabled by a two-phase task graph transformation technique that incorporates selective task duplication to enhance reliability while avoiding the overhead of unnecessary task replicas. • We holistically address objectives and constraints often overlooked by existing approaches. Specifically, we jointly optimize latency, energy, and reliability under precedence, deadline, reliability, capability, memory, storage, and energy constraints. We further account for heterogeneous multicore processors and multiple capabilities per device, and explicitly model time-dependent cumulative constraints for the concurrent use of limited resources, which are often omitted due to their complexity. • As our approach is the first to provide an optimal schedule for the specific objectives, constraints, and CPS architecture, we evaluate and compare it against one of the most effective and well-established workflow scheduling heuristics, the heterogeneous earliest finish time (HEFT) algorithm [18]–[20]. To ensure a fair and meaningful comparison, we extend HEFT to integrate selective task duplication and the same objectives and constraints as our method. • Our experimental evaluation is based on a representative real-world IoT workflow for UAV-enabled autonomous power infrastructure inspection, considering different system configurations and objective trade-offs. To further validate the proposed approach and assess its scalability across varying workflow sizes, we also employ synthetic IoT task graphs. The rest of the paper is organized as follows. Section II provides an overview of related studies. Section III presents the proposed MILP method. Section IV describes our extension to HEFT. Section V presents the experimental setup and results. Section VI concludes the paper. II. R ELATED W ORK Scheduling workflow applications in multicore and distributed environments has been widely studied using a variety of techniques, both exact and heuristic [18]–[35]. A. Exact Approaches MILP-based approaches are proposed in [21]–[25], with [22] and [25] focusing on specific CPS architectures. While these methods [21]–[25] yield optimal schedules for deadlineconstrained workflows, they do not jointly optimize latency,

B. Heuristic Approaches In addition to exact methods, various heuristics have been extensively explored for workflow scheduling in multicore and multi-tier architectures [18]–[20], [26]–[31]. One of the most well-established and effective heuristics is HEFT [18], which remains widely used for heterogeneous multicore processors due to its ability to provide high-quality schedules. For example, HEFT is employed in [19] and [20] to improve latency in embedded workflow applications. However, HEFT does not address the energy and reliability objectives, nor the deadline, reliability, capability, memory, storage, and energy constraints of the considered CPS. Among other relevant heuristics, [26] proposes an ant colony optimization-based approach to minimize energy consumption under a reliability constraint. [27] jointly optimizes latency and energy consumption in a heterogeneous edge computing system, whereas [28] enhances latency and energy efficiency in a cloud setting. [29] improves latency within a predefined deadline in a CPS with multiple sensors and actuators per device, while [30] optimizes both latency and reliability in a multi-tier system with storage limitations. A multi-tier architecture is also examined in [31], where latency and energy are jointly optimized under deadline, memory, and storage constraints. Although these heuristics are applicable to systems with heterogeneous multicore processors, with [30] and [31] also supporting a multi-tier setting, none of them addresses all the objectives and constraints of the considered CPS. On the other hand, multi-objective workflow scheduling strategies that jointly optimize latency, energy, and reliability in heterogeneous multicore environments are introduced in [32]–[35]. Specifically, [32] adapts HEFT for multi-objective scheduling in a cloud computing setting, whereas [33] combines various problem-specific heuristics in a multiprocessor system with reliability and energy limitations. Similarly, [34] and [35] employ particle swarm optimization and task duplication, respectively, to improve all three objectives under reliability and deadline constraints. However, these methods do not consider all the constraints and the multi-tier environment addressed by our approach. Moreover, they cannot guarantee an exact solution, due to their heuristic nature. C. Summary of Research Gaps Overall, existing exact and heuristic workflow scheduling techniques fail to holistically address all the objectives

TABLE I C OMPARISON W ITH E XISTING W ORKFLOW S CHEDULING A PPROACHES

Energy

Storage

Memory

Capability (s/m)1

Deadline

Constraints Reliability

Max. Reliability

Objectives Min. Energy

Ref.

Min. Latency

energy, and reliability. Furthermore, they overlook the memory and storage limitations of devices and do not consider a multitier system. Specifically, [21] and [22] minimize the overall latency, whereas [23]–[25] optimize energy consumption under reliability and energy constraints. [22] and [25] focus on single-core processors, while [23] and [24] assume homogeneous multicore processors. Although [25] considers the sensing and actuating capabilities of CPS devices, it restricts each device to only one sensor or actuator. On the other hand, the sensing and actuating capabilities of devices are not addressed in [22], despite focusing on a CPS. With respect to the problem formulation, [21] and [22] adopt a discrete-time model, whereas [23]–[25] employ a continuous-time approach.

Exact Multi-tier Multicore Solution Environ. Processors (h/H)3 (d/c)2

[18] ✓ - - - ✓(H) [19] ✓ - - - ✓(H) [20] ✓ - - - ✓(H) [21] ✓ ✓ - - ✓(d) ✓(H) [22] ✓ ✓ - - ✓(d) [23] ✓ ✓ ✓ - - ✓ ✓(c) ✓(h) [24] ✓ ✓ ✓ - - ✓ ✓(c) ✓(h) [25] ✓ ✓ ✓ ✓(s) - - ✓ ✓(c) [26] ✓ - ✓ - - ✓(H) [27] ✓ ✓ - - - ✓(H) [28] ✓ ✓ ✓ - - ✓ ✓(H) [29] ✓ ✓ - ✓(m) - - ✓(H) [30] ✓ ✓ - - ✓ ✓ ✓(H) [31] ✓ ✓ ✓ ✓ ✓ ✓ ✓(H) [32] ✓ ✓ ✓ - - - ✓(H) [33] ✓ ✓ ✓ - ✓ - - ✓ ✓(H) [34] ✓ ✓ ✓ ✓ ✓ - - ✓(H) [35] ✓ ✓ ✓ ✓ ✓ - - ✓(H) Ours ✓ ✓ ✓ ✓ ✓ ✓(m) ✓ ✓ ✓ ✓(c) ✓ ✓(H) 1 single/multiple capabilities (e.g., sensors and/or actuators) per CPS device. 2 discrete/continuous-time exact approach. 3 homogeneous/Heterogeneous multicore processors.

(latency, energy, and reliability) and constraints (deadline, reliability, capability, memory, storage, and energy) considered in the examined problem. Moreover, they do not take into account the specific CPS architecture and do not provide an optimal solution based on the desired trade-off between these objectives. Table I highlights this gap by qualitatively comparing existing approaches with the proposed method, which jointly addresses all the considered aspects. D. Differences from Preliminary Research This work builds upon our preliminary research in [17]. Although both works consider the same architectural paradigm and utilize a continuous-time MILP approach, the preliminary research is limited to a single-objective formulation targeting latency, without considering reliability. In contrast, this work reformulates the problem into a multi-objective and multi-constrained optimization framework, jointly optimizing latency, energy, and reliability. We employ a reliability model that utilizes reliability thresholds for each task and selective task duplication to enhance reliability, resulting in primary and replica tasks, which further complicate the examined scheduling problem. We incorporate multiple reliability constraints and reformulate all other constraints (precedence, deadline, capability, memory, storage, and energy constraints) to account for both primary and replica tasks. Furthermore, we propose a two-phase task graph transformation technique, in contrast to the single-step task graph extension used in [17], to facilitate the new problem formulation through an extended task graph that encompasses the system, application, energy, and reliability models. Since the proposed approach is the first to provide an exact solution for this expanded problem setting, we re-implement HEFT to operate on the new extended task graph and to incorporate the same objectives, constraints, and selective task duplication mechanism as our approach. Moreover, we empirically investigate different tradeoffs between latency, energy, and reliability, as well as various

TABLE II C OMPARISON W ITH P RELIMINARY R ESEARCH Aspect Optimization Type

Preliminary Research [17] This Work Single-objective Multi-objective

Objectives

Latency

Latency, energy, reliability

Constraints

Precedence, deadline, capability, memory, storage, energy constraints

Reliability & reformulated (replica-aware) precedence, deadline, capability, memory, storage, energy constraints

Reliability Model

Not considered

Selective task duplication, reliability thresholds

Task Representation Primary tasks only

Primary & replica tasks

Task Graph Transformation

Single-step transformation Two-phase transformation

HEFT Extension

Single-objective, no reliability support

Evaluation Focus

Latency-driven evaluation, Multi-objective-driven evaluation, fixed capability assignment various capability provisioning strategies

Multi-objective & reliabilityaware re-implementation

capability provisioning strategies for the edge devices, in contrast to [17], which considers only latency and a fixed capability assignment. Table II summarizes the key theoretical and empirical contributions of this work compared to our preliminary research in [17]. III. P ROPOSED E XACT M ULTI -O BJECTIVE & M ULTI -C ONSTRAINED MILP A PPROACH A. High-Level Overview To facilitate our problem formulation we utilize a twophase task graph transformation technique. In phase 1, we transform the initial task graph (TG) of the application into an intermediate task allocation graph (TAG), which represents all applicable task allocations on the processing cores of the system devices, taking into account the capability requirements of the tasks and the capabilities provided by each device. Based on the resulting TAG, we subsequently define the adopted energy and reliability models. In phase 2, we convert the intermediate TAG into the final extended task allocation graph (ETAG), driven by the reliability requirements of the tasks, using selective task duplication. We leverage the ETAG, which encapsulates the considered system, application, energy, and reliability models, to formulate and optimally solve the investigated problem, based on the desired trade-off between latency, energy, and reliability. B. System Model The considered edge-hub-cloud CPS comprises a set of α P devices U = {uµk | µ ∈ {e, h, c}, 1 ≤ k ≤ αµ , µ∈{e,h,c} αµ = α}, where µ denotes the device type, with e, h, and c representing an edge device, a hub device, and a cloud server, respectively. k is the device index and αµ is the number of devices of type µ. a) Processing resources: Each device uµk ∈ U has a set of βµk reserved processing cores (hereafter referred to as cores) Pµk = {pµk.q | 1 ≤ q ≤ βµk } for the execution of the workflow application, where q is the core index. Each core can execute one task at a time. Without loss of generality, we abstract the processor level (a device may comprise one or more multicore processors) and directly model cores as the computational resources, as in [21]. Each device uµk

bgt bgt bgt has memory Mµk , storage Sµk , and energy Eµk budgets, which are shared among its reservedS cores. The set of all reserved cores in the system is P = uµk ∈U Pµk . Cores are heterogeneous across the system and may also differ within the same device. Hence, the time and power required to execute a given task depend on its assigned core. b) Communication: The edge devices and the hub device are fully connected, while the hub device is also connected to the cloud server (see example in Fig. 2a). This logical network topology enables close collaboration between the edge devices and the hub device, and facilitates the execution of more demanding tasks on the cloud server. A communication channel between two devices uµk and uνl is defined as ψµk,νl = ⟨ϵµk,νl , πµk,νl , σµk,νl , Iµk,νl ⟩, where ϵµk,νl is its bandwidth, and πµk,νl and σµk,νl indicate the energy required to transmit and receive a unit of data over the particular channel, respectively. If devices uµk and uνl communicate directly, then Iµk,νl = ∅. Otherwise, if communication occurs through an intermediate device uξm (i.e., the hub device), then Iµk,νl = {uξm }. Intra-device data transfers are assumed to incur negligible latency and energy costs compared to interdevice communication [25]. Routing and protocol details are abstracted, as the focus of this work is on task scheduling rather than network-level optimization [26]. c) Device capabilities: We consider a set of γ device capabilities C = {ca | 0 ≤ a < γ}, where c0 denotes the basic computational capability of a device, whereas ca with a > 0 represents a specialized capability (in addition to the basic computational capability), such as a specific sensor, actuator, or software/hardware module. Each device uµk features a set of capabilities Cµk ⊆ C, such that c0 ∈ Cµk . The binary ca parameter yµk denotes whether device uµk has capability ca ca ca ∈ C (yµk = 1) or not (yµk = 0).

C. Application Model (TG) The considered workflow application comprises a set of δ tasks T = {τi | 1 ≤ i ≤ δ}. A task is an indivisible unit of work. The TG of the workflow is represented by a directed acyclic graph G = (N , A) [20], where N = {Ni | τi ∈ T } is the set of its nodes, and A = {Ai→j | Ni , Nj ∈ N , i ̸= j, ∃ a data dependency Ni → Nj } is the set of its arcs. A node Ni ∈ N represents a task τi ∈ T . An arc Ai→j ∈ A between two nodes Ni and Nj (corresponding to parent task τi and child task τj , respectively) represents the communication and precedence relationship between the two tasks. Each task requires a device capability [29]. The binary parameter zica denotes whether task τi requires capability ca ∈ C (zica = 1) or not (zica = 0). All tasks of the application should be completed before a predefined deadline (latency threshold) Lthr , which also indicates the time horizon of the scheduling problem. For periodic applications, Lthr is equal to the application period [25]. Tasks are considered to be non-preemptive, as preemption in deadline-constrained applications may lead to performance degradation [28]. D. TG Transformation Phase 1 (TAG) We first transform TG G into TAG G′ = (N ′ , A′ ). Specifically, we transform each node Ni ∈ N in G into a composite

node (i.e., set of nodes) Ni′ ∈ N ′ in G′ , such that: ca ca Ni′ = {Ni,µk.q | pµk.q ∈ P, yµk zi = 1, ca ∈ C}.

(1)

Ni′

An individual node Ni,µk.q ∈ represents the possible allocation of task τi on core pµk.q . Thus, Ni′ encompasses all applicable allocations of τi on the reserved cores of the devices featuring its required capability. Similarly, we transform each arc Ai→j ∈ A in G into a composite arc (i.e., set of arcs) A′i→j ∈ A′ in G′ , such that: A′i→j ={Ai,µk.q→j,νl.r =Ni,µk.q →Nj,νl.r | pµk.q , pνl.r ∈P, cb cb ca ca zj =1, ca , cb ∈ C}. yµk zi =yνl

(2)

An individual arc Ai,µk.q→j,νl.r ∈ A′i→j denotes the transfer of data from node Ni,µk.q to Nj,νl.r . 1) TAG Node Parameters: A node Ni,µk.q ∈ G′ has the ca following parameters, in addition to the binary parameters yµk ca and zi defined in Sections III-B and III-C, respectively: • Mi : main memory required by task τi . • Si : storage required by τi . • Di : output data size of τi . • Qi : set of child tasks of τi . • ϕi : binary parameter denoting whether τi is an exit task, i.e., without any child tasks: ( 1, if |Qi | = 0, ϕi = (3) 0, if |Qi | > 0. Li,µk.q : execution time of τi on core pµk.q . • Pi,µk.q : power required to execute τi on pµk.q . • Ei,µk.q : energy required to execute τi on pµk.q . It is given by (7), based on the energy model in Section III-E. • Ri,µk.q : reliability of τi on pµk.q , i.e., probability that τi is executed on pµk.q without any failures. It is defined by (9), based on the reliability model in Section III-F. thr • Ri : reliability threshold of τi (i.e., lowest required reliability). • ζi,µk.q : binary parameter indicating whether the reliability of τi on pµk.q is below its reliability threshold Rithr : ( 1, if Ri,µk.q < Rithr , ζi,µk.q = (4) 0, if Ri,µk.q ≥ Rithr . •

2) TAG Arc Parameters: An arc Ai,µk.q→j,νl.r ∈ G′ has the following parameters: ξm • θi,µk.q→j,νl.r : binary parameter denoting whether Ai,µk.q→j,νl.r involves indirect communication between devices uµk and uνl through device uξm : ( 1, if Iµk,νl = {uξm }, ξm θi,µk.q→j,νl.r = (5) 0, if Iµk,νl = ∅. •

CLi,µk.q→j,νl.r : time required to transfer the output data Di of task τi that is allocated on pµk.q , to task τj that is allocated on pνl.r :  Di ξm if θi,µk.q→j,νl.r = 0,  ϵµk,νl ,     (µ, k) ̸= (ν,   l), CLi,µk.q→j,νl.r =

      

1 1 ϵµk,ξm + ϵξm,νl , ξm if θi,µk.q→j,νl.r = 1,

if (µ, k) = (ν, l).

CEi,µk.q→j,νl.r : energy required to transfer Di from task τi (allocated on pµk.q ) to task τj (allocated on pνl.r ). It is given by (8), based on the energy model in Section III-E. 3) Transformation Example (Phase 1): Fig. 2 depicts an example of transforming a TG G (Fig. 2b), first into TAG G′ (Fig. 2c) and subsequently into ETAG G′′ (Fig. 2d), considering a CPS with two edge devices ue1 and ue2 , a hub device uh1 , and a cloud server uc1 , communicating as shown in Fig. 2a. The sets of reserved cores Pµk and capabilities Cµk are also specified for each device uµk . These capabilities (denoted by purple integers) are a subset of those defined in the real-world use case, as shown in Table III. TG G (Fig. 2b) comprises four tasks, with entry and exit tasks shown in green and yellow, respectively, and intermediate tasks depicted in blue. The required capability of each task is indicated by its adjacent purple integer. In phase 1 of the transformation (Fig. 2c), TAG G′ results from all applicable allocations of the tasks on the cores of system devices, taking into account the capability requirement of each task and the capabilities featured by each device. Phase 2 is described in Section III-G3. •

(6)

E. Energy Model The energy required to execute task τi on core pµk.q is given by: Ei,µk.q = Pi,µk.q Li,µk.q . (7) The energy required to transfer the output data Di of parent task τi that is allocated on pµk.q to child task τj that is allocated on pνl.r is defined as:  ξm  Di (πµk,νl + σµk,νl ) , if θi,µk.q→j,νl.r = 0,      (µ, k) = ̸ (ν, l),  CEi,µk.q→j,νl.r = Di (πµk,ξm + σµk,ξm + πξm,νl + σξm,νl ),   ξm  if θi,µk.q→j,νl.r = 1,    0, if (µ, k) = (ν, l). (8) This energy model captures both the computational and communication energy required for workflow execution in the considered edge-hub-cloud architecture, while remaining independent of low-level power management mechanisms to ensure broader applicability [31], [34]. F. Reliability Model Cores are subject to transient failures caused by hardware faults (e.g., soft errors), which may disrupt task execution. Such failures are typically modeled using the Poisson distribution [24], [26], [36]. This model is standard and appropriate for such faults, whose occurrence is dominated by stochastic phenomena (e.g., cosmic rays) rather than cumulative wearout effects. We assume that failures are detected by the underlying hardware or runtime environment [23]–[26], [36]. This commonly used assumption allows us to focus on designtime reliability enhancement through selective task duplication, while abstracting from runtime-specific failure handling mechanisms. The reliability of task τi on core pµk.q over the duration of its execution Li,µk.q is given by [13]: Ri,µk.q = e−λµk.q Li,µk.q ,

(9)

Cloud Server

high-availability storage

Pc1 = {pc1.1} Cc1 = {0,9}

uc1 Hub Device uh1

Ph1 = {ph1.1} Ch1 = {0,7}

Edge Devices

ue1

ue2

integrated display

(a) CPS

IoT Workflow

N′1 N1,e1.1 N1,e2.1 N1,e2.2 N′2 N2,e1.1

N′3 N3,c1.1

Phase 1

N′4 N4,h1.1

task τ4

LiDAR sensor

allocation of task τ4 on core ph1.1

capability-compliant allocations of tasks on cores

(b) TG G

primary candidate nodes

replica candidate nodes

″ N1.1

″ N1.2

″ N2.1

N1″ N1.1,e1.1 N1.1,e2.1 N1.1,e2.2 N1.2,e1.1 N1.2,e2.1 N1.2,e2.2 N2″ N2.1,e1.1

Phase 2

basic computational capability

Pe1 = {pe1.1} Pe2 = {pe2.1, pe2.2} reserved cores device Ce1 = {0,1,2} Ce2 = {0,2} capabilities thermal camera

task allocation requiring task duplication

orange arcs denote indirect communication between devices

″ N3″ N3.1,c1.1 N3.1

allocation of replica task τ1.2 on core pe2.2

″ N4″ N4.1,h1.1 N4.1

allocation of primary task τ4.1 on core ph1.1

capability-compliant allocations of primary and replica tasks on cores

(d) ETAG G″

Fig. 2. TG transformation example: (a) considered CPS, (b) TG G, (c) TAG G′ (transformation phase 1), and (d) ETAG G′′ (transformation phase 2).

where λµk.q is the failure rate of pµk.q . Ri,µk.q denotes the probability of executing τi on pµk.q without any failures. From (9), it holds that Ri,µk.q ∈ (0, 1]. The probability that the execution of τi on pµk.q fails is equal to 1 − Ri,µk.q ∈ [0, 1). If the reliability of τi on pµk.q is below its reliability threshold (ζi,µk.q = 1), we duplicate τi , yielding a primary task τi.1 and a replica task τi.2 . In this case, the total reliability of τi is defined as [37]: Ri,µk.q,νl.r = 1 − (1 − Ri,µk.q ) (1 − Ri,νl.r ) ,

(10)

where Ri,µk.q and Ri,νl.r denote the reliabilities of τi.1 (when allocated on pµk.q ) and τi.2 (when allocated on pνl.r ), respectively. Thus, Ri,µk.q,νl.r represents the probability that at least one of τi.1 and τi.2 executes without failure. By definition, if Ri,µk.q < 1 and Ri,νl.r < 1, then the total reliability of τi is Ri,µk.q,νl.r > max(Ri,µk.q , Ri,νl.r ). Otherwise, if Ri,µk.q = 1 or Ri,νl.r = 1, then Ri,µk.q,νl.r = 1. Consequently, by duplicating task τi we probabilistically improve its reliability. Both the primary task τi.1 and its replica τi.2 have the same resource and capability requirements, and share identical communication and precedence relationships with the same parent/child tasks. Consequently, the replica task τi.2 is scheduled under the same constraints as its primary counterpart τi.1 , except for an additional restriction applied when τi is an exit task (ϕi = 1). In that case, τi.1 and τi.2 must be allocated on the same device to ensure that a single final output is retained or a single actuator action is performed. Otherwise, if τi is not an exit task (ϕi = 0), τi.1 and τi.2 may be allocated on the same or different devices/cores. It is noted that if the reliability of τi on pµk.q is greater than or equal to its reliability threshold (ζi,µk.q = 0), no task duplication is required. Hence, a selective task duplication strategy is employed, avoiding unnecessary task replicas and the additional overhead they entail. G. TG Transformation Phase 2 (ETAG) We transform TAG G′ into ETAG G′′ = (N ′′ , A′′ ), by applying the selective task duplication technique described in Section III-F. Specifically, we transform each composite node Ni′ ∈ N ′ in G′ into another composite node Ni′′ ∈ N ′′ in G′′ , such that: ′′ ′′ Ni′′ = Ni.1 ∪ Ni.2 . (11)

′′ is the set of nodes that represent Similar to Ni′ in (1), Ni.1 the applicable allocations of primary task τi.1 on the reserved cores of the devices featuring its required capability. Thus, ′′ Ni.1 is defined as: ′′ Ni.1 = {Ni.1,µk.q | Ni,µk.q ∈ Ni′ } .

(12)

′′ Ni.2 is the set of nodes denoting the allocations of replica τi.2 on the same cores as primary task τi.1 , i.e.: ′′ ′′ Ni.2 ={Ni.2,µk.q | Ni.1,µk.q ∈Ni.1 , ∃ Ni,νl.r ∈Ni′ : ζi,νl.r =1}. (13)

Hence, if there exists at least one node in Ni′ (i.e., at least one ′′ allocation of τi ) that requires task duplication, then Ni.2 ̸= ∅, ′′ ′′ otherwise Ni.2 = ∅. An individual node Ni.n,µk.q ∈ Ni.n , where n ∈ {1, 2}, represents the possible allocation of primary (if n = 1) or replica (if n = 2) task τi.n on a specific core pµk.q . We refer to Ni.n,µk.q as a candidate node. If n = 1, Ni.n,µk.q is a primary candidate node, else if n = 2, Ni.n,µk.q is a replica candidate node. We transform each composite arc A′i→j ∈ A′ in G′ into another composite arc A′′i→j ∈ A′′ in G′′ , such that: A′′i→j ={Ai.n,µk.q→j.o,νl.r =Ni.n,µk.q →Nj.o,νl.r | Ai,µk.q→j,νl.r ∈A′i→j , Ni.n,µk.q ∈Ni′′, Nj.o,νl.r ∈Nj′′ }. (14) Ni′′ and Nj′′ include the primary and replica candidate nodes of parent task τi and child task τj , respectively. Thus, each pair of candidate nodes of tasks τi and τj is connected by an individual arc in A′′i→j . 1) ETAG Candidate Node Parameters: A primary or replica candidate node Ni.n,µk.q ∈ G′′ has the same parameters as Ni,µk.q ∈ G′ (Section III-D1). Additionally, if Ni.n,µk.q is a primary candidate node (n = 1), it has the following parameter, which denotes the total reliability of task τi : ( ′′ Ri,µk.q,νl.r , if ζi,µk.q = 1, Ni.2,νl.r ∈ Ni.2 , R̂i,µk.q = (15) Ri,µk.q , if ζi,µk.q = 0, where Ri,µk.q,νl.r is given by (10). Hence, if task duplication is required (ζi,µk.q = 1), R̂i,µk.q is the probability that τi.1 , τi.2 , or both execute without failure. Otherwise (ζi,µk.q = 0), R̂i,µk.q is the probability that solely τi.1 executes without failure.

2) ETAG Arc Parameters: An arc Ai.n,µk.q→j.o,νl.r ∈ G′′ has the same parameters as Ai,µk.q→j,νl.r ∈ G′ . 3) Transformation Example (Phase 2): Continuing from Section III-D3, TAG G′ (Fig. 2c) is transformed into ETAG G′′ (Fig. 2d), driven by the reliability requirements of the tasks. Specifically, as task allocation represented by node N1,e2.1 ∈ G′ requires task duplication, composite node N1′ ∈G′ is transformed into composite node N1′′ ∈ G′′ , comprising ′′ the set of primary candidate nodes N1.1 = {N1.1,e1.1 , N1.1,e2.1 , ′′ N1.1,e2.2 } and the set of replica candidate nodes N1.2 = {N1.2,e1.1 , N1.2,e2.1 , N1.2,e2.2 } (depicted in pink). As there is no capability-compliant allocation of the remaining tasks that requires task duplication, only a set of primary candidate nodes is generated in G′′ for these tasks. 4) ETAG Size Analysis: In the worst case of our transformation technique, where all devices feature all capabilities in C and all tasks require duplication, for |P| cores, the number of candidate nodes and arcs in ETAG G′′ increases by 2|P| and 4|P|2 times, respectively, compared to those in TG G. H. MILP Problem Formulation 1) Conceptual Overview: We leverage the derived ETAG G′′ to formulate the problem as a continuous-time multiobjective MILP model. The proposed formulation simultaneously decides (a) where (on which core) a task (and its potential replica) is allocated, (b) whether each task allocated on a specific core requires duplication to satisfy its reliability requirements, and (c) when each task (and its potential replica) starts execution, while minimizing latency and energy and maximizing reliability, subject to timing and resource constraints. We use binary decision variables to select exactly one feasible allocation for each primary task and, when required, at most one replica allocation. Continuous variables determine task start times, while auxiliary binary variables are introduced to preserve linearity when modeling conditional relationships and ordering decisions between tasks, and timedependent cumulative resource constraints. We employ a combined objective function that captures the inherent trade-offs between latency, energy, and reliability. Selection constraints ensure valid task allocations, reliability constraints activate task duplication only when necessary, temporal constraints preserve precedence and prevent task overlap on shared cores, and cumulative resource constraints enforce device capability, memory, storage, and energy limits over time. 2) Key Design Choices & Modeling Rationale: To achieve a realistic model, the proposed approach adopts a continuoustime formulation rather than a discrete-time one. Discrete-time formulations restrict events to predefined time slots, which may not adequately capture the continuous nature of task execution and resource usage. In the proposed formulation, time-dependent cumulative constraints for the concurrent use of limited resources such as device capabilities, memory, and storage are enforced only at task start times. This event-driven enforcement is sufficient, as violations of such constraints may occur only when a task begins execution. Consequently, we avoid partitioning the entire scheduling horizon into time intervals and thus introducing unnecessary variables. The size

of the resulting ETAG increases in the worst case as analyzed in Section III-G4. However, in practice, this growth is significantly constrained, as capability requirements prune infeasible task allocations during the initial transformation phase (Section III-D), and selective task duplication generates replicas only for task allocations that violate reliability thresholds during the second transformation phase (Section III-G). As shown in our experiments in Section V-C2, the resulting ETAGs have substantially fewer nodes and arcs than the theoretical worst case, ensuring that the MILP model is practically tractable for problem sizes relevant to the targeted applications. 3) Decision Variables: We employ the following variables: xi.n,µk.q : binary variable corresponding to a (primary or replica) candidate node Ni.n,µk.q ∈ G′′, such that xi.n,µk.q = 1 if Ni.n,µk.q is selected, and 0 otherwise. • xi.n,µk.q→j.o,νl.r : binary variable corresponding to an arc Ai.n,µk.q→j.o,νl.r ∈ G′′ , such that xi.n,µk.q→j.o,νl.r = 1 if Ai.n,µk.q→j.o,νl.r is selected, and 0 otherwise. • ti.n : continuous variable denoting the start time of (pri′′ mary or replica) task τi.n , corresponding to set Ni.n ∈ G′′ . • T : continuous variable indicating the completion time of the application. • xi,µk.q,νl.r : auxiliary binary variable corresponding to a primary candidate node Ni.1,µk.q and a replica candidate node Ni.2,νl.r of task τi , such that xi,µk.q,νl.r = 1 if both nodes are selected, and 0 otherwise. It is used when task duplication is required and a primary and a replica candidate node of τi should be jointly considered, while preserving the linearity of the model. • xi.n,j.o : auxiliary binary variable denoting whether task τi.n will be executed before task τj.o (xi.n,j.o = 1) or not (xi.n,j.o = 0). It is used when both tasks are allocated on the same core and there is no precedence relationship between them, and thus their order of execution should be determined to avoid overlap. i.n,µk.q • xh : auxiliary binary variable indicating whether task τi.n will be in execution on its allocated core pµk.q at time sh (xi.n,µk.q = 1) or not (xi.n,µk.q = 0). It is h h used to prevent exceeding the capability, memory, and storage capacity of a device during the execution of its assigned tasks. For this purpose, given that the time interval in which a task τi.n will be in execution on pµk.q is [ti.n , ti.n + Li,µk.q ), we consider a set encompassing the start times of all primary and replica tasks, i.e., ′′ S = {sh | sh = ti.n , Ni.n ∈ N ′′ }. To preserve the linearity of the model, we use an additional related auxiliary binary variable x̂i.n,µk.q . h •

4) Objectives: We aim to minimize the overall latency and energy consumption, and maximize the overall reliability of the IoT workflow in the considered CPS. a) Overall latency: It is equal to the completion time of the application: flat = T.

(16)

b) Overall energy: It encompasses both the computational and communication energy required for the execution of

the application (first and second terms in (17), respectively): X fen = Ei,µk.q xi.n,µk.q Ni.n,µk.q ∈N ′′

(17)

CEi,µk.q→j,νl.r xi.n,µk.q→j.o,νl.r .

Ai.n,µk.q→j.o,νl.r ∈A′′

c) Overall reliability: It is defined as the probability that all tasks of the application are executed such that: (a) if a task is duplicated, the primary task, its replica, or both are executed without any failures (first term in (18)), and (b) if a task is not duplicated, the primary task is executed without any failures (second term in (18)) [37]: Y Y x x R̂ (G′′ ) = (Ri,µk.q,νl.r ) i,µk.q,νl.r (Ri,µk.q ) i.1,µk.q . Ni.1,µk.q ∈N ′′ , ζi,µk.q =0

Ni.1,µk.q , Ni.2,νl.r ∈N ′′ , ζi,µk.q =1

(18) To define the objective function, we linearize (18) by taking its natural logarithm [38]: frel = ln R̂ (G′′ ) X = ln (Ri,µk.q,νl.r ) xi,µk.q,νl.r Ni.1,µk.q , Ni.2,νl.r ∈N ′′ , ζi,µk.q =1

(19)

ln (Ri,µk.q ) xi.1,µk.q .

Ni.1,µk.q ∈N ′′ , ζi,µk.q =0

d) Multi-objective: Since latency, energy, and reliability vary in magnitude, we normalize their corresponding functions (16), (17), and (19) in the interval [0, 1] [15]: f˙ =

f − min (f ) , max (f ) − min (f )

(20)

where f represents flat , fen , or frel . Similarly, f˙ denotes the normalized form of the respective function, i.e., f˙lat , f˙en , or f˙rel . Given that the first two objectives aim to minimize latency and energy, while the third aims to maximize reliability, we convert the third objective into a minimization problem by considering f¨rel = −f˙rel . We define the multi-objective function as the weighted sum of f˙lat , f˙en , and f¨rel [15], [39]: g = wlat f˙lat + wen f˙en + wrel f¨rel ,

(21)

where wlat , wen , and wrel are predefined weights reflecting the relative importance of each objective (0 ≤ wlat , wen , wrel ≤ 1, wlat + wen + wrel = 1). Hence, the problem is formulated as: min g

(22)

subject to the constraints defined in Section III-H5. 5) Constraints: We consider the following constraints: a) Candidate node selection constraints: Only one primary candidate node per task should be selected in G′′ : X xi.1,µk.q = 1, ∀ Ni′′ ∈ N ′′ . (23) Ni.1,µk.q ∈Ni′′

b) Arc selection constraints: If a parent and child candidate nodes are selected, their corresponding arc should be selected as well: xi.n,µk.q→j.o,νl.r ≤ xi.n,µk.q , ∀ Ai.n,µk.q→j.o,νl.r ∈ A′′ ,

(24)

xi.n,µk.q→j.o,νl.r ≤ xj.o,νl.r , ∀ Ai.n,µk.q→j.o,νl.r ∈ A′′ ,

(25)

xi.n,µk.q→j.o,νl.r ≥ xi.n,µk.q + xj.o,νl.r − 1, ∀ Ai.n,µk.q→j.o,νl.r ∈ A′′ .

(26)

c) Task reliability constraints: If the selected primary candidate node requires task duplication, only one replica candidate node should be selected for the specific task. Otherwise, no replica candidate node should be selected: X X xi.2,νl.r , ∀ Ni′′ ∈ N ′′ . (27) ζi,µk.q xi.1,µk.q = Ni.2,νl.r ∈Ni′′

Ni.1,µk.q ∈Ni′′

If a primary candidate node corresponds to an exit task and requires task duplication, then the replica should be allocated on the same device as the primary task to ensure that a single final output is retained or a single actuator action is performed: X xi.1,µk.q ≤ xi.2,µk.r , ∀ Ni.1,µk.q ∈ N ′′ , ζi,µk.q = ϕi = 1. Ni.2,µk.r ∈N ′′

(28) Moreover, if a primary candidate node requires task duplication, the selected replica candidate node should ensure that the total reliability of the task is greater than or equal to its reliability threshold: Ri,µk.q,νl.r xi,µk.q,νl.r + (1 − xi,µk.q,νl.r )Ω ≥ Rithr , ∀ Ni.1,µk.q , Ni.2,νl.r ∈ N ′′ , ζi,µk.q = 1.

(29)

In (29), we use a sufficiently large constant Ω (Ω > Rithr ) to formulate the conditional aspect of the constraint in linear form. Specifically, the constraint becomes meaningful (Ri,µk.q,νl.r ≥ Rithr ) only if both the primary and replica candidate nodes Ni.1,µk.q and Ni.2,νl.r , respectively, are selected for task τi , i.e., only if xi,µk.q,νl.r = 1. Otherwise, if xi,µk.q,νl.r = 0, the constraint becomes irrelevant (Ω ≥ Rithr ), as it is always true. By definition, xi,µk.q,νl.r = 1 if both Ni.1,µk.q and Ni.2,νl.r are selected. We express this in a similar manner to (24)–(26), as follows: xi,µk.q,νl.r ≤ xi.1,µk.q , ∀Ni.1,µk.q , Ni.2,νl.r ∈ N ′′, ζi,µk.q =1, (30) xi,µk.q,νl.r ≤ xi.2,νl.r , ∀Ni.1,µk.q , Ni.2,νl.r ∈ N ′′, ζi,µk.q =1, (31) xi,µk.q,νl.r ≥ xi.1,µk.q + xi.2,νl.r − 1, ∀ Ni.1,µk.q , Ni.2,νl.r ∈ N ′′ , ζi,µk.q = 1.

(32)

d) Task precedence constraints: The precedence relationships among the tasks should be preserved: ti.n + Li,µk.q xi.n,µk.q + CLi,µk.q→j,νl.r xi.n,µk.q→j.o,νl.r ≤ tj.o , ∀ Ai.n,µk.q→j.o,νl.r ∈ A′′ . (33)

e) Application completion time & deadline constraints: The completion time of the application should be equal to the completion time of its last task: ti.n + Li,µk.q xi.n,µk.q ≤ T, ∀ Ni.n,µk.q ∈ N ′′ .

(34)

h) Device capability, memory & storage constraints: At each instant sh ∈ S, at most one task from those executed on a particular device should use a specific specialized capability: X i.n,µk.q ca ca xh yµk zi ≤1, ∀sh ∈ S, ∀uµk ∈ U, ∀ca ∈ C, a >0. Ni.n,µk.q ∈N ′′

Moreover, it should be within its predefined deadline: T ≤ Lthr .

(43) (35)

f) Task non-overlapping constraints: Any two tasks without a precedence relationship between them, allocated on the same core, should not be executed at the same time, as each core can process only one task at a time: ti.n +Li,µk.q xi.n,µk.q ≤ tj.o +(3−xi.n,µk.q −xj.o,µk.q −xi.n,j.o)Ω , ∀Ni.n,µk.q , Nj.o,µk.q ∈ N ′′, i < j ∨(i=j ∧n < o), τi ∈Q / j , τj ∈Q / i, (36) tj.o +Lj,µk.q xj.o,µk.q ≤ ti.n +(2−xi.n,µk.q −xj.o,µk.q +xi.n,j.o)Ω , ∀Ni.n,µk.q , Nj.o,µk.q ∈ N ′′, i < j ∨(i=j ∧n < o), τi ∈Q / j , τj ∈Q / i. (37) Similar to (29), in (36) and (37) we utilize constant Ω (Ω > Lthr ) to ensure that task τi.n is executed either before (xi.n,j.o = 1) or after (xi.n,j.o = 0) task τj.o , respectively, when both tasks are allocated on the same core pµk.q (i.e., if xi.n,µk.q = xj.o,µk.q = 1). Additionally, among the conditions of (36) and (37), we use i < j ∨ (i = j ∧ n < o) to prevent the generation of redundant constraints. g) Task execution constraints: The time instants sh ∈ S at which each task will be in execution are determined by: xi.n,µk.q ≤ xi.n,µk.q , ∀ sh ∈ S, ∀ Ni.n,µk.q ∈ N ′′, h

(38)

ti.n ≤ sh + 2−xi.n,µk.q −xi.n,µk.q Ω, ∀sh ∈ S, ∀Ni.n,µk.q ∈ N ′′, h (39) sh + ω ≤ ti.n + Li,µk.q xi.n,µk.q + 2 − xi.n,µk.q − xi.n,µk.q Ω, h ∀ sh ∈ S, ∀ Ni.n,µk.q ∈ N ′′, (40) sh + ω ≤ ti.n + 2 − xi.n,µk.q + xi.n,µk.q − x̂i.n,µk.q Ω, h h (41) ∀ sh ∈ S, ∀ Ni.n,µk.q ∈ N ′′, i.n,µk.q ti.n +Li,µk.q xi.n,µk.q ≤sh + 1−xi.n,µk.q +xi.n,µk.q + x̂ Ω, h h ∀ sh ∈ S, ∀ Ni.n,µk.q ∈ N ′′. (42) In (38), we enforce xi.n,µk.q ≤ 1 only if task τi.n is allocated h on pµk.q , i.e., only if xi.n,µk.q = 1. In (39) and (40), we ensure xi.n,µk.q = 1 if ti.n ≤ sh < ti.n + Li,µk.q . Similarly, h in (41) and (42) we enforce xi.n,µk.q = 0 if either sh < ti.n h or sh ≥ ti.n + Li,µk.q , using the additional binary variable x̂i.n,µk.q . Conditional constraints (39)–(42) are defined in linear h form using constant Ω . Strict inequalities (which are not supported in MILP) in (40) and (41) are converted to non-strict inequalities using a positive tolerance constant ω, sufficiently smaller than all the variables and parameters of the model.

Similarly, at each instant sh ∈ S the memory and storage budgets of each device should not be exceeded: X bgt Mi xi.n,µk.q ≤ Mµk , ∀ sh ∈ S, ∀ uµk ∈ U, (44) h Ni.n,µk.q ∈N ′′

bgt Si xi.n,µk.q ≤ Sµk , ∀ sh ∈ S, ∀ uµk ∈ U. h

(45)

Ni.n,µk.q ∈N ′′

i) Device energy constraints: The energy budget of each device should not be exceeded for the execution of the application: X Ei,µk.q xi.n,µk.q Ni.n,µk.q ∈N ′′

ξm Di xi.n,µk.q→j.o,νl.r πµk,νl 1 − θi,µk.q→j,νl.r

Ai.n,µk.q→j.o,νl.r ∈A′′ ξm + πµk,ξm θi,µk.q→j,νl.r

ξm Dj xj.o,νl.r→i.n,µk.q σνl,µk 1 − θj,νl.r→i,µk.q

Aj.o,νl.r→i.n,µk.q ∈A′′ ξm + σξm,µk θj,νl.r→i,µk.q

µk Di xi.n,νl.q→j.o,ξm.r (σνl,µk + πµk,ξm )θi,νl.q→j,ξm.r

Ai.n,νl.q→j.o,ξm.r ∈A′′ bgt ≤ Eµk , ∀ uµk ∈ U, (µ, k) ̸= (ν, l) ̸= (ξ, m).

(46) The first term in (46) denotes the computational energy consumption of device uµk . The next three terms represent its communication energy consumption, considering data transmitted from (second term) and received at (third term) uµk , as well as the case where uµk is used for data transfers between other devices (fourth term). j) Non-negativity & binary constraints: The nonnegativity (47), (48) and binary nature (49)–(53) of the continuous and binary variables, respectively, should be ensured: ′′ ti.n ≥ 0, ∀ Ni.n ∈ N ′′ ,

(47)

T ≥ 0,

(48)

xi.n,µk.q ∈ {0, 1}, ∀ Ni.n,µk.q ∈ N ′′ ,

(49) ′′

xi.n,µk.q→j.o,νl.r ∈ {0, 1}, ∀ Ai.n,µk.q→j.o,νl.r ∈ A ,

(50)

xi,µk.q,νl.r ∈ {0, 1}, ∀ Ni.1,µk.q , Ni.2,νl.r ∈ N ′′, ζi,µk.q = 1, (51) xi.n,j.o ∈ {0, 1}, ∀ Ni.n,µk.q , Nj.o,µk.q ∈ N ′′, i < j ∨ (i = j ∧ n < o), τi ∈ / Qj , τj ∈ / Qi ,

(52)

xi.n,µk.q , x̂i.n,µk.q ∈ {0, 1}, ∀ sh ∈ S, ∀ Ni.n,µk.q ∈ N ′′ . (53) h h The main notations used in this work are summarized in Appendix A in the supplementary material.

6) MILP Complexity: The computational complexity of our MILP approach depends on both the problem size and the employed solver. Well-established solvers such as Gurobi [40] typically use undisclosed proprietary algorithms and thus their computational complexity cannot be derived [25]. The problem size (i.e., the number of variables and constraints) depends on the size of the resulting ETAG G′′ , whose growth with respect to the initial TG G is analyzed in Section III-G4. As relevant applications do not typically involve an excessive number of tasks [5]–[8], the benefits of our approach outweigh the moderate complexity introduced by the size increase of G′′ . We demonstrate this experimentally in Section V-C2. IV. M ULTI -O BJECTIVE & M ULTI -C ONSTRAINED HEFT A. Extension Methodology Overview As discussed in Section II, our exact MILP method is the first to provide a holistic and optimal solution to the specific multi-objective and multi-constrained problem in the examined CPS. Nevertheless, it remains important to quantify the practical benefit of this optimality by comparing it against a strong and well-established baseline under identical modeling assumptions. Adapting other exact approaches to accommodate the same objectives, constraints, and architecture would yield formulations essentially equivalent to the one proposed in this work, which is among our key contributions, offering limited additional insight. Therefore, we consider HEFT, which remains one of the most widely used, effective, and easily adapted scheduling heuristics for workflow applications [18]–[20]. HEFT follows a sequential two-phase procedure: (a) a task prioritization phase, where tasks are prioritized based on their upward rank (i.e., the longest distance to an exit task, in terms of latency), and (b) a core selection phase, where each task, in order of priority, is assigned to the core that minimizes its finish time (i.e., its overall latency), which serves as the objective function at each step. Due to these properties, HEFT can be systematically extended to accommodate the key aspects of the examined problem. The proposed extension preserves the fundamental heuristic nature of HEFT, which remains a greedy list-scheduling heuristic, as task priorities are computed once using upward ranks and tasks are then scheduled sequentially in that order. The extension does not introduce global search, backtracking, or iterative improvement. Once a task (and, when applicable, its replica) is committed, the decision is not revised. Selective task duplication and the objectives and constraints used in our MILP method are embedded into HEFT in an analogous manner, without changing its algorithmic paradigm. Specifically, selective task duplication is not discovered or optimized dynamically. In contrast, it is pre-encoded in the input ETAG, which is also used by the MILP approach. After rank calculation in the first phase, primary and (when required) replica candidate node sets are constructed, and are then evaluated during the existing second phase of HEFT. Reliability, deadline, capability, memory, storage, and energy constraints are embedded in the second phase, along with the existing precedence and non-overlapping constraints, and are enforced as hard feasibility checks that discard invalid

candidates. Among the remaining feasible options for each task, selection is based on a local (myopic) multi-objective score with respect to the current partial schedule, using the same latency, energy, and reliability objectives as in the MILP formulation, while preserving the main selection mechanism of HEFT. B. Algorithmic Implementation Details Since HEFT is originally designed for latency-driven scheduling under precedence and non-overlapping constraints, we enhance it to incorporate the same objectives, constraints, and selective task duplication technique as the proposed MILP method, under identical modeling assumptions, to ensure a fair and meaningful comparison. Without incorporating these into HEFT, any comparison would be inherently biased in favor of the MILP approach. Our extended version of HEFT is shown in Algorithm 1. We use as input the ETAG G′′ , which integrates selective task duplication. In the first phase (lines 1–5), we determine the upward rank of each candidate node Ni.n,µk.q ∈ G′′ (line 2), based on the upward rank of its child nodes [18]: ρi.n,µk.q = Li,µk.q +

max

{CLi,µk.q→j,νl.r + ρj.o,νl.r}.

Ai.n,µk.q→j.o,νl.r ∈A′′

(54) Given that task duplication is required for certain primary candidate nodes (as in (27) of our MILP approach), and to jointly consider the scheduling of both the primary and replica candidate nodes in such cases, we construct a list Λ comprising sets of candidate nodes for each task (line 4). For primary candidate nodes requiring task duplication, we generate a set for each combination of the primary candidate node with a replica candidate node. Otherwise, we create a set containing only the specific primary candidate node. The sets in Λ are prioritized based on the upward rank of the primary candidate node in each set (line 5). In the second phase (lines 6–62), for each unscheduled task τi we examine each of its corresponding sets in Λ (in order of rank) to select the one that minimizes the employed multi-objective function. Specifically, for each set Λv ∈ Λ, we first check if its candidate nodes concern the allocation of τi.1 and τi.2 on different devices (in case τi is an exit task and task duplication is required), and if the resulting total reliability is below the reliability threshold of τi (line 12), as in MILP constraints (28) and (29), respectively. If one of these conditions holds, we skip Λv and continue with the next (according to its rank) set of τi (line 13). Otherwise, for each candidate node Ni.n,µk.q ∈ Λv , we examine if it would exceed the energy budget of any device (lines 20–25), using (46). Additionally, we check if the memory or storage requirements of τi exceed the respective budgets of device uµk (line 25). If any of these conditions hold, we skip Λv and continue with the next set of τi (line 26). Otherwise, we determine the earliest finish time EF Ti.n,µk.q of candidate node Ni.n,µk.q using Algorithm 2. In Algorithm 2, we ensure that the precedence constraints of primary or replica task τi.n are satisfied (line 1), as in (33). Moreover, we ensure that the execution of τi.n does not overlap with other tasks

Algorithm 1: Extended HEFT.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

Algorithm 2: Calculation of EFT in extended HEFT.

Input: ETAG G′′ = (N ′′, A′′ ). Output: xi.n,µk.q ∀Ni.n,µk.q ∈ N ′′, xi.n,µk.q→j.o,νl.r ∀Ai.n,µk.q→j.o,νl.r ∈ A′′, ′′ and ti.n ∀ Ni.n ∈ G′′. // Phase A - candidate node prioritization: foreach candidate node Ni.n,µk.q ∈ N ′′ starting from exit task candidate nodes do Calculate upward rank ρi.n,µk.q using (54); end Λ ← {{Ni.1,µk.q , Ni.2,νl.r } | Ni.1,µk.q , Ni.2,νl.r ∈ N ′′, ζi,µk.q = 1} ∪ {{Ni.1,µk.q } | Ni.1,µk.q ∈ N ′′, ζi,µk.q = 0}; Sort list of sets Λ by non-increasing order of ρi.n,µk.q of primary candidate nodes; // Phase B - candidate node selection: ′′ isInf easible ← 0, Nsel ← ∅, A′′ sel ← ∅; while ∃ unscheduled tasks corresponding to sets of candidate nodes in Λ do Select first unscheduled task τi based on order of sets in Λ; foreach set Λv ∈ Λ corresponding to τi do isSkippedv ← 0; Calculate total reliability R̂i,µk.q provided by Λv using (15); if (ζi,µk.q = ϕi = 1 ∧ (µ, k) ̸= (ν, l)) ∨ R̂i,µk.q < Rithr then isSkippedv ← 1; Continue; // Λv is not applicable end ′′ ′′ Ntemp ← Nsel ; foreach candidate node Ni.n,µk.q ∈ Λv do ′′ ′′ Ntemp ← Ntemp ∪ {Ni.n,µk.q }; ˆ ′′ ′′ ′′ A′′ ← A temp sel ∪ {Aj.o,νl.r→i.n,µk.q ∈ A | Nj.o,νl.r ∈ Nsel }; energyBgtExceeded ← 0; foreach device uνl ∈ U do ′′ ′′ if constraint (46) is violated for uνl using Ntemp ˆ , Atemp in place of N ′′ , A′′ , respectively then energyBgtExceeded ← 1; Break; end end bgt bgt if energyBgtExceeded ∨ Mi > Mµk ∨ Si > Sµk then isSkippedv ← 1; Break; // Λv is not applicable else Calculate earliest finish time EF Ti.n,µk.q using Algorithm 2; ′′ ′′ Ntemp ← Ntemp ∪ {Ni.n,µk.q }; end end if isSkippedv then Continue; else // total latency, energy, and reliability of Λv : {EF Ti.n,µk.q }; Lv ← max

1 2 3 4 5

′′ Input: Candidate node Ni.n,µk.q and sets Ntemp and A′′ temp from Algorithm 1. Output: EF Ti.n,µk.q and ti.n of task τi.n on core pµk.q. ti.n ← max {tj.o + Lj,νl.r + CLj,νl.r→i,µk.q }; Aj.o,νl.r→i.n,µk.q ∈A′′ temp

′′ Λµk ← {Nj.o,µk.r ∈ Ntemp | tj.o + Lj,µk.r > ti.n }; Sort list Λµk by non-decreasing order of tj.o + Lj,µk.r ; for η ← 1 to |Λµk | do ′′ Nj.o,µk.r ← Λµk ← {Ni.n,µk.q } ∪ {Nb.h,µk.d ∈ Λµk | d ̸= ˆ η , Ntemp q, ti.n < (tb.h + Lb,µk.d ) ∧ (ti.n + Li,µk.q ) > tb.h }; if (r= q ∧ ti.n < (tj.o + Lj,µk.r ) ∧ (ti.n + Li,µk.q ) >tj.o ) P ca ca zb > 1 ∧ zica = 1 ∧ a > 0 ∨ yµk Nb.h,µk.d ∈N ′′ ˆ temp

P bgt Mb > Mµk Nb.h,µk.d ∈N ′′ ˆ temp

∨ 7 8 9 10 11

P bgt Sb > Sµk then Nb.h,µk.d ∈N ′′ ˆ temp

∨

ti.n ← tj.o + Lj,µk.r ; end η ← η + 1; end EF Ti.n,µk.q ← ti.n + Li,µk.q ;

Input: ETAG G″ incorporating selective task duplication

Input: TG G and system model

Phase A: Candidate node prioritization

Phase A: Task prioritization

Phase B: Candidate node selection

Phase B: Processing core selection Objective: 1. Min. Latency Constraints: 1. Precedence 2. Non-overlapping Output: Allocation and start times of tasks

(a) HEFT

Objectives: 1. Min. Latency 2. Min. Energy 3. Max. Reliability Constraints: 1. Precedence 2. Non-overlapping 3. Reliability 4. Deadline

5. Capability 6. Memory 7. Storage 8. Energy

Output: Allocation and start times of primary and replica tasks

(b) Extended HEFT

Fig. 3. Overview of our extension to HEFT.

Ni.n,µk.q ∈Λv

Ev ←

Ei,µk.q Ni.n,µk.q ∈Λv

CEj,νl.r→i,µk.q ; Ni.n,µk.q ∈Λv, Aj.o,νl.r→i.n,µk.q ∈A′′ sel

Rv ← R̂i,µk.q ; end end if ∃ Λv ∈ Λ corresponding to τi with isSkippedv = 0 then foreach set Λv ∈ Λ corresponding to τi with isSkippedv = 0 do Normalize Lv , Ev , Rv in [0, 1] to yield L̇v , Ėv , Ṙv , respectively; // multi-objective gv ← wlat L̇v + wen Ėv − wrel Ṙv ; end Select Λv ∈ Λ corresponding to τi that minimizes gv ; if Lv ≤ Lthr then foreach candidate node Ni.n,µk.q ∈ Λv do ′′ ′′ xi.n,µk.q ← 1, Nsel ← Nsel ∪ {Ni.n,µk.q }; foreach Aj.o,νl.r→i.n,µk.q ∈ A′′ do ′′ if Nj.o,νl.r ∈ Nsel then ′′ xj.o,νl.r→i.n,µk.q ← 1, A′′ sel ← Asel ∪{Aj.o,νl.r→i.n,µk.q }; end end end Mark task τi as scheduled; else isInf easible ← 1; Break; end else isInf easible ← 1; Break; end end return isInf easible;

allocated on pµk.q , and that the capability, memory, and storage constraints of device uµk are not violated (lines 2–11), similar to (36), (37), and (43)–(45) in our MILP method, respectively. Subsequently, in Algorithm 1, we determine the total latency, energy, and reliability of set Λv (lines 35–37), and we use their normalized values to calculate the multi-objective function for

each set of τi (lines 41–44). Finally, we select for τi the set of candidate nodes that minimizes the multi-objective function, without exceeding the defined deadline (lines 45–55), as in (35). If there is a task for which no set satisfies all of the above constraints, then the problem is infeasible. The output of extended HEFT includes the selected candidate nodes and arcs in G′′ , i.e., the resulting allocation of primary and replica tasks, and their start times. Fig. 3 shows an overview of our extension to HEFT, with our modifications highlighted in yellow. C. Extended HEFT Complexity In the worst case, each task τi ∈ T can be allocated on any processing core pµk.q ∈ P, with each allocation requiring task duplication. Hence, there are |N ′′ | = 2|T ||P| candidate nodes in N ′′ , and therefore |T ||P|2 sets of candidate nodes in list Λ, where |T | > |P|. Moreover, in dense ETAGs the number of arcs |A′′ | is proportional to |N ′′ |2 [18]. Thus, the worst-case time complexity of the first phase of extended HEFT is dominated by the operations in lines 1–3, resulting in O(|T |3 |P|3 ). The worst-case time complexity of the second phase is O(|U||T |3 |P|4 ), determined by the operations in lines 20–24. Hence, the overall worst-case time complexity of extended HEFT is O(|U||T |3 |P|4 ). Regarding ETAG G′′ , which is used as input in both extended HEFT and our MILP approach, as mentioned in Section III-G4, in the worst case the number of its nodes and arcs increases by linear and quadratic

TABLE III D EVICE C APABILITIES

Cloud Server

uc1 uh1

Device Task Type Type 0 Basic computational capability All All 1 Thermal camera e Entry 2 LiDAR sensor e Entry 3 Multispectral camera e Entry 1 4 High-precision GNSS module e Interm. 5 Tag release mechanism e Exit 6 UAV coordination module h Interm. 7 Integrated display h Exit 8 High-performance GPU c Interm. 9 High-availability storage c Exit 1 Global Navigation Satellite System. ca Capability

Hub Device

ue1

ue4

ue2

ue3 Edge Devices

(equipped with sensors and actuators)

Fig. 4. Examined CPS.

factors, respectively, with respect to the number of available cores |P|, compared to TG G. V. E VALUATION We assessed the proposed MILP method in comparison with extended HEFT, using a relevant real-world IoT workflow under different system configurations, while varying the relative importance of latency, energy, and reliability. We further validated our approach and investigated its scalability across different task graph sizes, using suitable synthetic IoT workflows we developed for this purpose. A. Experimental Setup The examined edge-hub-cloud CPS (Fig. 4) comprised four different edge devices, a hub device, and a cloud server, each modeled after typical real-world counterparts with heterogeneous multicore processors and diverse memory, storage, and energy capacities. All devices also featured various sensing, actuating, or other specialized capabilities, based on the examined real-world use case. These capabilities, denoted by integers 0–9, were assigned to system devices based on their type (edge e, hub h, or cloud c), accommodating the requirements of entry, intermediate, and exit tasks, as shown in Table III. Each edge device was assumed to be attached to a UAV. We examined three system configurations (C1–C3) with varied capabilities assigned to the edge devices, to reflect different provisioning strategies. In configuration C1 (moderately provisioned), each specialized capability in {1, 2, 3, 4, 5} was assigned to two edge devices. In C2 (minimally provisioned), each of these capabilities was assigned to only one edge device, whereas in C3 (over-provisioned), each capability was assigned to all four edge devices. In all configurations, the hub device and the cloud server were assigned the specialized capabilities {6, 7} and {8, 9}, respectively, while all devices featured the basic computational capability (denoted by 0). As the computational resources in the targeted CPS are typically limited and shared among different applications, the bgt bgt bgt budgets Mµk , Sµk , and Eµk , as well as the number of reserved cores βµk , were subsets of the respective resources on each device. Table IV shows the system devices and their hardware specifications, the considered budgets and reserved cores on each device, and the assigned capabilities per configuration. The core failure rates for each device type (edge

e, hub h, and cloud c) are shown in Table V. They were derived from [41], reflecting that edge devices are typically less reliable than a hub device, which is in turn less reliable than a cloud server. Table VI shows the bandwidth and energy parameters for the communication channels between each pair of devices, derived from real-world measurements [42], [43]. As we adopt an offline optimization approach, all application, system, and network parameters were treated as fixed inputs during optimization. These parameters were instantiated with conservative values derived from real-world measurements and application profiling to ensure feasibility under adverse operating conditions. In line with the safetycritical nature of the targeted use cases, the reserved cores across the system devices were assumed to be used exclusively for the considered workflow application. While parameters do not vary at runtime, the framework can be re-executed at design time with different parameter sets to evaluate alternative operating conditions. We implemented our MILP approach and extended HEFT in C++. The formulated MILP problem was solved using Gurobi Optimizer 11.0.3 [40], on a server running CentOS 7.9, equipped with an Intel Xeon Gold 6240 processor @ 2.6 GHz and 400 GiB of RAM. All experiments were executed using the default Gurobi solver parameters (including feasibility and optimality tolerances), except for the Integrality Focus parameter, which was set from its default value of 0 to 1 to emphasize the early discovery of integerfeasible solutions. No parameter tuning was performed to avoid bias and ensure result generality. B. Experiments With Real-World IoT Workflow 1) Overview: We considered a real-world IoT workflow for the UAV-enabled autonomous inspection of power transmission towers and lines, based on [8]. Table VII lists its tasks along with their required capabilities and reliability thresholds. Fig. 5 illustrates its TG. Entry and exit tasks are depicted in green and yellow, respectively, while intermediate tasks are shown in blue. The workflow involves the collaboration of multiple UAVs, each equipped with an edge device, to capture multispectral, LiDAR, and thermal images for the detection of infrastructure issues, such as vegetation encroachment, structural integrity problems, and overheated components, respectively. The collected data are fused to create a visual representation of the infrastructure, necessitating a cloud-based high-performance GPU (as data fusion is computationally demanding) and high-availability storage (to ensure data accessibility). The fused data are used by the hub device for tag deployment path planning. The output is displayed on the hub device, while a UAV starts deploying location-transmitting tags at the identified problematic sections of the infrastructure. We investigated the execution of this workflow under system configurations C1–C3 (Table IV), while varying the weight of each objective (wlat , wen , and wrel ) in increments and decrements of 1/3 within the interval [0, 1], to examine a comprehensive range of scenarios. For each configuration, the workflow TG was transformed into the corresponding ETAG. The number of ETAG candidate nodes and arcs in each case is shown in Table VIII. The ETAG parameters Mi , Si , Di ,

TABLE IV S YSTEM D EVICES Hardware Specifications Budgets & Reserved Cores Capability Assignment per Configuration bgt bgt bgt Memory Storage Battery3 Mµk Sµk Eµk βµk C1 C2 C3 (GiB) (GiB) (Wh) (GiB) (GiB) (Wh) ue1 Raspberry Pi 3 Cortex-A53 @ 1.4 GHz 1 16 33.3 0.95 1.0 1 2 {0, 1, 5} {0, 5} {0, 1, 2, 3, 4, 5} ue2 Odroid XU4 Cortex-A7 & Cortex-A151 @ 2.0 GHz 2 16 33.3 1.00 1.5 1 2 {0, 1, 5} {0, 1} {0, 1, 2, 3, 4, 5} ue3 Jetson TX2 NVIDIA Denver2 & Cortex-A572 @ 2.0 GHz 8 32 33.3 2.00 2.0 1 2 {0, 2, 3, 4} {0, 3} {0, 1, 2, 3, 4, 5} ue4 Jetson Xavier NX NVIDIA Carmel ARMv8.2 @ 1.4 GHz 8 32 33.3 2.00 2.5 1 2 {0, 2, 3, 4} {0, 2, 4} {0, 1, 2, 3, 4, 5} uh1 Mi Notebook Pro Intel i5 8250U @ 1.6 GHz 8 512 60.0 3.00 5.0 2 4 {0, 6, 7} {0, 6, 7} {0, 6, 7} uc1 HPE DL580 Gen10 Intel Xeon Gold 6240 @ 2.6 GHz 400 10240 – 4.00 10.0 10 6 {0, 8, 9} {0, 8, 9} {0, 8, 9} 1,2 Without loss of generality, the reserved cores are considered to be located on Cortex-A15 and Cortex-A57, respectively. 3 A compatible external battery (TalentCell YB1203000-USB) is considered for the edge devices.

uµk

Device

TABLE V P ROCESSING C ORE FAILURE R ATES Device λµk.q Type (failures/s) −4 e [6 × 10 , 8 × 10−4 ] h [4 × 10−4 , 6 × 10−4 ] c [2 × 10−4 , 4 × 10−4 ]

Processor

TABLE VI C OMMUNICATION C HANNELS Comm. ϵµk,νl πµk,νl σµk,νl Channel (Mbit/s) (µJ/bit) (µJ/bit) uek ↔ uel [6, 9] [0.6, 1.0] [0.4, 0.6] uek → uh1 [9, 13] [0.8, 1.2] [0.6, 0.8] uh1 → uel [7, 10] [0.7, 1.1] [0.5, 0.7] uh1 → uc1 [10, 15] [1.8, 2.7] [0.8, 1.2] uc1 → uh1 [16, 24] [2.0, 3.0] [1.0, 1.5]

TABLE VIII R EAL -W ORLD I OT W ORKFLOW ETAG S Config. C1 C2 C3

#Nodes/ #Variables/ Avg. Solver Arcs Constraints Runtime (s) 278 / 5904 23793 / 72699 249.7 256 / 5440 20977 / 64359 126.3 314 / 6832 26869 / 83531 270.1

TABLE IX R EAL -W ORLD W ORKFLOW ETAG PARAMETER R ANGES

Param. Range Mi [12.4, 453.0] MiB Si [29.3, 448.9] MiB Di [0.4, 18.1] MiB Li,µk.q [2.6, 12648.4] ms Pi,µk.q [0.3, 23.7] W Rithr [0.9990, 0.9999]

TABLE VII R EAL -W ORLD I OT W ORKFLOW TASKS

N1 N5 N9 Task Description ca Rithr N1 Capture multispectral image 3 0.9999 N2 Multispectral image preprocessing 0 0.9996 N3 Detect power transmission lines 0 0.9994 N4 Detect vegetation encroachment 0 0.9994 N5 Perform LiDAR scan 2 0.9998 N6 Data preprocessing/get GNSS data 4 0.9997 N7 Detect power transmission towers 0 0.9996 N8 Detect structural integrity problems 0 0.9997 N9 Capture thermal image 1 0.9999 N10 Thermal image preprocessing 0 0.9995 N11 Detect overheated components 0 0.9993 N12 Multi-source data fusion 8 0.9999 N13 Save data on high-availability storage 9 0.9995 N14 Plan path/coordinate tag deployment 6 0.9998 N15 Display final output 7 0.9993 N16 Deploy tags at problematic sections 5 0.9998

N2 N6 N10 N3 N7 N11 N4 N 8 N12 N13 N14 N15 N16 Fig. 5. Real-world IoT workflow TG.

Li,µk.q , and Pi,µk.q were determined through profiling and power monitoring tools (perf and Powertop) [44] across all system devices. The reliability threshold Rithr of each task was set within [0.9990, 0.9999], so that based on (9) it would not always be met by solely executing the primary task [41]. The values of the ETAG parameters are listed in Table IX. Ei,µk.q , Ri,µk.q , ζi,µk.q , CLi,µk.q→j,νl.r , and CEi,µk.q→j,νl.r were determined based on (7), (9), (4), (6), and (8), respectively. Qi and ξm ϕi were derived from the TG structure, whereas θi,µk.q→j,νl.r was derived from the corresponding TAG structure. For each ETAG, the deadline Lthr was set at 1.5 times the length of its critical path (i.e., the longest path from an entry task candidate node to an exit task candidate node), taking into account the computational and communication latency of the candidate nodes and arcs on the path, respectively, as this was a realistic yet challenging scenario [29]. 2) Results: Figs. 6, 7, and 8 demonstrate the comparison between the proposed MILP approach and extended HEFT for

the considered real-world workflow under system configurations C1, C2, and C3, respectively, while varying the weights of the three objectives (latency, energy, and reliability). Specifically, Figs. 6a, 7a, and 8a show the normalized overall latency, energy, and reliability, with respect to wlat , wen , and wrel , yielded by our MILP method (bars in solid color) and extended HEFT (bars in patterned color). Lower latency and energy, and higher reliability, indicate better performance. Figs. 6b, 7b, and 8b illustrate the percentage improvement in latency, energy, and reliability provided by the proposed MILP technique over extended HEFT, with respect to the examined weight combinations. Figs. 6c, 7c, and 8c showcase the allocation of the primary tasks and their replicas (depicted in solid and patterned color, respectively) on the examined CPS for each set of weights. In all figures, the case where all three objectives were equally important (wlat =wen =wrel =1/3) is shown first, followed by the cases where only two objectives were optimized (in different weight combinations). The singleobjective cases where only latency (wlat = 1), energy (wen = 1), or reliability (wrel =1) was optimized, are shown last. As shown in Figs. 6a, 6b, 7a, 7b, 8a, and 8b, MILP consistently outperformed HEFT across all weight combinations and system configurations, achieving significant improvements in latency, energy, and reliability. Specifically, MILP attained an overall average decrease of 14.47% in latency and 20.37% in energy, along with an overall average increase of 20.11% in reliability, compared to HEFT. In system configurations C1–C3, when optimizing for all three objectives (i.e., wlat = wen = wrel = 1/3), MILP outperformed HEFT in latency, energy, and reliability. When optimizing for any two of the three objectives, MILP outperformed HEFT in latency and energy, and either matched or exceeded HEFT in reliability. For example, for wlat = 0, wen = 1/3, and wrel = 2/3, both

1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.0

Normalized Objective (1/3,1/3,1/3) (1/3,2/3,0) (2/3,1/3,0) (1/3,0,2/3) (2/3,0,1/3) (0,1/3,2/3) (0,2/3,1/3)

(1,0,0)

(0,1,0)

1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.0 (1/3,1/3,1/3) (1/3,2/3,0) (2/3,1/3,0) (1/3,0,2/3) (2/3,0,1/3) (0,1/3,2/3) (0,2/3,1/3)

(0,0,1)

MILP (Energy) HEFT (Energy)

MILP (Latency) HEFT (Latency)

MILP (Energy) HEFT (Energy)

MILP (Latency) HEFT (Latency)

MILP (Reliability) HEFT (Reliability)

Improvement (%)

(0,0,1)

MILP (Reliability) HEFT (Reliability)

20 10

40 30 20 10 0

0 (1/3,1/3,1/3) (1/3,2/3,0) (2/3,1/3,0) (1/3,0,2/3) (2/3,0,1/3) (0,1/3,2/3) (0,2/3,1/3)

(1,0,0)

(0,1,0)

(1/3,1/3,1/3) (1/3,2/3,0) (2/3,1/3,0) (1/3,0,2/3) (2/3,0,1/3) (0,1/3,2/3) (0,2/3,1/3)

(0,0,1)

Latency

Energy

Reliability

Avg. Latency

(1,0,0)

(0,1,0)

(0,0,1)

(wlat, wen, wrel)

(wlat, wen, wrel) Avg. Energy

Latency

Avg. Reliability

Energy

Reliability

Avg. Latency

Avg. Energy

Avg. Reliability

(b)

(b) 28

Number of Tasks

20 16 12 8 4

Hub (Primary Tasks) Hub (Replicas)

MILP HEFT

(1/3,1/3,1/3) (1/3,2/3,0) (2/3,1/3,0) (1/3,0,2/3) (2/3,0,1/3) (0,1/3,2/3) (0,2/3,1/3)

(1,0,0)

(0,1,0)

(0,0,1)

(wlat, wen, wrel)

(wlat, wen, wrel) Edge (Primary Tasks) Edge (Replicas) Total Primary Tasks

MILP HEFT

(0,0,1)

MILP HEFT

(0,1,0)

MILP HEFT

(1,0,0)

MILP HEFT

(1/3,1/3,1/3) (1/3,2/3,0) (2/3,1/3,0) (1/3,0,2/3) (2/3,0,1/3) (0,1/3,2/3) (0,2/3,1/3)

MILP HEFT

Improvement (%)

(0,1,0)

(a)

Number of Tasks

(1,0,0)

(wlat, wen, wrel)

MILP HEFT

Normalized Objective

Cloud (Primary Tasks) Cloud (Replicas)

Edge (Primary Tasks) Edge (Replicas) Total Primary Tasks

Hub (Primary Tasks) Hub (Replicas)

Cloud (Primary Tasks) Cloud (Replicas)

(c)

Fig. 6. Comparison between proposed MILP approach and extended HEFT for the real-world IoT workflow under system configuration C1.

Fig. 7. Comparison between proposed MILP approach and extended HEFT for the real-world IoT workflow under system configuration C2.

methods achieved the same optimal reliability, whereas for wlat = 1/3, wen = 0, and wrel = 2/3, MILP yielded higher reliability than HEFT. When focusing on a single objective, MILP outperformed HEFT in all three objectives, except for wrel =1, where it yielded the same optimal reliability as HEFT. These observations across all objective weight combinations indicate that, for the specific IoT workflow, reliability was more sensitive to its corresponding weight and the employed system configuration than latency and energy. This led to more pronounced fluctuations in reliability, as well as a few cases where MILP and HEFT achieved the same optimal reliability. This increased sensitivity is directly linked to the strong dependence of reliability on the utilized capability provisioning strategy, as primary tasks and their replicas requiring specialized capabilities such as sensors or actuators could only be allocated on specific devices, with configuration C2 being more restrictive than C1 and C3 in that regard. The average

improvement in each objective per configuration is shown in Table X. As demonstrated in Figs. 6c, 7c, and 8c, the task allocation yielded by each method was not always intuitive or straightforward. For example, in cases where the reliability objective was not taken into account (e.g., wlat = 2/3, wen = 1/3, and wrel = 0), some tasks were still duplicated. This was due to the reliability constraints considered in both MILP and HEFT. Furthermore, MILP generally allocated more primary tasks on the cloud server than HEFT, while utilizing at least as many replicas as HEFT. This is particularly evident for wlat =wen = wrel =1/3. Despite this trend, MILP still outperformed HEFT by optimally allocating the primary tasks and their replicas in the examined CPS under each weight combination, while using a reasonable number of replicas (ranging from 2 to 10 for 16 primary tasks). Overall, the experimental results in Figs. 6, 7, and 8 show-

Normalized Objective

1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.0

TABLE X AVERAGE I MPROVEMENT IN L ATENCY, E NERGY, AND R ELIABILITY FOR R EAL -W ORLD I OT W ORKFLOW Config.

(1/3,1/3,1/3) (1/3,2/3,0) (2/3,1/3,0) (1/3,0,2/3) (2/3,0,1/3) (0,1/3,2/3) (0,2/3,1/3)

(1,0,0)

(0,1,0)

(0,0,1)

C1 C2 C3 Overall

Avg. Improvement Latency Energy Reliability 15.27% 18.56% 24.36% 14.35% 20.17% 17.92% 13.80% 22.38% 18.05% 14.47% 20.37% 20.11%

(wlat, wen, wrel) MILP (Energy) HEFT (Energy)

MILP (Latency) HEFT (Latency)

MILP (Reliability) HEFT (Reliability)

TABLE XI S YNTHETIC I OT W ORKFLOW TG S & ETAG S

(a) TG Size TG Avg. ETAG Avg. ETAG Upper Bound Avg. #Var./ Avg. Solver (#Nodes) #Arcs #Nodes/Arcs #Nodes/Arcs Constraints Runtime (h) 10 13 202 / 5737 360 / 16848 14581 / 48067 0.01 20 28 400 / 13315 720 / 36288 44012 / 137017 0.21 30 45 620 / 24277 1080 / 58320 90629 / 280992 1.67 40 64 788 / 32289 1440 / 82944 138110 / 417383 5.66 50 74 974 / 32961 1800 / 95904 557406 / 243625 10.47

Improvement (%)

60 50 40 30 20 10 0 (1/3,1/3,1/3) (1/3,2/3,0) (2/3,1/3,0) (1/3,0,2/3) (2/3,0,1/3) (0,1/3,2/3) (0,2/3,1/3)

(1,0,0)

(0,1,0)

(0,0,1)

(wlat, wen, wrel) Latency

Energy

Reliability

Avg. Latency

Avg. Energy

Avg. Reliability

(b)

Number of Tasks

28 24 20 16 12 8 4 MILP HEFT

MILP HEFT

(1/3,1/3,1/3) (1/3,2/3,0) (2/3,1/3,0) (1/3,0,2/3) (2/3,0,1/3) (0,1/3,2/3) (0,2/3,1/3)

MILP HEFT

(1,0,0)

(0,1,0)

(0,0,1)

(wlat, wen, wrel) Edge (Primary Tasks) Edge (Replicas) Total Primary Tasks

Hub (Primary Tasks) Hub (Replicas)

Cloud (Primary Tasks) Cloud (Replicas)

(c) Fig. 8. Comparison between proposed MILP approach and extended HEFT for the real-world IoT workflow under system configuration C3.

case that the proposed MILP approach is more adaptable and effective in jointly optimizing latency, energy, and reliability across different objective weight combinations and system configurations, compared to HEFT. The inferior performance of HEFT stems from its inherent limitation of scheduling one task at a time without exploring the entire solution space, in contrast to MILP. The Gurobi solver required between 126.3 and 270.1 seconds to return a solution for our MILP method, as demonstrated in Table VIII, which also shows the number of variables and constraints for each system configuration. Given the pre-programmed nature of the examined workflow, which enables its offline scheduling, the solver runtime is short and practical. C. Experiments With Synthetic IoT Workflows 1) Overview: As demonstrated by the real-world IoT workflow in Section V-B, the targeted workflows for the examined

system architecture typically have a coarse-grained nature, featuring a small-to-moderate number of tasks (10–20 tasks) [5]–[8]. However, to further validate our MILP approach and explore its scalability under more demanding workloads, we additionally investigated larger TGs. Specifically, we generated 25 random TGs, divided into five sets of different sizes, using the generator in [45]. Each set included five TGs with 10, 20, 30, 40, or 50 tasks [21], [23]–[25], and an average in/out degree (incoming/outgoing arcs per node) of 1.45. We randomly assigned specialized capabilities to the tasks of each TG, based on the type of each task, considering that entry and exit tasks often require a specific sensor or actuator, respectively. We transformed the generated TGs into the corresponding ETAGs based on system configuration C1, as it represented the most balanced capability provisioning strategy. We considered equal importance for all three objectives, i.e., wlat = wen = wrel = 1/3. Table XI shows the average number of nodes and arcs of the TGs and the corresponding ETAGs for the considered synthetic workflows. It also includes the theoretical upper bounds on the number of ETAG nodes and arcs, derived from the analysis in Section III-G4, for |P| = 18 reserved cores across the system. We randomly assigned values to the device-independent ETAG candidate node parameters Mi , Si , and Di from those obtained in the real-world application. The device/core-dependent parameters Li,µk.q and Pi,µk.q were first determined for the candidate nodes involving the least computationally capable device, Raspberry Pi 3 (which served as the reference device), by using values measured for the particular device in the real-world use case. For candidate nodes involving other devices, Li,µk.q and Pi,µk.q were calculated based on the performance ratio of each device with respect to the reference device, where the performance ratio was determined by running relevant benchmarks [46], [47] on all devices, as shown in Table XII. The remaining ETAG candidate node and arc parameters were determined as outlined in Section V-B1. To support reproducibility, all synthetic workflows used in our experiments are publicly available at [48]. 2) Scalability Analysis: Fig. 9 demonstrates the improvement achieved by the proposed MILP method over extended

TABLE XII

Benchmark Scores1 Perf. uµk Device Geek Num R Scikit Tensor Ratio3 bench 5 Py Bench. Learn Flow ue1 Raspberry Pi 32 99 pts 4.25 pts 9.50 s 3433.85 s 17391.52 s 1.00 ue2 Odroid XU4 149 pts 4.49 pts 9.17 s 3145.17 s 13078.08 s 1.20 ue3 Jetson TX2 187 pts 12.68 pts 7.21 s 870.94 s 4491.59 s 2.80 ue4 Jetson Xavier NX 216 pts 22.17 pts 2.62 s 400.84 s 1905.90 s 5.74 uh1 Mi Notebook Pro 589 pts 85.40 pts 0.67 s 149.97 s 1335.72 s 15.23 uc1 HPE DL580 Gen10 1578 pts 91.75 pts 0.44 s 102.19 s 1099.98 s 21.70 1 Higher scores in points (pts) and lower scores in seconds (s) indicate better performance (single-core benchmark scores are reported). 2 Used as reference device (least computationally capable device). 3 Average of individual score ratios between each device and the reference device.

75% 25%

Latency

Energy

Max Median

× Mean

Min

Reliability

Fig. 9. Improvement in latency, energy, and reliability objectives attained by proposed MILP approach over extended HEFT under increasing TG size. Box plots show the distribution of improvement in each objective across ETAGs for each TG size. The rightmost set of box plots aggregates the results across all TG sizes.

HEFT in all three objectives (latency, energy, and reliability) as we increased the size of the TGs. Notably, MILP consistently outperformed HEFT in all objectives across all TG sizes. Specifically, MILP provided a latency decrease over HEFT ranging from 6.15% to 53.25%, with a mean and median of 29.83% and 32.46%, respectively. The energy decrease ranged from 14.21% to 51.79%, with a mean of 33.96% and a median of 28.79%. The reliability increase ranged from 9.78% to 56.31%, with a mean and median of 28.49% and 24.81%, respectively. It can be observed that the improvement in each objective presented high variability, indicating that the structure and size of the TGs, and by extension the required capabilities of the entry, intermediate, and exit tasks, significantly affect performance in the examined environment. The time required by the Gurobi solver to provide a solution for our MILP approach as the TG size increased is shown in Fig. 10. The average solver runtime is also reported in Table XI, along with the average number of variables and constraints for each TG size. For reference, the runtime of extended HEFT ranged from 0.1 to 13.6 seconds. Our approach required longer runtimes for larger TGs due to the increase in the number of variables and constraints resulting from the growing size of the corresponding ETAGs. However, the resulting ETAGs contained significantly fewer nodes and arcs than the theoretical upper bounds (see Section III-H2). For example, as shown in Table XI, for TGs with 50 tasks (which on average comprised 74 arcs), the corresponding ETAGs included on average 974 nodes and 32 961 arcs, which are substantially fewer than the worst-case bounds of 1800 nodes

Runtime (h)

B ENCHMARK S CORES & P ERFORMANCE R ATIOS OF S YSTEM D EVICES

75%

25%

Max Median

× Mean

Min

10 8 6 4 2 0

TG Size (#Tasks)

Fig. 10. Solver runtime for proposed MILP method under increasing TG size. Box plots show the runtime distribution across ETAGs for each TG size, while the solid line connects the mean runtime values.

and 95 904 arcs, respectively. The growth of ETAG nodes and arcs under increasing TG size, as well as the comparison between empirical averages and their corresponding theoretical upper bounds, are further illustrated in Appendix B in the supplementary material. Across all workflow sizes, the empirical ETAG node and arc averages are shown to be well below these bounds, demonstrating the practical tractability of the proposed approach. Considering the NP-hardness of the problem [22], the exact and offline nature of the proposed MILP method, as well as the significant improvement it consistently provided over HEFT in all three objectives, the time required by the solver is reasonable and practical, even for large TGs. More importantly, given that relevant applications for the specific architecture typically involve 10–20 tasks (as shown in Section V-B), the practicality of our approach is further underscored. For these TG sizes, the solver yielded optimal solutions in a short time frame, ranging from 20 seconds to 16.6 minutes. VI. C ONCLUSION & F UTURE W ORK We proposed a multi-objective and multi-constrained continuous-time MILP approach to optimally schedule an IoT workflow in an edge-hub-cloud CPS. Our formulation is enabled by a two-phase task graph transformation technique that incorporates selective task duplication to enhance reliability while avoiding unnecessary task replicas. In contrast to existing approaches, the proposed method comprehensively optimizes latency, energy, and reliability under precedence, deadline, reliability, capability, memory, storage, and energy constraints, while considering heterogeneous multicore processors and multiple sensing, actuating, or other specialized capabilities per device. We evaluated the proposed approach against the well-established HEFT heuristic using both a representative real-world IoT workflow and synthetic IoT task graphs of varying sizes, under different system configurations and objective trade-offs. To ensure a fair and meaningful comparison, we incorporated into HEFT selective task duplication and the same objectives and constraints as our method. The experimental results demonstrate the effectiveness of the proposed MILP approach in jointly optimizing the conflicting objectives of the considered problem. Specifically, MILP consistently outperformed HEFT in the real-world use case, achieving overall average improvements of 14.47% in latency, 20.37% in energy, and 20.11% in reliability, across all

system configurations and objective trade-offs. For synthetic workflows, it provided average improvements of 29.83% in latency, 33.96% in energy, and 28.49% in reliability, while attaining practical solver runtimes. These findings show that the proposed method is effective and scalable for IoT workflows of sizes and characteristics commonly encountered in the targeted applications and system architecture. In future work, we will explore hybrid exact and heuristic scheduling approaches that are applicable to different use cases and system architectures. Moreover, we will investigate scenarios involving uncertainty in parameters such as task execution times and network bandwidth. R EFERENCES [1] L. Qu, J. Wang, and C. Assi, “Resource scheduling and delay optimization of IoT devices in drone-assisted multiaccess edge computing,” IEEE Internet Things J., vol. 12, no. 11, pp. 16 998–17 011, Jun. 2025. [2] K. Kant, A. Jolfaei, and K. Moessner, “IoT systems for extreme environments,” IEEE Internet Things J., vol. 11, no. 3, pp. 3671–3675, Feb. 2024. [3] A. Kouloumpris, G. L. Stavrinides, M. K. Michael, and T. Theocharides, “An optimization framework for task allocation in the edge/hub/cloud paradigm,” Future Gener. Comput. Syst., vol. 155, pp. 354–366, Jun. 2024. [4] A. Mohammadzadeh, M. Masdari, and F. S. Gharehchopogh, “Energy and cost-aware workflow scheduling in cloud computing data centers using a multi-objective optimization algorithm,” J. Netw. Syst. Manag., vol. 29, no. 3, pp. 31–64, Apr. 2021. [5] Q. Zheng, Q. Tang, Z. L. Wang, and Z. Li, “Self-powered cardiovascular electronic devices and systems,” Nat. Rev. Cardiol., vol. 18, no. 1, pp. 7–21, Jan. 2021. [6] R. Alam, J. Dugan, N. Homdee, N. Gandhi, B. Ghaemmaghami, H. Meda, A. Bankole, M. Anderson, J. Gong, T. Smith-Jackson, and J. Lach, “BESI: Reliable and heterogeneous sensing and intervention for in-home health applications,” in Proc. IEEE/ACM Int. Conf. Connect. Health Appl. Syst. Eng. Technol. (CHASE), 2017, pp. 147–156. [7] Z. Kashino, G. Nejat, and B. Benhabib, “Multi-UAV based autonomous wilderness search and rescue using target iso-probability curves,” in Proc. Int. Conf. Unmanned Aircr. Syst. (ICUAS), 2019, pp. 636–643. [8] A. Savva, A. Zacharia, R. Makrigiorgis, A. Anastasiou, C. Kyrkou, P. Kolios, C. Panayiotou, and T. Theocharides, “ICARUS: Automatic autonomous power infrastructure inspection with UAVs,” in Proc. Int. Conf. Unmanned Aircr. Syst. (ICUAS), 2021, pp. 918–926. [9] N. Rasouli, C. Klein, and E. Elmroth, “Resource management for mission-critical applications in edge computing: Systematic review on recent research and open issues,” ACM Comput. Surv., vol. 58, no. 3, pp. 71:1–71:37, Sep. 2025. [10] M. Hosseinzadeh, A. Haider, A. M. Rahmani, F. S. Gharehchopogh, S. Rajabi, P. Khoshvaght, T. Porntaveetus, and S.-W. Lee, “SDN-based NFV deployment for multi-objective resource allocation in edge computing: A deep reinforcement learning for IoT workload scheduling,” Sustain. Comput. Inform. Syst., vol. 48, p. 101218, Dec. 2025. [11] P. Khoshvaght, A. Haider, A. M. Rahmani, S. Rajabi, F. S. Gharehchopogh, J. Lansky, and M. Hosseinzadeh, “A self-supervised deep reinforcement learning for zero-shot task scheduling in mobile edge computing environments,” Ad Hoc Netw., vol. 178, p. 103977, Nov. 2025. [12] M. Ottavi, S. Pontarelli, D. Gizopoulos, C. Bolchini, M. K. Michael, L. Anghel, M. Tahoori, A. Paschalis, P. Reviriego, and O. e. a. Bringmann, “Dependable multicore architectures at nanoscale: The view from Europe,” IEEE Des. Test, vol. 32, no. 2, pp. 17–28, Apr. 2015. [13] S. K. Biswas, P. K. Muhuri, and U. K. Roy, “Binary search-based fast scheduling algorithms for reliability-aware energy-efficient task graph scheduling with fault tolerance,” IEEE Trans. Sustain. Comput., vol. 9, no. 3, pp. 433–451, May 2024. [14] M. Maniatakos, M. Michael, C. Tirumurti, and Y. Makris, “Revisiting vulnerability analysis in modern microprocessors,” IEEE Trans. Comput., vol. 64, no. 9, pp. 2664–2674, Sep. 2015. [15] O. Grodzevich and O. Romanko, “Normalization and other topics in multi-objective optimization,” in Proc. First Fields–MITACS Ind. Probl. Workshop, 2006, pp. 89–101.

[16] C. A. Floudas and X. Lin, “Mixed integer linear programming in process scheduling: Modeling, algorithms, and applications,” Ann. Oper. Res., vol. 139, no. 1, pp. 131–162, Oct. 2005. [17] A. Kouloumpris, G. L. Stavrinides, M. K. Michael, and T. Theocharides, “Optimal multi-constrained workflow scheduling for cyber-physical systems in the edge-cloud continuum,” in Proc. IEEE Annu. Comput. Softw. Appl. Conf. (COMPSAC), 2024, pp. 483–492. [18] H. Topcuoglu, S. Hariri, and M.-Y. Wu, “Performance-effective and lowcomplexity task scheduling for heterogeneous computing,” IEEE Trans. Parallel Distrib. Syst., vol. 13, no. 3, pp. 260–274, Mar. 2002. [19] C. Kühbacher, C. Mellwig, F. Haas, and T. Ungerer, “A functional programming model for embedded dataflow applications,” in Proc. IEEE Annu. Comput. Softw. Appl. Conf. (COMPSAC), 2019, pp. 646–651. [20] S. Aldegheri, N. Bombieri, and H. Patel, “On the task mapping and scheduling for DAG-based embedded vision applications on heterogeneous multi/many-core architectures,” in Proc. Des. Autom. Test Eur. Conf. Exhib. (DATE), 2020, pp. 1003–1006. [21] T. A. L. Genez, L. F. Bittencourt, and E. R. M. Madeira, “Timediscretization for speeding-up scheduling of deadline-constrained workflows in clouds,” Future Gener. Comput. Syst., vol. 107, pp. 1116–1129, Jun. 2020. [22] G. v. Zengen, J. Yu, and L. C. Wolf, “Adaptive real-time scheduling for cooperative cyber-physical systems,” in Proc. IEEE Conf. Ind. Cyberphys. Syst. (ICPS), 2020, pp. 79–86. [23] W. Liu, J. Yi, M. Li, P. Chen, and L. Yang, “Energy-efficient application mapping and scheduling for lifetime guaranteed MPSoCs,” IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., vol. 38, no. 1, pp. 1–14, Jan. 2019. [24] L. Mo, Q. Zhou, A. Kritikakou, and J. Liu, “Energy efficient, real-time and reliable task deployment on NoC-based multicores with DVFS,” in Proc. Des. Autom. Test Eur. Conf. Exhib. (DATE), 2022, pp. 1347–1352. [25] L. Mo, Q. Zhou, A. Kritikakou, and X. Cao, “Energy optimized task mapping for reliable and real-time networked systems,” ACM Trans. Sen. Netw., vol. 19, no. 4, pp. 1–26, Nov. 2023. [26] L. Ye, L. Yang, X. Zhao, and Y. Xia, “An energy-aware multistages hybrid scheduling approach for IoT workflow applications with reliability constraint in cloud computing systems,” IEEE Internet Things J., vol. 12, no. 15, pp. 29 670–29 681, Aug. 2025. [27] Q. Jiang, X. Xin, T. Zhang, and K. Chen, “Energy-efficient task scheduling and resource allocation in edge-heterogeneous computing systems using multiobjective optimization,” IEEE Internet Things J., vol. 12, no. 17, pp. 36 747–36 764, Sep. 2025. [28] G. L. Stavrinides and H. D. Karatza, “An energy-efficient, QoS-aware and cost-effective scheduling approach for real-time workflow applications in cloud computing systems utilizing DVFS and approximate computations,” Future Gener. Comput. Syst., vol. 96, pp. 216–226, Jul. 2019. [29] Y. Bai, Y. Huang, G. Xie, R. Li, and W. Chang, “ASDYS: Dynamic scheduling using active strategies for multifunctional mixed-criticality cyber-physical systems,” IEEE Trans. Ind. Inf., vol. 17, no. 8, pp. 5175– 5184, Aug. 2021. [30] V. De Maio and D. Kimovski, “Multi-objective scheduling of extreme data scientific workflows in fog,” Future Gener. Comput. Syst., vol. 106, pp. 171–184, May 2020. [31] S. Tuli, G. Casale, and N. R. Jennings, “MCDS: AI augmented workflow scheduling in mobile edge cloud computing systems,” IEEE Trans. Parallel Distrib. Syst., vol. 33, no. 11, pp. 2794–2807, Nov. 2022. [32] H. M. Fard, R. Prodan, J. J. D. Barrionuevo, and T. Fahringer, “A multi-objective approach for workflow scheduling in heterogeneous environments,” in Proc. IEEE/ACM Int. Symp. Clust. Cloud Grid Comput. (CCGrid), 2012, pp. 300–309. [33] J. Huang, R. Li, X. Jiao, Y. Jiang, and W. Chang, “Dynamic DAG scheduling on multiprocessor systems: Reliability, energy, and makespan,” IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., vol. 39, no. 11, pp. 3336–3347, Nov. 2020. [34] S. Saeedi, R. Khorsand, S. Ghandi Bidgoli, and M. Ramezanpour, “Improved many-objective particle swarm optimization algorithm for scientific workflow scheduling in cloud computing,” Comput. Ind. Eng., vol. 147, p. 106649, Sep. 2020. [35] A. Taghinezhad-Niar and J. Taheri, “Reliability, rental-cost and energyaware multi-workflow scheduling on multi-cloud systems,” IEEE Trans. Cloud Comput., vol. 11, no. 3, pp. 2681–2692, Jul. 2023. [36] Y. Tang, Y. Yuan, and Y. Liu, “Cost-aware reliability task scheduling of automotive cyber-physical systems,” Microprocess. Microsyst., vol. 87, p. 103507, Nov. 2021. [37] G. Xie, G. Zeng, Y. Chen, Y. Bai, Z. Zhou, R. Li, and K. Li, “Minimizing redundancy to satisfy reliability requirement for a parallel application

on heterogeneous service-oriented systems,” IEEE Trans. Serv. Comput., vol. 13, no. 5, pp. 871–886, Sep. 2020. [38] N. Kherraf, S. Sharafeddine, C. M. Assi, and A. Ghrayeb, “Latency and reliability-aware workload assignment in IoT networks with mobile edge clouds,” IEEE Trans. Netw. Serv. Manag., vol. 16, no. 4, pp. 1435–1449, Dec. 2019. [39] F. Anka, G. G. Tejani, S. K. Sharma, and M. Baljon, “A bioinspired method for optimal task scheduling in fog-cloud environment,” Comput. Model. Eng. Sci., vol. 142, no. 3, pp. 2691–2724, Mar. 2025. [40] Gurobi Optimization, https://www.gurobi.com, acc. Jul. 8, 2025. [41] M. Cui, A. Kritikakou, L. Mo, and E. Casseau, “Fault-tolerant mapping of real-time parallel applications under multiple DVFS schemes,” in Proc. IEEE Real-Time Embed. Technol. Appl. Symp. (RTAS), 2021, pp. 387–399. [42] J. Huang, F. Qian, A. Gerber, Z. M. Mao, S. Sen, and O. Spatscheck, “A close examination of performance and power characteristics of 4G LTE networks,” in Proc. Int. Conf. Mob. Syst. Appl. Serv. (MobiSys), 2012, pp. 225–238. [43] V. Papić, P. Šolić, A. Milan, S. Gotovac, and M. Polić, “High-resolution image transmission from UAV to ground station for search and rescue missions planning,” Appl. Sci., vol. 11, no. 5, pp. 1–19, Feb. 2021. [44] Powertop, https://github.com/fenrus75/powertop, acc. Jul. 8, 2025. [45] R. P. Dick, D. L. Rhodes, and W. Wolf, “TGFF: Task graphs for free,” in Proc. Int. Workshop Hardw./Softw. Codesign, 1998, pp. 97–101. [46] Geekbench, https://www.geekbench.com, acc. Jul. 8, 2025. [47] Open Benchmarking, https://openbenchmarking.org, acc. Jul. 8, 2025. [48] A. Kouloumpris, G. L. Stavrinides, M. K. Michael, and T. Theocharides, “Datasets of synthetic workflows for evaluating a multi-objective and multi-constrained scheduling approach for cyber-physical applications,” Apr. 2024. [Online]. Available: https://doi.org/10.5281/zenodo.10978009

Andreas Kouloumpris graduated top of his class receiving the BSc degree in Computer Engineering from the Department of Electrical and Computer Engineering of the University of Cyprus in 2016. He received the PhD degree in Computer Engineering from the same university in 2024. He joined the KIOS Research and Innovation Center of Excellence at the University of Cyprus as a Research Assistant in 2017. He is a member of the Cyprus Scientific and Technical Chamber and a member of the high IQ society MENSA. His research interests include task allocation and scheduling, mathematical optimization, graph theory, edge and cloud computing.

Georgios L. Stavrinides (Member, IEEE) received the BSc degree in Informatics from Aristotle University of Thessaloniki, Greece in 2006 and the MSc degree in Advanced Computing from Imperial College London, UK in 2007. He received the PhD degree in Informatics from Aristotle University of Thessaloniki, Greece in 2014. He is currently a Postdoctoral Fellow at the KIOS Research and Innovation Center of Excellence at the University of Cyprus. He serves on the editorial board of Simulation Modelling Practice and Theory. His research interests include task scheduling in distributed environments and performance optimization of cyber-physical systems in the edge-cloud continuum.

Maria K. Michael (Member, IEEE) received the PhD degree in Computer Engineering from Southern Illinois University, USA. She is currently an Associate Professor at the Department of Electrical and Computer Engineering, and a co-founding faculty member of the KIOS Research and Innovation Center of Excellence, at the University of Cyprus. Her current research focuses on IC/embedded test and reliability, hardware-inspired cyber-security, and resource allocation and reliability in cyber-physical and edge/embedded systems. Her research has been funded by local and international organizations and the industry. She is an associate editor of ACM Computing Surveys and serves on the steering, organizing, and program committees of several IEEE/ACM conferences in the areas of test and reliability.

Theocharis Theocharides (Senior Member, IEEE) received the PhD degree in Computer Engineering from Pennsylvania State University, USA. He is currently an Associate Professor at the Department of Electrical and Computer Engineering, and the Director of Research at the KIOS Research and Innovation Center of Excellence, at the University of Cyprus. His research focuses on the design, development and deployment of low-power and reliable onchip application-specific architectures, VLSI design, and real-time embedded/edge computing systems. His research has been funded by national/European agencies and the industry. He is an associate editor of IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, ACM Computing Surveys, and ACM Journal on Emerging Technologies in Computing Systems.

Exact, Efficient, and Reliable Multi-Objective and Multi-Constrained IoT Workflow Scheduling in Edge-Hub-Cloud Cyber-Physical Systems Supplementary Material Andreas Kouloumpris, Georgios L. Stavrinides, Member, IEEE, Maria K. Michael, Member, IEEE, and Theocharis Theocharides, Senior Member, IEEE

A PPENDIX A The main notations used in the manuscript are summarized in Table A.1. TABLE A.1 M AIN N OTATIONS Notation U uµk Pµk pµk.q λµk.q βµk P bgt Mµk

Definition Set of devices in the considered edge-hub-cloud cyber-physical system (CPS). Device in U , where µ indicates the type of the device (e=edge device, h=hub device, and c=cloud server) and k is the device index for the specific type (e.g., ue1 denotes edge device 1). Set of reserved cores on device uµk . Reserved core on device uµk (e.g., pe1.1 denotes reserved core 1 on edge device 1). Failure rate of core pµk.q . Number of reserved cores on device uµk (i.e., βµk = |Pµk |). Set of all reserved cores on all system devices in U . Memory budget for device uµk .

bgt Sµk

Storage budget for device uµk .

bgt Eµk ψµk,νl ϵµk,νl πµk,νl σµk,νl Iµk,νl C ca Cµk ca yµk T τi G = (N , A) Ni Ai→j zica Lthr G′ = (N ′ , A′ ) Ni′ Ni,µk.q A′i→j Ai,µk.q→j,νl.r

Energy budget for device uµk . Communication channel between devices uµk and uνl . Bandwidth of communication channel ψµk,νl . Energy required to transmit a unit of data over communication channel ψµk,νl . Energy required to receive a unit of data over communication channel ψµk,νl . Set containing the device used for the communication between devices uµk and uνl when they cannot communicate directly. Set of sensing, actuating, or other device capabilities in the considered CPS. Device capability in C. Set of capabilities of device uµk (Cµk ⊆ C). Binary parameter denoting whether device uµk has capability ca ∈ C. Set of tasks of the considered IoT workflow application. Task in T . Initial task graph (TG) of the application, where N and A are the sets of its nodes and arcs, respectively. Node in N representing task τi ∈ T . Arc in A representing the communication and precedence relationship between tasks τi , τj ∈ T . Binary parameter denoting whether task τi requires capability ca ∈ C. Predefined deadline before which the application should be completed (latency threshold). Intermediate task allocation graph (TAG), where N ′ and A′ are the sets of its composite nodes and arcs, respectively. Composite node in N ′ comprising a set of Ni,µk.q nodes. Node in Ni′ representing the possible allocation of task τi on core pµk.q . Composite arc in A′ comprising a set of Ai,µk.q→j,νl.r arcs. Arc in A′i→j representing the transfer of data from node Ni,µk.q to Nj,νl.r . Continues on next page.

TABLE A.1 M AIN N OTATIONS (C ONT.) Notation Mi Si Di Qi ϕi Li,µk.q Pi,µk.q Ei,µk.q Ri,µk.q Rithr ζi,µk.q

Definition Main memory required by task τi . Storage required by task τi . Output data size of task τi . Set of child tasks of task τi . Binary parameter denoting whether task τi is an exit task. Execution time of task τi on core pµk.q . Power required to execute task τi on core pµk.q . Energy required to execute task τi on core pµk.q . Reliability of task τi on core pµk.q . Reliability threshold (lowest required reliability) of task τi . Binary parameter denoting whether task τi when allocated on core pµk.q requires duplication.

ξm θi,µk.q→j,νl.r

Binary parameter denoting whether arc Ai,µk.q→j,νl.r involves indirect communication between devices uµk and uνl through device uξm . Time required to transfer output data Di from task τi (allocated on pµk.q ) to task τj (allocated on pνl.r ). Energy required to transfer output data Di from task τi (allocated on pµk.q ) to task τj (allocated on pνl.r ). Final extended task allocation graph (ETAG), where N ′′ and A′′ are the sets of its composite nodes and arcs, respectively. Primary (if n = 1) or replica (if n = 2) task of task τi . ′′ and N ′′ . Composite node in N ′′ consisting of subsets Ni.1 i.2 Set of primary candidate nodes Ni.1,µk.q . Set of replica candidate nodes Ni.2,µk.q . Primary (if n = 1) or replica (if n = 2) candidate node in Ni′′ representing the possible allocation of τi.1 or τi.2 on core pµk.q , respectively. Composite arc in A′′ comprising a set of Ai.n,µk.q→j.o,νl.r arcs. Arc in A′′ i→j representing the transfer of data from candidate node Ni.n,µk.q to Nj.o,νl.r . Total reliability of task τi when its primary task τi.1 is allocated on core pµk.q , considering whether task duplication is required (R̂i,µk.q = Ri,µk.q,νl.r ) or not (R̂i,µk.q = Ri,µk.q ). Total reliability of primary task τi.1 and its replica τi.2 when allocated on cores pµk.q and pνl.r , respectively. Binary decision variable corresponding to candidate node Ni.n,µk.q ∈ G′′ . Binary decision variable corresponding to arc Ai.n,µk.q→j.o,νl.r ∈ G′′ . ′′ ∈ G′′ ). Continuous decision variable denoting the start time of task τi.n (corresponding to set Ni.n Continuous decision variable denoting the completion time of the application. Auxiliary binary decision variable corresponding to candidate nodes Ni.1,µk.q and Ni.2,νl.r of task τi . Auxiliary binary decision variable denoting whether task τi.n will be executed before task τj.o .

CLi,µk.q→j,νl.r CEi,µk.q→j,νl.r G′′ = (N ′′ , A′′ ) τi.n Ni′′ ′′ Ni.1 ′′ Ni.2 Ni.n,µk.q A′′ i→j Ai.n,µk.q→j.o,νl.r R̂i,µk.q Ri,µk.q,νl.r xi.n,µk.q xi.n,µk.q→j.o,νl.r ti.n T xi,µk.q,νl.r xi.n,j.o xi.n,µk.q h

Auxiliary binary decision variable denoting whether task τi.n will be in execution on core pµk.q at time sh ∈ S.

x̂i.n,µk.q h S sh f˙lat f˙en f¨rel

Auxiliary binary decision variable used in conjunction with xi.n,µk.q to preserve the linearity of the model. h Set of start times of all primary and replica tasks of the application. Time instant in S. Normalized objective function of overall latency. Normalized objective function of overall energy. Negated normalized objective function of overall reliability. Multi-objective function comprising the weighted sum of f˙lat , f˙en , and f¨rel . Weight reflecting the relative importance of overall latency in g. Weight reflecting the relative importance of overall energy in g. Weight reflecting the relative importance of overall reliability in g. Upward rank of candidate node Ni.n,µk.q ∈ G′′.1 Earliest finish time of candidate node Ni.n,µk.q ∈ G′′.1

g wlat wen wrel ρi.n,µk.q EF Ti.n,µk.q 1

Used in extended HEFT.

A PPENDIX B Figs. B.1a and B.1b demonstrate the growth of ETAG nodes and arcs, respectively, under increasing TG size for synthetic IoT workflows. Figs. B.2a and B.2b illustrate the comparison between the average number of ETAG nodes and arcs, respectively, against their corresponding theoretical upper bounds under increasing TG size. The analysis of these results is provided in Section V-C2 of the manuscript. 60

1200

ETAG #Arcs (103)

ETAG #Nodes

1000

Max Median × Mean 25% Min

75%

800 600 400 200 0

25%

Max Median

× Mean

Min

40 30 20 10 0

75%

TG Size (#Tasks)

(a)

(b)

120

2000 1800 1600 1400 1200 1000 800 600 400 200 0

ETAG #Arcs (103)

ETAG #Nodes

Fig. B.1. ETAG (a) number of nodes and (b) number of arcs under increasing TG size. Box plots show the distribution of the number of nodes and arcs across ETAGs for each TG size, while the solid line connects the mean values.

100

80 60 40 20 0

Avg.

Upper Bound

(a)

TG Size (#Tasks)

Avg.

Upper Bound

(b)

Fig. B.2. ETAG (a) average number of nodes and (b) average number of arcs compared against their corresponding theoretical upper bounds under increasing TG size.

Record · ID 138892 · SHA-256 2bee2e507f0975f6
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.