L'invention concerne le domaine du placement et plus particulièrement le domaine de l'automatisation du placement.

La logistique est un domaine qui a connu un formidable développement, et qui est devenu un des cœurs du développement du commerce électronique. Grâce à des méthodes toujours plus innovantes, le coût de stockage des produits a baissé, permettant de gérer des entrepôts à bas coût, le gain étant reversé aux consommateurs.

Afin d'améliorer encore l'efficacité de ces entrepôts, une automatisation avancée est souhaitable, optimisée pour le placement par groupes d'objets similaires. Un tel exemple se pose dans le cas d'un entrepôt dans lequel des rayonnements sont agencés en rangs répartis de part et d'autre d'une allée centrale. Un ou plusieurs robots sont chargés du placement, avec la contrainte que ceux-ci ne peuvent pas reculer dans l'allée, et qu'un robot qui est engagé dans un rang bloque tous les rangs ultérieurs de l'allée.

À ce jour, il n'existe pas de solution satisfaisante pour traiter ce genre de situation, en particulier lorsque les objets à placer arrivent en vrac.

L'invention vient améliorer la situation.

A cet effet, l'invention propose un dispositif de placement comprenant une mémoire recevant des données d'emplacements désignant des emplacements agencés en rangs numérotés de manière consécutives à partir de la valeur un et accessibles par un unique chemin à partir d'une entrée de sorte que l'accès à un emplacement d'un rang donné n'est possible que si tous les rangs dont le numéro est inférieur à celui du rang donné sont libres sur le chemin, des données de réservation associant des données d'identifiant et des données d'emplacement, et des données de groupe associant des identifiants entre eux, chaque groupe comprenant un nombre d'identifiants supérieur ou égal à deux, le dispositif comprenant en outre un trieur agencé pour recevoir un identifiant courant et un rang courant, et exécuter les opérations suivantes : a) déterminer si l'identifiant courant est présent dans les données de réservation, et si c'est le cas, retourner des données de placement associant l'identifiant courant avec les données d'emplacement correspondantes, et si non,

b) déterminer si l'identifiant courant est présent dans les données de groupe, et, si c'est le cas, retourner des données de placement en fonction de la présence de données de placement d'un ou plusieurs des identifiants associés à l'identifiant courant dans les données de groupe et/ou du rang courant, et si non,

c) déterminer si l'identifiant courant peut être associé avec un emplacement dans le rang courant, et si c'est le cas, retourner des données de placement correspondantes, et si non, décrémenter la valeur du rang courant d'une première quantité choisie et répéter l'opération c) jusqu'à retourner des données de placement, et

d) une fois des données de placement retournées pour l'identifiant courant, décrémenter la valeur du rang courant d'une deuxième quantité choisie. Ce dispositif permet d'optimiser la procédure de placement, en affectant un emplacement qui optimise le temps de rangement compte tenu de l'état d'occupation de l'allée centrale.

Dans diverses variantes, le dispositif pourra présenter une ou plusieurs des caractéristiques suivantes :- le trieur est agencé pour exécuter l'opération b), lorsque l'identifiant courant est présent dans les données de groupe et qu'un des identifiants associés à l'identifiant courant dans les données de groupe est associé à des données de placement et présente dans le même rang un emplacement libre et immédiatement voisin, en retournant des données de placement associant l'identifiant courant avec des données d'emplacement associant l'identifiant courant et ledit emplacement libre et immédiatement voisin,

- le trieur est agencé pour exécuter l'opération b), lorsque l'identifiant courant est présent dans les données de groupe et qu'aucun des identifiants associés à l'identifiant courant dans les données de groupe n'est associé à des données de placement, en déterminant si le rang courant comprend suffisamment d'emplacements libres pour stocker tous les identifiants des données de groupes dans lesquelles l'identifiant courant est présent, et si c'est le cas, retourner des données de placement associant l'identifiant courant et un desdits emplacements libres, et si non, décrémenter la valeur du rang courant d'une troisième quantité choisie jusqu'à trouver un rang courant comprend suffisamment d'emplacements libres pour stocker tous les identifiants des données de groupes dans lesquelles l'identifiant courant est présent,

- le trieur est agencé pour exécuter l'opération c) en déterminant de manière préalable s'il reste des données de groupes dont aucun identifiant n'est associé à des données de placement, et si c'est le cas, exécuter l'opération c), et si non, déterminer s'il reste plus de groupes d'emplacements contigus que de groupes dont aucun identifiant n'est associé à des données de placement, et si c'est le cas, exécuter l'opération c), et si non, décrémenter la valeur du rang courant d'une quatrième quantité choisie jusqu'à trouver un rang courant comprenant un emplacement libre qui ne correspond pas à des emplacements libres contigus devant être associés à des identifiants de données de groupes,

- le trieur est agencé pour décrémenter la valeur du rang courant d'une première quantité choisie ou d'une deuxième quantité choisie ou d'une troisième quantité choisie ou d'une quatrième quantité choisie en définissant le rang courant comme le plus éloigné de l'entrée lorsque le rang courant décrémenté est inférieur à 1,

- la première quantité choisie ou la troisième quantité choisie ou la quatrième quantité choisie sont égales à un,

- la deuxième quantité choisie est égale à deux, et

- le trieur est agencé pour exécuter les opérations b) et c) en maintenant une liste de couples associant chacun d'une part une partition d'emplacements contigus rassemblés en un ou plusieurs groupes et d'autre part un compteur du nombre de fois où cette partition doit être utilisée.

