Der Weg zum praktischen Warten
Inhaltsverzeichnis
Vorgänge, bei denen beliebige Einheiten (Transaktionen) in unregelmäßigen und oft unkontrollierbaren Abständen auf Engpässe (Abfertigungseinheit) zukommen, an denen sie abgefertigt werden wollen (Warteschlange).
Quelle: Prof. Dr. Marco Lübbecke, RWTH Aachen, Lehrstuhl für Operations Research, Lehrstuhlinhaber
Hintergrund und Ziel
Warteschlangen treten an Bedienungssystemen auf, bei denen Ankunfts- und Abfertigungsprozess nicht durch zentrale Steuerung miteinander synchronisiert sind.
Beispiele: Schalterhallen in Postämtern, Banken und Behörden, Kassenschalter in Selbstbedienungsläden, Straßenkreuzungen mit und ohne Verkehrsampeln, Abfertigungsschalter an Flughäfen, Abflug- und Landeschlangen von Flugzeugen an Flughäfen, Fertigungsaufträge vor Fertigungsmaschinen (Maschinenbelegungsplanung).
Die Warteschlangentheorie dient der Untersuchung der Entwicklung von Warteschlangen in Abhängigkeit von
- der Ankunft der zu bedienenden Einheiten
- der Abfertigung (Bedienung) dieser Einheiten und
- dem Bedienungssystem.
Insbesondere interessieren durchschnittliche Wartezeit sowie durchschnittliche Länge der Warteschlange
- Für bestimmte Standardfälle von Warteschlangenprozessen sind Standardformeln für die durchschnittliche Wartezeit und die durchschnittliche Warteschlangenlänge etc. entwickelt worden
- Für Nicht-Standardfälle müssen entsprechende Formeln neu entwickelt werden. Häufig hat sich hier die Anwendung der Simulation als nützlich erwiesen.
Befasst sich nicht mit Einzelvorgängen, sondern mit Massenerscheinungen.
Warteschlangen (Zugangswarteschlangen) entstehen, wenn die Zahl der Einheiten (Kunden, Lieferaufträge, Gäste, Flugzeuge, Maschinenstörungen, Werkstücke etc.), die in einem Zeitabschnitt an einer oder mehreren Abfertigungsstellen ankommen (Schalter, Auslieferungswagen, Kellner, Landebahnen, Reparaturmechaniker, Maschinen etc.), vorübergehend oder ständig größer sind als die im gleichen Zeitabschnitt verfügbare Abfertigungs- oder Bedienungskapazität.
- Bei Engpässen in der Abfertigungskapazität (periodenbezogen) entstehen Zugangswarteschlangen.
- Sind umgekehrt Bedienungsstationen frei und warten auf Einheiten, die bedient werden wollen
(z.B. Warteschlangen von Taxis, die auf Fahrgäste warten), so entstehen Abgangswarteschlangen
Damit ist der duale Charakter des Warteschlangenproblems angedeutet
Betrachtung von Vorgängen, in denen bestimmte Einheiten auf Engpässe treffen,
um eine Aussage über Länge entstehender Stauungen und Wartezeiten treffen zu können.
Ziel: Optimierung der Auslastung und Ermittlung der erforderlichen Anzahl an Abfertigungsstationen
Nutzung zur Analyse unterschiedlicher Systeme – beispielsweise:
- Fertigungsstraßen in Betrieben
- Logistiksysteme
- Telekommunikationssysteme und Computer
- Verkehrs- und Infrastruktursysteme
Eine Vernetzung mehrerer Wartesysteme wird als Warteschlangennetz bezeichnet.
Ziel der Warteschlangentheorie
Grundmodell und Variationen
Es besteht aus
- Bedienungsschalter (ein oder mehrere parallel arbeitende gleichartige Maschinen bzw. Arbeitsplätze)
- Warteraum
Kunden treffen einzeln und zu zufälligen Zeitpunkten vor dem Bedienungsschalter ein.
Neu ankommender Kunde wird bedient, sofern mindestens einer der Bedienungsschalter frei ist, andernfalls muss er sich in die Warteschlange einreihen.
- Kunden werden nicht einzeln, sondern gruppenweise bedient (Wartesysteme mit Gruppenbedienung)
Anwendung: Losfertigung in einem Produktionsbetrieb - Einige Kunden verlassen das System, bevor sie bedient worden sind (Wartesysteme mit Zeitbeschränkungen)
Anwendung: Lagerhaltung von verderblicher Ware - Nicht alle Bedienungsschalter stehen jedem Kunden zur Verfügung (Bedienungssysteme mit eingeschränkter Erreichbarkeit) Anwendung: Fertigungsstraßen mit dedizierten Maschinen, Koppelanordnungen in einem Fernsprechnetz
- Einige Kunden scheuen sich, in das Bedienungssystem einzutreten, weil ihnen die Warteschlange zu lang erscheint (Wartesysteme mit ungeduldigen Kunden)
Anwendung: übliches Kundenverhalten an einem Post-, Bank- oder Fahrkartenschalter - Kunde mit höherer Priorität verdrängt Kunden niedrigerer Priorität aus dem Bedienungsprozess (Prioritätssteuerung)
Anwendung: Express-Los-Steuerung in einem Fertigungsprozess - Kunde, der bei seiner Ankunft nicht sofort bedient werden kann, geht verloren (Verlustsysteme)
Anwendung: Telefonate in einem Fernsprechnetz
Systematik
Wartesystem – besteht aus:
- Bedienbereich, in dem ein oder mehrere Ausführungseinheiten Aufträge bearbeiten, und
Warteraum, in dem eintreffende Aufträge bei aktuell nicht freien, aber verfügbaren Ausführungseinheiten auf Bedienung warten. - Abgefertigte Aufträge verlassen das System.
Wartesysteme ohne Warteraum: Verlustsysteme
Warteschlangentheorie liefert Aussagen über Leistungsgrößen wie mittlere Warteschlangenlänge, Anzahl Kunden im Wartesystem, mittlere Wartezeit oder Ähnliches.
Einheitliche Notation zur Beschreibung der Wartesysteme (von David George Kendall entwickelt): Kendall-Notation.
Wartesystem – mit sechs Parametern beschrieben (in Reihenfolge der Kendall-Notation):
Ankunftsprozess Stochastischer Prozess, beschreibt Ankunft neuer Aufträge (häufig Poisson-Prozess verwendet)
Servicezeitverteilung Stochastische Verteilung der Ausführungszeiten (Bearbeitungsdauer eines Auftrags ohne Wartezeit)
In vielen Fällen Exponentialverteilung angenommen
Anzahl der Ausführungseinheiten Anzahl der Einheiten, die parallel Aufträge bearbeiten können
Beispielsweise Anzahl der (geöffneten) Kassen in einem Supermarkt
Kapazität der Warteschlange Maximale Anzahl wartender Aufträgen (maximale Länge der Warteschlange)
In vielen Fällen als unendlich groß angenommen
Population Menge aller möglichen Aufträge, aus denen durch den Ankunftsprozess Aufträge ins System gelangen
In vielen Fällen als unendlich groß angenommen
Abfertigungsdisziplin Reihenfolge der Abarbeitung wartender Aufträge in der Warteschlange
Meist FCFS-Prinzip (FIFO) angewendet: jeweils Auftrag am vorderen Ende der Schlange als nächster abgefertigt
Verwendete Variablen in verschiedenen Quellen oft abweichend, aber Reihenfolge der Inhalte immer identisch: A/S/c/K/N/D
A: Ankunftsprozess
Beschreibt die Verteilung des Eingangs neuer Kunden in die Warteschlange. So wird eine Exponentialverteilung nach Markov mit „M“ bezeichnet, eine deterministische Verteilung hingegen als „D“.
S: Serviceprozess
Beschreibt die Verteilung der Bearbeitung von Aufträgen aus der Warteschlange. Auch hier wird die Exponentialverteilung mit einem „M“ und eine mögliche deterministische Verteilung mit „D“.
c: Anzahl an Bedienern
Beschreibt die Anzahl an Servicestationen, die die Aufträge aus der Warteschlange bedienen. So bezeichnet eine „1“, dass genau eine Servicestation die Aufträge abarbeitet.
K: Kapazität des Systems
Beschreibt die Gesamtkapazität an Aufträgen, die in einem System Platz finden, bevor neue Kunden/Aufträge abgelehnt werden müssen.
N: Gesamtpopulation möglicher Kunden
Beschreibt die Anzahl potentiell möglicher Kunden. Je kleiner z.B. die übrigbleibende Population ist, desto weniger Aufträge werden im weiteren Verlauf ins System hinkommen können.
D: Art der Abfertigung
Beschreibt die Art der Abwicklung des Serviceprozesses. Häufig erfolgt dies nach dem FIFO Prinzip (First in First out).
M/M/1/15/100/FIFO – beschreibt eine Warteschlange mit einer Exponentialverteilung im Ankunfts- und Serviceprozess mit einem Bediener. Das System hat eine Gesamtaufnahmekapazität von zeitgleich 15 Aufträgen mit einer Gesamtpopulation von 100 potentiellen Aufträgen. Die Abfertigung erfolgt nach dem „First in First out“ – Prinzip.
Auf Basis dieser Überlegungen lassen sich nun beispielsweise die durchschnittliche Länge der Warteschlange, die Wartezeit oder die Gesamtdauer des Auftrags im System ermitteln. Dies ist dann die Basis für die weiteren Überlegungen zur Optimierung.
Wenn in einem System durchschnittlich a = 4 Ankünfte pro Zeiteinheit stattfinden, aber durchschnittlich b = 5 Abfertigungen möglich sind, so werden durchschnittlich n = 4 Elemente im System sein, die durchschnittlich 0,8 Zeiteinheiten warten werden.
Für einige komplexere Strukturen liefert die formelmässige Warteschlangentheorie nur Näherungswerte. Detaillierte Aussagen über das Verhalten besonderer Warteschlangensysteme sind dann zumeist nur mit Hilfe der —Simulation zu erhalten
Der einfachste Prozess M/M/1
Warteschlangenprozesse – nach einfacher Klassifikation von D. G. Kendall durch drei Symbole gekennzeichnet
- Ankunftsprozess
- Abfertigungsprozess
- Anzahl der Abfertigungsschalter
M/M/1
- Markoff*-Prozess der Ankünfte (Ankünfte zufällig und unabhängig voneinander)
- Markoff*-Prozess der Abfertigung sowie die Auslegung des Bedienungssystems
- Ein einzigen Schalter
Bei einer Rate von
- a durchschnittlichen Ankünften pro Zeiteinheit (bzw. 1/a durchschnittlicher zeitlicher Abstand)
- b Abfertigungen pro Zeiteinheit (bzw. 1/b durchschnittliche Bedienungszeit)
- Durchschnittliche Anzahl der im System befindlichen Einheiten: n= a/(b a)
- Durchschnittliche Wartezeit: w = n/b
Bedienungsregeln
Folgende Regeln und Bezeichnungen sind gebräuchlich
FIFO (FCFS) First In, First Out (First Come, First Served). Die Bedienung erfolgt in der Reihenfolge der Ankünfte.
LIFO (LCFS) Last In, First Out (Last Come, First Served). Die Bedienung erfolgt in umgekehrter Reihenfolge der Ankünfte.
SIRO Selection In Random Order. Der nächste Kunde wird zufällig ausgewählt.
Non-preemptive priority Relative Priorität. Manche Kunden werden gegenüber anderen Kunden vorrangig behandelt. Der laufende Bedienungsprozess wird jedoch nicht unterbrochen.
Preemptive priority Absolute Priorität. Besitzt der neu ankommende Kunde gegenüber den anderen Kunden im System eine höhere Priorität, so wird der laufende Bedienungsprozess unterbrochen und mit der neuen Forderung fortgesetzt. Die alte Forderung wird zurückgestellt.
RR Round Robin. Jeder Kunde kann den Bediener jeweils nur für ein bestimmtes Zeitintervall in Anspruch nehmen. Kunden, deren Abfertigung mehr Zeit benötigt, müssen sich deshalb mehrmals hintereinander in die Warteschlange einreihen.
Beispiele für Wartesysteme
Konsum und Gesundheit
Arztpraxis
Bücherei
Verkaufsabteilung, Versand
Verkaufsstand
Supermarktkassen, Bedienungsstände
Verkehr und Logistik
Tankstelle, Parkplätze, Zollabfertigung, Engpass
Transportsystem
Landebahn
Docks
Industrie, Dienstleistung und Gewerbe
Fertigungsstellen
Nachrichtenredaktion
Reparaturkolonne
Qualitätskontrollstellen