🔢 mathematics

Polling on a circle with non-uniform batch arrivals

Diese Arbeit analysiert ein Polling-System auf einem Kreis mit nicht-uniformen Batch-Ankünften, leitet die Laplace-Stieltjes-Transformierte der Batch-Verzögerung für eine global gesteuerte Policy ab, schlägt einen Mittelwertanalyse-Algorithmus für eine erschöpfende Policy vor und stellt zudem exakte Light- und Heavy-Traffic-Grenzwerte für die Systemleistung her.

Ursprüngliche Autoren: Tim Engels, Ivo Adan, Onno Boxma, Jacques Resing

Veröffentlicht 2026-10-07

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Tim Engels, Ivo Adan, Onno Boxma, Jacques Resing

Originalarbeit lizenziert unter CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

In der Welt der Logistik und Warteschlangentheorie untersuchen Forscher, wie einzelne Server, wie etwa ein Busfahrer oder ein Computerprozessor, mehrere Warteschlangen von wartenden Kunden verwalten. Ein klassisches Modell hierfür ist das Polling-System, bei dem sich ein Server im Kreis bewegt, an verschiedenen Punkten anhält, um wartende Artikel abzuarbeiten, bevor er zum nächsten Punkt weiterzieht. Seit Jahrzehnten analysieren Wissenschaftler diese Systeme unter der Annahme, dass Kunden mit gleicher Wahrscheinlichkeit an zufälligen Stellen entlang des Kreises eintreffen, ähnlich wie Regentropfen, die gleichmäßig auf ein Trommelfell fallen. Reale Systeme verhalten sich jedoch selten so perfekt zufällig. In Lagern beispielsweise werden beliebte Artikel oft in spezifischen, vorhersehbaren Zonen gelagert, um das Kommissionieren zu beschleunigen, während weniger beliebte Artikel an anderer Stelle verstaut werden. Dies erzeugt ein nicht-uniformes Muster, bei dem einige Bereiche des Kreises viel geschäftiger sind als andere. Zu verstehen, wie ein Server arbeitet, wenn die Nachfrage in spezifischen Standorten konzentriert ist, anstatt gleichmäßig verteilt zu sein, ist entscheidend für das Design effizienter Systeme, die alles von automatisierten Lagerkommissionierern bis hin zu Datennetzwerken handhaben.

Ein Forschungsteam der Eindhoven University of Technology hat diese Komplexität angegangen, indem sie ein kontinuierliches Polling-System analysierten, bei dem Chargen von Kunden zu zufälligen Zeiten eintreffen, ihre Standorte jedoch einer spezifischen, nicht-uniformen Verteilung folgen. Sie konzentrierten sich auf zwei unterschiedliche Arten, wie ein Server operieren kann: die „globale Gated“-Strategie (globale Gate-Politik) und die „Exhaustive“-Strategie (erschöpfende Politik). Unter dem globalen Gate-Ansatz macht der Server eine Momentaufnahme aller wartenden Kunden, sobald er eine neue Runde beginnt, und bedient nur diejenigen, die bereits da waren, während er jeden ignoriert, der während seiner Arbeit eintrifft. Im Gegensatz dazu ist die Exhaustive-Strategie dynamischer; der Server bedient jeden Kunden, den er antrifft, so lange, bis der gesamte Kreis leer von wartenden Artikeln ist, selbst wenn währenddessen neue Kunden eintreffen. Die Forscher waren besonders an zwei Leistungsmaßen interessiert: der Zeit, die benötigt wird, um eine spezifische Gruppe von Kunden zu bedienen (die Batch-Sojourn-Zeit), und der Gesamtzeit, bis diese gesamte Gruppe zum Ausgangspunkt zurückgeliefert wurde (die Lieferzeit).

Unter Verwendung fortgeschrittener mathematischer Techniken leitete das Team exakte Formeln für die globale Gated-Strategie ab und berechnete die präzise Verteilung der Wartezeiten, unabhängig davon, wie die Kunden über die Fläche verteilt waren. Für die komplexere Exhaustive-Strategie entwickelten sie eine neue Methode zur Berechnung der durchschnittlichen Wartezeiten, indem sie darlegten, wie sich Kunden relativ zur Position des Servers über den Kreis verteilen. Ihre Analyse ergab ein überraschendes und kontraintuitives Ergebnis: Das spezifische Muster, wo Kunden eintreffen, hat sehr wenig Einfluss auf die durchschnittliche Gesamtleistung des Systems. Ob die Kunden eng gestaffelt nahe dem Start der Route, gleichmäßig verteilt oder am fernen Ende konzentriert sind – die durchschnittliche Zeit für die Bedienung und Lieferung einer Charge bleibt bemerkenswert stabil. Dieser Befund legt nahe, dass Manager für viele praktische Anwendungen, wie etwa die in modernen Lagern verwendeten „Milkrun“-Kommissioniersysteme, die Lagerorte nicht perfekt optimieren müssen, um eine hohe Effizienz zu erreichen.

Die Studie verglich auch die beiden Service-Strategien unter verschiedenen Verkehrsbedingungen. Wenn das System schwach ausgelastet ist, also nur wenige Bestellungen eintreffen, schneidet die Exhaustive-Strategie im Allgemeinen besser ab, da der Server keine Zeit verschwendet, um zum Startpunkt zurückzugehen und seine Liste zurückzusetzen, bevor er neue Artikel aufnimmt. Wenn das System jedoch stark ausgelastet ist, also viele Bestellungen eingehen, kann die globale Gated-Strategie manchmal effizienter sein, insbesondere wenn die Zeit, die für das Umrunden des Lagers benötigt wird, lang im Vergleich zur Zeit ist, die für das Kommissionieren eines Artikels benötigt wird. Die Forscher bestätigten diese theoretischen Vorhersagen durch numerische Simulationen und zeigten, dass die Wahl der Lagerstrategie zwar in sehr spezifischen Szenaden mit geringem Verkehrsaufkommen eine Rolle spielt, der Unterschied jedoch in den meisten realen Situationen vernachlässigbar ist. Letztlich bietet die Arbeit ein robustes mathematisches Fundament für das Verständnis kontinuierlicher Polling-Systeme und zeigt auf, dass die Stabilität und Effizienz des Systems weitaient mehr gegenüber Änderungen der Kundenstandortmuster resistent sind, als bisher angenommen wurde.

Technische Zusammenfassung: Polling auf einem Kreis mit nicht-uniformen Batch-Ankünften

Problemdefinition
Diese Arbeit analysiert ein kontinuierliches Polling-System auf einem Kreis mit dem Umfang 1, bei dem ein einzelner Server zyklisch mit einer festen Geschwindigkeit fährt, um Kunden zu bedienen. Das System ist durch zwei primäre Merkmale gekennzeichnet:

Batch-Ankünfte: Kunden kommen in Batches (Chargen) gemäß einem Poisson-Prozess an. Die Batch-Größen sind identisch und unabhängig verteilt (i.i.d.).
Nicht-uniforme Ankunftslokationen: Im Gegensatz zu früheren kontinuierlichen Polling-Modellen, die von uniformen Ankunftslokationen ausgehen, setzt diese Arbeit voraus, dass jeder Kunde innerhalb eines Batches gemäß einer allgemeinen, bekannten kontinuierlichen Verteilung $\pi(x)$ einem Ort auf dem Kreis zugewiesen wird. Dies modelliert reale Szenarien wie das Milkrun-Order-Picking in der Lagerlogistik, bei denen Lagerrichtlinien die Position der Artikel bestimmen.

Die Studie konzentriert sich auf zwei Leistungsmetriken für einen Batch:

Batch-Verweilzeit ( $S_B$ ): Die Zeit vom Eintreffen eines Batches bis zum Abschluss der Bedienung des letzten Kunden in diesem Batch.
Zeit bis zur Auslieferung ( $D$ ): Die Zeit vom Eintreffen eines Batches bis zur vollständigen Rücklieferung des gesamten Batches an das zentrale Depot.

