Independent colorful vertex sets in large dynamic vertex colored conflict graphs

Abstract

Time-Sensitive Networks are a substantial part of the Industrial Internet of Things. Extensive computation is required to generate sufficient schedules, in order to allow for real-time communication within them. This is due to a time-constraint that each communication has. These communications can vary from various logistical operations to heavy machinery. As such, not meeting these time-constraints can incur financial costs, or even human harm. Most existing solutions for this problem are ill-suited for the dynamic scenario which often appears in real-life. Modern factories are rarely static, since changes to devices, and therefore their communications, occur as new ones are added, or old ones are modified. We built upon a previous approach, using a vertex colored conflict graph model and searching for an independent colorful set, to solve the time-triggered flow scheduling problem. Specifically, we introduce two new algorithms that dynamically generate an independent colorful set, and do so in a fraction of the time. We compare our algorithms to the original one, concluding that a combined approach might lead to the best outcome in terms of runtime and resulting scheduling quality.

Time-Sensitive Networks sind ein wesentlicher Bestandteil des Industrial Internet of Things. Umfangreiche Berechnungen sind erforderlich, um Zeitpläne zu generieren, die eine Kommunikation darin ermöglichen. Dies liegt daran, dass jede Kommunikation eine Zeitbeschränkung hat. Diese Kommunikation kann von verschiedenen logistischen Operationen bis hin zu Schwermaschinen variieren. Daher kann die Nichteinhaltung dieser Zeitbeschränkungen zu finanziellen Kosten oder sogar zu Personenschäden führen. Die meisten bestehenden Lösungen für dieses Problem sind für das dynamische Szenario, das in der Realität üblich ist, schlecht geeignet. Moderne Fabriken sind selten statisch, da sich die Geräte, die miteinander kommunizieren müssen, ändern, wenn neue hinzugefügt oder alte modifiziert werden. Wir haben auf einem existierenden Ansatz aufgebaut, der ein gefärbtes Konfliktdiagrammmodell verwendet und nach einem unabhängigen farbigen Menge gesucht haben, um das zeitgesteuerte Flussplanungsproblem zu lösen. Insbesondere führen wir zwei neue Algorithmen ein, die dynamisch ein unabhängiges buntes Set erzeugen, und zwar in einem Bruchteil der Zeit. Wir vergleichen unsere Algorithmen mit dem Original und kommen zu dem Schluss, dass ein kombinierter Ansatz zu den besten Ergebnissen in Bezug auf Laufzeit und resultierende Scheduling-Qualität führen könnte.