Machine Learning-Based Waiting Time Prediction for Priority Queues with Preemptive and Non-Preemptive Service Rules
Diese Arbeit zeigt, dass Machine-Learning-Modelle, insbesondere rekurrenten neuronalen Netzen, Wartezeiten in komplexen, zeitvarianten Prioritätswarteschlangensystemen unter Verwendung von lediglich Warteschlangenlänge und Kundenpriorität präzise vorhersagen können und dabei baumbasierte Methoden bei nicht-präemptiven sowie verschiedenen präemptiven Bedienregeln übertreffen.
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
Stellen Sie sich vor, Sie stehen in einer belebten Schlange in einem Freizeitpark. Normalerweise gilt die Regel „Wer zuerst kommt, mahlt zuerst“. In dieser Arbeit untersuchen die Autoren jedoch eine komplexere Schlange, in der einige Personen VIPs (Priorität 1) sind und andere reguläre Gäste (Priorität 2). Die VIPs dürfen sich vordrängeln, was die Wartezeit für alle anderen verändert.
Die große Frage, die sich die Autoren gestellt haben, war: Können wir ein Computerprogramm (Maschinelles Lernen) verwenden, um genau vorherzusagen, wie lange eine Person warten wird, selbst wenn die Schlange chaotisch ist und VIPs ständig dazwischenspringen?
Hier ist eine einfache Aufschlüsselung dessen, was die Autoren gemacht haben und was sie herausgefunden haben, unter Verwendung alltäglicher Analogien.
Die drei Regeln der Schlange
Die Autoren testeten ihre Computerprogramme unter drei verschiedenen „Verkehrsregeln“ für den Ablauf der Schlange:
- Die „Keine Unterbrechung“-Regel (Nicht-präemptiv): Stellen Sie sich einen Barbier vor, der das Haar eines Kunden schneidet. Selbst wenn ein VIP eintrifft, beendet der Barbier den aktuellen Haarschnitt, bevor er wechselt. Die Person im Stuhl bleibt sitzen.
- Die „Von vorn beginnen“-Regel (Präemptiv-Wiederholung): Stellen Sie sich einen Koch vor, der ein Steak brät. Wenn ein VIP ankommt, hört der Koch auf, das Steak des regulären Kunden zu garen, wirft es weg und beginnt ein ganz neues Steak für den VIP. Wenn der VIP fertig ist, muss der reguläre Kunde mit seinem Steak wieder ganz von vorne anfangen.
- Die „Fortsetzen“-Regel (Präemptiv-Resümee): Stellen Sie sich einen Charakter in einem Videospiel vor, der gegen einen Boss kämpft. Wenn ein VIP auftaucht, wird der Kampf pausiert. Der „Lebensbalken“ des regulären Kunden bleibt exakt dort, wo er war. Wenn der VIP geht, wird der Kampf genau an der Stelle fortgesetzt, an der er gestoppt wurde.
Die Daten: Eine 200-Tage-Simulation
Da sie nicht 200 Tage lang in einer echten Schlange warten konnten, um dies zu testen, bauten sie eine digitale Simulation. Sie erschufen eine künstliche Welt, in der:
- Menschen zu zufälligen Zeiten ankommen (manchmal ist die Schlange leer, manchmal herrscht ein Ansturm).
- Es zwei Arten von Menschen gibt: VIPs und Reguläre.
- Sie ließen diese Simulation über 200 „Tage“ laufen, um eine riesige Menge an Daten darüber zu generieren, wer wie lange gewartet hat.
Der Wettbewerb: Fünf Computer-Gehirne
Sie ließen fünf verschiedene Arten von „Computer-Gehirnen“ (Modelle des Maschinellen Lernens) gegeneinander antreten, um zu sehen, welches die Wartezeit am besten vorhersagen kann.
- Die „Baum“-Gehirne (GBM & Random Forest): Betrachten Sie dies als ein Team von Detektiven, die eine Serie von „Ja/Nein“-Fragen stellen: „Ist die Schlange lang? Ist die Person ein VIP?“ Sie bauen einen Entscheidungsbaum auf, um die Wartezeit zu schätzen. Sie testeten auch eine Version, bei der sie die Detektive zwangen, sich in zwei separate Teams aufzuteilen (eines für VIPs, eines für Reguläre), um zu sehen, ob dies half.
- Das „Zeitreisende“ Gehirn (RNN): Dies ist ein Rekurrentes Neuronales Netz. Betrachten Sie dies als ein Gehirn, das sich an die Geschichte der Schlange erinnert. Es betrachtet nicht nur den gegenwärtigen Moment; es erinnert sich an die Abfolge der Menschen, die vor ihm angekommen sind. Es versteht, dass „ein VIP, der direkt nach einer langen Schlange aus Regulären eintrifft“, eine spezifische Kettenreaktion auslöst.
Die großen Erkenntnisse
1. Das „Zeitreisende“ Gehirn hat das Rennen gewonnen
Das RNN (dasjenige, das sich an die Abfolge der Ereignisse erinnert) war der klare Gewinner. Es war am genauesten darin, die Wartezeiten vorherzusagen, insbesondere bei den chaotischen „Von vorn beginnen“- und „Fortsetzen“-Regeln, bei denen Unterbrechungen stattfinden.
- Warum? Weil das Warten in einer Prioritätsschlange nicht nur davon abhängt, was gerade jetzt passiert; es geht auch darum, was kurz zuvor geschah und was als Nächstes passieren könnte. Das RNN ist gut darin, diese Geschichte zu lesen.
2. Die „Baum“-Gehirne waren gut, aber nicht perfekt
Die Entscheidungsbaum-Modelle (GBM und Random Forest) machten einen ordentlichen Job, waren aber nicht so scharf wie das RNN. Sie hatten etwas mehr Schwierigkeiten, wenn die Schlange häufig unterbrochen wurde.
3. Das Aufteilen des Teams half kaum
Die Autoren versuchten, die Baum-Modelle dazu zu bringen, separate Teams für VIPs und Reguläre zu bilden (der „Erzwungene Prioritäts-Split). Sie dachten, dies könnte helfen, damit sich die Modelle besser konzentrieren können.
- Das Ergebnis: Es machte kaum einen Unterschied. Die Standardmodelle waren bereits klug genug, um den Unterschied zwischen VIPs und Regulären von selbst zu erkennen. Das Aufteilen war so, als würde man zwei separate Köche einstellen, obwohl ein einziger guter Koch beide Menüs bewältigen kann.
4. Die „Magischen Zwei“ Eingaben
Dies ist der überraschendste Teil. Normalerweise benötigt man, um eine Wartezeit perfekt vorherzusagen, alles: die exakte Ankunftsrate, die Serviergeschwindigkeit, die Tageszeit usw.
- Die Entdeckung: Die Autoren fanden heraus, dass die Modelle die Wartezeiten sehr genau vorhersagen konnten, indem sie nur zwei Informationen verwendeten:
- Wie viele Leute sind gerade in der Schlange? (Warteschlangenlänge)
- Ist die Person ein VIP oder ein Regulärer? (Priorität)
- Selbst ohne zu wissen, wie spät es ist oder wie schnell die Leute normalerweise ankommen, reichte das Wissen über die aktuelle Crowd-Größe und den Status der Person aus, damit der Computer eine großartige Schätzung abgeben konnte.
Das Fazit
Die Arbeit zeigt, dass man kein superskomplexes System mit einer Million Datenpunkten braucht, um Wartezeiten in einer Prioritätsschlange vorherzusagen.
- Wenn Sie die beste Genauigkeit wollen, verwenden Sie ein Modell, das sich an die Abfolge der Ereignisse erinnert (wie das RNN).
- Wenn Sie Einfachheit wollen, können Sie durch das bloße Zählen der Menschen in der Schlange und das Überprüfen ihres Prioritätsabzeichens überraschend gute Ergebnisse erzielen.
Dies ist eine großartige Nachricht für reale Systeme (wie Krankenhäuser oder Callcenter), da diese oft nicht über perfekte Daten zu Ankunftsraten verfügen, aber sie wissen, wie viele Leute warten und wer wichtig ist. Sie können diese einfachen Eingaben nutzen, um den Menschen genaue Wartezeit-Schätzungen zu geben.
Ertrinken Sie in Arbeiten in Ihrem Fachgebiet?
Erhalten Sie tägliche Digests der neuesten Arbeiten passend zu Ihren Forschungsbegriffen — mit technischen Zusammenfassungen, in Ihrer Sprache.