In [4]:
%%javascript
$.getScript('http://kmahelona.github.io/ipython_notebook_goodies/ipython_notebook_toc.js')

Przykład - prosty system kolejkowy

Przykład na potwierdzenie, że w Pythonie można napisać symulacje DES prostego systemu kolejkowego M/M/1 w kilku liniach kodu

In [ ]:
# parametryzacja
N = 1000 # number of events (arrivals) to simulate
arrival_rate = 1 # parametr 'lambda' rozkladu wykladniczego, z ktorego generujemy kolejne zdarzenia
arrival = 0 # first arrival at time 0
endtime = 0 # init processing end time
In [ ]:
import random as rnd

# symulacja M/M/1
for i in range(N):
    arrival += rnd.expovariate(arrival_rate)
    starttime = max(arrival, endtime) # processing start time
    endtime = starttime + rnd.expovariate(1) # processing end time

Zeby sie przekonac czy symulacja działa, zbierzmy kilka uzytecznych statystyk z jej przebiegu:

In [ ]:
arrival = 0 # first arrival at time 0
endtime = 0 # init processing end time
arrhist = [] # to store arrival history
endhist = [] # to store history of processing end times
In [ ]:
N = 1000
for i in range(N):
    arrival += rnd.expovariate(arrival_rate)
    starttime = max(arrival, endtime) # processing start time
    endtime = starttime + rnd.expovariate(2) # processing end time
    arrhist.append(arrival) # store arrival history
    endhist.append(endtime) # store end time history

Wygenerujemy teraz wykres prezentujący dynamike dlugosci kolejki. Historie kolejnych zdarzen (pojawiania sie klientow w kolejce) mamy w wektorze arrhist. Dlugosc kolejki musimy niestety policzyc:

In [ ]:
qhist = [] # queue length history
for i in range(N):
    l = len([x for x in endhist[:i] if x >= arrhist[i]])
    qhist.append(l)

Teraz mozemy juz wygenerowac wykres. Skorzystamy w tym celu z funkcji plot pakietu matplotlib.

In [ ]:
# queue length plot
from matplotlib.pyplot import plot
In [ ]:
plot(arrhist, qhist) # queue length against arrival times

Powyzsza implementacja systemu M/M/1 ma kilka wad. Główną jest to, że wymaga dodatkowego kodu do policzenia dlugosci kolejki. Sposób w jaki to robimy nie jest optymalny (prosze sprobowac zwiekszyc ilosc zdarzen dziesieciokrotnie i sprawdzic jak wplynie to na wydajnosc symulacji). Poprawimy kod. Skorzystamy z metod append i pop, ktore pozwalaja korzystac z list jak z kolejek:

In [ ]:
# parametryzacja
N = 10000 # number of events (arrivals) to simulate
arrival_rate = 1 # parametr 'lambda' rozkladu wykladniczego, z ktorego generujemy kolejne zdarzenia
arrival = 0 # first arrival at time 0
endtime = 0 # init processing end time

arrhist = [] # to store arrival history
qhist = []   # to store queue length history 
q = [] # The Queue
In [ ]:
l = []
In [ ]:
l.append('Ala')
In [ ]:
l.pop(0)
In [ ]:
l
In [ ]:
for i in range(N):
    arrival += rnd.expovariate(arrival_rate)
    q.append(arrival)
    while endtime <= arrival:
        starttime = max(q.pop(0), endtime) # processing start time
        endtime = starttime + rnd.expovariate(2) # processing end time
    arrhist.append(arrival) # store arrival history
    qhist.append(len(q)) # store the queue size history

jak widac moglismy bez istotnego wplywu na wydajnosc wykonac przebieg dla 100x wiekszej ilosci zdarzen! takze wygenerowanie wykresu nie sprawia juz trudnosci:

In [ ]:
plot(arrhist, qhist) # queue length against arrival times

Rozkład wykładniczy

Wyjaśnimy, dlaczego korzystamy z rozkładu wykładniczego do generowania czasu pomiedzy kolejnymi zdarzeniami w symulacji systemu kolejkowego. Skorzystamy z modułu numpy:

In [ ]:
from numpy.random import exponential
from numpy import cumsum

Z rozkladu wykładniczego z parametrem $\lambda = 1$ wygenerujmy losowy wektor, który określi przerwy czasu pomiędzy kolejnymi klientami zjawiającymi się w kolejce

In [ ]:
arrivals = exponential(1,10000)
In [ ]:
arrivals
In [ ]:
%pylab inline

dla jasnosci wyswietlamy histogram. Korzystamy z funkcji hist pakietu matplotlib:

In [ ]:
from matplotlib.pyplot import hist
hist(arrivals, 40);

Jeśli teraz spojrzymy na rozkład tych zdarzeń na osi czasu symulacji, okaże sie ze jest on jednostajny:

In [ ]:
hist(cumsum(arrivals),10);

wygenerowany w ten sposob przebieg zdarzeń jest realizacją procesu Poissona.

Zad 2.7

Zmodyfikuj omówiony kod systemu kolejkowego tak, aby pierwszy klient przybywał w chwili t=0.

In [ ]:
 

Zad 2.8

Zmodyfikuj omówiony kod systemu kolejkowego wprowadzając drugi serwer z osobną kojeką i o innym rozkładzie czasu obsługi. Przybywający klient wybiera krótszą z kolejek.

In [ ]: