elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Impressum | Datenschutz | Kontakt | English
Schriftgröße: [-] Text [+]

Periodic event scheduling for automated production systems

Helmberg, Christoph und Hofmann, Tobias und Wenzel, David (2021) Periodic event scheduling for automated production systems. INFORMS Journal on Computing, 34 (2), Seiten 1291-1304. Institute for Operations Research and the Management Sciences. doi: 10.1287/ijoc.2021.1101. ISSN 1091-9856.

[img] PDF - Nur DLR-intern zugänglich - Verlagsversion (veröffentlichte Fassung)
1MB

Offizielle URL: https://pubsonline.informs.org/doi/abs/10.1287/ijoc.2021.1101

Kurzfassung

Consider optimizing a periodic schedule for an automated production plant as a last step of a more comprehensive design process. In our scenario, each robot's cyclic sequence of operations and trajectories between potential waiting points have already been fully specified. Further given are those precedences that fix sequence requirements on operations between different robots. It remains to determine the starting time for each operation or movement of each robot within a common cyclic time period so as to avoid collisions of robots that operate in the same space simultaneously. So the task is to find a conflict-resolving schedule that minimizes this common periodic cycle time while observing all precedence relations and collision avoidance constraints. The proposed cycle time minimization problem for robot coordination has, to the best of our knowledge, not been studied before. We develop an approach for solving it by employing binary search for determining the smallest feasible period time of an iso-periodic event scheduling problem (IPESP). This is a variant of the periodic event scheduling problem in which the objects that have to be scheduled need to obey exactly the same period time. The possibility to wait arbitrarily long at waiting points turns out to be essential to justify the use of binary search for identifying the minimum cycle time, thereby avoiding bilinear mixed integer formulations. Special properties of the given scenario admit bounds on the periodic tension variables of an integer programming formulation. Although the IPESP subproblems remain NP-complete in general, these bounds allow solving real-world instances sufficiently fast for the approach to be applicable in practice. Numerical experiments on real-world and randomly generated data are supplied to illustrate the potential and limitations of this approach.

elib-URL des Eintrags:https://elib.dlr.de/190063/
Dokumentart:Zeitschriftenbeitrag
Titel:Periodic event scheduling for automated production systems
Autoren:
AutorenInstitution oder E-Mail-AdresseAutoren-ORCID-iDORCID Put Code
Helmberg, ChristophTU CHemnitzNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Hofmann, TobiasTU ChemnitzNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Wenzel, DavidDavid.Wenzel (at) dlr.deNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Datum:16 Dezember 2021
Erschienen in:INFORMS Journal on Computing
Referierte Publikation:Ja
Open Access:Nein
Gold Open Access:Nein
In SCOPUS:Ja
In ISI Web of Science:Ja
Band:34
DOI:10.1287/ijoc.2021.1101
Seitenbereich:Seiten 1291-1304
Verlag:Institute for Operations Research and the Management Sciences
ISSN:1091-9856
Status:veröffentlicht
Stichwörter:automated systems, network optimization, periodic event scheduling, mixed-integer programming
HGF - Forschungsbereich:Luftfahrt, Raumfahrt und Verkehr
HGF - Programm:Raumfahrt
HGF - Programmthema:Erdbeobachtung
DLR - Schwerpunkt:Raumfahrt
DLR - Forschungsgebiet:R EO - Erdbeobachtung
DLR - Teilgebiet (Projekt, Vorhaben):R - Solar-Terrestrische Physik SO
Standort: Neustrelitz
Institute & Einrichtungen:Institut für Solar-Terrestrische Physik > Weltraumwettereinfluß
Hinterlegt von: Wenzel, David
Hinterlegt am:05 Dez 2022 11:55
Letzte Änderung:05 Dez 2022 11:55

Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags

Blättern
Suchen
Hilfe & Kontakt
Informationen
electronic library verwendet EPrints 3.3.12
Gestaltung Webseite und Datenbank: Copyright © Deutsches Zentrum für Luft- und Raumfahrt (DLR). Alle Rechte vorbehalten.