This paper addresses the deadline-constrained task offloading and resource allocation problem in multi-access edge computing. We aim to determine where each task is offloaded and processed, as well as corresponding communication and computation resource allocations, to maximize the total saved energy for IoT devices, while considering task deadline and system resource constraints. Especially, our system allows each task to be offloaded to one of its accessible access points (APs) and processed on a server that is not co-located with its offloading AP. We formulate this problem as an Integer Nonlinear Programming problem and show it is NP-Hard. To address this problem, we propose a Graph-Matching-based Approximation Algorithm (GMA), the first approximation algorithm of its kind. GMA leverages linear relaxation, tripartite graph construction, and a Linear Programming rounding technique. We prove that GMA is a$\frac{1-\alpha}{2+\epsilon}$-approximation algorithm, where$\epsilon$is a small positive value, and$\alpha(0 \leq \alpha<1)$is a system parameter that ensures the resource allocated to any task by an AP or a server cannot exceed$\alpha$times its resource capacity. Experiments show that, in practice, GMA's energy saving achieves 97% of the optimal value on average.

Vehicular Edge Computing (VEC) has emerged as a promising paradigm for enhancing the computational efficiency and service quality in intelligent transportation systems by enabling vehicles to wirelessly offload computation-intensive tasks to nearby Roadside Units. However, efficient task offloading and resource allocation for time-critical applications in VEC remain challenging due to constrained network bandwidth and computational resources, stringent task deadlines, and rapidly changing network conditions. To address these challenges, we formulate a Deadline-Constrained Task Offloading and Resource Allocation Problem (DOAP), denoted as P, in VEC with both bandwidth and computational resource constraints, aiming to maximize the total vehicle utility. To solve$\mathbf{P}$, we propose SARound, an approximation algorithm based on Linear Program rounding and local-ratio techniques, that improves the best-known approximation ratio for DOAP from$\frac{1}{6}$to$\frac{1}{4}$. Additionally, we design an online service subscription and offloading control framework to address the challenges of short task deadlines and rapidly changing wireless network conditions. To validate our approach, we develop a comprehensive VEC simulator, VecSim, using the open-source simulation libraries OMNeT++ and Simu5G. VecSim integrates our designed framework to manage the full life-cycle of real-time vehicular tasks. Experimental results, based on profiled object detection applications and real-world taxi trace data, show that SARound consistently outperforms state-of-the-art baselines under varying network conditions while maintaining runtime efficiency.

This work studies fixed priority (FP) scheduling of real-time jobs with end-to-end deadlines in a distributed system. Specifically, given a multi-stage pipeline with multiple heterogeneous resources of the same type at each stage, the problem is to assign priorities to a set of real-time jobs with different release times to access a resource at each stage of the pipeline subject to the end-to-end deadline constraints. Note, in such a system, jobs may compete with different sets of jobs at different stages of the pipeline depending on the job-to-resource mapping. To this end, following are the two major contributions of this work. We show that an OPA-compatible schedulability test based on the delay composition algebra can be constructed, which we then use with an optimal priority assignment algorithm to compute a priority ordering. Further, we establish the versatility of pairwise priority assignment in such a multi-stage multi-resource system, compared to a total priority ordering. In particular, we show that a pairwise priority assignment may be feasible even if a priority ordering does not exist. We propose an integer linear programming formulation and a scalable heuristic to compute a pairwise priority assignment. We also show through simulation experiments that the proposed approaches can be used for the holistic scheduling of real-time jobs in edge computing systems.

Mobile-edge computing (MEC) has emerged as a promising paradigm for enabling Internet of Things (IoT) devices to handle computation-intensive jobs. Due to the imperfect parallelization of algorithms for job processing on servers and the impact of IoT device mobility on data communication quality in wireless networks, it is crucial to jointly consider server resource allocation and IoT device mobility during job scheduling to fully benefit from MEC, which is often overlooked in existing studies. By jointly considering job scheduling, server resource allocation, and IoT device mobility, we investigate the deadlineconstrained job offloading and resource management problem in MEC with both communication and computation contentions, aiming to maximize the total energy saved for IoT devices. For the offline version of the problem, where job information is known in advance, we formulate it as an Integer Linear Programming problem and propose an approximation algorithm, LHJS, with a constant performance guarantee. For the online version, where job information is only known upon release, we propose a heuristic algorithm, LBS, that is invoked whenever a job is released. Finally, we conduct experiments with parameters from real-world applications to evaluate their performance.

In an edge-cloud system, mobile devices can offload their computation intensive tasks to an edge or cloud server to guarantee the quality of service or satisfy task deadline requirements. However, it is challenging to determine where tasks should be offloaded and processed, and how much network and computation resources should be allocated to them, such that a system with limited resources can obtain a maximum profit while meeting the deadlines. A key challenge in this problem is that the network and computation resources could be allocated on different servers, since the server to which a task is offloaded (e.g., a server with an access point) may be different from the server on which the task is eventually processed. To address this challenge, we first formulate the task mapping and resource allocation problem as a non-convex Mixed-Integer Nonlinear Programming (MINLP) problem, known as NP-hard. We then propose a zero-slack based greedy algorithm (ZSG) and a linear discretization method (LDM) to solve this MINLP problem. Experiment results with various synthetic tasksets show that ZSG has an average of 2.98% worse performance than LDM with a minimum unit of 5 but has an average of 6.88% better performance than LDM with a minimum unit of 15.

In an edge-cloud system, end devices can offload computation intensive tasks to servers for processing, to satisfy deadline requirements of time-critical tasks, or maintain a good quality of service. Because the system has limited bandwidth and computation resource, it can be very challenging to determine where tasks should be offloaded and processed (task mapping), and how much bandwidth and computation resource should be allocated to each task (resource allocation). In this paper, we propose a task mapping and multi-resource allocation problem with both communication and computation contentions in an edge-cloud system, which aims to maximize the total profit gained by the system while meeting the deadlines of mapped tasks. Besides, the backhaul network of the proposed edge-cloud system is modeled as a directed incomplete graph with bandwidth contention on every edge of the graph. We formulate the problem into a nonconvex Mixed-Integer Nonlinear Programming (MINLP) problem and provide a linearization method to reformulate the MINLP problem into an Integer Linear Programming (ILP) problem formulation, which can be solved with ILP solvers.