Employee planning is a complex task that affects the operations and profitability of many companies. It requires optimizing total operating costs and profitability while satisfying constraints such as employee availability, skills and preferences, which oftentimes leads to the use of combinatorial optimization techniques, a powerful tool to solve this problem. Traditional combinatorial optimization techniques rely on branch and bound, cutting plane, and local search techniques to find the optimal solution. However, these traditional techniques can be computationally expensive for and are oftentimes not scalable for large-scale problem instances. To overcome these issues, we propose a new method which utilizes the power of deep neural networks. We first convert the employee scheduling problem into a graph and build a novel graph neural network (GNN) to learn the optimal solution on the graphical representation of the problem. We evaluate the performance of our enhanced techniques on a large number of instances of employee scheduling problems, which show that our approach can significantly improve the performance of traditional combinatorial optimization techniques (approximately 20.86% to 46.79% compared to the state-of-the-art solver, CPLEX).