Chapitre 72
Le renvoi de l’ascenseur

Résumé : optimiser le fonctionnement d’un ascenseur est une tâche intéressante : cela permet de réduire les temps d’attente et d’économiser les ressources. L’ordinateur est capable de simuler des files d’attente et le comportement des ascenseurs.

Mots-clés : simulation, modélisation, file d’attente.

Enoncé

L’exercice s’inspire du livre The Art of Computer Programming, Volume 1, Fundamental Algorithms, Reading, Massachussetts, 1973 et du rapport de gestion 2000 de l’entreprise Schindler, Ebikon, 2001.

Donald E. Knuth est un mathématicien américain, spécialiste d’informatique et d’algorithmique. Les gens qui travaillent dans ces domaines connaissent son grand ouvrage, The art of computer programming et, notamment, le volume 1, paragraphe 2.2.5. Lors de la rédaction de l’ouvrage, Donald E. Knuth s’est intéressé au fonctionnement de « son » ascenseur (celui qu’il apercevait depuis son bureau).

Le programme développé par Knuth simule l’ascenseur du bâtiment de mathématiques de l’Institut de technologie de Californie. Le bâtiment dispose de cinq étages : sous-sol, rez-de-chaussée, premier, deuxième et troisième étage. Il n’y a qu’un ascenseur qui dispose de contrôles automatiques et qui peut s’arrêter à chaque étage. A chaque étage, il y a deux boutons d’appel (un pour monter et un pour descendre, sauf, évidemment au sous-sol et au dernier étage). La situation décrite ici est celle observée par un utilisateur ; la situation est plus intéressante vue depuis l’ascenseur. L’ascenseur se trouve à tout moment dans un des trois états : il monte, il descend ou il est à l’arrêt. S’il est à l’arrêt et ne se trouve pas à l’étage numéro 2, l’ascenseur ferme ses portes et change d’état : il monte ou descend pour atteindre l’étage numéro 2 (c’est l’étage par défaut, puisque la plupart des utilisateurs emprunte l’ascenseur à cet étage). L’ascenseur met un certain temps à ouvrir et fermer les portes, à se déplacer entre les étages, à accélérer et à ralentir. Cet algorithme est le résultat de l’observation pendant plusieurs heures par l’auteur du comportement de l’ascenseur lors de l’écriture du paragraphe consacré à ce thème.

Le rapport de gestion de l’entreprise Schindler aurait pu inspirer Donald E. Knuth : l’entreprise y décrit en effet une nouvelle commande d’appel. « Les commandes d’ascenseurs traditionnelles fonctionnent selon le principe de l’appel de cabine. L’ascenseur est commandé à un étage donné en pressant un bouton. Le passager ne choisit sa destination qu’une fois dans l’ascenseur. La cabine s’arrête à chaque étage sélectionné par un occupant.

La commande d’appel de destination mise au point par Schindler enregistre la destination des passagers dès que ceux-ci commandent l’ascenseur. Au lieu de simplement appuyer sur un bouton, le passager indique sur le clavier numérique l’étage auquel il souhaite se rendre lorsqu’il appelle l’ascenseur. L’ordinateur enregistre les commandes et attribue un ascenseur à chaque personne en attente au moyen d’un affichage lumineux et/ou d’une voix électronique.

Les passagers qui se rendent au même étage sont dirigés vers la même cabine. Ce système permet de réduire le nombre des arrêts tout en évitant d’inutiles courses à vide.

Avec les commandes d’ascenseurs conventionnelles, les passagers empruntent la première cabine disponible, quelque soit l’étage auquel ils se rendent. De nombreux arrêts sont nécessaires pour libérer la cabine.

Avec la commande d’appel de destination, les passagers sont regroupés avant de pénétrer dans l’ascenseur. Ceux qui se rendent au même étage parviennent directement à destination, sans arrêts intermédiaires. Les étapes étant moins nombreuses, la cabine est plus rapidement disponible.

Le but du problème est de simuler le comportement d’un ascenseur et de mesurer les performances à fin de comparaison.

Indications

L’ascenseur décrit par D. Knuth est simulé par deux procédures, une pour les passagers et une pour l’ascenseur ; ces procédures décrivent tous les traitements à effectuer ainsi que les durées variables utilisées pour la simulation. Dans la description, on utilisera la variable temps pour simuler l’horloge. Les unités sont données en dixièmes de seconde. Il y a également d’autres variables :

étage,

