ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Auteurs : soumettez
votre article en ligne

APPEL À
CONTRIBUTION

Le comité de rédaction du JESA lance un appel à proposition de numéros spéciaux.

En savoir plus >>
Autres revues >>

Journal Européen des Systèmes Automatisés

1269-6935
Revues des Systèmes
 

 ARTICLE VOL 46/8 - 2012  - pp.835-854  - doi:10.3166/jesa.46.835-854
TITRE
Chargement de véhicules à l’aide d’un convoyeur

TITLE
Loading trucks from a conveyor with automated vehicle

RÉSUMÉ

Cet article s’intéresse à la prise de palettes sur un convoyeur à gravité. Chaque palette de la séquence de production a une destination précise et l’équipement de transport peut retirer du flux au plus K palettes consécutives de même destination parmi les M premières (seules visibles constituant la taille de la fenêtre de prise) . La minimisation du nombre de rotations du convoyeur s’apparente à une version du jeu Clickomania de dimension un, qui est un problème NP-difficile. Si ce problème a été récemment montré de complexité polynomiale, la borne en O(N 6 ) rend sa résolution coûteuse en temps lorsque le nombre N de palettes croît. Deux approches de résolution sont proposées dans cet article. La première est une modélisation mathématique permettant de mieux comprendre la problématique étudiée. La seconde est un algorithme de programmation dynamique qui, bien que non linéaire par rapport à la taille de la fenê tre de prise, le nombre de destinations et le nombre de prises simultanées, se comporte de manière linéaire en N. Il peut donc avantageusement être utilisé lors que l’ordre de grande ur de ces trois paramètres critiques est faible, ce qui était le cas dans le pr oblème industriel initialement étudié.



ABSTRACT

This article addresses the problem of optimizing pallet picking on a con veyor, which can extract at most K consecutive of them from the production line among the M first pallets, the only visible ones (the size of the window), provided they have the same destination. The goal is to minimize the number of conveyor rotations from the production line to the corresponding trucks. This problem is related to a version of the Clikomania game, known to be NP-hard, in its one dimension version, but with a limit on the number of extracted pallets and on the size of the window. This problem has been recently shown to be solvable in O(N 6 ), but this complexity makes its resolution time consuming when N, the number of pallets, increases. We propose in this paper two resolution approaches. The first is a mathematical formulation to understand the structure of the problem. The second is a dynamic programming algorithm.



AUTEUR(S)
Pierre BAPTISTE, Djamal REBAINE, Zahneb BRIKA

MOTS-CLÉS
chargement de véhicules, Clickomania, optimisation, picking, samegame

KEYWORDS
Clickomania, optimization, picking, samegame, truck loading

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 7.5 €
• Non abonné : 15.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (803 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier