Learning to Schedule with Graph Neural Networks and Reinforcement Learning : Investigation of Embeddings and Performance

Sammanfattning

The increasing number of cores in commercial processors and the rising demand for high performance computing has made the problem of sched􀀸 uling tasks in parallel increasingly relevant. Previous methods have focused on classic heuristics and linear programming, achieving varying levels of performance for the problem. The success of machine learning based methods for combinatorial optimization suggests an entirely learning based method might be utilized. This thesis investigates the possibility of using an end􀀸to􀀸end machine learning method, with a graph neural network based architecture and reinforcement learning training, to produce schedules for the problem of scheduling tasks in parallel with precedence constraints. We focus on a simple task model where precedence between tasks is encoded as a directed acyclic graph, and each subtask has an associated runtime. The results indicate that the method has learned structural properties of the graph, achieving performance comparable to classic methods for small testcases. However a gap remains for larger testcases, with our method struggling to achieve parity to classic methods. An investigation of our graph representation module reveals that the produced node embeddings for tasks are highly explainable. Finally, we suggest further investigation of hybrid methods, more complex task models and with greater computational resources.