Optimal Multi-Constrained Workflow Scheduling for Cyber-Physical Systems in the Edge-Cloud Continuum

Andreas Kouloumpris, Georgios L. Stavrinides, Maria K. Michael, and Theocharis Theocharides · 2025

Read Optimal Multi-Constrained Workflow Scheduling for Cyber-Physical Systems in the Edge-Cloud Continuum by Andreas Kouloumpris, Georgios L. Stavrinides, Maria K. Michael, and Theocharis Theocharides (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-07466.txt.

Introduction

Andreas Kouloumpris and colleagues schedule work across phones, hubs, and cloud servers that run cyber-physical apps. Edge devices sense and act quickly but have small processors, batteries, and radios. A hub and a cloud server add power at the cost of delay.

The team formulates optimal scheduling that cuts total workflow delay across that edge-hub-cloud chain. Their model handles mixed multicore chips and devices with special sensing or acting roles. A full treatment compares placements and orders under several limits at once. System designers get a benchmark for latency-critical tasks such as monitoring and control that must react in real time.

Catalog record

CREATORAndreas Kouloumpris, Georgios L. Stavrinides, Maria K. Michael, and Theocharis Theocharides
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-07466

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Optimal Multi-Constrained Workflow Scheduling for Cyber-Physical Systems in the Edge-Cloud Continuum Andreas Kouloumpris, Georgios L. Stavrinides, Maria K. Michael, and Theocharis Theocharides Abstract The emerging edge-hub-cloud paradigm has enabled the development of innovative latency-critical cyber-physical applications in the edge-cloud continuum. However, this paradigm poses multiple challenges due to the heterogeneity of the devices at the edge of the network, their limited computational, communication, and energy capacities, as well as their different sensing and actuating capabilities. To address these issues, we propose an optimal scheduling approach to minimize the overall latency of a workflow application in an edge-hub-cloud cyber-physical system. We consider multiple edge devices cooperating with a hub device and a cloud server. All devices feature heterogeneous multicore processors and various sensing, actuating, or other specialized capabilities. We present a comprehensive formulation based on continuous-time mixed integer linear programming, encapsulating multiple constraints often overlooked by existing approaches. We conduct a comparative experimental evaluation between our method and a well-established and effective scheduling heuristic, which we enhanced to consider the constraints of the specific problem. The results reveal that our technique outperforms the heuristic, achieving an average latency improvement of 13.54% in a relevant real-world use case, under varied system configurations. In addition, the results demonstrate the scalability of our method under synthetic workflows of varying sizes, attaining a 33.03% average latency decrease compared to the heuristic. I Introduction The edge-hub-cloud paradigm has emerged as an alternative to the conventional edge computing concept. This shift is driven by the increasing demand for intelligent decision-making and real-time response at the network edge [ 31 , 1 , 12 , 25 ] . In contrast to the traditional concept that typically has three distinct layers within the edge-cloud continuum (i.e., edge devices, edge servers, and cloud servers), this paradigm considers edge and hub devices that are usually battery-powered in the bottom layer, and cloud servers in the top layer. A hub device (e.g., a smartphone or laptop) often has a higher computational capacity than an edge device (e.g., a wearable or single-board computer). Furthermore, it is physically closer to the edge devices than an edge server (although less capable), facilitating their communication with the remote cloud data center. With the advent of the edge-hub-cloud paradigm, novel cyber-physical applications have been developed, consisting of precedence-constrained tasks that require diverse device capabilities for their execution, such as specific sensors, actuators, or software/hardware modules [ 19 ] . These applications, referred to as workflows, encompass a wide range of latency-critical scenarios. The use of biomedical edge devices with integrated sensors and actuators for remote patient monitoring and support (e.g., smart pacemakers and wearable cardioverter defibrillators) [ 31 , 1 ] or the use of unmanned aerial vehicles (UAVs) with different capabilities for autonomous critical infrastructure inspection or search-and-rescue missions (e.g., UAVs with thermal/multispectral cameras or customized payload release systems) [ 12 , 25 ] , are some prominent examples. In these scenarios, multiple edge devices with distinct capabilities cooperate with a hub device and a cloud server, which may also feature specialized software or hardware components, like libraries or accelerators for machine learning inference. The intrinsic criticality of such applications requires optimal task scheduling to determine where to allocate and when to execute each task, so as to achieve the minimum possible latency, which is usually bounded by a strict deadline [ 27 ] . In contrast to heuristic approaches, exact methods such as mixed integer linear programming (MILP) can yield optimal schedules, but are typically computationally intensive. However, the pre-programmed nature of the examined applications allows the use of these methods for offline scheduling—although solutions should still be provided in a reasonable time to be practical. In exact methods, time is modeled as either discrete or continuous. Discrete-time models simplify the problem by considering that events occur only at the beginning or end of predefined time intervals, which is not a realistic assumption. On the other hand, continuous-time models offer higher accuracy by allowing events to occur at any time. However, this flexibility makes the problem formulation more challenging, particularly the modeling of time-dependent cumulative constraints for the concurrent utilization of limited resources by multiple tasks, such as main memory, storage, or specific device capabilities [ 7 ] . Moreover, challenges arise due to the heterogeneity of the devices where the considered applications are deployed, as they often feature different multicore processors and varied sensing/actuating capabilities. These challenges are amplified by the diverse communication characteristics of the operating setting. In addition, moving from the cloud towards the network edge, there are increasing limitations in the computational, memory, storage, and energy capacities of the devices. In such environments, it is imperative to employ a workflow scheduling strategy that takes into account all these constraints, which make finding an optimal schedule particularly challenging. To this end, we propose an offline continuous-time MILP approach to optimally schedule a workflow application in an edge-hub-cloud cyber-physical system (CPS) with multiple edge devices, heterogeneous multicore processors, and distinct device capabilities. Our objective is to minimize the overall latency, while considering crucial constraints that characterize these systems. The contributions of this work are summarized as follows: • We propose a comprehensive continuous-time MILP formulation to optimally schedule a workflow application in the examined edge-hub-cloud CPS by minimizing the overall latency. Our formulation is facilitated by an extended representation of the application task graph. • We holistically address multiple constraints that are overlooked by existing scheduling methods, both exact and heuristic. These constraints are based on the memory, storage, and energy limitations of the devices, the heterogeneity and multicore architecture of the processors, the diverse device capabilities, the execution deadline, as well as the computational and communication latency and energy requirements of the tasks. • As the proposed approach is the first to provide an optimal solution for the considered problem, constraints, and architecture, we evaluate and compare it against a widely used and effective scheduling heuristic, the heterogeneous earliest finish time (HEFT) [ 28 , 18 , 2 ] . To ensure a fair and meaningful comparison, we extended HEFT to incorporate the constraints of the examined problem. • In our experiments, we consider a real-world workflow for the autonomous UAV-based power infrastructure inspection, under various system configurations. To further validate and investigate the scalability of our method to applications of different sizes, we utilize multiple synthetic workflows with appropriate parameters. The rest of the paper is organized as follows. Section II provides an overview of related literature. Section III describes the proposed MILP approach, whereas Section IV explains our extension to HEFT. Section V presents the experimental setup, the evaluation results, and the empirical scalability analysis of our technique. Section VI provides concluding remarks. II Related Work Workflow scheduling in distributed environments is a well-studied problem that has been investigated extensively using both exact and heuristic methods [ 9 , 21 , 20 , 29 , 30 , 5 , 3 , 26 , 28 , 18 , 2 ] . For example, MILP-based scheduling techniques for deadline-constrained workflows are proposed in [ 9 , 21 , 20 , 29 , 30 ] , with [ 20 ] and [ 30 ] focusing on specific CPS architectures. While these methods [

Read the complete text