Première partie

Objectifs d'apprentissage

  • Utiliser des files afin de résoudre des problèmes.
  • Décrire à haut niveau les éléments d'une simulation.

Introduction

Il y a plusieurs applications des files dans la vie de tous les jours. Les files d'attente en sont un bon exemple. Afin d'améliorer le service à la clientèle, les gestionnaires cherchent des techniques permettant de réduire le temps moyen d'attente ou la longueur moyenne des files. Pour les compagnies aériennes, on a fait l'introduction de files d'attente séparées pour les voyageurs adhérant à un programme de fidélité (frequent flyers), en plus des files normales. Pour les supermarchés, nous avons fait l'ajout de files express, en plus des files normales. Ce sont là des façons de réduire le temps d'attente.

Cependant, les gestionnaires ont besoin d'outils leur permettant de comparer plusieurs scénarios afin d'améliorer les services à moindres coûts. Ils doivent donc connaître le temps moyen d'attente pour chaque scénario.

Il y a deux grandes approches permettant de déterminer ces statistiques. Une branche des mathématiques (Queueing theory) étudie spécifiquement ces questions. L'approche alternative consiste à développer une simulation informatique de ces systèmes et de mesurer les valeurs de certains paramètres à l'aide de la simulation.

Pour ce laboratoire, nous développons une simulation des files d'attente pour un supermarché ayant des files express ainsi que des files normales. Les files d'attente seront modélisées à l'aide de files (objets réalisant l'interface Queue).

Implémentation d'une file

Les méthodes

public interface Queue<E> {

    public abstract void enqueue( E obj );
    public abstract E dequeue();
    public abstract boolean isEmpty();
    public abstract int size();

}
  • void enqueue: ajouter un élément à l'arrière de la file
  • E dequeue: retire et retourne l'élément au début de la file
  • boolean isEmpty: retourne true si la file est vide, false autrement
  • int size: retourne le nombre d'éléments dans la file

Prenez le temps de déterminer les pré-conditions de chacune des méthodes.

L'implémentation avec des éléments chaînés

public class LinkedQueue<E> implements Queue<E> {

    private static class Elem<T> {

        private T value;
        private Elem<T> next;

        private Elem(T value, Elem<T> next) {
            this.value = value;
            this.next = next;
        }
    }

    private Elem<E> front;
    private Elem<E> rear;
	private int size;

	public LinkedQueue() {
		size = 0;
    }

    public int size() {
        return size;
    }

    public void enqueue(E value) {
        Elem<E> newElem;
        newElem = new Elem<E>(value, null );

        if (rear == null) {
            front = rear = newElem;
        } else {
            rear.next = newElem;
            rear = newElem;
        }
		size++;
    }

    public E dequeue() {
        E result = front.value;
        if (front != null & front.next == null) {
            front = rear = null;
        } else {
            front = front.next;
        }
		size--;
        return result;
    }

    public boolean isEmpty() {
        return front == null;
    }

}

Cette implémentation diffère de celle vue précédemment. Nous utilisons cette fois 3 variables d'instance, soit Elem front, elem rear et int size. Qu'est-ce que cet objet de type Elem? Il provient de la classe imbriquée statique privée Elem (private static class) dans laquelle sont sauvegardés la valeur réelle de l'élément de la pile (un type T générique!) ainsi qu'une référence au prochain Elem de la pile. Ainsi, front est une référence au premier Elem de la pile, tandis que rear est le dernier Elem de la pile.

Réflexion:

  • Dans quel cas est-ce que front == rear?
  • La pile peut-elle être pleine?
  • Sans la variable size, comment pourrions-nous déterminer la taille de notre pile?

Deuxième partie

Application d'une file à un problème de la vie courante

Les principales classes de la simulation Figure 1 : Les principales classes de la simulation.

Customer

Vous devez concevoir une classe afin de modéliser un client. Un client mémorise le moment de son arrivée, le nombre initial de produits (articles), ainsi que le nombre de produits qui n'ont pas encore été traités par le caissier. Le nombre maximal d'articles est le même pour tous les clients (MAX_NUM_ITEMS).

  • Quelles sont les variables d'instances ?
  • Quelles sont les variables de classes ?

L'unique constructeur de cette classe n'a qu'un paramètre. Ce dernier spécifie l'heure à laquelle le client s'est joint à la file. Pour le bien de cette exercice, le temps d'arrivée sera une variable de type int Le nombre initial d'articles est déterminé à l'aide de la formule suivante :

Random generator;  
generator = new Random();  
 
int numItems;  
numItems = generator.nextInt(MAX_NUM_ITEMS-1)+1;

Ainsi, nous nous assurons qu'il y ait au moins un (1) item.

