Academic Journal
Learning Precedences for Scheduling Problems with Graph Neural Networks
| العنوان: | Learning Precedences for Scheduling Problems with Graph Neural Networks |
|---|---|
| المؤلفون: | Verhaeghe, Hélène, Cappart, Quentin, Pesant, Gilles, Quimper, Claude-Guy |
| المساهمون: | Hélène Verhaeghe and Quentin Cappart and Gilles Pesant and Claude-Guy Quimper |
| بيانات النشر: | Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| سنة النشر: | 2024 |
| المجموعة: | DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics ) |
| مصطلحات موضوعية: | Scheduling, Precedence graph, Graph neural network |
| الوصف: | The resource constrained project scheduling problem (RCPSP) consists of scheduling a finite set of resource-consuming tasks within a temporal horizon subject to resource capacities and precedence relations between pairs of tasks. It is NP-hard and many techniques have been introduced to improve the efficiency of CP solvers to solve it. The problem is naturally represented as a directed graph, commonly referred to as the precedence graph, by linking pairs of tasks subject to a precedence. In this paper, we propose to leverage the ability of graph neural networks to extract knowledge from precedence graphs. This is carried out by learning new precedences that can be used either to add new constraints or to design a dedicated variable-selection heuristic. Experiments carried out on RCPSP instances from PSPLIB show the potential of learning to predict precedences and how they can help speed up the search for solutions by a CP solver. |
| نوع الوثيقة: | article in journal/newspaper conference object |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | Is Part Of LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.30 |
| DOI: | 10.4230/LIPIcs.CP.2024.30 |
| الاتاحة: | https://doi.org/10.4230/LIPIcs.CP.2024.30 https://nbn-resolving.org/urn:nbn:de:0030-drops-207150 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.30 |
| Rights: | https://creativecommons.org/licenses/by/4.0/legalcode |
| رقم الانضمام: | edsbas.759C6537 |
| قاعدة البيانات: | BASE |
| DOI: | 10.4230/LIPIcs.CP.2024.30 |
|---|