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.

image

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 ): Expected value of the number of people in the system --Average queue length ( L_q ): Expected value of the number of people in the queue --Average system time ( W ): Expected value of time spent in the system --Average wait time ( W_q $): Expected value of time in queue

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.

  1. 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