Solving Open Shop Scheduling Problem via Graph Attention Neural Network
Jing Li, Xingye Dong, Kai Zhang, Sheng Han
Abstract
Open Shop Scheduling Problem (OSSP) minimizing makespan has attracted attention increasingly. Complex constraints and large solution space cause great difficulty for acquiring optimal solutions. Traditional methods attempt to get suboptimal solutions based on pre-defined rules or local search. However, these methods are not universal and only applicable for problems with particular distributions. In this paper, we introduce Discount Memory into Graph Attention Model (GAM-DM) to solve OSSP and train the model with reinforcement learning. By constructing incremental graph solution, OSSP is converted to sequence to sequence problem, which makes GAM suitable for OSSP. Moreover, the proposed DM can help clarify the different influences of historical decisions on current decision-making step. We integrate GAM-DM into reinforcement learning to optimize the solution and conduct experiments on randomly generated problem sets. The experiment results indicate that our model outperforms traditional methods, benefiting from high-quality solution close to the lower bound. Compared with OR-Tool, our model achieves comparable solution quality with less computational time.