Scheduling Periodic Jobs with Discretely Controllable Processing Time on Edge and Cloud Systems

Abstract

In recent years, the rapid development of the processing capability of smart devices enables us to process a wide variety of intelligent applications in a variety of scenarios. However, due to the limited size and energy, current smart devices are still unable to provide sufficient computational capability when dealing with complex smart applications. Therefore, computation offloading becomes a natural solution. The resource-constrained devices can offload their computational jobs to an edge server or a cloud server to accelerate their computation processes. Other than computation offloading, under many real-world situations, the processing time of computational jobs can be shortened if an acceptable result is expected. This is referred to as discretely controllable processing time, where the original processing time can be shortened to a number of levels with less satisfactory but acceptable processing results.

In this thesis, we are motivated to investigate how to accelerate the computation on the edge/cloud computing systems by combining the advantages of both computation offloading and controllable processing time under different network conditions. We formulate and solve three scheduling problems of periodic jobs with discretely controllable processing time (abbr. PDCPT) with respect to three scenarios: (1) When the edge/cloud system is experiencing the service outage and the computation offloading becomes unavailable, all jobs can only be accelerated by the controllable processing time on the local device. In this case, we propose a dynamic programming based algorithm (i.e., PDCPT-1 solver) to find the best achievable solution with a pseudo-polynomial computational complexity; (2) When the edge/cloud system is under a high-speed network condition with the negligible offloading delay, we can employ both the computation offloading and the controllable processing time to accelerate the computation. In this case, we propose another dynamic programming based algorithm (i.e., PDCPT-2 solver) to generate the optimal schedule within a pseudo-polynomial time; (3) When the edge/cloud system is under a low-speed network condition with the non-negligible offloading delay, we use both the computation offloading and the controllable processing time optimisation techniques. In this case, we design the PDCPT-3 solver to optimally schedule the jobs in a dynamic programming manner with a pseudo-polynomial computational complexity.

For each of the three mentioned cases, we developed novel solutions with analytical analysis. Meanwhile, we also evaluate the performance of the proposed algorithms through conducting a series of trace-driven simulations. For the first case, we design a real world experiment to show the practicability of the PDCPT-1 solver. All results, including both the experiments and simulations, demonstrate the effectiveness of our solutions in accelerating computation on edge/cloud systems.