DeepMAG: Deep reinforcement learning with multi-agent graphs for flexible job shop scheduling

The flexible job shop scheduling (FJSS) is important in real-world factories due to the wide applicability. FJSS schedules the operations of jobs to be executed by specific machines at the appropriate time slots based on two decision steps, namely, the job sequencing (i.e., the sequence of jobs executed on a machine) and the job routing (i.e., the route of a job to a machine). Most current studies utilize either deep reinforcement learning (DRL) or multi-agent reinforcement learning (MARL) for FJSS with a large search space. However, these studies suffer from two major limitations: no integration between DRL and MARL, and independent agents without cooperation. To this end, we propose a new model for FJSS, called DeepMAG based on Deep reinforcement learning with Multi-Agent Graphs. DeepMAG has two key contributions. (1) Integration between DRL and MARL. DeepMAG integrates DRL with MARL by associating a different agent to each machine and job. Each agent exploits DRL to find the best action on the job sequencing and routing. After a job-associated agent chooses the best machine, the job becomes a job candidate for the machine to proceed to its next operation, while a machine-associated agent selects the next job from its job candidate set to be processed. (2) Cooperative agents. A multi-agent graph is built based on the operation relationships among machines and jobs. An agent cooperates with its neighboring agents to take one cooperative action. Finally, we conduct experiments to evaluate the performance of DeepMAG and experimental results show that it outperforms the state-of-the-art techniques.