Online Decision-Making under Uncertainty in Edge Computing Systems

Abstract

Scheduling has been a principal area of computer science research because it directly influences the performance, efficiency, and utility of computational and network systems. The scheduler can generally make better decisions with enhanced foreknowledge of the system’s current and future status, which we refer to as offline scheduling. However, obtaining such comprehensive insight is often unfeasible in most real-world scenarios, which limits the application of offline scheduling. In contrast to offline scheduling, online scheduling strives to establish a mechanism for making online decisions as tasks arrive, without comprehensive knowledge of the future system status. In our work, we focus on online scheduling in Edge Computing Systems. We introduce the Cloud-Edge Stretch Minimisation Algorithm (CESMA), an innovative online heuristic that optimises max-stretch in Cloud- Edge Systems. CESMA outperforms existing solutions in terms of performance, adaptability, and computational overhead, showcasing its potential for practical Cloud-Edge Systems. Following this, we propose online decision-making algorithms for practical applications on the Edge Computing Platform. We emphasize the application of Edge Computing in the energy management field. This scenario necessitates online decision-making for effective energy management. We first propose the Virtual Algorithm-based Lightweight Online Scheduling (VALOS) to reduce the energy cost in an energy system. VALOS is a lightweight online algorithm that operates on Edge Computing Platform, designed to improve the energy management under uncertainties. Subsequently, we extend our study to minimise the microgrid operating cost under peak load limitations. We introduce a Rankbased Multiple-choice Secretary Algorithm, RMSA, specifically designed for the price-based demand response scheme. We conducted extensive experiments using real-world datasets, demonstrating its robustness and adaptability in varied and complex scenarios.