L'invention concerne également un procédé de placement comprenant :

a) recevoir des données d'emplacements désignant des emplacements agencés en rangs numérotés de manière consécutives à partir de la valeur un et accessibles par un unique chemin à partir d'une entrée de sorte que l'accès à un emplacement d'un rang donné n'est possible que si tous les rangs dont le numéro est inférieur à celui du rang donné sont libres sur le chemin, des données de réservation associant des données d'identifiant et des données d'emplacement, et des données de groupe associant des identifiants entre eux, chaque groupe comprenant un nombre d'identifiants supérieur ou égal à deux,

b) recevoir un identifiant courant et un rang courant, et :

bl) déterminer si l'identifiant courant est présent dans les données de réservation, et si c'est le cas, retourner des données de placement associant l'identifiant courant avec les données d'emplacement correspondantes, et si non,

b2) déterminer si l'identifiant courant est présent dans les données de groupe, et, si c'est le cas, retourner des données de placement en fonction de la présence de données de placement d'un ou plusieurs des identifiants associés à l'identifiant courant dans les données de groupe et/ou du rang courant, et si non,

b3) déterminer si l'identifiant courant peut être associé dans un emplacement associé au rang courant, et si c'est le cas, retourner des données de placement correspondantes, et si non, décrémenter la valeur du rang courant d'une première quantité choisie et répéter l'opération b3) jusqu'à retourner des données de placement,

b4) utiliser les données de placement afin de placer une entité liée à l'identifiant courant à l'emplacement correspondant, et décrémenter la valeur du rang courant d'une deuxième quantité choisie.

Dans ce procédé, les opérations b2) et b3) peuvent être réalisées en maintenant une liste de couples associant chacun d'une part une partition d'emplacements contigus rassemblés en un ou plusieurs groupes et d'autre part un compteur du nombre de fois où cette partition doit être utilisée.

D'autres caractéristiques et avantages de l'invention apparaîtront mieux à la lecture de la description qui suit, tirée d'exemples donnés à titre illustratif et non limitatif, tirés des dessins sur lesquels :

- la Figure 1 représente un diagramme générique d'un dispositif selon l'invention,

- la Figure 2 représente un schéma fonctionnel d'une boucle de fonctionnement du dispositif de la Figure 1 ,

- la Figure 3 représente un exemple de réalisation d'une première fonction de la Figure 2, - la Figure 4 représente un exemple de réalisation d'une deuxième fonction de la Figure 2,

- la Figure 5 représente un exemple de réalisation en variante d'une première fonction de la Figure 2, et

- la Figure 6 représente un exemple de réalisation en variante d'une deuxième fonction de la Figure 2.

Les dessins et la description ci-après contiennent, pour l'essentiel, des éléments de caractère certain. Ils pourront donc non seulement servir à mieux faire comprendre la présente invention, mais aussi contribuer à sa définition, le cas échéant.

La présente description est de nature à faire intervenir des éléments susceptibles de protection par le droit d'auteur et/ou le copyright. Le titulaire des droits n'a pas d'objection à la reproduction à l'identique par quiconque du présent document de brevet ou de sa description, telle qu'elle apparaît dans les dossiers officiels. Pour le reste, il réserve intégralement ses droits.

La Figure 1 représente un diagramme générique d'un dispositif 2 selon l'invention. Le dispositif 2 comprend une mémoire 4 et un trieur 6.

La mémoire 4 peut être réalisée sous la forme de tout type de stockage de données propre à recevoir des données numériques : disque dur, disque dur à mémoire flash (SSD en anglais), mémoire flash sous toute forme, mémoire vive, disque magnétique, stockage distribué localement ou dans le cloud, etc. Les données calculées par le dispositif peuvent être stockées sur tout type de mémoire. Ces données peuvent être effacées après que le dispositif ait effectué ses tâches ou conservées.

La mémoire 4 contient des données d'emplacement qui décrivent l'ensemble des emplacements disponibles pour placer les objets. Ces emplacements sont organisés par rangs qui présentent chacun un numéro. Dans l'exemple décrit ici, les rangs présentent des numéros croissants à partir de 1, le rang 1 étant le plus proche de l'entrée. Selon les variantes, les numéros pourront être différents, mais resteront dans le cadre de l'invention dès lors que le parcours des rangs se fait selon un sens unique.

La mémoire 4 reçoit également :

- des données d'identifiant qui permettent d'identifier une entité à placer,

- des données de réservation, qui associent des données d'identifiant et des données d'emplacement, ce qui permet d'imposer le placement d'une entité donnée à un emplacement choisi,

- des données de groupe, qui associent des données d'identifiant entre eux, afin que des entités associées dans des données de groupe soient placés dans des emplacement contigus.

Dans l'exemple décrit ici, les données de groupe ne contiennent pas plus d'identifiants qu'il n'y a d'emplacements dans un rang. Dans le cas où il serait souhaité d'utiliser des données de groupe présentant plus d'identifiants qu'il n'y a d'emplacements dans les rangs, celles-ci seraient divisées en sous-groupes distincts jusqu'à ce que chaque sous- groupe présente un nombre d'identifiants inférieur ou égal au nombre d'emplacements dans le rang. De plus, les rangs peuvent comprendre des nombres différents d'emplacements.

Le trieur 6 peut être réalisé sous la forme d'un code informatique approprié exécuté sur un ou plusieurs processeurs. Par processeurs, il doit être compris tout processeur adapté au calcul de positions et de dérivées de ces positions. Un tel processeur peut être réalisé de toute manière connue, sous la forme d'un microprocesseur pour ordinateur personnel, d'une puce dédiée de type FPGA ou SoC (« System on chip » en anglais), d'une ressource de calcul sur une grille, d'un microcontrôleur, ou de toute autre forme propre à fournir la puissance de calcul nécessaire à la réalisation décrite plus bas. Un ou plusieurs de ces éléments peuvent également être réalisés sous la forme de circuits électroniques spécialisés tel un ASIC. Une combinaison de processeur et de circuits électroniques peut également être envisagée. La Figure 2 représente un exemple d'une boucle de fonctionnement du dispositif 2 selon l'invention. Dans une opération 200, le dispositif 2 exécute une fonction InitQ qui prépare le fonctionnement de l'opération suivante. La Figure 3 représente un exemple de mise en œuvre de la fonction Init().

Dans une opération 300, le trieur 6 reçoit des données d'emplacement PI, des données de réservation BkS, et initialise un compteur de rang i à 1 et un tableau de groupes potentiels PG[]. Dans l'exemple décrit ici, les données d'emplacement PI sont un tableau qui comprend pour chaque rang le nombre d'emplacements. En variantes, par exemple lorsque tous les rangs comprennent le même nombre d'emplacements, les données d'emplacements PI peuvent être remplacées par un couple indiquant le nombre de rangs et le nombre d'emplacements par rang. Dans l'exemple décrit ici, les données de réservation BkS comprennent des triplets qui associent un couple (emplacement ; rang) et un identifiant. Le couple (emplacement ; rang) pourrait être stocké de toute autre manière appropriée, explicite ou implicite.

Ensuite, dans une opération 310, une fonction Len() calcul le nombre de rang NR des données d'emplacement Pl. Une boucle est alors lancée dans une opération 320 avec un test qui vérifie que l'indice i est inférieur ou égal à NR.

Dans la boucle, une fonction Add() est exécutée dans une opération 330, et reçoit comme argument le rang courant i, les données de réservation BkS, et le tableau de groupes potentiels PG[]. La fonction Add() a pour but de déterminer, dans un rang donnée, quels sont les groupes potentiels qui pourraient y être logés. Par exemple, si dans un rang donné, les données de réservation BkS indiquent qu'un groupe de 3 entités, et deux groupes de 2 entités sont possibles, alors le premier élément du tableau de groupes potentiels PG[] est augmenté de 2, et le deuxième élément est augmenté de 1.

Ensuite, l'indice i est incrémenté dans une opération 340 et la boucle se répète jusqu'à avoir parcouru tous les rangs, et la fonction InitQ se termine dans une opération 399. Après cette opération, le trieur 6 exécute une fonction Place() dans une opération 210. La Figure 4 représente un exemple de réalisation de la fonction Place(). La fonction Place() réalise une affectation d'emplacement en partant du rang le plus éloigné et en cherchant à optimiser le placement selon trois possibilités :

1) Une entité à placer a un emplacement réservé,

2) Une entité à placer appartient à un groupe,

3) Une entité à placer ne satisfait ni 1), ni 2)

Afin d'optimiser le placement, et comme les entités arrivent en vrac, la fonction Place() maintient à la fois les données de groupes au fur et à mesure des placements, mais également un tableau GTBL[] des groupes restant à placer. Ainsi, dans une opération 400, la fonction Place() reçoit comme arguments les données de réservation BkS, les données d'emplacement PI, le nombre de rangs NR, les données de groupe AG, et la liste des entités arrivant en vrac L.

Dans une opération 402, une fonction Min() définit le tableau GTBL[] à partir de données de groupe AG et du tableau de groupes potentiels PG[]. Pour cela, chaque élément du tableau GTBL[] est tiré d'une comparaison entre la valeur de l'élément correspondant du tableau de groupes potentiels PG[] et le nombre de groupes présentant le nombre d'éléments correspondants dans les données de groupe AG. Dans certaines situations, cela peut être réalisé en gardant le minimum entre ces deux valeurs. Par exemple, si le tableau PG[] contient 5 pour le troisième élément (c'est-à- dire qu'il y a 5 groupes potentiels de 4 entités dans les données d'emplacement en tenant compte des données de réservation), et que les données de groupe AG indiquent qu'il y a 3 groupes de 4 entités, alors le tableau GTBL[] recevra la valeur 3 pour son troisième élément. Ainsi, le trieur 6 ne cherchera pas à placer plus de groupes que cela n'est possible. Dans des cas plus complexes, comme quatre emplacements contigus peuvent loger deux groupes de deux entités, ou un groupe de trois entités ou un groupe de quatre entités, mais pas tout cela simultanément, la fonction Min() est agencée pour mettre en œuvre des critères de choix de groupes. En effet, il existe une forte possibilité qu'il ne soit pas possible de placer tous les groupes qui sont prévus pour être ensemble. La fonction Min() sera donc optimisée pour placer un maximum de groupes de grands nombre, ou pour placer le nombre total de groupes dont la somme des éléments est maximale, ou encore en appliquant une approche « premier arrivé, premier servi ». Ensuite, un indice i de rang courant est initialisé avec la valeur NR dans une opération 404. Après cette initialisation, une boucle est lancée dans laquelle chaque identifiant de la liste d'entités en vrac est dépilé et se voit affecter des données de placement. Ainsi, dans une opération 406, une fonction Pop() dépile la liste L et retourne un triplet comprenant un identifiant d'entité id, un emplacement réservé s et une liste d'identifiants de groupe M. Si l'entité n'a pas d'emplacement réservé, alors s contient une valeur nulle, et de même pour la liste M.

Lorsque la liste L n'est pas vide, un premier test est réalisé dans une opération 408 afin de tester la possibilité 1) mentionnée plus haut. Si l'entité a un emplacement réservé, alors dans une opération 410, une fonction Log() qui reçoit l'identifiant id et les données d'emplacement s produits comme arguments des données de placement associant ces arguments. De manière optionnelle, la fonction Log() tient compte du fait que l'emplacement réservé s n'est pas forcément dans le même rang que le rang courant i. Pour cela, afin d'optimiser le temps de placement des entités, le rang courant i est mis à jour avec la valeur du rang de l'emplacement réservés.

Ensuite, dans une opération 412, le rang courant i est mis à jour en lui retirant la valeur 2. Ainsi, la prochaine entité sera placée dans un rang plus proche de l'entrée de l'entité courante, sauf si cette prochaine entité est une entité ayant un emplacement réservé et que cet emplacement est dans un rang supérieur au rang courant i. Dans tous les cas, cela permet d'améliorer la cadence de placement des entités dans le cadre de l'arrivée en vrac des entités en maximisant les cas où le placement d'une entité ne gêne pas le placement d'une entité qui la suit.

Dans une opération 414, il est vérifié si l'indice de courant rang i n'a pas été diminué jusqu'à l'entrée. Si c'est le cas, alors l'indice de rang courant i est réinitialisé avec la valeur NR en répétant l'opération 404, et si non, la boucle reprend avec le traitement de l'entité suivante en répétant l'opération 406.

Si l'opération 408 est négative, alors la possibilité 2) est testée dans une opération 416. Si ce test est positif, alors la possibilité 2) est réalisée et une opération 418 teste avec une fonction Lgd() si un élément de la liste M a déjà des données de placement qui lui sont associées. En effet, si c'est le cas, alors l'entité courante doit être placée de manière contiguë à cet élément, et la fonction Log() est appelée à cette fin dans une opération 420 avec l'identifiant id de l'entité courante et avec la liste M afin de déterminer les données de placement déjà attribuées et de produire des données de placement contigues pour l'entité d'indice id courant. Ici encore, de manière optionnelle, la fonction Log() tient compte du fait que l'emplacement des données de placement de la liste M n'est pas forcément dans le même rang que le rang courant i. Pour cela, afin d'optimiser le temps de placement des entités, le rang courant i est mis à jour avec la valeur du rang de l'emplacement des données de placement de la liste M. Ensuite, les opérations 412 et 414 sont exécutées pour mettre à jour l'indice de rang courant et traiter l'élément suivant.

Si le test de l'opération 418 est négatif, alors aucun élément du groupe de la liste M ne présente de données de placement, et l'entité d'identifiant id courant est le premier élément de son groupe à être placé. Une boucle est alors lancée dans une opération 422 afin de déterminer le premier rang d'indice inférieur ou égal à i qui peut recevoir le groupe. Pour cela, une fonction Rm() est exécutée dans l'opération 422 et reçoit comme arguments l'indice de rang courant i et la liste M, et détermine si le rang i comprend un nombre d'emplacements contigus égal au nombre d'identifiants de la liste M. De manière optionnelle, la fonction Rm() peut également vérifier dans le tableau GTBL[] et le tableau AG[] qu'un rang qui contiendrait suffisamment d'emplacements contigus pour loger les éléments de la liste M ne doit pas être réservé pour stocker un autre groupe qui ne pourrait être stocké que dans ce rang.

Si le test de l'opération 422 est négatif, alors l'indice de rang courant i est décrémenté d'une valeur égale à 1 dans une opération 424. Ensuite, dans une opération 426, il est vérifié si l'indice de courant rang i n'a pas été diminué jusqu'à l'entrée. Si c'est le cas, alors l'indice de rang courant i est réinitialisé avec la valeur NR dans une opération 428 et la boucle pour trouver le rang qui peut recevoir le groupe reprend avec l'opération 422. Si non, la boucle pour trouver le rang qui peut recevoir le groupe reprend directement avec l'opération 422 après l'opération 426.

Comme on peut le voir, les opérations 424 et 426 sont très similaires aux opérations 412 et 414 au détail près que l'indice de rang courant i est décrémenté de 1 et non de 2. La raison à cela est que, dans le cas de l'opération 412, des données de placement viennent d'être produites, et le but est que les opérations de placement qui vont suivre ne perturbent pas le placement de l'entité suivante, alors que, dans le cas de l'opération 424 les données de placement n'ont pas été produites, et qu'il est important de parcourir tous les rangs pour trouver le bon. Une fois que le rang i pouvant loger le groupe a été déterminé, une fonction d() est exécutée dans une opération 430. La fonction d() reçoit comme argument le tableau GTBL[] et a pour rôle de décrémenter l'élément de ce tableau qui est impacté par le fait que le groupe va être placé dans le rang i. Le tableau PG[] est traité de manière similaire dans une opération 432. Enfin, des données de placement sont produites dans une opération 434 en exécutant la fonction Log() avec comme arguments l'identifiant id et l'indice de rang courant i et les associe pour produire des données de placement, puis les opérations 412 et 414 sont exécutées afin de traiter l'entité suivante.

Lorsque le test de l'opération 416 est négatif, cela signifie que c'est la possibilité 3) qui s'applique. Dans ce cas, un autre test est réalisé dans une opération 436 pour déterminer s'il y a un nombre de rangs comprenant des emplacements contigus propres à recevoir les groupes à placer strictement supérieur au nombre de groupe restants à placer. Cela est réalisé par une fonction Sac() qui peut par exemple comparer le tableau PG[] et le tableau GTBL[] élément par élément, ou en faisant la somme des éléments de chaque tableau et en la comparant. En effet, dans ce cas, il est possible de « sacrifier » un emplacement potentiel de groupe pour placer immédiatement l'entité courante.

Si le test de la fonction Sac() est positif, alors une boucle d'opérations 440, 442, 444 et 446 est lancée afin de trouver le rang d'indice i qui peut loger l'entité d'identifiant id sans créer de problème. Pour cela, les opérations 442, 444 et 446 sont identiques aux opérations 424, 426 et 428. L'opération 440 est légèrement différente en ce qu'elle exécute une fonction Sml() au lieu de la fonction Rm() de l'opération 422. La fonction Sml() se distingue de la fonction Rm() en ce que la fonction Sml() vérifie uniquement que le rang peut recevoir l'entité courante.

Enfin, la fonction d() est appelée avec le tableau PG[] dans une opération 448 afin de décrémenter le tableau PG[] pour tenir compte du fait qu'un logement possible de groupe a été sacrifié, puis la fonction Log() reçoit comme arguments l'identifiant id et l'indice de rang courant i et les associe pour produire des données de placement dans une opération 450, puis les opérations 412 et 414 sont exécutées afin de traiter l'entité suivante.

Lorsque le test de la fonction Sac() est négatif, l'opération 448 est suivie par une boucle d'opérations 452, 454, 456 et 458 identiques aux opérations 440, 442, 444 et 446. Ici, aucun logement possible de groupe n'est sacrifié, mais une fonction Sm2() est là encore exécutée afin de s'assurer de ne casser aucun groupe.

L'opération Sm2() se distingue de l'opération Sml() en ce qu'elle vérifie que le fait de loger l'entité d'identifiant id dans un rang i donné ne va pas empêcher de loger un groupe. Cela peut être détecté en comparant le tableau GTBL[] et PG[] et en identifiant les éléments qui ont exactement la même valeur. Par exemple donné, si le tableau GTBL[] et le tableau PG[] ont tous les deux la valeur 2 associée à leur deuxième élément, cela signifie qu'il reste deux rangs qui peuvent loger un groupe de trois entités, et deux groupes à loger. Si le rang i peut loger 3 entités, alors la fonction Sm2() doit retourner une valeur négative, afin d'éviter de casser un groupe.

Enfin, la fonction Log() reçoit comme arguments l'identifiant id et l'indice de rang courant i et les associe pour produire des données de placement dans une opération 460, puis les opérations 412 et 414 sont exécutées afin de traiter l'entité suivante.

Lorsque toutes les entités de la liste L ont reçu des données de placement, le test de l'opération 406 est négatif et la fonction Place() se termine dans une opération 499.

Dans ce qui précède, la description de la fonction Place() est quelque peu complexifiée par le fait qu'elle gère la possibilité d'avoir des groupes de différentes tailles. Lorsque la taille des groupes est fixée, par exemple à 2, la fonction peut être simplifiée, et les tableaux GTBL[] et PG[] peuvent être réduits à des scalaires, et les tests des fonctions Rm(), Sm() et Sac() grandement simplifiés.

Les figures 5 et 6 représentent une mise en œuvre en variante des fonctions des figures 3 et 4. Dans cette variante, le placement des groupes est réalisé de manière plus complexe et avec encore plus de sophistication, aboutissant à un risque plus faible qu'un groupe ne soit pas réuni par rapport aux fonctions des figures 3 et 4. Cela est notamment obtenu grâce à une préparation approfondie représentée sur la Figure 5, et à une gestion plus complexe du placement comme représenté sur la Figure 6. De plus, la fonction Place() de la Figure 6 décrit un unique placement, et doit être appelée répétitivement pour chaque entité de la liste L.

Les fonctions des figures 5 et 6 utilisent des partitionnements des espaces pour les groupes. Plus précisément, toutes les possibilités de partitionnement des rangs sont étudiées. Par exemple, un bloc de 3 places pourra être vu comme :

- Une partition logeant un groupe de trois emplacements (partition monobloc, ou triviale),

- Une partition logeant un groupe de deux emplacements et un groupe d'un emplacement seul (partition multiblocs, ou non triviale), - Une partition logeant trois groupes d'un emplacement seul (partition multiblocs, ou non triviale).

Lors de l'initialisation, le nombre de groupes à placer est d'abord déterminé. Ensuite, la détermination du nombre de partitions triviales (comprenant un seul groupe de taille égale à celle de la partition) est privilégiée, puis la détermination du nombre de partitions non triviales est réalisée en parcourant ces partitions par groupes de taille décroissante, et de sorte qu'une partition donnée n'est retenue que s'il y a au moins un groupe à placer pour chacun des groupes contenant plus d'un emplacement qu'elle contient.

Une fois que l'initialisation est réalisée, le placement se fait à la volée, sans se soucier d'où précisément une entité particulière va être placée : ce qui compte, c'est qu'il est certain qu'un nombre donné de groupes peut se voir attribuer des données de placement contiguës, et cela est réalisé de la manière la moins impactante possible.

Ainsi, la Figure 5 commence par une opération 500 dans laquelle le tableau de groupes potentiels PG et les données de groupe AG sont reçues, un indice j est initialisé avec la valeur 2, et un tableau de partitions utiles Parts[] est créé vide. Comme on le verra plus bas, le tableau Parts[] reçoit des couples associant une partition (explicite ou implicite) et un nombre qui représente le nombre de fois où cette partition est censée être utilisée.

Deux boucles se succèdent alors. Dans une première boucle, les partitions triviales sont testées pour déterminer combien d'entre elles devraient être utilisées lors de la détermination des données de placement. Puis, dans la deuxième boucle, les partitions non triviales sont à leur tour testé dans le même but.

La première boucle commence par une opération 505 dans laquelle un couple est défini avec une partition triviale référencée part de taille j et une valeur tbu calculée en appliquant la fonction Min() déjà décrite. Ensuite, dans une opération 510, le nombre de groupes de taille j restant à affecter à une partition RTBA[j] est calculé en comptant le nombre de groupes de taille j dans les données de groupe AG au moyen d'une fonction Count() et en retirant la valeur tbu.

Le tableau de groupes potentiels PG est mis à jour en retirant la valeur tbu à la valeur d'indice j de ce tableau dans une opération 515, et le tableau de groupes censés être placés GTBL est incrémenté en ajoutant la valeur tbu à la valeur d'indice j de ce tableau dans une opération 520. Enfin, le tableau Parts[] reçoit le couple (part ; tbu) dans une opération 525, et le tableau PG est testé dans une opération 529 pour déterminer si toutes les largeurs de rang possibles ont été traversées. Lorsque ce n'est pas le cas, l'indice j est incrémenté dans une opération 530 et la première boucle reprend avec l'opération 505. Lorsque c'est le cas, la première boucle est achevée, et la deuxième boucle commence dans une opération 535. Dans cette opération, une fonction Partnt() reçoit l'indice j comme argument (qui a pour valeur la largeur maximale de rang en sortie de la première boucle), et produit une liste de partitions non triviales PartL ordonnées par groupes de taille décroissante. Par exemple, si la largeur de rang maximale est 4, ces partitions seront : [3 ;1], [2 ;2], [2 ;1 ;1], [2 ;1], [1 ; 1 ; 1 ; 1], [1 ;1 ;1], et [1

La deuxième boucle va ensuite parcourir la liste de partitions PartL et déterminer, pour chacune d'entre elles, le nombre de fois où cette partition peut être utilisée pour les données de placement. Pour cela, une fonction Pop() dépile la liste de partitions PartL dans une opération 540 et génère un couple (part ;tbu) correspondant dans lequel tbu est initialisé à 0.

Une fonction Siz() est ensuite exécutée dans une opération 545 et détermine la taille t de la partition part, puis le premier groupe de la partition part est testé dans une opération 550 pour déterminer si cette partition comprend au moins un groupe de deux emplacements. Lorsque cela n'est pas le cas, alors la partition ne contient que des groupes d'un emplacement. La valeur tbu est ajoutée du nombre de groupes potentiels PG[t] dans une opération 555, le tableau Parts reçoit le couple (part ;tbu), dans une opération 560, et la deuxième boucle reprend avec l'opération 540. Lorsque le test de l'opération 550 est positif, une boucle interne est réalisée au sein de la deuxième boucle pour déterminer combien de fois la partition part peut être utilisée pour les données de placement. Pour cela, dans une opération 565, une fonction Ind() recevant la partition part comme argument détermine l'indice s dans la partition part du groupe de taille la plus petite supérieure ou égale à 2. Ensuite, la boucle interne commence dans une opération 570 avec un test qui est positif lorsque le nombre de groupes de taille t encore affectables PG[t] est supérieur à 0, et qu'une fonction MkR(s) retourne une valeur positive. La fonction MkR(s) détermine si, pour tous les indices de la partition part d'indice inférieur à s, le nombre de groupes à affecter à une partition est supérieur au nombre de fois où ces groupes apparaissent dans la partition part. Par exemple, si la partition part est [2 ;2] et que RTBA[2] vaut 1 , alors la fonction MkR(s) retourne une valeur négative, car il reste moins de groupes de taille 2 à affecter qu'il n'y en a dans cette partition. De même, si la partition part est [2 ;1 ;1] et que RTBA[2] vaut 6, alors la fonction MkR(s) retourne une valeur positive, puisque la partition pourra bien être remplie avec un groupe restant à affecter.

Lorsque le teste de l'opération 570 est positif, la valeur tbu est incrémentée dans une opération 575, le tableau RTBA[] est décrémenté pour toutes les groupes de la partition part de taille supérieure ou égale à 2, le tableau de groupes potentiels de taille t est décrémenté dans une opération 585, le tableau des groupes censés être placés GTBL est incrémenté pour toutes les groupes de la partition part de taille supérieure ou égale à 2 dans une opération 590, et la boucle interne reprend avec l'opération 570.

Lorsque le test de l'opération 570 est négatif, la boucle interne est terminée, et l'opération 560 est exécutée pour ajouter cette partition dans le tableau Parts, puis la deuxième boucle reprend avec l'opération 540 et la partition suivante. Lorsque la liste PartL est vide, le teste de l'opération 540 est négatif, et la fonction Init() se termine dans une opération 599. A ce stade, toutes les partitions possibles ont été introduites dans le tableau Parts, et chacune est associée au nombre de fois où elle doit être utilisée pour générer les données de placement, compte tenu du nombre de groupes potentiels et des emplacements déjà attribués.

La Figure 6 représente une mise en œuvre de la fonction Place(), à partir des éléments déterminés par la fonction de la Figure 5. Selon la Figure 6, les emplacements sont attribués un à un, c'est-à-dire que la Figure 6 est exécutée à chaque fois qu'un emplacement doit être attribué, contrairement à la Figure 4 qui traitait toutes les entités de la liste L en une seule séquence.

Dans une opération 600, le tableau Parts, le tableau de nombres de groupes restants à placer GTBL, les données de groupes AG, la liste de emplacements réservés BkS, un identifiant d'entité à placer id et un identifiant d'emplacement réservé s pour l'identifiant id sont reçus, et un indice i de parcours est initialisé. L'indice i est une variable globale héritée d'une exécution antérieure de la fonction, et est initialisée avec le nombre de rangs NR pour la première exécution.

La fonction fonctionne comme suit :

- si l'identifiant id est associé à un emplacement réservé, il est placé directement,

- si l'identifiant fait partie d'un groupe, alors un premier traitement est appliqué si c'est le premier membre de ce groupe, et un deuxième traitement est appliqué si un membre du groupe a déjà été placé,

- si l'identifiant ne fait partie d'aucun groupe, un troisième traitement est appliqué.

Dans une opération 602, l'identifiant d'emplacement réservé s est testé. S'il n'est pas vide, alors dans une opération 604, une fonction Log() identique à celle de l'opération 410 est exécutée dans une opération 604, puis la fonction se termine dans une opération 699.

Sinon, alors une opération 606 est exécutée dans laquelle une variable m est calculée au moyen d'une fonction Mat() qui reçoit comme arguments l'identifiant id et les données de groupes AG. La fonction Mat() renvoie 0 si l'identifiant id n'est pas présent dans un groupe des données de groupe AG, ou si ce groupe a été cassé, comme on le verra plus bas, et renvoie une variable m comprenant la liste des identifiants appartenant au groupe de l'identifiant id sinon.

Dans une opération 608, il est testé si la variable m est vide ou non. Si elle n'est pas vide, alors dans une opération 610, une fonction MB() reçoit la variable m comme argument et détermine si l'identifiant id est le premier du groupe à faire l'objet d'une affectation de données de placement. Lorsque cela n'est pas le cas, le résultat de la fonction MB() est une donnée d'emplacement, et la fonction Log() est exécutée avec l'identifiant i et la donnée d'emplacement MB(m) dans une opération 612, puis la fonction se termine avec l'opération 699.

Lorsque l'identifiant id est le premier de son groupe à faire l'objet de l'affectation de données de placement, la taille j du groupe auquel il appartient est déterminé au moyen d'une fonction Siz() dans une opération 614. Ensuite, dans une opération 616, le tableau des groupes restants à placer GTBL est testé pour déterminer si le groupe peut encore être associé à des données de placement contigues compte tenu des emplacements déjà occupés.

Si c'est le cas, alors une fonction KGrp() recevant l'indice de rang courant i et la taille du groupe j est exécutée dans une opération 618. La fonction KGrp() retourne un couple (k,p) où k est une taille d'emplacements contigus supérieur ou égal à j dans le rang d'indice i, et p une partition qui contient ces emplacements. La fonction KGrp() cherche ainsi dans le rang i s'il existe une partition p de taille k, telle que cette partition comprend un groupe de j emplacements contigus, et telle que la valeur tbu associée à la partition p dans la liste Parts soit non nulle.

Par exemple, si j vaut 2 et que le rang i courant présente 4 emplacements libres contigus, la fonction KGrp() va étudier toutes les partitions de longueur 4 dans la liste Parts() et considérer celles qui pourraient loger j emplacements contigus. Pour cela, la fonction KGrpQ analyse les sommes partielles des groupes contenus dans chaque partition, c'est-à-dire l'ensemble de tous les groupes possibles en recombinant les groupes d'une partition donnée. Par exemple, pour une partition [2 ;1 ;1], les sommes partielles sont [4 ; 3 ; 2 ; 1]. Si aucune partition p compatible n'est trouvée, alors k est nul, et une opération 620 de test lance une opération 622 de décrémentation de l'indice i au moyen d'une fonction Nxt(). La fonction Nxt() décrémente l'indice i de 1 , ou le fixe à la valeur NR si i vaut 1.

Compte tenu de ce que l'opération 616 est positive, il existe nécessairement au moins une partition dans un des rangs qui remplira les critères. Une fois le couple (k ;p) déterminé, une fonction FrS() recevant l'indice de rang courant i, la taille j et la taille k est exécutée dans une opération 622. La fonction FrS() a pour rôle de déterminer dans le rang i où placer l'identifiant id, ainsi que les autres emplacements pour le groupe auquel il appartient. Afin d'optimiser les temps de mise en place, les données d'emplacement pour les j entités du groupe sont choisies dans la manière la plus extrême par rapport à l'accès aux emplacements, et la donnée d'emplacement s pour l'identifiant id est elle- même choisie la plus extrême au sein du groupe. Ainsi, lorsqu'une autre entité du groupe sera testée avec l'opération 610, le résultat de la fonction MB() lui donnera l'emplacement du groupe libre le plus extrême, et ainsi de suite.

Une fois que les données d'emplacements pour l'identifiant id et pour les autres entités du groupe ont été déterminés, des opérations doivent être mises en œuvre pour maintenir la liste des partitions et les différents tableaux de nombres de groupes. En effet, comme on vient de le voir, afin d'être plus efficace, l'invention ne cherche pas à placer un groupe dans une partition de taille identique, mais le place dans la partition la plus proche, compte tenu du rang courant. Il faut donc mettre à jour cette partition, puisque des emplacements sont réservés pour les autres entités du groupe, mais également potentiellement mettre à jour une autre partition pour tenir compte du fait que la partition retenue n'a pas forcément la même taille que le groupe.

Pour cela, dans une opération 624, une fonction SubP() reçoit la partition p et la taille j comme arguments et retourne une partition r qui correspond aux emplacements retirés à p pour les emplacements du groupe. Par exemple, si la partition p est [2 ; 1 ; 1] et que j vaut 2, la partition r est [2].

Ensuite, dans une opération 626, une partition q est calculée en retirant la partition r à la partition p. La partition q correspond ainsi à ce qui reste de la partition p une fois retirés les emplacements retenus pour placer le groupe de taille j. Par exemple, si la partition p est [2 ; 1 ; 1] et que j vaut 2, alors q est [1 ; 1].

Dans une opération 628, le tableau de groupes restants à placer GTBL est décrémenté pour l'indice j (puisqu'un groupe de taille j vient d'être placé), puis des fonctions DecParts() et IncParts() sont appelées dans des opérations 630 et 632. La fonction DecParts() reçoit comme arguments la partition p et la liste Parts et décrémente la valeur tbu associée à p dans la liste Parts. La fonction IncParts() reçoit comme arguments la partition q et la liste Parts et incrémente la valeur tbu associée à q dans la liste Parts. En effet, il y a une partition de type p en moins à utiliser, et une partition de type q en plus à utiliser.

Un test est alors réalisé dans une opération 634 pour déterminer si la partition r est triviale ou pas. Lorsque ce n'est pas le cas, comme mentionné plus haut, il faut aller trouver une partition qui contient un groupe de taille j pour tenir compte du fait que la partition p a été coupée en deux et permettre de loger les groupes qui auraient formé la sous-partition r de p.

Pour cela, une fonction NxtP() est exécutée avec la liste Parts et la taille j dans une opération 636. La fonction NxtP() recherche la partition z contenant un groupe de taille j dans la liste Parts et dont la valeur associée tbu est non nulle.

Ensuite, une partition y égale à z -[] ^' ]+ r est déterminée dans une opération 638. Cela revient à prendre une partition triviale de taille j qui aurait pu être utilisée pour loger le groupe de taille j si elle avait été située dans le rang courant, et à la découper pour permettre de loger la partition r qui a été produite à l'opération 624. La fonction DecParts() est exécutée sur la partition z dans une opération 640 pour tenir compte du fait de son découpage, et la fonction IncrParts() est exécutée sur la partition y dans une opération 642. Enfin, ou dans le cas où l'opération 634 était positive, la fonction Log() est exécutée dans une opération 644.

Lorsque l'opération 616 est négative, alors il n'y a plus d'emplacements contigus pour loger un groupe de taille j. Cela signifie que le groupe doit être cassé et que ses entités doivent être placées comme si elles étaient non groupées. Pour cela, une fonction Brk(m) est exécutée dans une opération 646.

Ensuite, ou lorsque l'opération 608 est négative, un identifiant id qui n'a pas de groupe associé, ou qui n'a pas de groupe associé qui puisse être placé de manière contiguë fait l'objet d'un placement. Pour cela, une fonction S() qui reçoit comme argument le rang courant i est exécutée dans une opération 648. La fonction S() détermine si le rang i peut recevoir l'identifiant id en cherchant s'il existe un emplacement isolé, et si ce n'est pas le cas, s'il existe une partition qui pourrait être placée dans le rang d'indice i, cette partition comprenant la valeur 1 , et la valeur tbu associée à cette partition dans la liste Parts est non nulle. Si ce n'est pas le cas, alors le rang d'indice i ne peut pas être utilisé, car il ne serait plus possible de placer cette partition ailleurs, et la valeur x retournée est nulle. Sinon, x vaut 1.

Une opération 652 teste la valeur x, et applique la fonction Nxt() dans une opération 652 si nécessaire, puis l'opération 648 est répétée, jusqu'à trouver une valeur x non nulle dans un rang i donné. Un test détermine alors dans une opération 654 si le rang i comprend un emplacement isolé. Si c'est le cas, alors la fonction Log() est exécutée dans une opération 656 avec cet emplacement et la fonction se termine avec l'opération 699.

Sinon, une fonction Min() reçoit i comme argument dans une opération 658 et détermine la taille k de la plus petite partition qui peut être placée dans le rang i, qui comprend la valeur 1, et dont la valeur tbu associée dans la liste Parts est non nulle. La fonction Min() retourne également l'emplacement le plus extrême de cette partition dans le rang d'indice i. La fonction Log() est alors exécutée dans une opération 660, puis des opérations 662 à 668 sont exécutées, qui correspondent aux opérations 636 à 642 avec r = [1]. Enfin, la fonction se termine avec l'opération 699.

Grâce au traitement du dispositif 2, le placement des entités peut donc être grandement optimisé afin d'obtenir une efficacité maximale lorsque ceux-ci arrivent en vrac et doivent être placés en tenant compte d'impératifs de réservation d'emplacements et de groupes.

Bien que l'exemple ayant été décrit en rapport avec l'invention s'applique particulièrement bien au remplissage d'un entrepôt de stockage avec des produits, le dispositif peut trouver son application dans d'autres contextes. Par exemple, le dispositif peut être utilisé pour affecter des places dans un avion au moment de l'embarquement en tenant compte de places déjà réservées ainsi que de groupes de passagers. Le dispositif permet alors de remplir l'avion de la manière la plus rapide possible, ce qui permet de réaliser des économies substantielles.