À propos de la file d'attente

Que faites-vous?

Jetons un bref coup d'œil à la file d'attente, simulons-la et vérifions-la via un programme Python.

Qu'est-ce qu'une file d'attente?

Phénomène de congestion d'un système qui se comporte de manière probabiliste Une théorie pour l'analyse utilisant un modèle mathématique. Un domaine de la recherche opérationnelle.

Dans la file d'attente, ceux qui fournissent des services sont appelés serveurs et ceux qui fournissent des services sont appelés clients (clients). Les clients se produisent de manière probabiliste (ou déterministe) et s'alignent dans une matrice FIFO (First In First Out). Ensuite, il faut un temps probabiliste (ou défini) depuis le début pour recevoir le service, et une fois le service terminé, il se termine. Un tel mécanisme est appelé système ou système.

image

Le modèle le plus simple de la file d'attente est le modèle M / M / 1.

Qu'est-ce que le modèle M / M / 1?

Dans la file d'attente, il est important (A) comment il arrive, (B) comment il est desservi et (C) combien de serveurs il a. Écrivez ces trois informations comme A / B / C [symbole de Kendall](https://ja.wikipedia.org/wiki/%E3%82%B1%E3%83%B3%E3% Il est appelé 83% 89% E3% 83% BC% E3% 83% AB% E3% 81% AE% E8% A8% 98% E5% 8F% B7). En d'autres termes, M / M / 1 fait référence aux systèmes suivants.

  • Processus d'arrivée = M: Arrivée à Poisson (grosso modo, arrivée au hasard) --Service = M: Distribution exponentielle du temps de service --Nombre de serveurs = serveur 1: 1

M est [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), l'intervalle est [Distribution exponentielle](https://ja.wikipedia.org/wiki/%E6%8C%87%E6%95%B0%E5%88%86% S'il s'agit de E5% B8% 83), le nombre d'arrivées est distribution de Poisson % B3% E5% 88% 86% E5% B8% 83), et le comportement est le processus de Markov.

Paramètres dans la file d'attente

--λ (lambda): ** Taux d'arrivée moyen ** = Nombre moyen de clients arrivant en unité de temps [^ 1](inverse de l'intervalle d'arrivée moyen) --μ (mu): ** Taux de service moyen ** = Nombre moyen de clients qui terminent le service dans une unité de temps (inverse du temps de service moyen)

[^ 1]: L'heure unitaire est l'heure standard, qui peut être 1 heure ou 1 minute, et le créateur du modèle peut décider de ce qu'il aime.

On peut calculer que ρ calculé comme suit en utilisant ces paramètres est ** le taux d'utilisation moyen du serveur ** (décrit plus loin).

--ρ (faible): = $ \ frac {\ lambda} {\ mu} $

Statistiques dans la file d'attente

--Nombre moyen de personnes dans le système ($ L ): nombre prévu de personnes dans le système --Longueur moyenne de la file d'attente ( L_q ): nombre attendu de personnes dans la file d'attente --Temps moyen dans le système ( W ): valeur attendue du temps passé dans le système --Temps d'attente moyen ( W_q $): valeur attendue du temps dans la file d'attente

Expressions importantes dans la file d'attente

Petit officiel

[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) signifie que le nombre moyen à long terme de clients $ L $ dans un système stable est le produit du taux d'arrivée moyen à long terme $ λ $ et du temps moyen à long terme dans le système $ W $. La loi de l'égalité. (Même si le système est en file d'attente)

L = \lambda W
L_q = \lambda W_q

Cette formule vaut pour toute arrivée ou distribution de service. Cette formule est également intuitivement facile à comprendre. C'est,

Empiriquement, trois personnes se rendent à l'hôpital général toutes les heures. On sait également qu'en moyenne 6 personnes attendent dans la salle d'attente. Le temps d'attente moyen est estimé à 2 heures.

Cela signifie que nous avons calculé $ W_q = L_q / \ lambda = 6/3 = 2 $. Ce calcul vaut pour les moyennes. Le temps d'attente prévu pour «6 personnes alignées à mon arrivée» est de 6 fois le temps moyen de service (si le service est M).

Valeur théorique de la valeur statistique

Avec M / M / 1, la valeur théorique de la valeur statistique peut être obtenue relativement facilement. Même si vous ne mémorisez pas la valeur théorique, vous pouvez la calculer en vous rappelant les deux points suivants.

  1. La probabilité que le nombre de personnes dans le système augmente de ρ fois lorsqu'une personne augmente (dérivée du processus de Markov) --Petit officiel

Premièrement, la probabilité $ P_i $ qu'il y ait $ i $ personnes dans le système est de (1) à $ \ alpha \ rho ^ i $. Si vous ajoutez toutes les probabilités, il vaut 1, vous pouvez donc calculer comme suit.

\ alpha (1 + \ rho + \ rho ^ 2 + \ rho ^ 3 + \ cdots) = \ frac {\ alpha} {1- \ rho} = 1 à \ alpha = 1- \ rho
i Probabilité d'être dans le système P_i = (1- \ rho) \ rho ^ i

Vous pouvez également l'utiliser pour voir que l'utilisation moyenne du serveur = $ \ sum_ {i = 1} {P_i} = 1 --P_0 = 1- (1- \ rho) = \ rho $.

Vous pouvez également utiliser la formule de Little pour calculer:

Nombre moyen de personnes dans le système ($ L $) = $ \ sum_ {i = 0} {i P_i} = (1- \ rho) (\ rho + 2 \ rho ^ 2 + 3 \ rho ^ 3 + \ cdots) = \ frac {\ rho} {1- \ rho} $ Longueur moyenne de la file d'attente ($ L_q $) = $ Nombre moyen de personnes dans le système - Utilisation moyenne du serveur = L- \ rho = \ frac {\ rho ^ 2} {1- \ rho} $ Temps système moyen ($ W $) = $ L / \ lambda = \ frac {1} {\ mu- \ lambda} $ Temps d'attente moyen ($ W_q $) = $ L_q / \ lambda = \ frac {\ rho} {\ mu- \ lambda} $

Confirmé avec Python

La simulation de file d'attente est utile avec $ \ mbox {simpy} $ de Python. L'installation peut être effectuée avec "pip install simpy". Soit le taux d'arrivée λ = 1/5 et le taux de service μ = 1/3.

python3


import simpy, random, numpy as np
random.seed(1)
env = simpy.Environment() #Environnement de simulation
queue, intime = [], [] #Queue(Liste des heures d'arrivée)Et une liste de l'heure dans le système

#Événement d'arrivée
def arrive():
    while True:
        yield env.timeout(random.expovariate(1.0 / 5)) #Taux d'arrivée moyen 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)) #Taux de service moyen 1/3
        tm, queue = queue[0], queue[1:]
        intime.append(env.now - tm)

#Courir
env.process(arrive())
env.run(1000000)
print('total = %d clients, W = %.2f' % (len(intime), np.average(intime)))
>>>
total = 199962 clients, W = 7.53

La valeur théorique est $ W = \ frac {1} {\ mu- \ lambda} = \ frac {1} {\ frac {1} {3} - \ frac {1} {5}} = 7,5 $, soit environ Vous pouvez voir qu'ils correspondent.

c'est tout

Recommended Posts