Communication Augmented Latest Possible Scheduling for cloud computing with delay constraint and task dependency

Abstract

We consider a system consisting of a remote cloud and a network of heterogeneous local processors. We aim to identify the optimal scheduling decision for a mobile application comprising of dependent tasks, such that the total cost is minimized subject to an application deadline. The total cost for application execution accounts for the execution of tasks and the communication of input/output data between the mobile device and the remote cloud. We propose the Communication Augmented Latest Possible Scheduling (CALPS) algorithm to obtain an approximate solution for this NP-hard problem in polynomial time. Through simulation, we study the effect of communication delay and application deadline on the application cost and feasibility. Furthermore, we compare the CALPS algorithm with the optimal solution, a lower bound, and an existing state-of-the-art algorithm to demonstrate the advantage of CALPS in performance and computational complexity.