DAG Scheduling with Communication Delays Based on Graph Convolutional Neural Network

In vehicular edge computing (VEC), tasks and data collected by sensors on the vehicles can be offloaded to roadside units (RSUs) equipped with a set of servers through the wireless transmission. These tasks may be dependent of each other and can be modeled as a directed acyclic graph (DAG). The DAG scheduling problem is aimed at scheduling the tasks to the servers to minimize the scheduling length (makespan), i.e., the maximum finish time of all tasks. The conventional heuristic algorithms only utilize partial information of the DAG, so the performance of these algorithms is not stable. The state-of-the-art scheduling method employs the graph neural network to further reduce the makespan. However, this method ignores the fact that there are communication delays between tasks scheduled on different servers. In this paper, we tackle the DAG scheduling problem considering communication delays which makes the problem much more challenging. Our method is based on graph convolutional neural network and reinforcement learning. Experimental results show that our scheduling method reduces the DAG scheduling length by 8% to 15% compared with the representative scheduling strategies based on graph neural network models (GAT, GraphSAGE) and 15% to 25% compared with the conventional algorithms (HEFT, LC, and CPOP) and the sequence-to-sequence model.