Es werden zwei Bedienungsdisziplinen untersucht:

Global Gated (Global Gated): Der Server bedient nur Kunden, die zu Beginn des Zyklus präsent sind.
Exhaustive (Erschöpfend): Der Server bedient alle Kunden, denen er begegnet, bis die Warteschlange leer ist.

Methodik
Die Autoren verwenden aufgrund der durch nicht-uniforme Ankunftslokationen eingeführten Komplexität unterschiedliche analytische Ansätze für die beiden Bedienungsdisziplinen.

Globally Gated Policy: Die Analyse stützt sich auf die Ableitung der Laplace-Stieltjes-Transformierten (LST) der Zykluszeit. Durch die Modellierung der Zykluszeit als Funktionalgleichung, die den Ankunftsprozess und die Servicezeiten beinhaltet, leiten die Autoren die LST für die Zykluszeit als unendliches Produkt ab. Unter Verwendung der gemeinsamen Verteilung von Alter (Age) und Rest-Zykluszeit leiten sie exakte LSTs für die Zeit bis zur Auslieferung ( $D$ ) und die Batch-Verweilzeit ( $S_B$ ) ab. Die Ableitung für $S_B$ erfolgt durch Konditionierung auf den Ort des am weitesten entfernten Kunden in einem Batch relativ zum Depot.
Exhaustive Policy: Die Ableitung exakter LSTs für die Exhaustive-Policy mit nicht-uniformen Ankünften ist unpraktikabel. Stattdessen schlagen die Autoren eine Mean-Value Analysis (MVA) vor.
- Sie definieren $f(x, y)$ als die durchschnittliche Dichte wartender Kunden an Position $x$ , gegeben die Position des Servers bei $y$ .
- Unter Verwendung eines Verzweigungsprozess-Arguments mit Immigration und einer Variante des Little'schen Gesetzes beweisen sie, dass $f(x, y)$ eine spezifische Integralgleichung erfüllt.
- Sie zeigen, dass diese Integralgleichung eine eindeutige Lösung in einer spezifischen Funktionsklasse besitzt, die mittels sukzessiver Substitution gefunden werden kann.
- Die Autoren liefern partielle analytische Lösungen für die Integralgleichung (Trennung der Terme bezüglich Fahrzeit, Rest-Servicezeit und Batch-Größen-Effekten) und leiten exakte Ausdrücke für die mittlere Batch-Verweilzeit und die mittlere Zeit bis zur Auslieferung basierend auf der Lösung dieser Integralgleichung ab.
Grenzverhalten (Limiting Behavior): Die Arbeit leitet exakte Ausdrücke für die Systemleistung sowohl im leichten Verkehr ( $\lambda \downarrow 0$ ) als auch im schweren Verkehr ( $\rho \uparrow 1$ ) für beide Service-Policies ab.

Wesentliche Beiträge

Exakte Ausdrücke für die Globally Gated Policy: Die Arbeit leitet exakte LSTs und Mittelwerte für sowohl die Batch-Verweilzeit als auch die Zeit bis zur Auslieferung unter der Globally Gated-Disziplin her und berücksichtigt dabei allgemeine Ankunftslokationsverteilungen.
Integralgleichung für die Exhaustive Policy: Für die Exhaustive-Disziplin beweisen die Autoren, dass die durchschnittliche Streuung der Kunden eine Integralgleichung erfüllt. Sie liefern eine Methode (sukzessive Substitution), um diese Gleichung numerisch zu lösen, und leiten exakte Ausdrücke für die mittleren Leistungsmetriken ab, die von dieser Lösung abhängen.
Grenzverhalten im leichten und schweren Verkehr: Exakte Grenzwerte werden für beide Policies abgeleitet. Bemerkenswert ist, dass die Analyse im schweren Verkehr zeigt, dass der Einfluss der Ankunftslokationsverteilung $\pi(x)$ abnimmt, wenn das System die Sättigung erreicht, insbesondere bezüglich der Batch-Verweilzeit.
Anwendung auf Milkrun-Systeme: Die theoretischen Ergebnisse werden auf ein Milkrun-Order-Picking-System in der Lagerlogistik angewendet. Die Studie untersucht, wie verschiedene Lagerrichtlinien (z. B. zufällige vs. klassenbasierte Lagerung) die Systemleistung beeinflussen.

Ergebnisse

Einfluss der Lagerrichtlinie: Ein kontraintuitives Ergebnis ist, dass die Ankunftslokationsverteilung (Lagerrichtlinie) einen minimalen Effekt auf die durchschnittliche Systemleistung hat, insbesondere unter schwerem Verkehr oder bei der Exhaustive-Service-Policy. Während die erwartete Batch-Verweilzeit empfindlich auf die Fahrzeit zum am weitesten entfernten Kunden in einem Batch reagiert, sind die Leistungsunterschiede zwischen verschiedenen Lagerrichtlinien (z. B. Platzierung von Schnelldrehern am Anfang, in der Mitte oder am Ende der Route) in den meisten praktischen Szenarien vernachlässigbar.
Vergleich der Policies:
- Unter leichtem Verkehr wird die Exhaustive-Policy im Allgemeinen gegenüber der Globally Gated-Policy bevorzugt, da der Server nicht vor dem Depot warten muss, bevor er neue Ankünfte bedient, was die Leerlauf-Fahrzeit reduziert.
- Unter schwerem Verkehr hängt die Präferenz vom Verhältnis von Fahrzeit zu Servicezeit ab. Wenn die Fahrzeiten groß im Vergleich zu den Servicezeiten sind, bleibt die Exhaustive-Policy vorzuziehen. Wenn jedoch die Servicezeiten groß und die Batch-Größen signifikant sind, kann die Globally Gated-Policy besser abschneiden, da sie verhindert, dass der Server beim Bedienen neuer Ankünfte "stecken bleibt", während ein Batch noch bearbeitet wird.
Effekte der Batch-Größe: Bei der Globally Gated-Policy erhöht eine steigende Batch-Größe die erwartete Verweilzeit aufgrund der größeren erwarteten Distanz zum am weitesten entfernten Kunden. Für die Exhaustive-Policy ist der Effekt der Ankunftslokationsverteilung auf die Leistung bei kleinen Batch-Größen und leichtem Verkehr ausgeprägter, nimmt aber mit steigenden Batch-Größen und hoher Verkehrsbelastung ab.

Bedeutung und Ansprüche
Die Arbeit beansprucht, die bestehende Literatur zu kontinuierlichen Polling-Modellen zu erweitern, indem sie die Annahme von uniformen Ankunftslokationen aufhebt, was für reale Anwendungen wie die Lagerlogistik, in denen Lagerrichtlinien nicht-uniform sind, entscheidend ist. Die Autoren betonen, dass die mathematische Ableitung zwar deutlich komplexer wird (Übergang von eindimensionalen zu zweidimensionalen Repräsentationen), die resultierenden Leistungsmetriken jedoch überraschend robust gegenüber der spezifischen Wahl der Lagerrichtlinie sind.

Die Bedeutung liegt in der Bereitstellung eines rigorosen analytischen Rahmens für kontinuierliches Polling mit Batch-Ankünften und nicht-uniformen Lokationen, der exakte Lösungen für den Gated-Fall und einen robusten algorithmischen Ansatz für den Exhaustive-Fall bietet. Die Ergebnisse legen nahe, dass die Optimierung der Lagerrichtlinie (z. B. klassenbasierte Lagerung) im Vergleich zur Wahl der Service-Disziplin (Exhaustive vs. Gated) geringere Erträge liefert, insbesondere in Hochlastumgebungen. Die Arbeit schließt mit dem Hinweis, dass das aktuelle Modell unabhängige Ankunftslokationen innerhalb eines Batches annimmt und vorschlägt, dass zukünftige Arbeiten korrelierte Lokationen (z. B. zusammen gelagerte Artikel) und stochastische Gehzeiten untersuchen könnten.

Mehr davon