Task Offloading in Edge-Cloud Computing: Optimal Algorithm and Complexity for the Backlogged Case

We study a task offloading problem in edge-cloud computing environments with task backlogs. Specifically, we consider a scenario in which an event at the edge triggers a computationally intensive program that can be partitioned into a collection of independent tasks. The objective is to assign each task to either the edge or one of the cloud servers in order to minimize the overall completion time of all tasks. A distinguishing feature of this problem is that, at the time of task assignment, both the edge and cloud servers may already have backlogs of previously assigned tasks. We propose an algorithm that builds on a dynamic programming solution for knapsack-like problems and establish a theoretical framework proving its optimality. Additionally, we conduct a detailed complexity analysis and show that the algorithm's complexity is independent of the backlog sizes. This is a significant result, as backlogs can often be much larger than the total size of the newly arrived tasks.