[PYTHON] About the queue
What do you do?
Let's take a brief look at the queue and simulate and verify it through a Python program.
What is a queue?
The congestion phenomenon of a system that behaves stochastically Theory for analysis using mathematical models. A field of operations research.
In the queue, the one that provides the service is called the server, and the one that provides the service is called the customer (client). Customers occur probabilistically (or deterministically) and line up in a FIFO (First In First Out) matrix. Then, it takes a probabilistic (or definite) time from the beginning to receive the service, and after the service ends, it exits. Such a mechanism is called a system or system.
The simplest model in the queue is the M / M / 1 model.
What is the M / M / 1 model?
In the queue, (A) how it arrives, (B) how it is serviced, and (C) how many servers it has are important. Write these three pieces in a format like A / B / C [Kendall's notation](https://ja.wikipedia.org/wiki/%E3%82%B1%E3%83%B3%E3% It is called 83% 89% E3% 83% BC% E3% 83% AB% E3% 81% AE% E8% A8% 98% E5% 8F% B7). In other words, M / M / 1 refers to the following systems.
--Arrival process = M: Poisson arrival (roughly speaking, randomly arriving) --Service = M: Service time exponential distribution --Number of servers = 1: 1 server
M is [Markov](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%AB%E3%82%B3%E3%83%95%E9%81%8E%E7 % A8% 8B) (Markov), the interval is [Exponential distribution](https://ja.wikipedia.org/wiki/%E6%8C%87%E6%95%B0%E5%88%86% If it is E5% B8% 83), the number of arrivals is Poisson distribution % B3% E5% 88% 86% E5% B8% 83), and the behavior is a Markov process.
Parameters in the queue
--λ (Lambda): ** Average arrival rate ** = Average number of customers arriving in unit time [^ 1](reciprocal of average arrival interval) --μ (Mu): ** Average service rate ** = Average number of customers who end service in a unit time (reciprocal of average service time)
[^ 1]: The unit time is the standard time, which can be 1 hour or 1 minute, and the model creator can decide what he / she likes.
It can be calculated that ρ calculated as follows using these parameters will be ** average utilization of the server ** (described later).
--ρ (low): = $ \ frac {\ lambda} {\ mu} $
Statistics in the queue
--Average number of people in the system ($ L
Important expressions in the queue
Little official
[Little Official](https://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%88%E3%83%AB%E3%81%AE%E6%B3%95%E5 % 89% 87) means that the long-term averaged number of customers $ L $ in a stable system is the product of the long-term averaged arrival rate $ λ $ and the long-term averaged in-system time $ W $. The law of equality. (Same for queuing the system)
L = \lambda W L_q = \lambda W_q
This formula holds for any arrival or service distribution. This formula is also intuitively easy to understand. That is,
Experience shows that three people come to the general hospital every hour. It is also known that an average of 6 people are waiting in the waiting room. The average waiting time is considered to be 2 hours.
This means that we have calculated $ W_q = L_q / \ lambda = 6/3 = 2 $. This calculation holds for the mean. The expected waiting time for "6 people lined up when I arrived" is 6 x average service time (if the service is M).
Theoretical value of statistics
With M / M / 1, the theoretical value of the statistical value can be obtained relatively easily. Even if you don't memorize the theoretical value, you can calculate it by remembering the following two points.
- The probability of the number of people in the system increases by ρ times when one person increases (derived from the Markov process). --Little official
First, the probability $ P_i $ that there are $ i $ people in the system is from (1) to $ \ alpha \ rho ^ i $. If you add all the probabilities, it is 1, so you can calculate as follows.
\ alpha (1 + \ rho + \ rho ^ 2 + \ rho ^ 3 + \ cdots) = \ frac {\ alpha} {1-\ rho} = 1 to \ alpha = 1- \ rho Probability of i people in the system P_i = (1- \ rho) \ rho ^ i
You can also use this to see that the average server utilization = $ \ sum_ {i = 1} {P_i} = 1 --P_0 = 1-(1- \ rho) = \ rho $.
You can also use Little's formula to calculate:
Average number of people in the system ($ L $) = $ \ sum_ {i = 0} {i P_i} = (1- \ rho) (\ rho + 2 \ rho ^ 2 + 3 \ rho ^ 3 + \ cdots) = \ frac {\ rho} {1- \ rho} $ Average queue length ($ L_q $) = $ Average number of people in the system-Average server utilization = L-\ rho = \ frac {\ rho ^ 2} {1- \ rho} $ Average system time ($ W $) = $ L / \ lambda = \ frac {1} {\ mu-\ lambda} $ Average wait time ($ W_q $) = $ L_q / \ lambda = \ frac {\ rho} {\ mu-\ lambda} $
Check with Python
Queue simulation is useful with Python's $ \ mbox {simpy} $. You can install it with "pip install simpy". Let the arrival rate λ = 1/5 and the service rate μ = 1/3.
python3
import simpy, random, numpy as np
random.seed(1)
env = simpy.Environment() #Simulation environment
queue, intime = [], [] #Queue(List of arrival times)And a list of in-system time
#Arrival event
def arrive():
while True:
yield env.timeout(random.expovariate(1.0 / 5)) #Average arrival rate 1/5
env.process(into_queue())
#Queue
def into_queue():
global queue
queue.append(env.now)
if len(queue) > 1:
return
while len(queue) > 0:
yield env.timeout(random.expovariate(1.0 / 3)) #Average service rate 1/3
tm, queue = queue[0], queue[1:]
intime.append(env.now - tm)
#Run
env.process(arrive())
env.run(1000000)
print('total = %d clients, W = %.2f' % (len(intime), np.average(intime)))
>>>
total = 199962 clients, W = 7.53
The theoretical value is $ W = \ frac {1} {\ mu-\ lambda} = \ frac {1} {\ frac {1} {3}-\ frac {1} {5}} = 7.5 $, which is approximately You can see that it matches.
that's all
Recommended Posts