Simulation und Analyse der Leistung der UniversitÀtskantine:
Warteschlangenmodell fĂŒr den Durchfluss durch die UniversitĂ€tskantine, die Identifizierung von EngpĂ€ssen und der Vorschlag von Lösungen zur Optimierung der Durchlaufzeiten.
UniversitĂ€tskantinen spielen eine zentrale Rolle bei der UnterstĂŒtzung von Studierenden, indem sie
zuverlĂ€ssige Verpflegung und einen Ort fĂŒr soziale Interaktion bieten. Allerdings fĂŒhrt die Hektik in
diesen Kantinen oft zu Herausforderungen bei der effizienten Steuerung des Kundenstroms, was zu langen
Warteschlangen, verlĂ€ngerten Servicezeiten und insgesamt zu einer suboptimalen Erfahrung fĂŒhrt.
Da ich die Notwendigkeit erkannte, diese Probleme anzugehen, beteiligte ich mich als Masterstudent an einem
Team, das sich mit der Entwicklung von Warteschlangenmodellen zur Steigerung der Effizienz von
UniversitÀtskantinen befasste.
Unter der Aufsicht der FakultÀt hatten wir die Aufgabe, ein Warteschlangenmodell zu simulieren, um die
Betriebsdynamik unserer UniversitÀtskantine nachzubilden. Dieses Vorhaben sollte uns helfen, den gesamten
Warteschlangenprozess besser zu verstehen â vom Moment der Ankunft eines Studenten am Kantinen-Schalter bis
zum Abschluss seiner Zahlung.
Die Ziele dieses Simulationsprojekts waren zweierlei: erstens, tiefere Einblicke in die komplexen
Interaktionen zwischen Kunden, Dienstleistern und verfĂŒgbaren Ressourcen zu gewinnen; und zweitens,
potenzielle EngpÀsse innerhalb des bestehenden Systems zu identifizieren.
Dieses Projekt untersucht die verwendeten Methoden, die Bedeutung der Warteschlangentheorie â einem
etablierten Teilgebiet der Operations Research â und ihre Anwendung im Kontext von UniversitĂ€tsmensen. Wir
diskutieren auch die Herausforderungen, die wÀhrend des Simulationsprozesses auftraten, die wichtigsten
Ergebnisse der Analyse und die vorgeschlagenen Lösungen zur Beseitigung der identifizierten EngpÀsse.
Durch die Veröffentlichung dieser Forschungsergebnisse möchten wir eine breitere Diskussion ĂŒber die
praktischen Anwendungen von Warteschlangenmodellen in realen Szenarien anregen und effektive Lösungen zur
Steigerung der KapazitĂ€t, VerkĂŒrzung der Servicezeiten und letztendlich zur Optimierung der gesamten
Kundenvorlaufzeit vorstellen.
SCHRITT 1: VerstÀndnis der Industrie
I. Warteschlangentheorie:
Das UniversitÀtskantinenprojekt weist mehrere Gemeinsamkeiten mit der Warteschlangentheorie auf, einem
mathematischen Rahmenwerk, das zur Modellierung von warteschlangenbasierten Dienstleistungsumgebungen wie
Convenience-Stores, Restaurants oder Notfalldiensten sowie in GeschÀftsbereichen wie Telekommunikation,
Logistik und Bankwesen verwendet wird.
Die Warteschlangentheorie hilft bei der Optimierung der Ressourcenzuweisung und der Verbesserung des
Kundenservice, indem sie durch die Berechnung des Auslastungsfaktors fĂŒr jede Station EngpĂ€sse
identifiziert.
II. Datengenerierung:
Ein weiterer wichtiger Bestandteil dieses Projekts ist die Generierung von Daten fĂŒr Simulationsmodelle.
Die Datengenerierung ist entscheidend fĂŒr die Definition von Wahrscheinlichkeitsverteilungen fĂŒr
Eingabevariablen wie Ankunftsraten und Servicezeiten. Mithilfe der Monte-Carlo-Simulation haben wir groĂe
Mengen von Zufallsstichproben generiert, um verschiedene Szenarien innerhalb des Warteschlangensystems zu
simulieren.
Key Performance Indicators (KPI) konzentrierten sich auf den betrieblichen Mehrwert fĂŒr die Mensa,
wobei insbesondere die KapazitÀt, die Durchlaufzeiten und der Auslastungsfaktor jeder Servicestation im
Vordergrund standen.
SCHRITT 2: VerstÀndnis der Daten
Wie bei jedem Warteschlangenmodell kommen die Kunden nach einem bestimmten Ankunftsprozess zum System, der
in der Regel anhand von Poisson- oder Exponentialverteilungen modelliert wird. Bei der Ankunft wird der
Kunde, sofern ein Server verfĂŒgbar ist, sofort bedient und begibt sich dann zur nĂ€chsten Station, um die
Zahlung abzuschlieĂen.
Um das Warteschlangensystem der Kantine genau darzustellen, haben wir die folgenden KundenzustÀnde
berĂŒcksichtigt: Ankunft in der Kantine, Interaktion mit dem Kantinenpersonal, um Essen zu bestellen und zu
erhalten (erste Servicestation), und Bezahlung an der Kasse (zweite Servicestation).
Um dieses System zu simulieren, haben wir eine Markov-Kette angewendet â ein stochastisches Modell, das aus
definierten ZustĂ€nden und Ăbergangswahrscheinlichkeiten zwischen diesen besteht.
Markov-Warteschlangenprozesse ermöglichen die Simulation und Analyse des Systemverhaltens unter
verschiedenen Bedingungen und funktionieren ohne Speicher (zukĂŒnftige ZustĂ€nde werden nicht von vergangenen
Ereignissen beeinflusst).
In der Warteschlangentheorie wird die Kendall-Notation verwendet, um Warteschlangenknoten zu beschreiben
und zu klassifizieren. In unserem Fall wird das System als M/M/1/1/â/â/FIFO dargestellt, was einen
Markovschen Ankunftsprozess und Servicezeiten, einen Server pro Station, unbegrenzte
WarteschlangenkapazitÀt und eine First-in-First-out-Servicedisziplin bezeichnet.
SCHRITT 3: Aufbereitung der Daten
Auf Grundlage der Erkenntnisse aus der Datenanalysephase haben wir die wichtigsten Elemente des
Warteschlangensystems identifiziert. Diese wurden manuell durch direkte Besuche in der
UniversitÀtscafeteria erfasst, bei denen wir wichtige Details wie Spitzenzeiten, zu denen die
Kundennachfrage am höchsten war, beobachtet und aufgezeichnet haben.
Nachdem ausreichend Daten zu Ankunftsraten und Servicezeiten gesammelt worden waren, haben wir
Chi-Quadrat-Tests durchgefĂŒhrt, um zu bewerten, wie gut die beobachteten Daten einer Poisson-Verteilung
entsprechen. Mit zunehmendem Umfang der gesammelten Daten stieg auch der p-Wert des Chi-Quadrat-Tests. Nach
der Erfassung von etwa 150 Datenpunkten haben wir mit dem Prozess der Datengenerierung fortgefahren.
HINWEIS: Um Konsistenz zu gewÀhrleisten und Beobachterverzerrungen zu minimieren, wurden die Daten
ĂŒber mehrere Tage und Zeitfenster hinweg gesammelt, wobei Wochenenden ausgeschlossen wurden.
def augment_poisson(data_augmented, sim_iteration, label):
plt.figure(figsize=(10, 5))
plt.subplot(1, 2, 1)
data_augmented[1].plot(kind="hist", alpha=0.5, label="Order", color="green", bins=100)
plt.xlabel(f"{label} (People per minute)")
plt.ylabel("Frequency")
plt.title("Population Distribution Original")
mean = data_augmented[1].mean()
samples = np.random.poisson(mean, size=sim_iteration)
new_data = pd.DataFrame({1: samples})
data_augmented = pd.concat([data_augmented, new_data], ignore_index=True)
size_two = data_augmented.shape[0]
plt.subplot(1, 2, 2)
data_augmented[1].plot(kind="hist", alpha=0.5, label="Order", color="orange", bins=100)
plt.xlabel(f"{label} (People per minute)")
plt.ylabel("Frequency")
plt.title("Population Distribution Generated")
plt.tight_layout()
plt.show()
return data_augmented[1], size_two
Nach Abschluss der Datenerfassung haben wir eine Monte-Carlo-Simulation durchgefĂŒhrt, um auf der Grundlage
der beobachteten DatensÀtze zusÀtzliche Datenpunkte zu generieren. Durch die Analyse der Verteilung der
Ankunftsraten und Servicezeiten habe ich zwei separate Funktionen zur Datengenerierung entwickelt â eine
fĂŒr Poisson-verteilte Ankunftsraten und eine fĂŒr exponentiell verteilte Servicezeiten. Diese Funktionen
generierten bis zu 700 neue Datenpunkte, die die Eigenschaften der ursprĂŒnglichen Datenverteilungen
nachbildeten.
Durch die Definition von Wahrscheinlichkeitsverteilungen fĂŒr Eingabevariablen wie Ankunftsraten und
Servicezeiten und die Anwendung der Monte-Carlo-Simulation konnten wir eine Vielzahl von Szenarien
simulieren. Diese Szenarien ermöglichten die SchÀtzung wichtiger Leistungsindikatoren, darunter
durchschnittliche Wartezeit, WarteschlangenlÀnge, Systemauslastung und die Wahrscheinlichkeit von
Verzögerungen.
Ein Vergleich zwischen den ursprĂŒnglichen Daten und den generierten Daten â basierend auf Mittelwerten und
Verteilungsmustern â bestĂ€tigte, dass die generierten Daten die statistischen Eigenschaften des
ursprĂŒnglichen Datensatzes beibehielten.
SCHRITT 4: Datenexploration und -visualisierung
Die Untersuchung der DatensÀtze zu Ankunftsraten und Servicezeiten lieferte erste Einblicke in das
Verhalten und die Leistung des Warteschlangensystems. In Warteschlangensystemen werden wichtige
Leistungskennzahlen wie Wartezeiten, Auslastungsfaktor und Durchlaufzeiten durch Datenauswertung abgeleitet
und sind fĂŒr die Bewertung der Systemeffizienz von zentraler Bedeutung. Diese Leistungskennzahlen sind auch
nĂŒtzlich fĂŒr das Benchmarking verschiedener Personalszenarien oder Servicelayouts, die spĂ€ter getestet
werden könnten.
Mithilfe von Histogrammen und Boxplots konnten wir Schiefe, potenzielle AusreiĂer und Clustering-Muster
innerhalb der DatensÀtze beobachten.
Wartezeit: Diese Kennzahl bezieht sich auf die Zeit, die ein Kunde in der Warteschlange verbringt,
bevor er bedient wird. Sie wird berechnet, indem die Differenz zwischen der Ankunftszeit und dem Beginn der
Bedienung gemessen wird.
Durchlaufzeit: Die Durchlaufzeit erfasst die Gesamtzeit, die ein Kunde im System verbringt, von der
Ankunft bis zum Abschluss der Bedienung. Sie umfasst sowohl die Wartezeit als auch die Bedienungszeit und
wird durch Verfolgung der gesamten Customer Journey berechnet.
Auslastungsfaktor: Der Auslastungsfaktor gibt den Prozentsatz der Zeit an, in der Servicestationen
(Server) Kunden aktiv bedienen, im VerhĂ€ltnis zu ihrer GesamtverfĂŒgbarkeit. Er ist ein wichtiger Indikator
fĂŒr die KapazitĂ€t und Effizienz des Systems.
SCHRITT 5: Entwicklung von Merkmalen
Um diese Leistungskennzahlen in einem Simulationsmodell genau zu berechnen, mĂŒssen prĂ€zise Zeitstempel fĂŒr
die Ankunft der Kunden, den Beginn der Dienstleistung, das Ende der Dienstleistung und die Abreise erfasst
werden. In unserem Simulationsmodell haben wir die folgenden SchlĂŒsselelemente definiert:
-->
'Kundennummer'
-->'Ankunftsrate'
--> 'Wartezeit vor der Kantine'
--> 'Servicezeit Kantine'
-->
'Wartezeit vor der Kasse'
--> 'Servicezeit Kasse'
--> 'Durchlaufzeit'
Durch die Verfolgung dieser Werte und die Anwendung geeigneter Algorithmen konnten wir die Wartezeiten,
Durchlaufzeiten und Auslastungsfaktoren berechnen, die fĂŒr die Bewertung der Systemleistung und die
Ermittlung von Möglichkeiten zur Betriebsverbesserung erforderlich sind. Der Zweck dieser Funktionen
besteht nicht nur darin, die Kundenbewegungen durch das System zu verfolgen, sondern auch die
RĂŒckverfolgbarkeit der Simulationsergebnisse zu gewĂ€hrleisten.
avg_arrival_rate = np.mean(new_arrival) / 60
avg_service_time_uno = new_order.mean()
avg_service_time_dos = new_cashier.mean()
capacity_canteen = 1
capacity_cashier = 1
utilization_factor_canteen = (avg_arrival_rate * avg_service_time_uno) / capacity_order
utilization_factor_cashier = (avg_arrival_rate * avg_service_time_dos) / capacity_cashier
client_data = pd.DataFrame(columns=['Client Number', 'Arrival Rate', 'Waiting time before Canteen', 'Service Time Canteen', "Waiting time before Cashier", "Service Time Cashier", "Lead Time"])
client_data["Waiting time before Canteen"] = (client_data["Waiting time before Canteen"] - client_data["Service Time Canteen"]).abs()
client_data["Waiting time before Cashier"] = (client_data["Waiting time before Cashier"] - client_data["Service Time Cashier"]).abs()
client_data["Lead Time"] = client_data[['Waiting time before Canteen', 'Service Time Canteen', "Waiting time before Cashier", "Service Time Cashier", "Lead Time"]].sum(axis=1)
SCHRITT 6: Aufbau von Modellen
FĂŒr diese Simulation des Warteschlangensystems haben wir Python verwendet und die SimPy-Bibliothek
integriert, ein Paket fĂŒr diskrete Ereignissimulationen (DES), das zur Modellierung des dynamischen
Prozessverhaltens und des Ressourcenmanagements entwickelt wurde. Mit SimPy konnten wir die
Kantinenumgebung nachbilden und simulieren, wie Ressourcen (Kantine und Kassen) mit ankommenden Kunden
interagieren.
Der Python-Code repliziert das Warteschlangenverhalten, indem er zufÀllig Werte aus den drei generierten
DatensÀtzen auswÀhlt, die die inhÀrente VariabilitÀt im tÀglichen Kantinenbetrieb widerspiegeln. Der
zufÀllige Auswahlprozess stellt sicher, dass jeder Simulationslauf eine andere Variation aufweist, was eine
bessere BelastungsprĂŒfung des Systems ermöglicht.
Im Ankunftsprozess erhÀlt die erste Station (Canteen) die Ankunftsintervalle von der Funktion
âarrival_process_stationsâ und verarbeitet die Servicedauer ĂŒber die Funktion âservice_process_canteenâ.
Sobald die Anfrage eines Kunden abgeschlossen ist, wird sie an die zweite Station (CASHIER) weitergeleitet,
die mit der Funktion âservice_process_cashierâ simuliert wird.
env = simpy.Environment()
server_number_uno = simpy.Resource(env, capacity=capacity_order)
server_number_dos = simpy.Resource(env, capacity=capacity_cashier)
station_canteen = simpy.Store(env)
queue_between = simpy.Store(env)
station_cashier = simpy.Store(env)
env.process(arrival_process_stations(env, client_number=0, client_data=client_data))
env.run(until=(3600 * work_days))
# Was ist simpy.Environment()?
Innerhalb der SimPy-Bibliothek reprĂ€sentiert die Klasse âEnvironmentâ die Umgebung, in der Ereignisse auftreten und geplant werden, wobei sie wichtige Funktionen umfasst, die ausschlieĂlich in der SimPy-Bibliothek zu finden sind, wie Simulationszeit, Ereignisplanung und -bearbeitung, ProzessausfĂŒhrung usw.
# Was ist simpy.Resource()?
Innerhalb der SimPy-Bibliothek reprĂ€sentiert die Klasse âResourceâ die KapazitĂ€t einer Station, d. h. wie viele Prozesse gleichzeitig ausgefĂŒhrt werden können. Im Python-Code generieren Kunden request(), um Zugriff auf die Ressource zu erhalten, und werden dann nach Abschluss der Aufgabe mit release() freigegeben.
# Was ist simpy.Store()?
Innerhalb der SimPy-Bibliothek reprĂ€sentiert die Klasse âStoreâ die Warteschlangen, Puffer oder Haltebereiche, in denen Simulationsprozesse Ereignisse ablegen, wenn die Klasse Resource() belegt ist. Die Klasse Resource() ruft Ereignisse mithilfe der Funktion get() ab.
Ankunftsereignisse werden durch Stichproben von zufÀlligen Ankunftsratenwerten (gemessen in Ankunften pro
Minute) generiert, die in Intervallzeiten zwischen den Ankunftszeiten umgewandelt werden, um zu bestimmen,
wie lange das System wartet, bevor es den nÀchsten Kunden bedient.
Jeder neue Kunde erhÀlt eine Kundennummer und wird mit der Methode put() zur Warteschlange der
Kantine (station_order) hinzugefĂŒgt. Die Kantinenstation verarbeitet Kunden ĂŒber die Methode get()
und verfolgt dabei die Ankunftszeit des Kunden, die Wartezeit vor der Bedienung und die Verweildauer in der
Servicestation.
def arrival_process_stations(env, client_number, client_data):
while True:
arrival_select = np.random.choice(new_arrival.values)
client_data.loc[client_number, 'Arrival Rate'] = arrival_select
if arrival_select != 0:
interarrival_time = 60 / arrival_select
else:
interarrival_time = 60
yield env.timeout(interarrival_time)
client_number += 1
station_order.put((env.now, client_number))
env.process(service_process_order(env, client_data))
def service_process_cashier(env, client_data):
while True:
with server_number_dos.request() as request:
yield request
arrival_time, client_number = yield station_cashier.get()
service_time_dos = np.random.choice(new_cashier.values)
yield env.timeout(service_time_dos)
client_data.loc[client_number, "Service Time Cashier"] = service_time_dos
client_data.loc[client_number, 'Waiting time before Cashier'] = env.now - arrival_time
env.process(service_process_cashier(env, client_data))
Die Kassierstation funktioniert Àhnlich: Sie ruft den nÀchsten Kunden aus der Zwischenwarteschlange
(station_cashier) mit der Methode get() ab und zeichnet die Wartezeit vor der Kasse, die
Bearbeitungszeit und die Gesamtzeit an der Station auf.
Sobald der Kassiervorgang abgeschlossen ist, berechnet die Simulation die Durchlaufzeit fĂŒr jeden Kunden.
Nach dem Simulationslauf werden systemweite Kennzahlen berechnet, darunter die Auslastungsfaktoren beider
Stationen und die Gesamtzahl der bedienten Kunden.
SCHRITT 7: Modelltraining und -bewertung
Um die Genauigkeit der Simulation zu beurteilen, haben wir den Auslastungsfaktor jeder Station anhand von
zwei AnsÀtzen berechnet: erstens durch Anwendung der durchschnittlichen Ankunfts- und Servicezeiten aus dem
Datensatz und zweitens durch manuelle Berechnung der Auslastung anhand der wÀhrend der Simulation
aufgezeichneten Zeitstempel.
Ergebnisse aus dem Datensatz:
+ Auslastungsfaktor der CANTEEN-Station: 1.4912927763838917
+ Auslastungsfaktor der KASSIER-Station: 0.9009195651771269
Ergebnisse des Simulationsmodells:
+ Auslastungsfaktor der CANTEEN-Station: 1.498312288696883
+ Auslastungsfaktor der KASSIER-Station: 0.9030687642105081
HINWEIS: Dieser Vergleich hilft dabei, zu ĂŒberprĂŒfen, ob die erwarteten Werte aus dem Datensatz mit
dem wĂ€hrend der Simulation erfassten Verhalten ĂŒbereinstimmen.
Sowohl die visuelle ĂberprĂŒfung der Simulation als auch die Ergebnisse zum Auslastungsfaktor bestĂ€tigen,
dass der primÀre Engpass an der Kantinen-Bedienstation auftritt. Dieser Engpass wurde weiter untersucht,
indem die Anzahl der Bedienstellen an dieser Station erhöht wurde, um die Auswirkungen auf die Auslastung
und die Wartezeiten zu beobachten.
Durchschnittliche Messwerte bei (1 Server per Station):
+ Waiting time before Canteen 10020.542148
+ Service Time Canteen 38.377895
+ Waiting time before Cashier 15.112265
+ Service Time Cashier 23.131278
+ Lead Time 9042.589862
Client Number 1
Waiting time before Order 0.0
Service Time Order 22.832561
Waiting time before Cashier 0.0
Service Time Cashier 51.881967
Lead Time 74.714528
Name: 1, dtype: object
Client Number 48
Waiting time before Order 391.274495
Service Time Order 38.645774
Waiting time before Cashier 0.0
Service Time Cashier 21.77937
Lead Time 451.699639
Name: 48, dtype: object