A Learning-Based Superposition Operator for Non-Renewal Arrival Processes in Queueing Networks

Dieses Paper stellt einen skalierbaren, datengesteuerten Superpositionsoperator vor, der mithilfe von Deep Learning auf synthetischen Markov-Ankunftsprozessen trainiert wird, um die statistischen Eigenschaften nicht-erneuernder Ankunftsströme in Warteschlangennetzwerken präzise zu approximieren und dabei klassische Methoden in Bezug auf Genauigkeit und Berücksichtigung höherer Abhängigkeitsstrukturen übertrifft.

Das Wesentliche

Hier ist eine einfache, bildhafte Erklärung der Forschung, als würde man sie einem Freund beim Kaffee erzählen:

Das Problem: Der chaotische Verkehrsfluss

Stellen Sie sich vor, Sie sind der Verkehrsleiter an einer großen Kreuzung. Normalerweise kommen Autos in einem gleichmäßigen Takt (wie ein Metronom). Das ist einfach zu berechnen.

Aber in der echten Welt passiert etwas anderes:

1. Verschmelzung: Aus zwei verschiedenen Straßen kommen Autos zusammen und bilden eine einzige Spur.
2. Unvorhersehbarkeit: Manchmal kommen Autos in kleinen Gruppen (Stau), manchmal ganz allein, und manchmal in riesigen Wellen. Sie haben keine feste Uhrzeit.
3. Der "Geister-Effekt": Wenn ein Auto langsam kommt, folgt ihm oft ein schnelles, oder umgekehrt. Diese Muster sind schwer zu fassen.

In der Mathematik (genauer gesagt in der Warteschlangentheorie) ist das Zusammenführen dieser chaotischen Ströme ein Albtraum. Die alten Methoden waren wie ein grobes Sieb: Sie haben die feinen Details (die "Wellen" und "Gruppen") herausgefiltert und nur gesagt: "Im Durchschnitt kommen hier 10 Autos pro Minute." Das reicht aber nicht, um zu wissen, ob es bald einen riesigen Stau gibt oder nicht.

Andere Methoden waren wie ein riesiger, schwerer Supercomputer, der jeden einzelnen Fahrer simuliert – extrem genau, aber so langsam, dass man nie fertig wird.

Die Lösung: Ein "Lernender Übersetzer"

Der Autor, Eliran Sherzer, hat eine clevere Idee entwickelt: Ein neuronales Netzwerk (eine Art KI), das als "Übersetzer" fungiert.

Stellen Sie sich dieses KI-Modell wie einen erfahrenen Koch vor, der tausende von Rezepten probiert hat:

1. Das Training (Die Küche): Der Koch hat nicht mit echten Autos gearbeitet, sondern mit perfekten, simulierten Daten (den "MAPs"). Er hat gesehen, was passiert, wenn er zwei verschiedene Arten von Verkehrsströmen (z. B. einen ruhigen Fluss und einen stürmischen Fluss) zusammenmischt. Er hat gelernt: "Wenn ich Strom A (mit diesen Eigenschaften) und Strom B (mit jenen Eigenschaften) mische, sieht das Ergebnis so aus."
2. Die Eingabe (Die Zutaten): Statt den ganzen Verkehr zu simulieren, gibt man dem Koch nur die wichtigsten Kennzahlen:
   • Wie schnell kommen die Autos im Durchschnitt?
   • Wie unregelmäßig ist der Takt? (Ist es chaotisch oder gleichmäßig?)
   • Gibt es Muster? (Kommt nach einem langen Warten oft ein schnelles Auto?)
3. Die Ausgabe (Das Gericht): Der Koch sagt Ihnen sofort: "Wenn Sie diese beiden Ströme mischen, wird das Ergebnis so aussehen: Hier ist die neue Geschwindigkeit, hier ist das neue Chaos-Muster und hier sind die neuen Wellen."

Warum ist das genial?

• Es ist schnell: Der Koch braucht keine Stunden. Er braucht Millisekunden. Sie können Tausende von Szenarien gleichzeitig berechnen.
• Es ist präzise: Im Gegensatz zu den alten Methoden, die nur den "Durchschnitt" sehen, merkt sich dieser Koch auch die kleinen Details. Er weiß, dass wenn Autos in Gruppen kommen, die Warteschlange viel länger wird, als man es auf den ersten Blick denken würde.
• Es ist modular: Das ist wie ein Baukasten.
  • Modul 1: Mischt die Ströme (unser neuer Koch).
  • Modul 2: Berechnet, wie die Autos die Kreuzung wieder verlassen.
  • Modul 3: Sagt vorher, wie viele Autos im Stau stehen.
  • Zusammen können sie ein ganzes Netzwerk von Kreuzungen berechnen, ohne den Computer zum Absturz zu bringen.

Das Ergebnis im Test

Der Autor hat sein System gegen die alten Methoden getestet.

