EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3775. AM4FJSSP: An Attention Model formulation for the Flexible Job Shop Scheduling Problem

Invited abstract in session TA-3: (Deep) Reinforcement Learning for Combinatorial Optimization 3, stream Data Science Meets Optimization.

Tuesday, 8:30-10:00
Room: 1005 (building: 202)

Authors (first author is the speaker)

1. Lin Xie
Chair of Information Systemes and Business Analytics, Brandenburg University of Technolgy

Abstract

The flexible job shop scheduling problem (FJSSP) is a complex combinatorial optimization CO problem (COP) in manufacturing, involving the allocation of operations across multiple machines while considering varying processing requirements and machine capabilities. In contrast to normal job shop scheduling operations in the FJSSP may be processed on multiple machines with different processing times, introducing additional complexity.
Current deep reinforcement learning implementations for the FJSSP make use of graph neural networks, which are limited to local message passing and therefore underperform compared to the attention model (AM) on various COPs. Especially for the FJSSP with complex inter and intra node relationships, the self-attention mechanism of the AM could enhance feature representations. However, the AM is defined for problems with a single entity type, like customer nodes in the TSP, whereas machines and operations of the FJSSP pose different node types in a complex heterogeneous graph. Therefore, this work proposes an extension of the AM, integrating self- and cross-attention blocks to allow for message passing between all nodes and thus to capture inter and intra node relationships. Further, we present a factorized action-space formulation for the FJSSP, which – other than the composite action-space used in current implementations – does not grow quadratically. Consequently, a better sampling efficiency and scalability of our approach is to be expected.

Keywords

Status: accepted

Back to the list of papers