A Deep Reinforcement Learning Framework Based on an Attention Mechanism and Disjunctive Graph Embedding for the Job Shop Scheduling Problem


The job-shop scheduling problem (JSSP) is a classical NP-hard combinatorial optimization problem, and the operating efficiency of manufacturing system is affected directly by the quality of its scheduling scheme. In this paper, a novel deep reinforcement learning framework is proposed for solving the classical JSSP, where each machine has to process each job exactly once. This method based on an attention mechanism and disjunctive graph embedding, and a sequence-to-sequence pattern is used to model the JSSP in the framework. A disjunctive graph embedding process based on node2vec is used to learn the disjunctive graph representations containing JSSP characteristics, thereby generalizing the model considerably. An improved Transformer architecture based on a multi-head attention mechanism is used to generate solutions. Containing a parallel-computing encoder and a recurrent-computing decoder, it is adept at learning long-range dependencies and effective at solving large-scale scheduling problems. Experimental results verified the effectiveness of the proposed method.

IEEE Transactions on Industrial Informatics

Access the full text at the publisher

Publication Information

DOI: 10.1109/TII.2022.3167380

Funding Agency: the National Natural Science Foundation of China (Grant Number: 52075354)

Date of Publication: 14 April 2022

Publisher: IEEE

My Contribution
  • First Author
  • Innovation
  • Manuscript
  • Most of Graphs
  • Experiment and Analysis
Ruiqi (Ricky) Chen
Ruiqi (Ricky) Chen
PhD Student in ECRG