Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-34241
Titel: Cable tree wiring - benchmarking solvers on a real-world scheduling problem with a variety of precedence constraints
VerfasserIn: Koehler, Jana
Bürgler, Josef
Fontana, Urs
Fux, Etienne
Herzog, Florian
Pouly, Marc
Saller, Sophia
Salyaeva, Anastasia
Scheiblechner, Peter
Waelti, Kai
Sprache: Englisch
Titel: Constraints
Verlag/Plattform: Springer Nature
Erscheinungsjahr: 2021
Freie Schlagwörter: TSP with precedence constraints
Tour-dependent edge costs
Soft coupled task scheduling
Constraint optimization
Benchmarking CP-SAT
MIP
OMT solvers
DDC-Sachgruppe: 004 Informatik
Dokumenttyp: Journalartikel / Zeitschriftenartikel
Abstract: Cable trees are used in industrial products to transmit energy and information between different product parts. To this date, they are mostly assembled by humans and only few automated manufacturing solutions exist using complex robotic machines. For these machines, the wiring plan has to be translated into a wiring sequence of cable plugging operations to be followed by the machine. In this paper, we study and formalize the problem of deriving the optimal wiring sequence for a given layout of a cable tree. We summarize our investigations to model this cable tree wiring problem (CTW). as a traveling salesman problem with atomic, soft atomic, and disjunctive precedence constraints as well as tour-dependent edge costs such that it can be solved by state-of-the-art constraint programming (CP), Optimization Modulo Theories (OMT), and mixed-integer programming (MIP). solvers. It is further shown, how the CTW problem can be viewed as a soft version of the coupled tasks scheduling problem. We discuss various modeling variants for the problem, prove its NP-hardness, and empirically compare CP, OMT, and MIP solvers on a benchmark set of 278 instances. The complete benchmark set with all models and instance data is available on github and was included in the MiniZinc challenge 2020.
DOI der Erstveröffentlichung: 10.1007/s10601-021-09321-w
Link zu diesem Datensatz: urn:nbn:de:bsz:291--ds-342417
hdl:20.500.11880/31423
http://dx.doi.org/10.22028/D291-34241
ISSN: 1572-9354
1383-7133
Datum des Eintrags: 23-Jun-2021
Fakultät: MI - Fakultät für Mathematik und Informatik
Fachrichtung: MI - Informatik
Professur: MI - Prof. Dr. Jana Koehler
Sammlung:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Dateien zu diesem Datensatz:
Datei Beschreibung GrößeFormat 
Koehler2021_Article_CableTreeWiring-BenchmarkingSo.pdf1,69 MBAdobe PDFÖffnen/Anzeigen


Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons Creative Commons