Modélisation du temps d'attente

Dans ce jupyter, on se propose d'évaluer le temps d'attente de clients à des guichets en comparant la solution d'une unique file d'attente et la solution d'une file d'attente par guichet.

Dans ce jupyter :

Le temps sera modélisé par une variable globale temps qui sera incrémentée à chaque tour de boucle. Le tableau dispo indiquera, pour chaque guichet, le temps où se guichet sera occupé:

  • si la valeur est égale à 0, le guichet est libre
  • lorsqu'un nouveau client arrive au guichet, on choisi un temps de traitement au hasard entre 1 et 10.

On utilisera l'implémentation du type abstrait file contenu dans le fichier files.py :

In [2]:
from files import *
from random import *

help(filevide)
help(enfiler)
help(defiler)
help(sommet)
help(estvide)
help(long)

Help on function filevide in module files:

filevide()
    retourne une file vide

Help on function enfiler in module files:

enfiler(element, file)
    enfiler un element dans le file
    ne renvoie rien mais modifie la file

Help on function defiler in module files:

defiler(file)
    defiler l'élément au sommet de la file
    modifie la file et retourne l'élément

Help on function sommet in module files:

sommet(file)
    retourne le sommet de la file
    ne modifie pas le file

Help on function estvide in module files:

estvide(file)
    test si la file est vide

Help on function long in module files:

long(file)
    retourne la longueur de la file

1. Une unique file d'attente pour l'ensemble des guichets

Voici les varibales globales qui nous seront utiles :

In [3]:
NG = 5 #nombre de guichets
temps = 0 # le temps incrémenté à chaque tour de boucle
dispo = [0]*NG # au départ les guichets sont tous disponibles
file = filevide() #la file d'attente
total = 0 #temps d'attente total
servis = 0 #nombre de clients servis

Ecrire une fonction nouveau_client qui ajoute un client à la file d'attente. On ajoute l'heure d'arrivée de ce client dans la file.

In [3]:
def nouveau_client():
    ### BEGIN SOLUTION
    global temps, file
    enfiler(temps, file)
    #print('nv client',file)
    ### END SOLUTION

Ecrire la fonction servir qui :

  • enleve un client à la file d'attente
  • calcul le temps d'attente de ce client pour arriver au guichet et l'ajoute à total
  • incrémente servis
  • rempli le tableau dispo par une valeur aléatoire entre 1 et 10 à l'indice correspondant au guichet
In [4]:
def servir(numero_guichet):
    ### BEGIN SOLUTION
    #print('client servis',numero,dispo[numero])
    global temps, servis,total
    if not estvide(file):
        c = defiler(file)
        total = total + (temps-c)
        servis = servis + 1
        dispo[numero_guichet] = randint(1, 10)
        #print('client servis',numero,dispo[numero],total)
    ### END SOLUTION

Voici le corps du programme (qui devrait fonctionner si vous avez correctement écrit les fonctions servir et nouveau_client

In [5]:
#on rappel les variables globales pour les initialiser#

NG = 5
temps = 0 
dispo = [0]*NG
file = filevide()
total = 0 
servis = 0




for _ in range (100000): #on simule avec temps max 100 000 
    temps = temps+1
    
    if random() < 0.5: #en moyenne il y a un nouveau client toutes les 2 minutes
        nouveau_client()
    for numero in range(NG):
        if dispo[numero] == 0:
            servir(numero)
        else :
            dispo[numero] = dispo[numero] - 1
     
print("temps moyen d'attente :" + str(total / servis))
    

temps moyen d'attente :0.23067416178288083

2. Une file d'attente différente pour chacun des guichets

On imagine maintenant une file d'attente par guichet.

Le client se place au hasard sur la file d'un guichet.

Modifiez les fonctions nouveau_client et servir (le corps du programme a déjà été modifié, jetez y un oeil pour comprendre comment il fonctionne).

In [6]:
def nouveau_client():
    ### BEGIN SOLUTION
    global temps, file0, file1, file2, file3, file4
    
    num = randint(0, 4)
    #print(num)
    dico={0:file0, 1:file1, 2:file2, 3:file3, 4:file4}
    enfiler(temps, dico[num])
    #print('nv client',file)
    ### END SOLUTION


def servir(numero_guichet):
    ### BEGIN SOLUTION
    #print('client servis',numero,dispo[numero])
    global temps, servis, total
    dico={0:file0, 1:file1, 2:file2, 3:file3, 4:file4}
    if not estvide(dico[numero_guichet]):
        c = defiler(dico[numero_guichet])
        total = total + (temps-c)
        servis = servis + 1
        dispo[numero_guichet] = randint(1, 10)
        #print('client servis',numero,dispo[numero],total)
    ### END SOLUTION



NG = 5
temps = 0 
dispo = [0]*NG
file0 = filevide()
file1 = filevide()
file2 = filevide()
file3 = filevide()
file4 = filevide()
total = 0 
servis = 0




for _ in range (100000): #on simule avec temps max 100 000 
    temps = temps + 1
    
    if random() < 0.5: #en moyenne il y a un nouveau client toutes les 2 minutes
        nouveau_client()
    for numero in range(NG):
        if dispo[numero] == 0:
            servir(numero)
        else :
            dispo[numero] = dispo[numero] - 1
     
print("temps moyen d'attente :"+str(total / servis))

temps moyen d'attente :6.52131914723411

3. Des clients malins

On imagine maintenant une file d'attente par guichet mais des clients un peu plus malins qui se placent dans la file la plus courte (dans cette implémentation une file est une liste de Python, on peut donc utiliser la fonction len)

Modifiez les fonctions nouveau_client et servir (le corps du programme a déjà été modifié)

In [7]:
def nouveau_client():
    ### BEGIN SOLUTION
    global temps, file0, file1, file2, file3, file4
    dico={0:file0, 1:file1, 2:file2, 3:file3, 4:file4}
    
    mini = 0
    for num in range(1, 5):
        #print(num)
        #print(len(dico[num]))
        if long(dico[num]) < long(dico[mini]):
            mini = num
            #print(mini)
            
    #print(mini)
   
    enfiler(temps, dico[mini])
    #print('nv client',file)
    ### END SOLUTION


def servir(numero):
    ### BEGIN SOLUTION
    #print('client servis',numero,dispo[numero])
    global temps, servis, total
    dico={0:file0, 1:file1, 2:file2, 3:file3, 4:file4}
    if not estvide(dico[numero]):
        c = defiler(dico[numero])
        total = total + (temps-c)
        servis = servis + 1
        dispo[numero] = randint(1, 10)
        #print('client servis',numero,dispo[numero],total)
    ### END SOLUTION



NG = 5
temps = 0 
dispo = [0]*NG
file0 = filevide()
file1 = filevide()
file2 = filevide()
file3 = filevide()
file4 = filevide()
total = 0 
servis = 0




for _ in range (100000): #on simule avec temps max 100 000 
    temps = temps + 1
    
    if random() < 0.5: #en moyenne il y a un nouveau client toutes les 2 minutes
        nouveau_client()
    for numero in range(NG):
        if dispo[numero] == 0:
            servir(numero)
        else :
            dispo[numero] = dispo[numero] - 1
     
print("temps moyen d'attente :"+str(total / servis))

temps moyen d'attente :3.628810079141997

4. Conclusion

Quelle est donc selon vous la meilleure solution ?

votre réponse ici :