Des stratégies de contrôle efficaces pour les véhicules guidés automatisés (AGV) sont importantes pour les entreprises qui exploitent des systèmes de fabrication flexibles en termes de maximisation de la productivité. Dans cet article, nous concevons et analysons Pickup-or-Delivery-En-Route (PDER), un algorithme de répartition des AGV à charges multiples. PDER est une règle de détermination des tâches qui permet à un véhicule partiellement chargé se rendant à une destination de dépose de prendre et/ou de déposer des charges que le véhicule aurait autrement dépassées en route vers la destination initiale. Nous menons une expérience basée sur la simulation pour évaluer l'efficacité de l'algorithme PDER. Les résultats indiquent que le PDER peut produire des impacts positifs significatifs sur le débit et le temps dans le système dans les systèmes de fabrication flexibles utilisant des AGV à charges multiples.
Avec l'évolution constante de l'environnement commercial, des préférences des clients et de la technologie, les entreprises ne peuvent plus s'attendre à des rendements supérieurs en produisant des produits standardisés. Pour faire face à des problèmes tels que l'adaptation des produits, l'élargissement de la gamme de produits offerts et la diminution des quantités commandées, de nombreuses entreprises tentent de retrouver leur avantage concurrentiel en passant de la production de masse à la fabrication flexible. Shivanand, Benal et Koti (2006) définissent un système de fabrication flexible comme un groupe de postes de travail et de systèmes de stockage interconnectés par un système de manutention automatisé et contrôlés par un système de commande informatique intégré. Un tel système présente plusieurs caractéristiques complexes, telles que de grandes variations de produits, des schémas aléatoires de flux de matériaux et une demande stochastique où les systèmes de manutention traditionnels, tels que les convoyeurs, ne peuvent plus relever les défis que pose le déplacement des produits entre les postes de travail dans l'ensemble du système.
Les AGV peuvent accroître de manière significative la flexibilité d'un système de manutention et emprunter des chemins efficaces pour livrer les travaux en cours (WIP) en fonction des séquences de traitement des produits. Toutefois, la faible vitesse de déplacement, les temps de chargement et de déchargement importants et la capacité limitée des AGV peuvent limiter la capacité de production des systèmes de fabrication. Ainsi, un FMS à forte intensité de trafic peut nécessiter un grand nombre d'AGV pour assurer un flux et une distribution efficaces des matériaux. En outre, une flotte importante d'AGV implique un coût d'investissement élevé pour les véhicules, l'entretien des AGV, les problèmes de congestion du trafic et l'encombrement de l'espace.
Pour réduire le nombre d'AGV nécessaires, une alternative consiste à mettre en œuvre des AGV à chargements multiples. Les AGV à charge multiple peuvent généralement aider un FMS à atteindre un niveau élevé de débit avec une flotte plus petite que les AGV à charge unique (Ozden 1988). Parmi les autres avantages des AGV à chargements multiples, on peut citer une meilleure utilisation des AGV et une meilleure utilisation des machines (Bilge et Tanchoco 1997). La principale difficulté liée à la gestion des AGV à chargements multiples réside dans le fait que le ou les espaces de chargement supplémentaires augmentent les états décisionnels de l'AGV. Ho et Chien (2006) observent qu'un AGV à charge unique n'a que des états vide et chargé, alors qu'un AGV à charges multiples peut être vide, partiellement chargé et entièrement chargé. En outre, ils définissent quatre problèmes majeurs liés à la gestion des AGV à chargements multiples :
L'objectif de cette recherche est de développer une règle de détermination des tâches qui permette aux AGV à chargements multiples d'utiliser le(s) espace(s) vide(s) lorsqu'il(s) est (sont) partiellement chargé(s), dans le but de maximiser le débit du système et de minimiser le temps moyen dans le système des pièces dans un FMS. En particulier, la stratégie proposée, que nous appelons Pickup-or-Delivery-En-Route (PDER), permet à un véhicule partiellement chargé se rendant à une destination de dépôt de prendre et/ou de déposer des charges que le véhicule aurait autrement dépassées en route vers la destination initiale.
Le reste de l'article est organisé comme suit : un résumé des travaux connexes est présenté à la section 2 ; les détails de la règle PDER proposée sont expliqués à la section 3 ; une expérience de simulation visant à comparer des règles de répartition alternatives dans deux configurations de systèmes FMS est présentée à la section 4 ; enfin, nos conclusions sont discutées à la section 5.
Il existe un nombre relativement important de travaux dans le domaine des algorithmes de répartition des véhicules autoguidés. LeAnh et Koster (2006), qui présentent une étude complète des défis et des approches de la gestion des AGV, et Fazlollahtabar et Saidi-Mehrabad (2015), qui passent en revue les stratégies existantes pour les problèmes d'ordonnancement, de répartition et de routage des AGV, sont deux études approfondies. De nombreux auteurs se concentrent sur le problème de l'enlèvement et de la répartition des AGV à charge unique. Parmi les règles d'enlèvement et de répartition les plus courantes, citons les règles de la plus courte distance (STD), du premier arrivé, premier servi modifié (MFCFS), de la taille maximale de la file d'attente (MOQZ), de l'unité de charge et de l'heure d'arrivée à l'atelier (ULSAT) (Egbelu et Tanchoco, 1984). D'autres chercheurs ont montré que, dans certaines circonstances, les algorithmes de répartition multi-attributs peuvent être plus performants que les règles mono-attributs (Jeong et Randhawa 2001 ; Bilge et al. 2006 ; Guan et Dai 2009 ; Caridá, Morandin et Tuma 2015).
Azimi, Haleh et Alidoost (2010) développent une méthode de prise de décision multi-attributs floue (MADM) pour évaluer la stratégie de contrôle des AGV à chargements multiples, qui prend en compte dix critères de performance, tels que le débit du système, le temps moyen d'écoulement des pièces, la longueur moyenne des files d'attente aux points d'enlèvement et de livraison, entre autres. Ho et Chien (2006) comparent trois règles pour traiter le problème de détermination des tâches pour les AGV à chargements multiples, à savoir les règles Delivery-Task-First (DTF), Pickup-Task-First (PTF) et Load-Ratio (LR). Une règle DTF suggère qu'un AGV devrait toujours choisir de déposer le(s) chargement(s) restant(s) lorsqu'il est partiellement chargé. En vertu d'une règle PTF, l'AGV doit toujours effectuer les tâches d'enlèvement en premier, même si des tâches de livraison et d'enlèvement sont disponibles pour lui. Contrairement aux règles DTF ou PTF qui donnent aux tâches de livraison ou de ramassage une priorité plus élevée, la règle LR détermine la tâche suivante de l'AGV en fonction du taux de charge du véhicule. Les résultats montrent que la règle DTF est généralement plus performante que les règles PTF et LR en termes de débit du système et de retard moyen des pièces.
Dans ce travail, nous nous appuyons sur les connaissances acquises grâce aux études ci-dessus et concevons une règle (PDER) pour traiter les stratégies de prise en charge et de dépose employées lorsque l'AGV est partiellement chargé et en route vers une destination afin d'essayer d'améliorer les performances du système.
L'objectif essentiel de la règle Pickup-or-Delivery-En-Route (PDER) est de maximiser l'utilisation des espaces de chargement sur les AGV à chargements multiples. Ainsi, la règle PDER permet à un AGV partiellement chargé de prendre des charges supplémentaires sur son chemin vers la destination suivante. Lorsqu'un AGV à charge multiple a terminé toutes les actions nécessaires à un point d'enlèvement ou de livraison et qu'il est partiellement chargé, il recherche une nouvelle affectation parmi les tâches dont les points d'enlèvement sont géographiquement situés sur le chemin le plus court entre l'emplacement actuel de l'AGV et sa prochaine destination. Ces tâches sont qualifiées de tâches à faible coût car il est très pratique pour l'AGV de les prendre. S'il existe une ou plusieurs tâches à faible coût, l'AGV les récupère ou les dépose en cours de route vers la destination initiale.
L'algorithme PDER fonctionne de concert avec une règle de répartition des ramassages spécifiée pour contrôler les actions des AGV à chargements multiples. L'algorithme PDER est présenté à la figure 1, dans laquelle la notation suivante est utilisée :
𝑖 une tâche de transport (charge) dans le système.
𝐼 une liste d'attente de toutes les tâches non assignées dans le système.
𝑉 un AGV dans le système.
𝐷𝑉 liste des destinations de l'AGV, 𝑉, correspondant à ses tâches assignées et transportées.
𝑃𝑉 liste des points de ramassage situés entre l'emplacement actuel de l'AGV et sa prochaine destination.
𝐼𝑉 ensemble de travaux à faible coût en attente aux points de ramassage 𝑃𝑉 où 𝐼𝑉 ⊆ 𝐼. L'algorithme PDER est lancé dans le système lorsqu'un événement initié par le centre de travail ou un événement initié par le véhicule se produit.
Un événement initié par le centre de travail se produit lorsqu'une charge génère une nouvelle demande de transport vers le poste de travail suivant en fonction de sa séquence de traitement. Lorsqu'une pièce est terminée à un poste de travail, une tâche de transport 𝑖 est générée. Si aucun des AGV n'est libre à ce moment-là, la tâche 𝑖 est enregistrée dans la liste d'attente 𝐼. S'il n'y a qu'un seul véhicule inactif 𝑉, la tâche 𝑖 sera assignée à 𝑉. S'il y a plus d'un AGV inactif, les AGV sont en concurrence pour la tâche 𝑖 sur la base d'une règle initiée par le centre de travail. Parmi les règles les plus courantes, citons le véhicule le plus proche (NV), le véhicule le plus longtemps inactif (LIV) et le véhicule le moins utilisé (LUV) (Egbelu et Tanchoco 1984).
Un événement initié par un véhicule se produit lorsqu'un AGV atteint un point de ramassage ou de dépôt. L'AGV commence par effectuer la tâche de ramassage ou de dépôt prédéterminée pour la tâche assignée ou transportée, respectivement. Une fois que l'AGV a terminé la tâche prédéterminée, il se trouve dans l'un des trois cas suivants :
Dans les cas 1 et 2, une fois que la tâche i est assignée à 𝑉 et retirée de la liste d'attente I, les états ultérieurs de 𝑉 suivront soit le cas 2, soit le cas 3. En d'autres termes, 𝑉 ne quittera pas le point de ramassage ou de dépôt à moins que le véhicule ne soit entièrement affecté (𝐼 dans le cas 1 est vide ou 𝐼𝑉 dans le cas 2 est vide). Comme la destination suivante est définie comme le point de ramassage ou de dépôt le plus proche dans la liste de destinations de 𝑉, les décisions de livraison et d'expédition suivent toujours la règle STD.
Dans cette section, nous présentons une expérience basée sur la simulation pour évaluer l'efficacité de la règle de détermination des tâches PDER avec quatre règles alternatives d'enlèvement et d'expédition. Le PDER est comparé à la règle de détermination des tâches Delivery-Task-First (DTF) (Ho et Chien 2006) dans le contexte de deux configurations de système FMS où nous faisons varier le nombre d'AGV dans le système ainsi que les capacités des AGV. Une simulation-expérience est menée pour comparer la performance des combinaisons de règles dans les différentes configurations du système sur la base de mesures de performance, y compris le débit du système et le temps moyen dans le système.
Nous considérons deux configurations de système de fabrication flexible, FMS 1 et FMS 2. Les deux systèmes fonctionnent selon un concept de traction, de sorte qu'une nouvelle pièce d'un type aléatoire entre dans le système lorsque la longueur de la file d'attente du poste d'entrée est inférieure à sa capacité. Dans les deux configurations, les temps de chargement et de déchargement d'un AGV sont de 15 secondes par pièce, et sa vitesse de déplacement est de 2 miles par heure.
Le schéma de la première configuration FMS (FMS 1) est illustré à la figure 2. Le FMS 1 est un système à boucle unique, composé de 8 stations de travail reliées par des chemins unidirectionnels et produisant cinq types de pièces. La capacité du tampon de sortie du poste d'entrée est de 12. Après qu'un AGV a prélevé une pièce dans le tampon de sortie, une nouvelle pièce d'un type aléatoire est introduite dans le système en fonction des pourcentages de volume de production indiqués dans le tableau 1. En outre, le tableau 1 répertorie la séquence de traitement pour chaque type de pièce ainsi que le temps de traitement moyen. Nous supposons que le temps de traitement d'une pièce à un poste de travail suit une distribution exponentielle. Une pièce terminée quittera le système à partir du poste de sortie.
L'agencement de la deuxième configuration FMS (FMS 2) est illustré à la figure 3 et est basé sur l'agencement utilisé par Ho et Chien (2006). Le système se compose de 10 postes de travail et produit six types de pièces différents. Le tableau 2 présente la séquence de traitement et le pourcentage de volume (échantillonné de manière aléatoire) pour chaque type de pièce. Le temps de traitement des différents types de pièces à chaque poste de travail suit la même distribution normale, comme le montre le tableau 3.
Pour les expériences, nous utilisons plusieurs types de règles de contrôle AGV, notamment une règle initiée par le centre de travail, des règles de répartition des enlèvements, une règle de répartition des livraisons et une règle de sélection de la charge.
Une règle initiée par le centre de travail est appliquée lorsqu'une nouvelle demande de transport est générée et que plusieurs AGV sont à l'arrêt. La tâche consiste à déterminer quel véhicule inactif doit prendre la charge. Sur la base des résultats d'Egbelu et Tanchoco (1984), nous appliquons la règle du véhicule le plus proche (NV). Pour sélectionner un véhicule, chaque AGV trouve le chemin le plus court vers le point de ramassage de la charge. L'AGV qui a la plus petite distance à parcourir jusqu'au point d'enlèvement se verra attribuer la tâche.
Quatre règles de ramassage et de répartition sont utilisées en conjonction avec la détermination des tâches. Une règle d'enlèvement et de répartition est utilisée pour déterminer le point d'enlèvement où l'AGV doit se rendre. Les quatre règles considérées sont le temps le plus long dans le système (LTIS), le temps d'attente le plus long au point de ramassage (LWTPT), la distance la plus courte (STD) et la plus grande longueur de file d'attente (GQL). Pour plus de détails sur ces règles, voir Ho et Liu (2006).
Une règle de répartition des livraisons est utilisée pour déterminer quelle charge doit être livrée en premier lorsqu'un AGV transporte plus d'une charge. Dans cette étude, la règle de la distance la plus courte (SD) est utilisée pour la répartition des livraisons - voir Ho et Chien (2006). Une règle de sélection des charges est utilisée pour déterminer quelle charge doit être enlevée à un point d'enlèvement. Dans cette étude, nous utilisons la règle du premier entré, premier sorti dans la file d'attente (FIQFO), selon laquelle une pièce ayant un temps d'attente plus long dans la file d'attente aura une priorité plus élevée (Ho et Liu, 2006). Avec une règle de détermination des tâches DTF, la règle de sélection du chargement est invoquée lorsque l'AGV atteint le point d'enlèvement qu'il a décidé de visiter. L'AGV continue à charger des pièces en fonction de la règle de sélection de la charge jusqu'à ce qu'il soit complètement chargé ou que la file d'attente de sortie soit vide. Avec une règle de détermination des tâches PDER, la règle de sélection de la charge sera invoquée au cours du processus d'affectation des tâches et déterminera à quelle tâche à faible coût l'AGV doit être affecté.
Un modèle de simulation des deux systèmes FMS considérés a été construit à l'aide du logiciel de simulation Simio (Simio 2017). Plusieurs modifications/ajouts relativement importants ont été apportés à la logique de routage des véhicules standard de Simio pour permettre la mise en œuvre et l'exécution des diverses règles de contrôle des véhicules, y compris la règle de détermination des tâches PDER - pour plus de détails, voir Li (2017).
Les expériences basées sur la simulation comparent les performances des règles de détermination des tâches PDER et DTF associées à quatre règles alternatives de ramassage et d'expédition dans deux configurations FMS. Les autres facteurs pris en compte comprennent la taille de la flotte d'AGV allant de 1 à 4 véhicules, et les types de véhicules comprennent des AGV à double et triple charge, ce qui donne un total de 128 scénarios de test. Les facteurs expérimentaux et leurs niveaux sont présentés dans le tableau 4. Les principales mesures de performance considérées pour cette expérience sont le débit moyen et le temps moyen dans le système.
Les expériences de simulation sont conçues pour exécuter 20 répétitions de chaque combinaison de facteurs, soit 500 heures de fonctionnement continu, y compris une période d'échauffement de 6 et 12 heures pour le FMS 1 et le FMS 2, respectivement.
Pour chaque combinaison de traitement des expériences de simulation, des statistiques sur le débit et le temps passé dans le système sont enregistrées. Le débit moyen pour les SGF 1 et 2 est présenté dans les figures 4 et 5, respectivement.
Comme point de référence, une configuration de simulation supposant une manutention instantanée a été exécutée pour établir une limite supérieure pour le débit. La limite supérieure est de 6 000 pièces pour le SGF 1 et de 9 800 pièces pour le SGF 2. Au vu des résultats présentés dans les figures 4 et 5, nous observons plusieurs cas où le système est sous-capacitaire (SGF 1 avec un AGV, quelle que soit sa capacité, et SGF 2 avec un ou deux AGV à double charge et un AGV à triple charge). En outre, dans le SGF 1, lorsque quatre AGV sont utilisés et dans le SGF 2, lorsque quatre AGV à double charge ou trois ou quatre AGV à triple charge sont utilisés, le système devient surcapacitaire en termes d'AGV. En d'autres termes, la capacité des véhicules est suffisante pour que les règles de contrôle des AGV n'aient pas d'impact significatif (à 𝛼 ≤ 0,05) sur le débit. Par conséquent, nous concentrons notre analyse sur les scénarios du tableau 5.
Les tableaux 6 et 7 montrent le débit moyen et l'écart-type des scénarios sélectionnés dans FMS 1 et FMS 2, respectivement. Pour chaque scénario, un test de comparaison des moyennes multiples de Tukey est effectué à un niveau de signification de 0,05 afin de comparer le débit moyen pour chaque paire de règles de contrôle de l'AGV. Les valeurs de débit ombrées indiquent que la combinaison de règles correspondante produit le débit le plus élevé dans le scénario. Lorsque plusieurs valeurs sont grisées pour un scénario donné, les moyennes se situent dans le groupe de débit moyen le plus élevé, mais elles ne sont pas significativement différentes les unes des autres.
Le tableau 6 montre que le débit le plus élevé est toujours obtenu avec les règles STD et PDER. Lorsqu'il y a 3 AGV à double charge et 2 AGV à triple charge, n'importe quelle règle d'enlèvement et de répartition peut atteindre le débit le plus élevé tant qu'elle est associée à une règle de détermination des tâches PDER. Si l'on utilise la même règle d'enlèvement et de répartition, le PDER surpasse le DTF en termes de débit. De même, dans le tableau 7, lorsque l'on utilise 3 AGV à double charge ou 2 AGV à triple charge, le débit le plus élevé est toujours obtenu avec une règle PDER. Lorsque l'on utilise la même règle d'enlèvement et de répartition dans ces deux scénarios, la règle PDER permet d'obtenir un débit plus élevé.
Outre le débit, nous analysons les performances des règles de contrôle des AGV en fonction du temps moyen que les pièces passent dans le système. Les tableaux 8 et 9 résument la moyenne et l'écart-type du temps moyen passé dans le système pour chacun des scénarios sélectionnés dans FMS 1 et FMS 2, respectivement. Nous avons effectué un test analogue de comparaison de moyennes multiples sur ces moyennes et avons nuancé le groupe le plus performant pour chaque scénario. Dans le tableau 8, nous observons que le temps moyen dans le système le plus court est obtenu avec une règle STD avec PDER. Lorsque l'on utilise la même règle de prise en charge et d'expédition, le PDER surpasse les règles DTF dans la plupart des scénarios. La seule exception est l'utilisation de la règle LTIS avec DTF sur 2 AGV à double charge. Dans le tableau 9, c'est la règle STD avec PDER qui permet d'obtenir le temps moyen le plus court pour le système. Lors de l'utilisation des règles d'enlèvement et de distribution STD, LWTPT et GQL, la règle PDER est plus performante que la règle STD.
En général, la règle PDER est plus performante que la règle DTF en termes de débit du système. Lorsque l'on utilise la même règle d'enlèvement et d'expédition, la règle PDER permet généralement d'obtenir un débit plus élevé. La seule exception est l'utilisation de 2 AGV à double charge dans le second FMS, la règle GQL avec PDER et la règle GQL avec DTF sont à égalité pour la première place. On constate que la règle PDER a un impact moindre sur le débit dans le SGF 2. Comme la règle PDER permet à un AGV de prendre des tâches supplémentaires en route vers la destination suivante, la probabilité d'avoir un AGV vide devient très faible. Ainsi, au lieu d'être affecté à la tâche ayant la priorité la plus élevée dans le système, un AGV doté de la règle PDER sélectionne généralement une tâche peu coûteuse qui n'a que la priorité la plus élevée sur l'itinéraire actuel de l'AGV vers la destination suivante. En d'autres termes, au lieu d'assigner la tâche ayant la priorité la plus élevée dans le système, un AGV choisit généralement la tâche qui est relativement importante et plus commode à prendre. Ce problème est atténué dans le SGF 1, car il n'y a qu'un seul itinéraire reliant tous les postes de travail, de sorte que le nombre de passages devant chaque poste de travail est réparti plus uniformément.
La règle PDER présente également des performances exceptionnelles en termes de temps moyen passé par les pièces dans le système. Lorsque l'on utilise la même règle de répartition des enlèvements, la règle PDER est plus performante que la règle DTF, à l'exception du cas LTIS. L'objectif essentiel de la règle LTIS est de minimiser le temps passé par les pièces dans le système. Une pièce en attente au point d'enlèvement de la station d'entrée a toujours un temps dans le système inférieur à celui des pièces se trouvant dans les tampons de sortie des stations de travail. Ainsi, les AGV conduiront le système de fabrication à se concentrer sur l'achèvement des pièces qui ont déjà quitté la station d'entrée. Cet effet permet de minimiser le temps passé dans le système, mais réduit le nombre de pièces introduites dans le système, ce qui limite le débit.
Enfin, nous constatons que la règle PDER donne de très bons résultats en termes de débit et de temps passé dans le système lorsqu'elle est associée à la règle STD. Étant donné que la règle STD se concentre sur la minimisation des déplacements en tête de série et que la règle PDER réduit le problème de l'AGV au ramassage des pièces des postes de travail en amont tout en passant à côté des pièces en aval qui sont prêtes à être déplacées plus loin en aval, la règle PDER donne de très bons résultats en termes de débit et de temps dans le système. Par conséquent, la règle PDER a le potentiel d'augmenter de manière significative la productivité des systèmes FMS utilisant des AGV à chargements multiples.
Cet article présente une règle de détermination des tâches de ramassage ou de livraison en cours d'acheminement pour les véhicules autoguidés à chargements multiples. Une expérience basée sur la simulation est menée pour comparer la règle PDER et la règle DTF dans deux configurations de système avec des tailles de flotte et des types d'AGV différents. Grâce à cette étude, nous avons démontré le fort potentiel de l'utilisation de la règle PDER pour améliorer de manière significative la productivité qui peut être atteinte dans un FMS utilisant des AGV à capacité multiple. Sur la base de ce travail initial, nous prévoyons d'effectuer une analyse plus approfondie afin de déterminer les caractéristiques d'un FMS dans lequel l'utilisation de la règle PDER sera la plus avantageuse.