QoS-aware Scheduling of Periodic Real-time Task Graphs on Heterogeneous Pre-occupied MECs
1 st Ashutosh Shankar, 2 nd Astha Kuamari · 2025
Read QoS-aware Scheduling of Periodic Real-time Task Graphs on Heterogeneous Pre-occupied MECs by 1 st Ashutosh Shankar, 2 nd Astha Kuamari (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-2506-12415.txt.
Introduction
Ashutosh Shankar and Astha Kumari published a computing paper in 2025 on scheduling real-time task graphs on edge servers that are already partly busy. Tasks arrive in repeating cycles, linked as directed graphs, with strict deadlines and quality demands. The team adapts a classic list scheduling method to exploit leftover capacity on varied processors. Their version finds idle gaps without disturbing the existing workload.
The method builds a repeating schedule that assigns each task a machine, a version, and a start time. It respects order, timing, and resource limits while raising total quality. Tests show better load balance and resource use. The authors aim at edge systems serving periodic real-time jobs.
Catalog record
| CREATOR | 1 st Ashutosh Shankar, 2 nd Astha Kuamari |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-12415
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
QoS-aware Scheduling of Periodic Real-time Task Graphs on Heterogeneous Pre-occupied MECs 1 st Ashutosh Shankar, 2 nd Astha Kuamari Abstract In latency-sensitive applications, efficient task scheduling is crucial for maintaining Quality of Service (QoS) while meeting strict timing constraints. This paper addresses the challenge of scheduling periodic tasks structured as directed acyclic graphs (DAGs) within heterogeneous, pre-occupied Mobile Edge Computing (MEC) networks. We propose a modified version of the Heterogeneous Earliest Finish Time (HEFT) algorithm designed to exploit residual processing capacity in pre-occupied MEC environments. Our approach dynamically identifies idle intervals on processors to create a feasible hyperperiodic schedule that specifies an allocated virtual machine (VM), task version, and start time for each task. This scheduling strategy maximizes the aggregate QoS by optimizing task execution without disrupting the existing periodic workload, while also adhering to periodicity, precedence, and resource constraints. Experimental results demonstrate that our method achieves enhanced load balancing and resource utilization, highlighting its potential to improve performance in heterogeneous MEC infrastructures supporting real-time, periodic applications. I Introduction With the growth of cloud computing, resource heterogeneity has become critical to improving the performance and efficiency of cloud-based systems. Resource heterogeneity[9] is the integration of several specialized processing units inside a cloud architecture, each designed to handle certain types of workloads efficiently. These resources include central processing units (CPUs) for general-purpose computing, graphics processing units (GPUs) for parallel processing tasks, tensor processing units (TPUs) for deep learning, and field-programmable gate arrays (FPGAs) for customizable, low-latency applications. By leveraging this diversity, cloud platforms enable diverse applications in the domains of artificial intelligence (AI), scientific simulations, and big data analytics to operate at higher efficiencies, optimized for performance, cost, and adaptability. Unlike traditional homogeneous systems, where all processing units are identical [1] and perform at similar levels, heterogeneous systems enable cloud users to match specific workload requirements to the most suitable resources, improving overall performance and cost efficiency. In heterogeneous cloud environments, the challenge is to efficiently schedule and allocate tasks across diverse resources to achieve optimal performance, reduced idle time, and improved cost efficiency, while maximizing the quality of service (QoS) delivered by the system. This paper addresses this problem by focusing on a static scheduling approach, which is particularly suitable for predictable and periodic workloads. Static scheduling allows task assignments to be determined prior to execution, providing a high degree of predictability and control over resource distribution based on prior knowledge of task requirements and system capacity. Unlike dynamic scheduling, which allocates tasks at runtime and adapts to changing system states, static scheduling is ideal for applications where task patterns are known in advance, allowing for optimized resource allocation and quality maximization in a cloud environment with pre-occupied processors. Our approach specifically aims to maximize the quality by ensuring tasks are allocated to the most suitable resources, considering both performance and service-level objectives. Directed Acyclic Graphs (DAGs) are widely used in task scheduling for cloud computing as they represent workflows where nodes denote tasks and edges represent dependencies between them. In a DAG, each task must follow its precedence constraints, ensuring that a task does not start until its dependencies are fulfilled. This structure is particularly useful for modeling workflows in heterogeneous environments, as it enables visualization and tracking of tasks with dependencies, which is crucial for efficient scheduling. By representing workflows as a DAG, we can better manage the complexity of resource allocation and optimize task execution order, leading to improved performance, minimized idle time, and enhanced quality of service. One popular scheduling algorithm for heterogeneous computing environments, especially when dealing with DAGs, is the Heterogeneous Earliest Finish Time (HEFT) algorithm. HEFT is a static scheduling algorithm designed to achieve optimal task allocation by minimizing the makespan — the total execution time for all tasks in the workflow. HEFT prioritizes tasks based on their level, which is a measure of task importance derived from its position in the DAG and the weight of the edges leading to it. Tasks with higher levels (often near the top of the DAG) are prioritized for assignment. For each prioritized task, HEFT selects the processor that minimizes the task’s earliest possible finish time while considering both task dependencies and processor heterogeneity. This approach is especially suitable for heterogeneous environments, as it efficiently leverages diverse processing resources to meet the workflow’s scheduling constraints, thereby maximizing the overall quality of the service provided. This paper proposes a new scheduling algorithm that builds upon and modifies the HEFT algorithm to better suit the unique demands of heterogeneous cloud environments. This modified algorithm aims to improve task scheduling by minimizing the makepan and enhancing the effective use of diverse resources, specifically maximizing quality and ensuring that service-level objectives are met. The effectiveness of our proposed algorithm is demonstrated through a practical example. The remaining parts of this paper are organized as follows: Section II presents the Literature review. In Section III, we describe the task scheduling problem and its formulation. Section IV explains the problem statement. In Section V, we introduce our proposed scheduling algorithm, which is a modification of the HEFT algorithm, and demonstrate its performance through an example. Section VI presents the results of our work. Finally, Section VII concludes the paper and discusses future research directions. II Related Work II-A Maintaining the Integrity of the Specifications In this section, we conduct a survey of related work on task scheduling techniques in cloud computing, highlighting significant advancements that enhance scheduling efficiency and Quality of Service (QoS) in heterogeneous environments. Task scheduling is a critical component in managing the extensive virtualized resources available in cloud computing, where manual scheduling is impractical due to the scale of operations. The paper [2] provides a comprehensive overview of various scheduling strategies and metrics suitable for cloud environments. It categorizes existing research based on methods, applications, and parameter-based measures while identifying limitations in current methodologies. This survey can be used to highlight precisely where new algorithms are needed for an enhanced cloud scheduling performance. Varied techniques including heuristics[7], mathematical operations, and machine learning models as well as evolutionary algorithms – such as the genetic algorithm, [8]ant colony optimization algorithm, cuckoo search algorithm, and swarm intelligence algorithm – can be used to develop hybrid algorithms that can perform more effectively compared to existing approaches. The study [3] proposes an innovative two-stage strategy aimed at enhancing task scheduling performance and minimizing unreasonable task allocation in cloud environments. In the first stage, a job classifier inspired by Bayes’ design principle classifies tasks based on historical scheduling data, allowing for the pre-creation of virtual machines (VMs) of different types. This approach reduces delays associated with VM creation during task execution. In the second stage, tasks are dynamically matched with suitable VMs, effectively improving load balancing and overall scheduling performance compared to traditional methods. The proposed framework aims to minimize task execution costs while meeting deadlines by efficiently utilizing VMs and reducing waiting times. One notable approach focuses on scheduling user tasks in cloud environments while minimizing energy consumption and adhering to QoS requirements. This study introduces a model that analyzes the state of running tasks using a QoS prediction method based on an ARIMA model optimized with a Kalman filter. The authors propose a