• Die alten Methoden lagen oft daneben, besonders wenn der Verkehr sehr chaotisch war oder wenn Autos in Gruppen kamen. Ihre Fehler lagen oft bei 30% bis 3000% (ja, wirklich!).
• Die neue KI-Methode lag fast immer bei weniger als 3% Fehler. Sie hat die komplexen Muster der "Autogruppen" perfekt verstanden.

Zusammenfassung in einem Satz

Statt zu versuchen, den gesamten chaotischen Verkehr mit komplizierten Formeln zu berechnen, hat der Autor eine KI trainiert, die aus ein paar einfachen Kennzahlen lernt, wie sich zwei Verkehrsströme verhalten, wenn sie zusammenfließen – und das tut sie schneller und genauer als jede alte Methode.

Die Metapher:
Statt jeden einzelnen Regentropfen zu zählen, um vorherzusagen, wie viel Wasser in der Pfütze ist, hat die KI gelernt, aus der Art des Regens (leichter Nieselregen vs. heftiger Wolkenbruch) und dem Wind sofort zu sagen: "Hier wird es eine große Pfütze geben." Und das, ohne jemals einen Tropfen gemessen zu haben.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „A Learning-Based Superposition Operator for Non-Renewal Arrival Processes in Queueing Networks" von Eliran Sherzer auf Deutsch.

1. Problemstellung

Die Überlagerung (Superposition) von Ankunftsprozessen ist ein fundamentaler Vorgang in Warteschlangennetzwerken, bei dem mehrere unabhängige Verkehrsströme an einem Knoten (z. B. einem Server oder einer Kommunikationsleitung) zusammenlaufen.

• Analytische Unlösbarkeit: Während die Überlagerung von Poisson-Prozessen wieder einen Poisson-Prozess ergibt und Markovsche Ankunftsprozesse (MAPs) exakt durch Kronecker-Produkte dargestellt werden können, ist die Überlagerung allgemeiner nicht-erneuernder (non-renewal) Prozesse analytisch nicht lösbar. Das Ergebnis ist weder erneuernd noch Markovsch.
• Informationsverlust: Klassische Näherungsmethoden (z. B. von Whitt oder Albin) reduzieren die komplexen ankommenden Ströme oft auf einfache Deskriptoren wie die mittlere Ankunftsrate und den quadratischen Variationskoeffizienten (SCV). Dies vernachlässigt höherordentliche Momente und zeitliche Abhängigkeiten (Autokorrelation), die jedoch für die genaue Vorhersage von Warteschlangenlängen, Wartezeiten und Stabilität in stark ausgelasteten Systemen entscheidend sind.
• Skalierbarkeitsproblem: Exakte Methoden basierend auf MAPs führen zu einer exponentiellen Explosion des Zustandsraums, sobald mehrere Ströme überlagert werden, was sie für große Netzwerke unbrauchbar macht.

Das Ziel der Arbeit ist es, eine skalierbare Methode zu entwickeln, die die Überlagerung nicht-erneuernder Ströme approximiert, dabei aber höherordentliche Variabilitäts- und Abhängigkeitsinformationen erhält, um eine genaue Verteilungsanalyse von Warteschlangennetzwerken zu ermöglichen.

2. Methodik

Der Autor schlägt einen datengetriebenen Ansatz vor, der auf einem tiefen neuronalen Netzwerk (Deep Learning) basiert.

• Das neuronale Überlagerungs-Operator (NN 1):

  • Eingabe: Statistische Deskriptoren der einzelnen Eingangsströme, bestehend aus den ersten $n$ Momenten der Zwischenankunftszeiten und Autokorrelationskoeffizienten für kurze Verzögerungen (Lags).
  • Ausgabe: Die entsprechenden Deskriptoren (die ersten 5 Momente und Autokorrelationsstrukturen) des überlagerten Gesamtprozesses.
  • Architektur: Ein vollvernetztes Feed-Forward-Neuronales Netzwerk (ANN). CNNs oder RNNs wurden nicht verwendet, da die Eingaben statische statistische Deskriptoren und keine räumlichen oder sequenziellen Zeitreihen sind.

• Datengenerierung und Training:

  • Da keine analytische Lösung für die Überlagerung allgemeiner Prozesse existiert, werden Markovsche Ankunftsprozesse (MAPs) als flexible Datenquelle genutzt. MAPs können eine breite Klasse von stationären Punktprozessen approximieren.
  • Es werden große Mengen an MAP-Paaren synthetisch generiert, die verschiedene Variabilitätsbereiche (SCV, Schiefe, Kurtosis) und Abhängigkeitsstrukturen (positive und negative Autokorrelation) abdecken.
  • Labeling (Ground Truth): Für jedes Paar von MAPs wird die exakte Überlagerung mittels der klassischen Kronecker-Summen-Methode berechnet. Daraus werden die exakten Momente und Autokorrelationen des überlagerten Prozesses extrahiert.
  • Verlustfunktion: Das Netzwerk wird trainiert, um den Fehler zwischen den vorhergesagten und den exakten Deskriptoren zu minimieren. Die Verlustfunktion kombiniert den mittleren quadratischen Fehler (MSE) für die logarithmierten Momente und die Autokorrelationen.

