Das Märchen von der Schlange…

Gestern war ich mal wieder tanken - natürlich den teureren E5-Sprit - und durfte am Kassenhäuschen ein Zettelchen lesen. Auf dem wurde darum gebeten, mehrere Warteschlangen zu bilden, wenn mehrere Kassen geöffnet sind - angeblich, um die Wartezeiten zu verkürzen...

Aber stimmt das überhaupt? Ist es richtig, dass man kürzere Wartezeiten hat, wenn man die Wartenden auf mehrere Schlangen aufteilt? Ist es nicht vielleicht sogar effizienter, wenn man - wie in Großbritannien üblich - eine Warteschlange nutzt und diese zum Schluss auf die einzelnen Kassen aufteilt?

Was ihr evtl. noch nicht wusstest: Auch die Informatik befasst sich mit diesem - bzw. einem ähnlichen - Problem. Dort ist es unter dem Begriff "Scheduling" (dt. "Arbeitsplanerstellung") bekannt. Ohne Scheduling könntet ihr nur ein Programm gleichzeitig nutzen - euer Musikplayer würde stoppen, sobald ihr den Browser benutzt; die Webseite würde aufhören zu laden, sobald ihr eine E-Mail absendet, etc.
Beim PC kommt ein sogenanntes "preemptive Scheduling" zum Einsatz. Das bedeutet, dass die laufenden Prozesse unterbrochen werden, um anderen Prozessen Zeit zum Arbeiten zu geben. Sollte es doch dazu kommen, dass ein System wegen eines inperformanten Prozesses träge wird, dann gibt es meist Probleme mit dem Scheduling.

Bei der Warteschlange vor der Supermarktkasse, kann man solch ein System leider nicht einsetzen. Wäre ja merkwürdig, wenn die Kassiererin sich beim Bezahlen plötzlich zu einem anderen Kunden umdreht und den erstmal bezahlen lässt. Bei Systemen, die keine Unterbrechung der einzelnen Prozesse zulässt, spricht man vom "non-preemptive Scheduling".

Soviel zur grundlegenden Theorie... kommen wir nun also zur eigentlichen Frage: "Was ist schneller? Eine oder mehrere Warteschlangen?". Spannenderweise ist das garnicht entscheidend. Entscheidend ist nämlich das, was hinter dieser Entscheidung steht - und das ist die Frage "Welcher Scheduling-Algorithmus ist der effizientere?".

Wenn wir uns mal in die Lage eines Supermarkt-Besuchers versetzen, der an die Kasse kommt, dann fällt uns folgendes auf: Er versucht, anhand von Parametern zu ermitteln, bei welcher Warteschlange er wohl am kürzesten warten muss. Dabei hat er meist 4 Faktoren:

  1. Die Anzahl der Leute, die vor ihm stehen.
  2. Das Alter der Leute, die vor ihm stehen.
  3. Die Anzahl der Waren, die die Leute vor ihm haben.
  4. Die Arbeitsgeschwindigkeit der Kassiererin.

Viele Leute bedeuten lange Wartezeiten, alte Leute bedeuten meist lange Wartezeiten, viele Waren bedeuten meist längere Wartezeiten, ebenso bedeuten langsame Kassiererinnen meist lange Wartezeiten. Es werden also unterbewusst Gewichtungen zwischen den einzelnen Warteschlangen vorgenommen und sich dann für die Kasse entschieden, bei der die vermutete Wartezeit am geringsten ist. Das Vorgehen ist garnicht mal so doof und wird als "approximate Scheduling" bezeichnet - es wird also auf Basis von geschätzten Werten eine Entscheidung getroffen. Das mag funktionieren, kann aber auch tierisch in die Hose gehen...

Approximate Scheduling: Kein Problem

Im gezeigten Beispiel haben wir zwei Kassen und zwei Warteschlangen - an der einen Kasse warten 4 Personen, an der anderen Kasse nur eine. Von den Personen an Kasse A wird geschätzt, dass sie 1 Minute, 2 Minuten, 1 Minute, respektive 3 Minuten für das Abkassieren benötigen werden. An Kasse B steht nur eine Person, von der geschätzt wird, dass sie 3 Minuten für's Bezahlen brauchen wird. Die Wahl ist also klar: Ein Kunde, der sich für eine Kasse entscheiden müsste, würde wohl Kasse B wählen, da die zu erwartende Wartezeit geringer ist.

Approximate Scheduling: Problem

Man stelle sich nun aber vor, die eigene Approximation ist falsch - z.B. weil man nicht erkannt hat, dass die Person einen Artikel reklamieren will und auf den Manager wartet (oder weil die EC-Karte nicht funktioniert) - und die Person an Kasse B in Wirklichkeit 10 Minuten braucht, dann steht man plötzlich an der Kasse, an der man fast 50% länger warten muss.
Genau hier versagt das approximative Verfahren, das bei mehreren Schlangen zum Einsatz kommt. Und wirklich genervt ist man spätestens dann, wenn man sich entschließt, die Kasse zu wechseln, dort dann aber bereits neue Leute anstehen, sodass man dort genauso lange (oder länger) warten müsste.

