Dynamic Programming for Task Offloading in Edge-Cloud Computing

We study a task offloading problem in edge-cloud computing. Suppose the edge needs to start a computationally intensive program, which can be partitioned into a collection of tasks. Our goal is to assign each of the tasks to either the edge or one of the cloud centers so as to minimize the overall completion time of all the tasks. We develop an algorithm that uses dynamic programming solutions for knapsack-like problems as building blocks. Compared with general integer programming algorithms, we gain greater control over the internals of our algorithm so that we can extend it or adapt it for different practical purposes. In particular, we develop approximation algorithms by rounding and show the performance bounds. We also extend the algorithm to cover the case where the edge and cloud already have backlogs of tasks to process.