• Integration in Warteschlangennetzwerke:

  • Der Überlagerungsoperator ist Teil eines größeren Frameworks, das auch Module für die Approximation von Abgangsprozessen und stationären Verteilungen umfasst (basierend auf Sherzer, 2025).
  • Dies ermöglicht eine rekursive Zerlegung (Decomposition) von Feed-Forward-Netzwerken mit Überlagerungen, ohne den gesamten Zustandsraum des Netzwerks explizit zu konstruieren.

3. Wichtige Beiträge

1. Neuraler Überlagerungsoperator: Einführung eines neuronalen Netzwerks, das die Überlagerung nicht-erneuernder Ströme direkt auf Basis statistischer Deskriptoren abbildet, ohne parametrische Anpassung oder Zustandsraumexplosion.
2. Erhaltung höherordenter Informationen: Im Gegensatz zu klassischen Methoden erhält der Operator die ersten fünf Momente und die Kurzzeit-Abhängigkeitsstruktur, was für eine genaue Verteilungsanalyse notwendig ist.
3. Skalierbarkeit und Effizienz: Die Methode umgeht die kombinatorische Explosion der MAP-Methode. Die Inferenz ist nahezu instantan und parallelisierbar.
4. Open-Source-Implementierung: Der Code ist verfügbar, was Reproduzierbarkeit und Weiterentwicklung ermöglicht.
5. Erweiterung des Lösbarkeitsbereichs: Die Methode ermöglicht erstmals die approximative Analyse von stationären Verteilungen in allgemeinen nicht-Markovschen Feed-Forward-Netzwerken mit Überlagerungen, die zuvor analytisch als unzugänglich galten.

4. Ergebnisse

Die Studie wurde durch umfangreiche numerische Experimente validiert:

• Genauigkeit der Deskriptoren:

  • Das Netzwerk erreicht eine hohe Genauigkeit bei der Vorhersage der ersten 5 Momente und der Autokorrelationen über heterogene Szenarien hinweg.
  • Der mittlere absolute prozentuale Fehler (MAPE) für Momente liegt meist unter 3,5 %, selbst bei hoher Variabilität (SCV > 3) und starker Korrelation.
  • Klassische Methoden (Whitt, Albin) zeigen Fehler von oft 30 % bis über 3000 % in ähnlichen Szenarien.
  • Die Autokorrelationsvorhersagen haben einen sehr niedrigen mittleren absoluten Fehler (MAE), typischerweise im Bereich von 0,002 bis 0,032.

• Anwendung in Warteschlangennetzwerken (System 1 & 2):

  • In einem Zwei-Strömungs-System und einem komplexeren Drei-Stationen-Netzwerk wurde die Genauigkeit der vorhergesagten stationären Verteilung der Kundenanzahl getestet.
  • Die Methode (NN-Decomposition) erzielte im Durchschnitt eine relative Fehlerquote (REM) von ca. 2,86 % (System 1) bzw. 4,18 % (System 2).
  • Im Vergleich dazu lag der Fehler der klassischen Whitt-Näherung bei ca. 9,20 % bzw. 10,73 %.
  • Die Verbesserung ist besonders ausgeprägt in Szenarien mit hoher Variabilität und positiver Abhängigkeit, wo klassische Methoden systematisch die Staus unterschätzen.

• Rechenzeit:

  • Die Inferenzzeit ist extrem gering. Für 5.000 Instanzen benötigte das Netzwerk nur 0,004 Sekunden.
  • Selbst für komplexe Netzwerkanalysen mit mehreren Schritten lag die Gesamtlaufzeit im Bereich von Millisekunden bis Sekunden.

5. Bedeutung und Fazit

Diese Arbeit stellt einen Paradigmenwechsel in der Analyse nicht-Markovscher Warteschlangennetzwerke dar.

• Überwindung von Limitierungen: Sie löst das Dilemma zwischen analytischer Unlösbarkeit und rechnerischer Unmöglichkeit (durch MAPs).
• Praktische Relevanz: Die Methode ermöglicht schnelle, genaue Leistungsanalysen für komplexe Netzwerke in Echtzeit oder für Design-Explorationen, ohne auf vereinfachende Annahmen (wie Erneuerungsprozesse) zurückgreifen zu müssen.
• Zukunftsperspektive: Der Ansatz legt den Grundstein für die Analyse noch komplexerer Netzwerke, einschließlich solcher mit Rückkopplungsschleifen (Feedback), und kann in Optimierungs- und Steuerungsprozesse integriert werden.

Zusammenfassend bietet das vorgestellte Framework eine skalierbare, datengetriebene Alternative zu traditionellen analytischen Ansätzen, die sowohl die Rechenleistung als auch die statistische Genauigkeit für moderne, komplexe Warteschlangensysteme sicherstellt.