Original title: Grafové neuronové sítě a hluboké posilované učení při rozvrhování prací
Translated title: Graph neural networks and deep reinforcement learning in job scheduling
Authors: Bratko, Maroš ; Holeňa, Martin (advisor) ; Seidelmann, Thomas (referee)
Document type: Master’s theses
Year: 2024
Language: eng
Abstract: [eng] [cze]
The priority dispatching rule (PDR) is a greedy heuristic algorithm used to obtain approximate solutions to the NP-hard job scheduling problem (JSP). The manual design of PDRs requires domain knowledge to achieve good results. Recently, deep reinforcement learning has been used to auto- mate the process of designing PDRs, where PDRs are formulated as a Markov Decision Process exploiting graph representation of JSP, and a graph neural network (GNN) selects the operations to be dispatched. In this thesis, we present the overview of five models published in literature with their source code publicly available on GitHub and experimentally compare their per- formance on three different variants of JSP. Our experiments show that the choice of input features, e.g., the amount of remaining work, significantly affects the model's performance regardless of the GNN architecture. This suggests that the feature selection is essential for learning high-quality PDRs. Prioritní rozhodovací pravidla (PDRs) jsou hladové heuristické algoritmy používané ke získaní přibližného řešení NP-těžkého úkolu organizace práce (JSP). Manuální příprava PDR vyžaduje zkušenosti v dané oblasti pro zís- kaní dobrých výsledků. V posledních letech bylo k automatizaci přípravy PDR využito zpětnovazební učení, kde jsou PDR formulováný jako Marko- vův rozhodovací proces využívajíci grafovou reprezentaci JSP, ve které gra- fová neurónová síť (GNN) vybírá operace ke spuštění. V této prácí uvádíme přehled pěti modelů publikovaných v literatuře, kterých zdrojové kódy jsou volně dostupné na GitHubu, a experimentálňe porovnáme jejich výsledky. Naše experimentuji ukazují, že volba vstupních příznaků, napr. množství zbývající práce, významně ovlivňuje kvalitu výsledných řešení bez ohledu na architekturu GNN. To naznačuje, že výběr vstupních příznaků je pro pří- pravu kvalitních PDR zásadní.
Keywords: job-shop scheduling|graph neural networks|deep reinforcement learning|markov decision process; organizace práce|grafové neuronové sítě|hluboké zpětnovazebné učení|Markovův rozhodovací proces

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/190558

Permalink: http://www.nusl.cz/ntk/nusl-621969


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses