Répartition de charge entre deux ascenseurs

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.

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 :

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 :

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 :

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).

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.

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.