Il y a aussi les méthodes d'instance suivantes :

  • int getArrivalTime() retourne l'heure d'arrivée ;
  • int getNumberOfItems() retourne le nombre d'articles à traiter ;
  • int getNumberOfServedItems() retourne le nombre total d'articles traités ;
  • serve() décrémente de 1 le nombre d'articles de ce client.

Cashier

Un caissier traite une file de clients. Il sert un client à la fois. Puisque le but de cette simulation est d’estimer la valeur de certains paramètres, tel que le temps moyen d’attente, le caissier doit aussi mémoriser certaines données telles que le nombre de clients servis, le temps total passé dans la file d’attente, ainsi que le nombre total d’articles traités.

  • Quelles sont les variables d’instance ainsi que les variables de classe ?

Cette classe n’a qu’un constructeur. Ce dernier n’a aucun paramètre. Il sert à initialiser les variables d’instance de ce caissier.

La méthode addCustomer(Customer c) ajoute un client à l’arrière de la file. La méthode int getQueueSize() retourne le nombre de clients qui attendent présentement.

La méthode serveCustomers(int currentTime) est un élément clé de la simulation. La méthode serveCustomers de chaque caissier est appelée exactement une fois par itération. Le paramètre currentTime servira à déterminer le temps total qui s’est écoulé depuis que le client a joint la file. Voici le comportement du caissier.

  • Si le caissier n’a pas de clients courant, le prochain client en file devient le client courant, sauf si la file est vide, auquel cas, le caissier sera inactif pour cette itération. Lorsqu’un client est retiré de la file, il faut comptabiliser le temps total passé à attendre ;
  • Le caissier traite un article (appel à la méthode serve() du client courant) ;
  • Si tous les articles du client courant ont été traités, le caissier comptabilise le nombre total d’articles traités. Il laisse son client partir (ce caissier n’a plus de client courant).

Il y aussi 3 méthodes d’instances qui donnent accès aux statistiques de ce caissier : temps total passé en file, nombre total d’articles traités, ainsi que le nombre total de clients servit : int getTotalCustomerWaitTime(), int getTotalItemsServed(), et int getTotalCustomersServed(). Finalement, la méthode String toString() retourne une chaîne de caractères qui présente les statistiques accumulées par ce caissier.

Voici les fichiers requis pour votre file de clients.

Simulation

La classe Simulation orchestre la simulation. Un objet Simulation à deux caissiers, l’un est responsable de la file express, l’autre s’occupe d’une normale. Cet objet mémorise aussi la durée de la simulation. Le constructeur crée les deux caissiers nécessaires.

La méthode run() réalise la boucle principale de la simulation. Au début, l’horloge est mise à 0, pour chaque itération, l’horloge avance d’une quantité fixe (TICK).

À chaque itération, la méthode run() doit :

  • Déterminer si un nouveau client est arrivé, et si oui, le placer la bonne file, selon le nombre d’articles achetés ;
  • S’assurer que tous les caissiers traitent un client ;
  • Incrémenter la valeur de temps.

À la fin de la simulation, la méthode affiche les statistiques.

  1. Exécutez la simulation plusieurs fois. Discutez vos observations avec vos voisins.Voici un exemple de sortie :
    SIMULATION ::  
    The duration (in seconds) of the simulation was 28800  
     
    EXPRESS LINE ::  
    The total number of customers served is 376  
    The average number of items per customer was 6  
    The average waiting time (in seconds) was 16  
     
    REGULAR LINE ::  
    The total number of customers served is 311  
    The average number of items per customer was 18  
    The average waiting time (in seconds) was 2597
  2. Hum, comme vous pouvez le constater le temps moyen d’attente pour la file express est très court (16 secondes !). Cependant, le temps d’attente à la file normale est très long (près de 45 minutes !). Le gérant du supermarché devra ajouter de nouvelles files, mais combien ? Afin de l’aider avec sa prise de décision, vous devez modifier ces classes afin d’y ajouter des caisses normales ;
  3. Si le temps le permet, faites plusieurs expériences où vous allez varier les paramètres de la simulation, changer la probabilité de l’arrivée d’un client, le nombre maximal d’articles, ainsi que le nombre de caisses, express ou normales.

 

Troisième partie

Quiz (1 point)

Pour l’implémentation d’une file à l’aide d’éléments chaînés, laquelle des deux implémentations suivantes est préférable ?

  1. Celle où la variable d’instance front désigne le premier noeud (objet de la classe Elem) de la structure chaînée :
    Celle où la variable d’instance front désigne le premier noeudFigure 1 : Celle où la variable d’instance front désigne le premier noeud
  2. Celle où la variable d’instance rear désigne le premier noeud (objet de la classe Elem) de la structure chaînée :
    Celle où la variable d’instance rear désigne le premier noeudFigure 2 : Celle où la variable d’instance rear désigne le premier noeud

Inscrivez votre réponse à la question ci-dessus dans le champ Soumission : de la page de soumission du devoir : https://uottawa.brightspace.com/

 

Table of Contents