Bediensysteme

• Bediensystem oder Wartesystem (Queuing system):
  • abstraktes stochastisches Modell aus
    • Ankunftsprozess
    • Warteschlangen-Politik
    • Bedienprozess
  • graphisch
    • 
  • Beispiele
    • Kundenabfertigung an Schaltern
    • industrielle Fertigungsprozesse
    • Rechner-Netzwerke
    • Verkehrsplanung
• Kendall-Notation:
  • übliches Klassifizierungs-Schema von Wartesystemen
  • enthält sechs Parameter A|B|s|c|n|Q
  • Bedeutung

    • Parameter	Bedeutung	wichtige Werte
      A	Art des Ankunftsprozesses	M (Markov), G (allgemein)
      B	Art des Bedienprozesses	M (Markov), G (allgemein)
      s	Zahl der Bediener	1, 2, .., ∞
      c	Größe des Warteraums	1, 2, .., ∞
      n	max. Anzahl von Kunden	1, 2, .., ∞
      Q	Queue-Politik	FIFO, LIFO, Prio, Random

  • betrachten i.F. nur c = ∞, n = ∞, Q = FIFO
    • werden in Notation weggelassen
  • wichtigstes Beispiel: M|M|1
• Interessierende Kennzahlen:
  • mittlere Zahl von Kunden im System L
  • mittlere Zahl von Kunden in der Queue L_Q
  • mittlere Zeit eines Kunden im System W
  • mittlere Wartezeit eines Kunden in der Queue W_Q
• Formel von Little:
  • Ankunftsrate der Kunden sei λ. Dann ist
    • L = λ W
  • Voraussetzung: Mittelwerte existieren
  • anschauliche Begründung (Beweis: [2])
    • Annahme: Jeder Kunde zahlt 1 € pro Zeiteinheit im System
    • Nach großer Zeit T gilt
    • Gesamtverdienst des Systems V = L T
    • Gesamtzahl der Kunden N = λ T
    • mittlerer Betrag eines Kunden B = W
    • also V = N B ⇒ L = λ W
  • analog auch
    • L_Q = λ W_Q
• Stetige oder diskrete Zeit ?
  • Warteschlangentheorie meistens mit stetiger Zeit
    • Formeln einfach, Beweise schwer
  • hier mit diskreter Zeit
    • Formeln komplizierter, Beweise einfacher
  • Trick zur Vereinfachung
    • sehr kleine Zeitschritte h
    • Formeln nur in erster Ordnung h
    • Ergebnisse dann wie bei stetiger Zeit
• Ankunftsprozess:
  • feste Rate λ = mittlere Zahl der Kunden pro Zeiteinheit
  • Annahme: pro Takt h nur max. eine Ankunft
    • h klein
    • keine Gruppenankünfte
    • → pro Takt ein Bernoulliprozess mit p_a = λh
  • Eigenschaften des Ankunftsprozesses
    • Zahl der Ankünfte in n Takten ~ B(n,p_a)
    • Zahl der Ankünfte in disjunkten Zeitintervallen unabhängig
    • Zahl der Takte zwischen zwei Ankünften ~ G(p_a)
• Bedienprozess:
  • analog zum Ankunftsprozess
  • feste Rate μ = mittlere Zahl der Bedienungen pro Zeiteinheit (falls Kunden da)
    • 1/μ = mittlere Bedienzeit
    • pro Takt ein Bernoulliprozess mit p_b = μh
  • Eigenschaften des Bedienprozesses
    • Restbedienzeit ab beliebigem Zeitpunkt ebenfalls G(p_b)
    • Modell für Bedienprozess nicht besonders realistisch, aber Markov
• Gesamtmodell des M/M/1-Prozesses:
  • homogene Markov-Kette
  • Zustand = Zahl der Kunden (wartend + bedient)
  • beschrieben durch Übergangs-Graph
    • 
  • Vereinfachung für sehr kleine h
    • 
  • anschaulich: Wahrscheinlichkeit für gleichzeitige Ankunft und Bedienung sehr klein
    • wird vernachlässigt
    • → Ankunfts- und Bedienprozess nicht mehr unabhängig
    • aber kein Problem bei sehr kleinem h
  • Basis der folgenden Untersuchung
• Bestimmung der Gleichgewichtsverteilung π_i:
  • Schnittprinzip →
    • 
  • Einführung der Auslastung ρ
    • 
    • Name wird bald klar (s.u.)
  • durch Rekursion erhält man sofort
    • 
  • Normierungsbedingung
    • 
  • Fall ρ ≥ 1
    • Bedingung unerfüllbar
    • es existiert keine GGV
    • zu viele Kunden, Queue wächst immer weiter
  • Fall ρ < 1 über geometrische Reihe
    • 
  • Zustand im GGV also ~ G⁰(1-ρ)
• Auslastung A des Servers:
  • Anteil der Zeit, in der der Server beschäftigt ist
  • bei GGV also
    • 
  • bei ρ ≥ 1 geht A → 1
• Kennzahlen im Gleichgewicht:
  • mittlere Kundenzahl L
    • L = Erwartungswert von X im Gleichgewicht
    • π_i ~ G⁰(1-ρ), also
    • 
    • Streuung von L
    • 
  • mittlere Verweilzeit W eines Kunden
    • direkt mit Little
    • 
  • mittlere Wartezeit W_Q eines Kunden
    • 
  • mittlere Queuelänge L_Q über Little
    • 
• Bediensysteme bei stetiger Zeit:
  • Ankunftsprozess (bzw. Bedienprozess) sei wie immer Bernoulliprozess mit
    • p_a = λh, h klein
  • Zufallsvariable DT sei Zeit zwischen zwei Ankünften, dann ist
    • DT/h ~ G(λh) (Zahl der Takte zwischen zwei Ankünften)
    • für h → 0 gilt dann
    • DT ~ Ex(λ)
    • Beweis im Anhang
  • Zufallsvariable N sei Zahl der Ankünfte im Zeitintervall, dann
    • N ~ B(1/h, λh)
    • für h → 0 gilt dann (s. Poisson-Grenzwertsatz)
    • N ~ Po(λ)
  • umgekehrt kann man zeigen:
    • Für Ankunftsprozesse mit Markov-Eigenschaft sind die Zeitintervalle zwischen zwei Ankünften exponentiell verteilt
  • damit: Ergebnisse dieses Abschnitts gelten auch für stetiges M|M|1-System
• Aufgaben:
  • Aufgabe 24
  • Aufgabe 25