Semi-Online Multi-Machine with Restart Scheduling for Integrated Edge and Cloud Computing Systems

We study the multi-machine task scheduling problem in an integrated serverless edge and cloud computing system, where tasks can be scheduled locally on edge processors or offloaded to cloud servers, with the objective of minimizing the makespan, i.e., the total time to finish all tasks. The system is semi-online, where the edge processing delays of the tasks are known as priori, but the cloud processing delays remain unknown due to the uncertainty introduced by uploading and loading delay (loading the software environment). The problem is NP-hard in nature, and therefore we resort to approximation schemes and propose a novel algorithm named multi-machine with restart scheduling (MRS). MRS utilizes task restart, where a task that is cancelled will be restarted later when its processing time exceeds the threshold, and the threshold can be adaptively adjusted. We derive an O(1) competitive ratio for MRS so that its worst-case gap from the optimal solution is bounded. We also implement the MRS scheduler in a real-world system, which schedules a diverse set of Deep Neural Network (DNN) inference tasks. It shows that MRS achieves significant reduction in makespan compared to existing benchmark schemes.