Job Scheduling to Minimize Total Completion Time on Multiple Edge Servers

摘要

The mobile devices can send jobs to be processed at one of the nearby edge servers rather than the remote cloud server with low latency in edge computing systems. One key problem in such environment is how to assign the jobs to the edge servers so that the completion time is minimized. In this article, we propose a general model for this problem by considering the arbitrary arriving time of the jobs, the different processing speeds of the edge servers, the different time for uploading a job to different edge servers and the delay for returning the result back to a mobile device. Our goal is to minimize the total response time for complete all the jobs. We study a series of instances for this problem and provide lower bounded approximated offline algorithms in edge computing environments. The approximation ratio of our algorithm for the general problem is (max{2 + s(max)/s(min), d(max)/d(min)}). And it can be easily transformed to online algorithm whose theoretical performance is no twice worse than the offline algorithm. Moreover, the algorithm can be easily implemented in distributed systems. Extensive simulations show that both the proposed offline and online algorithms can derive good performance comparing with the optimal solution.