la position courante de l’ascenseur ;

D1,

une variable qui vaut 0 sauf lorsque les gens entrent ou sortent de l’ascenseur ;

D2,

une variable qui passe à 0 si l’ascenseur s’est arrêté à un étage sans se déplacer pendant 30 sec ou plus ;

D3,

une variable qui vaut 0 sauf lorsque les portes s’ouvrent ou se ferment et si personne n’entre ou ne sort de l’ascenseur ;

état,

l’état actuel de l’ascenseur (monte, descend, à l’arrêt).

La procédure homme

Elle décrit l’arrivée d’un être humain devant l’ascenseur :

Pas M1

[Entrer, préparer le successeur.] Les variables suivantes sont déterminées : in, l’étage d’entrée, out, l’étage d’arrivée (différent de celui d’entrée), tempsentrée, le temps avant qu’un autre individu entre dans le système, tempsabandon, le temps avant qu’il abandonne l’idée de prendre l’ascenseur et se décide à aller à pieds. Lorsque ces valeurs sont calculées, le programme de simulation fait en sorte qu’un autre homme entre dans le système au temps temps+tempsentrée.

Pas M2

[Signaler et attendre.] Le but de cette étape est d’appeler l’ascenseur ; certains cas particuliers se produisent si l’ascenseur est déjà au bon étage. Si l’ascenseur est au même étage mais les portes se ferment, alors, il faut stopper l’activité et réouvrir les portes. Si les portes sont ouvertes à cet étage mais plus personne ne sort ni n’entre, l’ascenseur fait preuve de courtoisie en donnant à l’individu qui abandonné une deuxième chance. Dans tous les autres cas, l’individu monte ou descend suivant son choix. Si l’ascenseur est en position d’attente, il prend une décision suivant la méthode décrite plus bas.

Pas M3

[Entrer dans la file.] Insérer l’individu à la fin de la file d’attente queue(n), qui est une liste linéraire représentant les individus attendant dans la queue. L’individu cesse alors son activité. Il abandonnera son attente après le temps d’abandon sauf si l’ascenseur arrive ; dans ce cas, il entrera.

Pas M4

[Abandon.] L’individu décide que l’ascenseur est trop lent ou qu’un peu d’exercice lui fera du bien. Si l’ascenseur arrive au même moment, il reste et attend.

Pas M5

[Entrer.] On efface l’individu de la file d’attente, on le place dans l’ascenseur, ascenseur qui est une pile, au sens informatique du terme, qui représente les individus qui se trouvent dans l’ascenseur. Si l’état est à l’arrêt, on le fixe à monter ou descendre, on ferme la porte après 25 unités de temps. L’individu attend jusqu’à la sortie, lorsque l’ascenseur aura atteint l’étage désiré.

Pas M6

[Sortir.] On efface l’individu de la pile ascenseur et du système.

La procédure ascenseur

Elle décrit les actions de l’ascenseur ainsi que celles d’un individu qui entre ou sort :

Pas E1

[Attendre un appel.] L’ascenseur attend au deuxième étage avec les portes fermées. Si quelqu’un appuie le bouton, la sous-procédure de décision nous enverra au pas E3 ou E6.

Pas E2

[Changement d’état ?] Si l’ascenseur monte et qu’aucun appel n’est en attente au dessus de l’étage, il passe à l’état d’attente ou de descente suivant les appels des étages inférieurs. On tient un raisonnement équivalent si l’ascenseur descend.

Pas E3

[Ouvrir la porte.] On met des valeurs non nulles dans les variables D1 et D2. On fixe le départ de l’activité E9 après 300 unités de temps. Cette activité peut être interrompue par l’activité E6. On demande également le démarrage de l’activité E5 après 76 unités de temps. Ensuite on attent 20 unités de temps pour simuler l’ouverture des portes et on poursuit à E4.

Pas E4

[Permettre l’entrée ou la sortie.] Si quelqu’un dans l’ascenseur doit sortir, on choisit celui qui est entré le plus récemment ; il exécute son pas M6, on attend 25 unités de temps et on répète l’étape E4. Si plus personne ne doit sortir mais que, la file d’attente à l’étage est non vide, on choisit le premier de la queue ; il exécute son M5 ; on attend 25 unités de temps et on recommence le pas E4. Si la file est vide, on met D1 à 0, D3 à une valeur non nulle ; on attend une nouvelle activité. Le pas E5 nous enverra à E6 ou le pas E2 relancera E4.

