Task Completion Time Minimization in Parallel Distributed Edge Computing Networks: Co-Design of Offloading Selections and Scheduling Order

The distributed edge computing network has been proposed as a promising approach to accelerate task computation. Incorporating parallel edge computing, we investigate a parallel distributed edge computing network where each edge device is allowed to receive one task and compute another task simultaneously, and meanwhile, edge devices are allowed to compute their respectively received tasks simultaneously. We minimize the total task completion time (TCT) of source nodes by jointly optimizing offloading selections of source nodes and scheduling order of task offloading, i.e., MTOS problem, which is proved to be NP-hard. To tackle it, we first study the MTOS problem with one edge device (MTOS-1), establish three task offloading rules to minimize the total TCT, and propose a priority-based scheduling order of task offloading algorithm. Based on the established task offloading rules for the MTOS-1 problem, we study the MTOS problem with M edge devices and additional offloading-adjacency constraint (MTOSO- M), establish another two task offloading rules for scheduling order, and propose an automatic adjustment-based joint offloading selections and scheduling order algorithm. By relaxing the offloading-adjacency constraint of the MTOSO- M problem, we further study the general MTOS problem with M edge devices (MTOS- M), derive a lower bound of the total TCT, and propose a queue jumping-based joint offloading selections and scheduling order algorithm. Extensive numerical results are conducted to discuss impacts of vital network parameters on the total TCT, verify the superiority of the proposed algorithms, and show that the communication-computation parallelism for edge devices and the computation parallelism among edge devices further reduce the total TCT.