Das Märchen von der Schlange...

08.03.2011 yahe legacy thoughts

Gestern war ich mal wieder tanken und durfte am Kassenhäuschen ein Zettelchen lesen, auf dem darum gebeten wurde, 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 England ü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. "Reihenfolgeplanung") bekannt. Ohne Scheduling könntet ihr an eurem Computer nur ein Programm gleichzeitig laufen lassen. 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 so genanntes "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 an 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 zulassen, spricht man vom "non-preemptive Scheduling".

Soviel zur grundlegenden Theorie. Kommen wir nun also zur eigentlichen Frage: "Was ist schneller? Eine oder mehrere Warteschlangen?" oder anders ausgedrückt: "Welcher non-preemtive Scheduling-Algorithmus ist effizienter?"

Wenn wir uns mal in die Lage eines Supermarktbesuchers versetzen, der an die Kasse kommt, dann fällt uns auf, dass er versucht, anhand von Parametern zu ermitteln, bei welcher Warteschlange er wohl die kürzeste Wartezeit zu erdulden hat. 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 des Kassierers.

Viele Leute in der Schlange bedeuten lange Wartezeiten, alte Leute bedeuten lange Wartezeiten, viele Waren bedeuten lange Wartezeiten und auch ein langsam arbeitender Kassierer bedeutet 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 gar nicht mal so doof und wird als "approximate Scheduling" bezeichnet. Es wird auf Basis von geschätzten Werten eine Entscheidung getroffen. Das mag funktionieren, kann aber auch tierisch in die Hose gehen.

Im gezeigten Beispiel haben wir zwei Kassen und zwei Warteschlangen. An der einen Kasse warten vier Personen, an der anderen Kasse nur eine. Von den Personen an Kasse A wird geschätzt, dass sie 1 Minute, 2 Minuten, 1 Minute und 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.

Man stelle sich nun aber vor, die eigene Schätzung ist falsch, z.B. weil man nicht erkannt hat, dass die Person an Kasse B einen Artikel reklamieren will und auf den Manager wartet und 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 Warteschlangen 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 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 die Warteschlange länger ist, wartet man statistisch gesehen weniger lange. Der Grund ist, dass bei Problemen an einer Kasse der Rest der Kunden automatisch auf die anderen Kassen verteilt wird. Man muss also keine Wartezeiten schätzen und auf Basis der Schätzungen entscheiden, sondern man nutzt die exakten, real existierenden Werte für eine optimale Verteilung. Man spricht hierbei vom exact Scheduling.

Leider wird diese Form der Warteschlange in Deutschland kaum eingesetzt. Ob nun beim Warten vor'm Sportstadion, vor der Kinokasse, im Supermarkt - die Deutschen scheinen mit dem Konzept nicht viel anfangen zu können. Bspw. in England sieht das zum Glück ein wenig anders aus. Dort gibt es meist eine so genannte "Queue Areas", in der sich alle Kunden anstellen. Durch Lampen an den Kassen oder durch Displays wird dem jeweils 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 einmal 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. :-)