Pas E5

[Fermer la porte.] Si la variable D1 est différente de 0, on attend 40 unités de temps et on répète cette étape (les portes se secouent un peu lorsque quelqu’un essaie encore d’entrer ou de sortir). Sinon on met D3 à 0 et on demande à l’ascenseur d’aller à l’étape E6 après 20 unités de temps. (Ceci simule la fermeture des portes après que les gens soient entrés ou sortis ; mais, si un individu arrive à cet étage pendant que les portes se ferment, elles s’ouvrent à nouveau comme indiqué à l’étape M2).

Pas E6

 [Préparer le déplacement.] On met à jour les variables : l’appel pour cet étage, les appels de montée et de descente vers cet étage à 0 (si l’état est descendre et monter respectivement pour ces deux derniers). On exécute ensuite la procédure de décision. Si l’état est l’arrêt même après le passage au travers de la procédure de décision, on va en E1. Sinon, si la variable D1 est différente de 0, on stoppe l’activité E9. Finalement, si l’ascenseur monte, on attend 15 unités de temps (pour permettre l’accélération de l’ascenseur) et on va en E7 ; si l’ascenseur descend, on attend 15 unités de temps et on va en E8.

Pas E7

[Monter un étage.] On modifie la variable de repère d’étage et on attend 51 unités de temps. Si quelqu’un attend ou désire sortir de l’ascenseur, on attend 14 unités de temps (décélération) et on va en E2. Sinon on répète l’étape.

Pas E8

[Descendre un étage.] Cette étape ressemble à E7 mais, les durées sont respectivement 61 et 23 unités de temps (c’est plus long de descendre que de monter).

Pas E9

 [Fixer un indicateur d’inactivité.] Mettre D2 à 0, et exécuter la procédure de décision (cette étape indépendante est lancée dans l’étape E3 mais elle est généralement annulée par l’étape E6).

La procédure décision

Cette procédure est exécutée à certaines étapes critiques, lorsqu’une décision doit être prise pour la direction suivante :

Pas D1

[Décision nécessaire ?] Si l’état est à l’arrêt, on quitte la procédure.

Pas D2

[Ouvrir la porte ?] Si l’ascenseur est à l’étape E1 et si les appels pour l’étage 2 sont non nuls, on démarre une activité E3 après 20 unités de temps et on quitte la procédure. (Si la procédure de décision est exécutée par l’activité indépendante E9, il est possible de placer l’ascenseur en activité E1).

Pas D3

 [Reste-t-il des demandes ?] Si des demandes sont pendantes, on va à l’étape D4. Sinon, on se déplace à l’étage 2 si la routine est appelée depuis E6 ; sinon enfin, on quitte la procédure.

Pas D4

[Fixer l’état.] Si l’étage est plus haut que le numéro indiqué d’appel on descend, sinon on monte.

Pas D5

[Ascenseur à l’arrêt ?] Si l’ascenseur est à l’arrêt et si l’appel est différent de l’étage 2, on exécute E6 après 20 unités de temps. On quitte alors la procédure.

Pour comprendre le système D. Knuth donne un exemple :

Dans cet exemple, l’ascenseur attend à l’étage 2 avec les portes fermées lorsqu’un individu arrive. Deux secondes plus tard, les portes s’ouvrent, encore deux secondes plus tard, il entre dans l’ascenseur ; lorsqu’il enfonce le bouton du troisième étage, l’ascenseur monte ; au troisième, l’ascenseur s’arrête, les portes s’ouvrent, l’individu quitte l’ascenseur et l’ascenseur retourne au deuxième étage.

La programmation du système de simulation mérite une attention particulière. A chaque instant de la simulation, on doit pouvoir simuler plusieurs individus dans le système ; on doit également permettre l’exécution simultanée des étapes E4, E5 et E9 si plusieurs personnes essaient de quitter l’ascenseur lorsque les portes se ferment. La simulation de l’exécution parallèle peut être programmée en utilisant une entité représentant un nœud qui inclut un champ indiquant l’heure d’exécution de la prochaine action et un champ indiquant la prochaine action à exécuter. Chaque action en attente est placée dans une liste à double chaînage (avant et arrière) ; il s’agit d’un échéancier trié selon l’heure d’exécution permettant l’exécution au bon moment. Le programme utilise également une structure de liste à double chaînage pour l’ascenseur et pour les files d’attente.

Solutions

Les solutions sont en cours de développement... Toute solution est la bienvenue.