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

Abstract

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.

Ruiqi (Ricky) Chen

PhD Student in ECRG