Learning topological representations with bidirectional graph attention network for solving job shop scheduling problem

Existing learning-based methods for solving job shop scheduling problems (JSSP) usually use off-the-shelf GNN models tailored to undirected graphs and neglect the rich and meaningful topological structures of disjunctive graphs (DGs). This paper proposes the topology-aware bidirectional graph attent...

Full description

Saved in:
Bibliographic Details
Main Authors: ZHANG, Cong, CAO, Zhiguang, WU, Yaoxin, SONG, Wen, SUN, Jing
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2024
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/9331
https://ink.library.smu.edu.sg/context/sis_research/article/10331/viewcontent/3_Learning_Topological_Represe.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-10331
record_format dspace
spelling sg-smu-ink.sis_research-103312024-09-26T07:37:11Z Learning topological representations with bidirectional graph attention network for solving job shop scheduling problem ZHANG, Cong CAO, Zhiguang WU, Yaoxin SONG, Wen SUN, Jing Existing learning-based methods for solving job shop scheduling problems (JSSP) usually use off-the-shelf GNN models tailored to undirected graphs and neglect the rich and meaningful topological structures of disjunctive graphs (DGs). This paper proposes the topology-aware bidirectional graph attention network (TBGAT), a novel GNN architecture based on the attention mechanism, to embed the DG for solving JSSP in a local search framework. Specifically, TBGAT embeds the DG from a forward and a backward view, respectively, where the messages are propagated by following the different topologies of the views and aggregated via graph attention. Then, we propose a novel operator based on the message-passing mechanism to calculate the forward and backward topological sorts of the DG, which are the features for characterizing the topological structures and exploited by our model. In addition, we theoretically and experimentally show that TBGAT has linear computational complexity to the number of jobs and machines, respectively, strengthening our method's practical value. Besides, extensive experiments on five synthetic datasets and seven classic benchmarks show that TBGAT achieves new SOTA results by outperforming a wide range of neural methods by a large margin. All the code and data are publicly available online at https://github.com/zcaicaros/TBGAT. 2024-07-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/9331 https://ink.library.smu.edu.sg/context/sis_research/article/10331/viewcontent/3_Learning_Topological_Represe.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Data-driven optimization deep reinforcement learning job shop scheduling graph neural network neural heuristics Artificial Intelligence and Robotics Graphics and Human Computer Interfaces
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Data-driven optimization
deep reinforcement learning
job shop scheduling
graph neural network
neural heuristics
Artificial Intelligence and Robotics
Graphics and Human Computer Interfaces
spellingShingle Data-driven optimization
deep reinforcement learning
job shop scheduling
graph neural network
neural heuristics
Artificial Intelligence and Robotics
Graphics and Human Computer Interfaces
ZHANG, Cong
CAO, Zhiguang
WU, Yaoxin
SONG, Wen
SUN, Jing
Learning topological representations with bidirectional graph attention network for solving job shop scheduling problem
description Existing learning-based methods for solving job shop scheduling problems (JSSP) usually use off-the-shelf GNN models tailored to undirected graphs and neglect the rich and meaningful topological structures of disjunctive graphs (DGs). This paper proposes the topology-aware bidirectional graph attention network (TBGAT), a novel GNN architecture based on the attention mechanism, to embed the DG for solving JSSP in a local search framework. Specifically, TBGAT embeds the DG from a forward and a backward view, respectively, where the messages are propagated by following the different topologies of the views and aggregated via graph attention. Then, we propose a novel operator based on the message-passing mechanism to calculate the forward and backward topological sorts of the DG, which are the features for characterizing the topological structures and exploited by our model. In addition, we theoretically and experimentally show that TBGAT has linear computational complexity to the number of jobs and machines, respectively, strengthening our method's practical value. Besides, extensive experiments on five synthetic datasets and seven classic benchmarks show that TBGAT achieves new SOTA results by outperforming a wide range of neural methods by a large margin. All the code and data are publicly available online at https://github.com/zcaicaros/TBGAT.
format text
author ZHANG, Cong
CAO, Zhiguang
WU, Yaoxin
SONG, Wen
SUN, Jing
author_facet ZHANG, Cong
CAO, Zhiguang
WU, Yaoxin
SONG, Wen
SUN, Jing
author_sort ZHANG, Cong
title Learning topological representations with bidirectional graph attention network for solving job shop scheduling problem
title_short Learning topological representations with bidirectional graph attention network for solving job shop scheduling problem
title_full Learning topological representations with bidirectional graph attention network for solving job shop scheduling problem
title_fullStr Learning topological representations with bidirectional graph attention network for solving job shop scheduling problem
title_full_unstemmed Learning topological representations with bidirectional graph attention network for solving job shop scheduling problem
title_sort learning topological representations with bidirectional graph attention network for solving job shop scheduling problem
publisher Institutional Knowledge at Singapore Management University
publishDate 2024
url https://ink.library.smu.edu.sg/sis_research/9331
https://ink.library.smu.edu.sg/context/sis_research/article/10331/viewcontent/3_Learning_Topological_Represe.pdf
_version_ 1814047911774781440