EdgeOPT: A Competitive Algorithm for Online Parallel Task Scheduling With Latency Guarantee in Mobile Edge Computing

The paradigm of mobile edge computing (MEC) has emerged as a promising solution to the increasing demand of time-sensitive applications, where tasks generated by users are offloaded to proximate edge clouds for low-latency execution. Due to the online nature of task generation and edge capacity bottleneck, a fundamental challenge for the MEC network is how to optimally schedule the tasks and resources in face of uncertain future arrivals. To this end, we propose a competitive algorithm named EdgeOPT for online parallel task scheduling aiming to maximize the cumulative reward of completed tasks subject to their hard deadlines. The algorithm leverages an adaptive threshold structure at each server to schedule tasks with different demand patterns based on the status of the system and all active users, while incorporating a subroutine for efficient resource allocations. We prove a bounded competitive ratio for EdgeOPT when scheduling monolithic tasks, and propose its extended version to schedule chains of dependent functions. We conduct extensive experiments to demonstrate the effectiveness and superiority of our proposal compared to all the baselines.