Anders sieht es aus, wenn man nur eine Warteschlange hat und der Kunde sich erst dann zur Kasse begibt, wenn diese frei ist. Auch wenn es für einige paradox klingt: Obwohl dort die Warteschlange länger ist, wartet man statistisch gesehen weniger lange. Der Grund dafür ist, dass bei Problemen an einer Kasse der Rest der Kunden automatisch auf die anderen Kassen verteilt wird. Man muss also keine Wartezeit schätzen und auf Basis der Schätzung entscheiden, sondern man nutzt die exakten, real existierenden Werte für eine optimale Verteilung.

Exact Scheduling: Keine Probleme

Leider wird diese Form der Warteschlange in Deutschland so gut wie garnicht eingesetzt - ob nun beim Warten vorm Sportstadion, vor der Kinokasse, im Supermarkt - die Deutschen scheinen mit dem Konzept nicht viel anfangen zu können. In Großbritannien und anderen Ländern sieht das zum Glück ein wenig anders aus. Dort gibt es meist sogenannte "Queue Areas": Es existiert ein Bereich, wo sich alle Kunden anstellen. Durch Lampen an den Kassen oder durch Displays wird dem Fordersten in der Schlange angezeigt, welche Kasse für ihn frei ist. Ich, als jemand, der etwa einmal im Jahr auf der Insel zu Besuch ist, finde diese Form der Warteschlange sehr entspannend, denn die Entscheidung, welche Kasse ich nehme, übernimmt das sich selbst optimierende System.

Die TU Clausthal hat das Thema übrigens mal stochastisch analysiert und ist genau zu den gleichen Ergebnissen gekommen. Interessant finde ich vor allem die letzte Darstellung, in der man einen deutlichen Unterschied zwischen der mittleren Wartezeit bei einer Warteschlange (blau) und der mittleren Wartezeit bei mehreren Warteschlangen (rot) erkennen kann.... wäre ich also ein Ladenbesitzer, dann würde ich meinen Kunden einen Gefallen tun und eine Queue Area einrichten. 🙂
Wartende Grüße, Kenny

6 Kommentare » Schreibe einen Kommentar

  1. Ein tolles Phänomen hab ich vor kurzem beim Abflug an einem Flughafen erlebt. Es gibt ja immer diejenigen, die sich schon ne Stunde vorher einreihen (das Flugzeug könnte ja wegfliegen...) und diejenigen die rumsitzen und warten. Jetzt war es aber so, dass plötzlich einer von den "Sitzern" eine neue Schlange von vorne gebildet hat und das Chaos war groß. Am Ende wurde wild geflucht und es bildete sich eine Traubenform. 😀

  2. Eine einzige schlange gibt es auch bei der Post. finde ihr sehr gut. Übrignes hat das ganze auch einen tollen nebeneffekt. unterbewusst nimmt man das warten auch nicht so lange wahr, da man ja ständig ein paar schritte vor läuft und nicht nur alle paar Minuten.

  3. Moin Kevin,

    wie die anderen Kommentare schon zeigen, ist das System in Deutschland doch nicht ganz unbekannt. Ich will noch die Schalter an Flughäfen erwähnen. Auch dort gibt es zumindest teilweise nur eine Warteschlange.

    • Jo, an wenigen Stellen wird es in der Tat genutzt - habe auch nix anders behauptet. Leider ist die Zahl doch recht eingeschränkt. Wenn ich an meine Flughafenerfahren zurückdenke, ist es dort auch meist eher so, dass die Leute sich von der einen Schlange eher genervt fühlen. So in der Art "aber es sind doch mehrere Kassen offen".

  4. Die Bahn betreibts an einigen Schaltern auch gerne. Heimische Wursttheke mittels Zettelchen ebenso - klappt prima. Leider kann sich der Deutsche nur schwer an solch' "neumodischen" Kram gewöhnen und ich ertappe mich auch immer wieder bei dem Gedanken: Lange Schlange -> EVIL. Dabei sollte ich es eigentlich besser wissen, nun hab' ich's immerhin wieder ins Gedächtnis gerufen bekommen 🙂

  5. Jupp,
    recht haste. Hab mir beim warten in diversen schlangen der letzten jahre auch ähnliches eruiert - deswegen ein lob auf die Post, ist das einzige unternehmen dass ich kenne, welches dieses queue-area system hierzulande durchzieht.
    Ansonsten gibts das system erstaunlicherweise öfters in ämtern: da dann ganz offiziell mit zettelchen ziehen und warten bis die nummer aufm display kommt zusammen mit der platznummer des jeweiligen sachbearbeiters.

Schreibe einen Kommentar

Um Ihnen beim weiteren Kommentieren auf dieser Webseite die erneute Eingabe Ihrer Daten zu ersparen, wird beim Absenden Ihres Kommentars ein Cookie an Ihren Browser gesendet und von diesem gespeichert. Mit dem Absenden eines Kommentars auf dieser Webseite stimmen Sie der Speicherung und Übertragung dieses Cookies explizit zu.

Pflichtfelder sind mit * markiert.