Multi-Batch Sequencing with Decentralized Control using Highest-Density Conveyor Networks

Die Entwicklungen der letzten Jahre haben im industriellen Umfeld heutzutage eine nie dagewesene Komplexität, Dynamik und Unsicherheit erzeugt. Im Zuge anhaltender Globalisierung sind riesige, weltweit verteilte Netzwerke entstanden, die eine effiziente Gestaltung und Steuerung ihrer Informations- und Materialflüsse erfordern. Um langfristig am Markt zu bestehen, sind ausgefeilte automatisierte Systeme unerlässlich. Hier werden Steuerungsarchitekturen zunehmend dezentralisiert, indem die Intelligenz des Gesamtsystems auf mehrere, unabhängige funktionale Einheiten verteilt wird. ... mehrSelbst für große und komplexe Systeme gewährleistet dies Flexibilität, Skalierbarkeit, Robustheit und Echtzeitfähigkeit auch unter unsicheren und volatilen Einsatzbedingungen. Darüber hinaus erfordern abnehmende Lagerbestände und reduzierte Pufferkapazitäten eine Umgestaltung gegenwärtiger Materialflusskonzepte, da benötigte Güter gemäß der Verbrauchsreihenfolge an ihrem Bedarfsort verfügbar sein müssen. Deshalb verspricht ein automatisiertes, dezentral gesteuertes System zur sequenzgetreuen Materialbereitstellung eine Optimierung der Materialflüsse für diverse Anwendungen im Logistik- wie Produktionssektor.

Die vorliegende Dissertation stellt einen dezentralen Algorithmus vor, der die gleichzeitige Sequenzierung mehrerer Batch-Aufträge in höchst-dichten Stetigfördernetzwerken ermöglicht. Dabei werden materielle Objekte, die von einem vorgelagerten Prozess in zufälliger Reihenfolge am System ankommen, so umgeordnet, dass sie einem nachgelagerten Prozess in der dort benötigten Reihenfolge am gewünschten Bedarfsort zur Verfügung stehen. Der entwickelte Algorithmus bedient mehrere Eingangs- und Ausgangspunkte zur parallelen Auftragsbearbeitung. Lokale Entscheidungen auf Basis lokaler Datenhaltung führen durch die Interaktion autonomer Systemelemente zur Gesamtfunktionalität. Aufgrund des modularen, dezentralen Systemaufbaus sind eingesetzte Sequenziersysteme hochflexibel, robust und skalierbar, sodass sie für spezifische Anwendungsszenarien individuell zugeschnitten werden können.

Die Sequenzierung basiert auf einer dynamischen Pufferstrategie, bei der zwischengelagertes Material bei Bedarf verschoben wird, um Routen zeit- und entfernungseffizient durch das Netzwerk zu planen. Hierbei liegt das Konzept der logischen Zeit zugrunde, wodurch die Ausführung der geplanten Transporte dezentral koordiniert werden kann.

Der vorgestellte dezentrale Sequenzierungsalgorithmus schließt Deadlocks, Livelocks und Starvation sowohl innerhalb der algorithmischen Operationen als auch der Ressourcenallokation grundsätzlich aus, wodurch die Lebendigkeit des Systems zu jedem Zeitpunkt sichergestellt ist. Der erforderliche Kommunikationsaufwand skaliert mit der Systemgröße $n$. Auf Netzwerkebene liegt die algorithmische Komplexität damit in der Größenordnung $\mathcal{O} ( n^3 )$, was auf Ebene der dezentralen Systemelemente auf $\mathcal{O} ( n^2 )$ reduziert wird.

Die Qualität dezentral generierter Lösungen kann für kleine Probleminstanzen im Vergleich zu optimalen Ergebnissen bewertet werden. Daraus ergibt sich ein durchschnittliches Lösungsdefizit von weniger als 20 %. Gemessen an einer analytisch berechneten unteren Schranke zeigt der dezentrale Sequenzierungsalgorithmus außerdem eine konstante Lösungsqualität über Systemvariationen größerer Problemstellungen hinweg.

Mithilfe simulativer Leistungsanalysen werden Batchgröße, vorgegebene Vorgänger-Nachfolger Beziehungen, der Bedarf an Umordnung der Objekte innerhalb des Systems sowie die verfügbare Ausschleusekapazität des Netzwerks als wesentliche Einflussgrößen des erzielbaren Grenzdurchsatzes identifiziert. Außerdem erweisen sich kompakte, hochvernetzte Systeme und geradlinige Wege zwischen Ein- und Ausgängen als vorteilhaft.

Due to the developments in recent years, today's industrial environments have become highly complex, dynamic, and uncertain. These are integrated within huge, globally distributed networks where the flow of information and materials need to be organized efficiently. Sophisticated, automated systems are crucial to ensure long-term productivity. Their control architectures are increasingly decentralized by distributing the overall intelligence to several independent functional entities. Even for large-scale and complex systems, this guarantees flexibility, scalability, robustness, and real-time capability under uncertain and volatile conditions. ... mehrAdditionally, decreasing inventory levels and limited buffer space complicate current material flow control, as required items need to be supplied at their point of use in the order of consumption. Therefore, an automated system based on decentralized control enabling sequenced item supply is able to enhance various material handling applications within warehouse operations or production systems.

This dissertation presents a decentralized algorithm for multi-batch sequencing using highest-density conveyor networks. Physical objects randomly arriving from an upstream process are reorganized within the system to be provided to a downstream process observing the correct sequence at the required point of consumption. The developed algorithm handles multiple input and output points which allows parallel order processing. Local decisions based on local databases yield the overall system functionality using the interaction of autonomous entities. Due to the modular, decentralized system setup, installed sequencing systems are highly flexible, robust, and scalable such that they can be individually customized for specific application scenarios.

Sequencing is realized using a dynamic buffering approach where buffered physical objects can be relocated to plan efficient paths regarding time and distance within the network. These are scheduled based on the concept of logical time which enables decentralized transport coordination.

The presented decentralized sequencing algorithm ensures system liveliness at any point in time by generally preventing deadlocks, livelocks and starvation within algorithmic operations as well as resource allocation. The required communication effort scales with system size $n$. At network level, we obtain an algorithmic complexity of order $\mathcal{O} ( n^3 )$ which reduces to $\mathcal{O} ( n^2 )$ at level of the decentralized system elements.

We assess the quality of solutions provided by the decentralized sequencing algorithm compared to optimal results for small problem settings. This yields an average decentralized solution deficit of less than 20 %. Larger problem settings are benchmarked against a lower bound approximation where the algorithmic quality level is maintained throughout the system variations with larger problem sizes.

Simulative performance evaluations indicate that batch size, predefined predecessor-successor dependencies, the rearrangement effort of objects within the system as well as the available outflow capacity of a network are key factors influencing the achieved limiting throughput. Additionally, we recommend compact system setups with highly connected network structures and straight paths from input to output nodes.