Les Newsletters Interstices
Interface de l'applet
    Niveau facile
    Niveau 1 : Facile

    Répartition de charge entre deux ascenseurs

    Culture & Société
    Algorithmes
    L’objectif de ce jeu est de répartir un groupe de personnes entre deux ascenseurs, sans dépasser leur charge maximale. Autrement dit, il s'agit de créer deux sous-groupes tels que le poids total de chaque sous-groupe soit inférieur à un poids maximal donné. Plus le niveau de difficulté augmente, plus la répartition doit être équilibrée.
    Avez-vous déjà, de bon matin, patienté devant une série d’ascenseurs au pied d’une tour de bureaux, et observé la foule se précipiter pour s’engouffrer dans le premier disponible ? Cette expérience nous a donné l’idée de ce jeu qui est l’illustration d’un problème de répartition.

    Dans la version un joueur, essayez de trouver une répartition plus équilibrée que celle de l’ordinateur pour les niveaux Débutant et Maître. Au niveau Expert, retrouvez la solution optimale calculée par l’ordinateur.
    Dans la version deux joueurs, trouvez une meilleure solution que votre adversaire.

    Pour accéder à l’applet Java, autorisez les applets du domaine https://interstices.info. Si votre navigateur n’accepte plus le plug-in Java, mais que Java est installé sur votre ordinateur, vous pouvez télécharger le fichier JNLP, enregistrez-le avant de l’ouvrir avec Java Web Start.
     

    Cette applet a été réalisée dans le cadre d’un projet étudiant de l’École Polytechnique de l’Université de Tours
    par Chi Thanh Bui, encadré par Yannick Kergosien, Christophe Lenté et Jean-Charles Billaut.
    Pour les personnages, merci à Andrew Scott du site DoppelMe.

    Les problèmes de répartition ont été étudiés sous diverses formes en recherche opérationnelle et continuent à l’être, car ils constituent un premier pas vers la résolution de problèmes plus complexes comme des problèmes de découpe, de chargement ou certains problèmes d’ordonnancement.

    Ces problèmes peuvent être envisagés selon différents points de vue. Certains sont décisionnels, c’est-à-dire qu’on se demande s’il est possible d’effectuer la répartition que l’on souhaite et qu’on attend comme réponse oui ou non. D’autres sont liés à un problème d’optimisation, c’est-à-dire qu’on cherche à effectuer la meilleure répartition possible suivant un critère prédéfini. La réponse est alors une valeur numérique.

    Le problème présenté ici combine ces deux approches.

    Une variante de problème d’empaquetage

    Parmi les problèmes de répartition les plus étudiés figure le bin packing, que l’on pourrait traduire par problème d’empaquetage. Dans sa version à deux dimensions, il modélise un problème de découpe. Le problème de chargement d’un ensemble de caisses dans un camion est un problème d’empaquetage à trois dimensions. Dans sa version à une dimension, à laquelle nous allons nous limiter, un contenant peut être vu comme un tube d’une hauteur donnée dans lequel on empile des objets cylindriques de hauteurs diverses. Plus précisément, on dispose d’un nombre fixe de tubes, tous de même hauteur H, et d’un ensemble d’objets dont les hauteurs sont connues mais éventuellement toutes différentes. On veut savoir s’il est possible de ranger tous les objets dans les tubes, sachant qu’aucun objet ne doit dépasser le haut d’un tube.

    Le jeu des ascenseurs, tel qu’il est présenté ici, est un problème à deux contenants. La charge maximale de chaque ascenseur correspond à la hauteur H des tubes et le poids des personnes aux hauteurs des objets.

    La réponse à un tel problème d’empaquetage peut être non, c’est-à-dire qu’il n’existe pas de rangement possible. Par exemple, on ne peut pas ranger 3 objets de hauteur 2 dans 2 tubes de hauteur 3. Si ce jeu des ascenseurs a toujours une solution, c’est que l’ordinateur s’arrange pour calculer une charge maximale en adéquation avec le poids des personnages. Pour cela, il commence par répartir les personnages entre les ascenseurs, puis il utilise comme charge maximale la charge de l’ascenseur le plus rempli. On est ainsi certain qu’il existe une solution au problème. Plus le niveau de jeu est élevé, plus la stratégie de répartition utilisée est sophistiquée et donc, plus la charge maximale est calculée au plus juste.

    Au niveau Débutant, l’ordinateur classe les personnes par poids croissant, puis les répartit alternativement dans les deux ascenseurs. Au niveau Maître, il classe les personnes par poids décroissant puis les affecte les unes après les autres à l’ascenseur le moins chargé. Au niveau Expert, l’ordinateur calcule la meilleure répartition possible, selon une méthode de programmation dynamique détaillée plus loin.

    Un cas pratique

    Bien sûr, dans la pratique, il est plutôt rare qu’on demande le poids des usagers en vue de leur indiquer l’ascenseur à prendre, et la charge des ascenseurs est prédéfinie en fonction de leurs caractéristiques techniques.

    Néanmoins, les méthodes utilisées ici peuvent s’appliquer, entre autres, à des cas simples de répartition du travail. Imaginons par exemple que des analyses doivent être réparties entre deux laborantins. Les deux laborantins ont la même durée quotidienne de travail et aucun ne veut effectuer d’heure supplémentaire. De plus, quand une analyse est commencée, elle ne peut pas être interrompue (pour être reprise le lendemain par exemple) et doit absolument être menée tout du long par le même laborantin. La durée d’une analyse peut être vue comme un poids et la durée de travail d’un laborantin comme une charge maximale, on retrouve alors exactement le problème des ascenseurs. Il est possible également d’étendre les techniques à plus de deux ascenseurs (ou laborantins).

    Méthodes utilisées par l’ordinateur

    Afin de mieux comprendre les différentes méthodes, comparons-les sur un exemple. Considérons cinq personnes A, B, C, D et E dont les poids respectifs sont 52 kg, 92 kg, 64 kg, 83 kg et 74 kg et voyons comment l’ordinateur les répartit et en déduit une charge maximale.

    Au niveau Débutant, l’ordinateur classe les personnes par poids croissants, c’est-à-dire ACEDB. Il les répartit ensuite alternativement dans les deux ascenseurs. Il mettra donc A dans le premier, puis C dans le second, puis E dans le premier, puis D dans le second et enfin B dans le premier. Ce qui fera pour l’ascenseur 1 une charge de 52 74 92 = 218 kg et de 64 83 = 147 kg pour le second. La charge maximale est alors fixée à 218 kg.

    Au niveau Maître, l’ordinateur classe les personnes par poids décroissants, c’est-à-dire BDECA. Il les affecte ensuite les unes après les autres à l’ascenseur le moins chargé. Les différentes étapes de la procédure sont détaillées dans le tableau ci-dessous.

    Charge de l’ascenseur 1 Charge de l’ascenseur 2 Décision
    Étape 1 : Les ascenseurs sont vides et on doit placer B 0 0 On met B dans un ascenseur pris au hasard, par exemple le 1.
    Étape 2 : B est placé et on doit placer D 92 0 On met D dans l’ascenseur 2 (le moins chargé)
    Étape 3 : B et D sont placés et on doit placer E 92 83 On met E dans l’ascenseur 2 (le moins chargé)
    Étape 4 : B, D et E sont placés et on doit placer C 92 83 74 = 157 On met C dans l’ascenseur 1 (le moins chargé)
    Étape 5 : B, C, D et E sont placés et on doit placer A 92 64 = 156 157 On met A dans l’ascenseur 1 (le moins chargé)
    Étape 6 : La répartition est terminée 156 52 = 208 157

     

    En résumé, l’ordinateur met B dans l’ascenseur 1, puis D dans le 2, puis E dans le 2, puis C dans le 1 et enfin A dans le 1, pour obtenir à la fin un poids total de 208 kg dans le premier ascenseur et de 157 kg dans l’autre. La charge maximale des ascenseurs est alors fixée à 208 kg.

    Au niveau Expert, l’ordinateur calcule la meilleure répartition possible. Il utilise pour cela une méthode de programmation dynamique. Avant de décrire cette méthode, il convient de faire deux remarques. Premièrement, les cinq personnes pèsent au total 365 kg. Cela veut dire que dans le meilleur des cas, il devrait y avoir 182,5 kg par ascenseur. Dans notre exemple, le poids de chaque personne étant un entier, on constate immédiatement que la répartition ne pourra pas être parfaitement équitable. Deuxièmement, dans ce cas de figure, l’ascenseur le plus chargé aura un poids supérieur à 182,5 kg et le moins chargé un poids inférieur à 182,5 kg, mais plus ces poids sont proches de 182,5 kg, plus la répartition sera équitable. La méthode de programmation dynamique décrite ci-dessous fait en sorte que l’ascenseur le moins chargé ait un poids le plus proche possible de la moyenne 182,5 kg, tout en restant inférieur.

    Nous allons étudier l’ensemble des charges envisageables de l’ascenseur 1, noté CH.

    S’il n’y a que la personne A, soit elle va dans l’ascenseur 1 soit elle va dans l’ascenseur 2. Dans le premier cas, l’ascenseur 1 a une charge de 52 kg et dans le second cas une charge nulle. Les deux cas sont résumés dans le tableau ci-dessous :

    Personnes dans l’ascenseur 1 Personnes dans l’ascenseur 2 Charge de l’ascenseur 1
    A   0 kg
    A 52 kg

     

    Ce que l’on peut résumer par CH(A)={0, 52}.

    Si on veut placer A et B, il y a quatre possibilités qui sont présentées dans le tableau ci-dessous :

    Personnes dans l’ascenseur 1 Personnes dans l’ascenseur 2 Charge de l’ascenseur 1
    A et B     0 kg
    A B   52 kg
    B A   92 kg
    A et B 144 kg

     

    Ce que l’on peut résumer par CH(AB)={0, 52, 92, 144}. Cela correspond à l’ensemble des charges possibles de l’ascenseur 1 si on ne répartit que les personnes A et B.

    Si maintenant on veut placer A, B et C, il y a cette fois huit possibilités :

    Personnes dans l’ascenseur 1 Personnes dans l’ascenseur 2 Charge de l’ascenseur 1
    A, B et C     0 kg
    A B et C   52 kg
    B A et C   92 kg
    A et B C 144 kg
    C A et B   64 kg
    A et C B 116 kg
    B et C A 156 kg
    A, B et C 208 kg

     

    Ce que l’on peut résumer par CH(ABC)={0, 52, 64, 92, 116, 144, 156, 208}. Cela correspond cette fois ci à l’ensemble des charges possibles de l’ascenseur 1 si on se limite à la répartition des personnes A, B et C.

    On constate qu’en continuant comme ça, les tableaux vont rapidement devenir très grands. Il y a 16 possibilités pour quatre personnes et 32 pour les cinq personnes. Mais on peut constater aussi que quand on prend en compte une personne supplémentaire X, l’ensemble des charges possibles de l’ascenseur 1 est égal à l’ensemble des charges possibles sans la personne X d’une part et à l’ensemble des charges possibles sans la personne X plus le poids de X d’autre part. Le premier cas correspond au fait que X monte dans l’ascenseur 2 et le second cas au fait que X monte dans l’ascenseur 1. Par exemple, CH(A)={0, 52}, CH(AB)= {0, 52, 92, 144}={0, 52, 0 92, 52 92} et CH(ABC)= {0, 52, 64, 92, 116, 144, 156, 208}={0, 52, 0 64, 92, 52 64, 92 64, 144, 144 64} (92 est le poids de B et 64 celui de C). Cela permet d’aller plus vite en calculant directement les ensembles CH. On va également accélérer les calculs en supposant qu’à la fin, c’est-à-dire quand les cinq personnes auront été réparties, l’ascenseur 1 sera le moins chargé des deux. Sa charge sera donc inférieure à 182,5 ce qui implique que l’on peut supprimer le 208 de CH(ABC). En utilisant ces deux remarques, on peut remplir le tableau ci-dessous qui contient les divers ensembles de charges jusqu’à CH(ABCDE).

    CH(A)     0   52
    CH(AB)     0   52   92 144
    CH(ABC)     0   52   64   92 116 144 156
    CH(ABCD)     0   52   64   83   92 116 135 144 147 156 175
    CH(ABCDE)     0   52   64   74   83   92 116 126 135 138 144 147 156 157 166 175

     

    Les charges supérieures à 182,5 ont été supprimées, puisqu’on suppose que l’ascenseur 1 est le moins chargé.

    Chaque case de ce tableau peut s’interpréter. En premier lieu, les nombres présents indiquent les valeurs possibles de la charge de l’ascenseur 1 après répartition des personnes de la ligne correspondante. Par exemple, sur la troisième ligne on trouve 116, cela veut dire qu’il est possible de répartir les trois personnes A, B et C de telle sorte qu’il y ait 116 kg dans l’ascenseur 1. Il est également possible, en effectuant une autre répartition de ces trois personnes, de mettre 144 kg dans l’ascenseur 1, ou n’importe quelle autre valeur de la ligne 3.

    Chaque case correspond donc à une répartition possible, il faut maintenant être capable de retrouver cette répartition. Pour cela, il faut se souvenir de la façon dont on a calculé les ensembles CH. Pour CH(ABC) par exemple, soit on a recopié CH(AB) et cela signifie que C n’est pas monté dans l’ascenseur 1, soit on a ajouté le poids de C à CH(AB) et ça signifie que C est monté dans l’ascenseur 1. Reprenons la valeur 116 de CH(ABC), elle n’apparaît pas dans CH(AB), cela veut donc dire qu’elle a été obtenue après addition du poids de C et donc que C est monté dans l’ascenseur 1. Et cela veut dire également qu’avant que C ne monte, autrement dit après répartition des deux premières personnes A et B, il y avait 116 – 64 = 52 kg dans l’ascenseur 1. Considérons maintenant la valeur 144 de CH(ABC), qui correspond donc à une autre répartition. La valeur 144 est également présente dans CH(AB), cela veut dire qu’elle a été recopiée de CH(AB) dans CH(ABC) et donc que C n’est pas monté dans l’ascenseur 1. Cela veut dire également que la charge de l’ascenseur 1 après répartition de A et B était déjà de 144 kg.

    À l’aide des remarques précédentes, on peut déduire la répartition optimale, c’est-à-dire celle qui équilibrera au mieux les charges des ascenseurs. Le cheminement dans le tableau est marqué par les cases jaunes.

    CH(A)     0   52
    CH(AB)     0   52   92 144
    CH(ABC)     0   52   64   92 116 144 156
    CH(ABCD)     0   52   64   83   92 116 135 144 147 156 175
    CH(ABCDE)     0   52   64   74   83   92 116 126 135 138 144 147 156 157 166 175

     

    En premier lieu, la charge de l’ascenseur 1 est de 175 kg, puisque c’est la plus grande valeur inférieure à 182,5 de CH(ABCDE). Mais 175 apparaît aussi sur la ligne 4, donc E ne monte pas dans l’ascenseur 1 et le poids dans cet ascenseur après répartition des personnes A, B, C et D est déjà de 175 kg. Par contre, 175 n’est pas dans CH(ABC), donc D monte dans l’ascenseur 1 et la charge de cet ascenseur après répartition de A, B et C est 175 – 83 = 92 kg (83 kg étant le poids de D). Ensuite, on constate que 92 est dans CH(AB), donc C ne monte pas dans l’ascenseur 1 et la charge de cet ascenseur après répartition de A et B est déjà de 92 kg. Enfin, 92 n’est pas dans CH(A), donc B monte dans l’ascenseur 1 et la charge de cet ascenseur après répartition de A est de 92 – 92 = 0 kg (92 kg étant le poids de B), donc A ne monte pas dans l’ascenseur 1.

    L’ascenseur 1 accueille donc B et D, pour un poids total de 83 92 = 175 kg et l’ascenseur 2 accueille A, C et E, pour un poids total de 52 64 74 = 190 kg. L’ordinateur fixe donc la charge maximale à 190 kg.

    Décomposer le problème en sous-problèmes et s’appuyer à chaque étape sur les résultats des étapes précédentes, c’est le principe de la programmation dynamique. En résumé, on commence à avancer en analysant toutes les situations possibles (sauf celles hors contraintes). Puis on choisit la solution qui répond le mieux au critère (ici, la répartition équitable des poids). Enfin, on repart en arrière pour trouver dans l’ensemble des étapes possibles celles qui correspondent à la solution.

    Newsletter

    Le responsable de ce traitement est Inria. En saisissant votre adresse mail, vous consentez à recevoir chaque mois une sélection d'articles et à ce que vos données soient collectées et stockées comme décrit dans notre politique de confidentialité

    Niveau de lecture

    Aidez-nous à évaluer le niveau de lecture de ce document.

    Si vous souhaitez expliquer votre choix, vous pouvez ajouter un commentaire (Il ne sera pas publié).

    Votre choix a été pris en compte. Merci d'avoir estimé le niveau de ce document !

    Christophe Lenté

    Voir le profil

    Yannick Kergosien

    Maître de conférences à l'Université de Tours (Laboratoire d'informatique) et à l'École Polytechnique de l'Université de Tours.

    Voir le profil

    Jean-Charles Billaut

    Professeur à l'Université de Tours, directeur du Laboratoire d'informatique et enseignant à l'École Polytechnique de l'Université de Tours, ancien président de l'association ROADEF.

    Voir le profil