Systems Using Graph Attention Networks in Solving Job Shop Scheduling Problems
Valtonen, Lari (2024)
2024
Tietotekniikan DI-ohjelma - Master's Programme in Information Technology
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2024-12-17
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-2024120710837
https://urn.fi/URN:NBN:fi:tuni-2024120710837
Tiivistelmä
Several industrial settings are formulable as a well-known computationally intractable combinatorial optimization (CO) problem called the job shop scheduling problem (JSSP). The increasing interest in machine learning (ML) along with the development of more powerful hardware has piqued the curiosity to apply machine learning methods in solving combinatorial optimization problems.
The representability of JSSPs as disjunctive graphs allows the employment of graph neural networks (GNN) to perform representation learning techniques on the problems. Graph attention network (GAT) is a type of a GNN that uses an attention mechanism to calculate the importance of nodes.
This study conducts a semi-systematic literature review on systems using GATs to solve JSSP and its variants. The literature search was conducted on Scopus, IEEE, and arXiv databases. 14 studies were reviewed. The literature was analyzed for GAT utilization, different graph representations, and ML methods.
GAT was received as valuable in extracting rich feature information from disjunctive and heterogeneous graphs. In addition, various graph features for enhancing the graph representation were identified. While the parameters in GAT architecture were a factor in the system performance, other methods used in conjunction with GAT were found to have a more considerable impact. Deep reinforcement learning was applied in all systems to learn feasible solutions along with several algorithms and other techniques. Even with training on small problem instances, the systems were able to solve large scheduling problems. The scheduling problem formulations were simplistic and did not represent a real-world situation.
The representability of JSSPs as disjunctive graphs allows the employment of graph neural networks (GNN) to perform representation learning techniques on the problems. Graph attention network (GAT) is a type of a GNN that uses an attention mechanism to calculate the importance of nodes.
This study conducts a semi-systematic literature review on systems using GATs to solve JSSP and its variants. The literature search was conducted on Scopus, IEEE, and arXiv databases. 14 studies were reviewed. The literature was analyzed for GAT utilization, different graph representations, and ML methods.
GAT was received as valuable in extracting rich feature information from disjunctive and heterogeneous graphs. In addition, various graph features for enhancing the graph representation were identified. While the parameters in GAT architecture were a factor in the system performance, other methods used in conjunction with GAT were found to have a more considerable impact. Deep reinforcement learning was applied in all systems to learn feasible solutions along with several algorithms and other techniques. Even with training on small problem instances, the systems were able to solve large scheduling problems. The scheduling problem formulations were simplistic and did not represent a real-world situation.