A Meta-Heuristic Real-Time Task Graph Scheduler for Partially Occupied Edge Computing Platforms

The integration of Quality of Service (QoS)-specific communications and Multi-access Edge Computing (MEC) in advanced 5G networks is driving the emergence of innovative applications and business models. An important outcome this development is the ability to execute real-time automated monitoring and control tasks as edge services on MEC servers. Such real-time control applications, which are often modeled as Directed Acyclic Graphs (DAGs) due to their intricate interdependencies, can be periodic and persistent or aperiodic and dynamic (e.g., event-triggered alarms). Tasks within these DAGs may operate at various QoS levels, where higher levels enhance accuracy and reliability, improving the overall application QoS. This paper proposes a QoS-aware anytime scheduling approach for dynamically scheduling an aperiodic DAG-structured application on an MEC system already supporting periodic real-time tasks. We propose the Meta-heuristic QoS-Aware DAG Scheduler (M-QADS), a metaheuristic approach that begins by creating initial base schedules and iteratively improves them through task QoS level enhancements. Extensive simulations using both randomly generated and standard benchmark DAGs, alongside comparisons with the baseline heuristic Enhanced QoS HEFT (EQ-HEFT), reveal that M-QADS outperforms EQ-HEFT across diverse scenarios, demonstrating its effectiveness.