View
6
Download
0
Category
Preview:
Citation preview
SYLVAIN BOUCHER
L'ORDONNANCEMENT D'UNE CELLULE ROBOTIQUE À DEUX ET TROIS MACHINES : REVISION DE LA MÉCANIQUE DES MOUVEMENTS DU ROBOT
Mémoire Présenté
a la Faculté des études supérieures de l'Université Laval
pour l'obtention du grade maître ès sciences (M.Sc.)
Département de génie mécanique FACULTÉ DES SCIENCES ET GÉNIE
UNIVERSITÉ LAVAL
NOVEMBRE 2000
O Sylvain Boucher, 2000
Naticnal Library of Canada
Bibiiothéque nationale du Canada
Acquisitions and Acquisitions et Bibliographie Services seivices bibliographiques
395 Wellington Street 395, nie Wellington Ottawa ON KI A ON4 OnawaON K1A ON4 Canada Canada
The author has granted a non- exclusive licence aiiowing the National Library of Canada to reproduce, loan, distribute or seil copies of this thesis in microform, paper or electronic formats.
The author retains ownership of the copyright in this thesis. Neither the thesis nor substantial extracts fiom it may be printed or otherwise reproduced without the author's permission.
L'auteur a accordé une licence non exclusive permettant à la Bibliothèque nationale du Canada de reproduire, prêter, distribuer ou vendre des copies de cette thèse sous la forme de microfichelfilm, de reproduction sur papier ou sur format électronique.
L'auteur conserve la propriété du droit d'auteur qui protège cette thèse. Ni la thèse ai des extraits substantiels de celle-ci ne doivent être imprimés ou autrement reproduits sans son autorisation.
Ce mémoire concerne l'ordonnancement d'une cellule flexible de production traitant
plusieurs produits de façon non cyclique. Le problème consiste à céduler les opérations
d'un robot qui dessert un atelier mono-gamme sans espace d'entreposage intermédiaire.
L'objectif est de minimiser le temps de cycle, qui est équivalent à maximiser le
rendement, dans une ceUule à robot mobile ramenable à robot centré. Actuellement, les
approches disponibIes sont basées sur une mécanique du robot déficiente, à laquelle nous
apportons plusieurs corrections. Nous utilisons un principe de résolution optimal basé
sur l'algorithme de Gilrnore & Gomory dans le cas à deux machines et prouvons que
deux des six séquences à trois machines ne peuvent être résolues en temps polynomial.
Nous démontrons que ce sont celles-ci qui ont le plus de chances d'être optimales, et
suggérons une piste d'heuristique. Nous aimerions étendre cette méthodologie à quatre
puis m machines, de même qu'à un processus d'arrivée dynamique des ordres de
fabrication.
AVANT-PROPOS
Je voudrais profiter de l'occasion pour remercier Mme Sophie D'amours, professeur-
chercheure en génie mécanique, et M. Fayez Boctor, professeur-chercheur en gestion des
opérations, pour leur support et entière collaboration tout au long de ce projet. Sans eux,
l'aboutissement de mes « élucubrations » que constitue ce mémoire eut été impossible.
Je désire également faire part de ma gratitude à MM. Clément Gosselin et Alain
Curodeau, professeurs-chercheurs en génie mécanique, pour leurs précieuses indications
en robotique, de même qu'à leur étudiant de maîtrise Guillaume Barrette et Martin
Gignac pour les démonstrations sur les robots.
Je suis aussi redevant envers tous mes coilègues étudiants-chercheurs du Centre de
Recherche sur les Technologies de l'organisation Réseau (CENTOR) pour le milieu de
travail stimulant qu'ils ont su créer dans leur sillon. Enfin, pour ses encouragements
constants et son amour, un remerciement spdcial va à Marie-Christine Chevrette, ma
compagne tout au long de ma maîtrise, ainsi qu'à mes amis (ils savent qui ils sont) pour
le bon temps passé durant ces deux dernières années.
TABLE DES MATIÈ:REs
Résumé ii
A van t-propos iii
Table des matières iv
Liste des tableaux vi
Liste des figures vii
2. Introduction généraie 2
2. Quelques éléments de la théorie d'ordonnancement 8
2.1 Introduction 8
2.2 Notation et definition 10
2.3 Une seule machine 13
2.4 f lusieurs machines identiques en paralléle 14
2.5 L'atelier mono-gamme 15 2.5.1 Atelier mono-gamme à deux machines 16 2.5.2 Atelier mono-gamme à m machines 17 2.5.3 Heuristiques 20 2.5.4 Ordonnancement cyclique 22
2.6 Autres ateliers 24
2.7 Conclusion 25
3. Revue de la litiérature 26
3.1 Mise en situation 26
3.2 Caracterisation des problémes étudies 34 3.2.1 Cas stochastique 35 3.2.2 Ateliers ouvert et multi-gammes 36 3.2.3 AteIier mono-gamme avec un seul produit 36 3.2.4 Atelier mono-gamme avec plusieurs produits 45
3 3 Conclusion 61
4. Révision de la mécanique de mouvement du robot 63
4.1 Sélection d'un aménagement de cellule robotique 63
4.2 Description du probléme étudié 67
4.3 Définition de la problématique 68 4.3.1 Cellule à robot centré 69 4.3.2 Cellule à robot mobiic 73
4.4 Calcul des temps de cycle 75 4.4.1 Cellule à robot centré 76 4.4.2 Cellule à robot mobile 79
4.5 Remarques 81
5. Analyse de la performance 84
5.1 Premier exemple 84 5.1. I Discussion 85
5.2 Deuxième et troisihe exemples 89 5.2.1 Discussion 91
6. Extension à trois machines 93
6.1 Calcul des temps de cycle 93 6. t .l Cellule à robot centré 97 6.1.2 Conditions de récurrence 107 6.1.3 Cellule à robot mobile 109 6.1.4 Conditions d'optimalité 116
7. Conclusion générale 125
8. Bibliograplt ie 128
Anrrexe A Lexique Anglais-Français des termes d'ordonnancement 135
Annexe B Analyse des autres ateliers 140
Aariexe C Descriptiort des robots 149
Annexe D DéWs et calculs des exemples 1 58
LISTE DES TABLEAUX
Tableau 1 : Problèmes résolubles en temps polynomùrl 25 Tableau 2 : Problèmes NP-durs 25 Tableau 3 : Récapitulat$des contributions dans la linérature 61 Tableau 4 : Temps de traitement der oràres de jàbrication de l 'exemple 1 84 Tableau 5 : Comparaison des résultau de l'exemple 1 85 Tableau 6 : Temps de traitement des ordres de fabrication de l'exemple 2 90 Tableau 7 : Temps de traitement des ordres de fabrication de l'exemple 3 90 Tableau 8 : Comparaison des résultats de l'exemple 2 90 Tableau 9 : Comparaison des résultats de i'exemple 3 91 Tableau 10 : Graphe des possibilite5 selon la séquence S,.J 122 Tableau I I : Graphe des possibilitk selon la séquence SZ3 122 Tableau 12 : Graphe des possibilités selon la séquence S,J 123 Tableau 13 : Graphe des possibilitésselon la séquence S ~ J 123 Tableau 14 : Graphe des possibilitk selon la séquence &J 123 Tableau 15 : Graphe des possibilités selon la séquence Sa 124 Tableau C-1 a : Spéci/cations génémles du modèle KarelS-300 152 Tableau C-1 b : Caractérirtiques cinématiques du modèle KarelS-300 152 Tableau C-2 a : Spéc$cations générala du mod& C M Plus A460 154 Tableau C-2 b : Caracrérhtiques cinématiques du modèle CRS Plus A460 154 Tableau C-3 a : Spéc$cations générales du modèle 1.M 7576 157 Tableau C-3 b : Caractéristiques cinématiquer du modèle IBM 7576 157 Tableau D-1 : Temps de rraitement der ordres de fabrication de l'exemple 1 159 Tnbleou D-2 : Données intermédiaires pour le robot GMF (exemple 1) 160 Tableau 0-3 : Étape 1 de l'algorirhme de Gilmore & Gomoy pour l'exemple 1 160 Tableau 0-4 : Étapes 2 et 3 de l'algorithme de Gilmore & Gomoty pour l'exemple 1 161 Tableau 0-5 : Étapes 4 et 5 de l'algorithme de Gilmore & Gomoty pour l'exemple 1 162 Tableau 0 -6 : Valeurs de la fonction Y *O) pour l'exemple 1 163 Tableau 0-7 : Données intermédiaires pour le robot CRIT (exemple 1) 166 Tableau D-8 : Temps de traitement des o r d m de Jobrication de 1 'exemple 2 169 Tableau 0-9 : Données intermédiaires pour le robot GMF (exemple 2) 1 70 Tableau D-IO : Étape 1 de l'algorithme de GiImore & Goniory pour le robot GMF (exemple 2) 1 70 Tableau D-11 : Étapes 2 et 3 de l'algorithme de Gilmore & Gomoy pour 1 'exemple 2 171 Tableau D-12 : Étapes 4 et 5 de l'algorithme de GiImore & Gomoy pour l'exemple 2 172 Tableau 0-13 : Valeurs de la fonction Y '0) pour 1 'exemple 2 1 73 Tableau 0-14 : Données intermédiaires pour le robot CRS {exemple 2) 1 75 Tableau D-15 : Étape 1 de l'algorithme de Gilmore & Gomory pour le robot CRS (eremple 2) 1 76 Tableau 0-16 : Temps de traitement des ordres de fobncation de l'exemple 3 1 79 Tableau 0-17 : Données intermédiaires pour le robot GMF (exemple 3) 1 79 Tableau D-18 : &ape 1 de I'algoriihme de Gilmore & Gomory pour le robot GMF (exemple 3) 180 Tableau 0-19 : h a P a 2 et 3 de I'algorirhme de Gilmore & Gomoty pour l'exemple 3 180 Tableau D-20 : Étapes 4 et 5 de l'algotfthme de Giimore & Gomoty pour l'exemple 3 181 Tableau 0-21 : Valeurs de la fonction Y *O) pour I'exemph 3 182 Tableau D-22 : Données intennèdiairer pour le robot CRS (enemple 3) 184 Tableau 0-13 : Temps de traitement des or&= de fübrication de l'exemple 4 187
LISTE DES FIGURES
Figure 1 : Exemple de cellule robotique 4 Figure 2 : Cellule à une seule machine 13 Figure 3 : Cellule à 3 machines en parallèle 14 Figure 4 : Atelier mono-gamme à trois machines 15 Figure 5 : Graphe orienté de Fm l p n n u / ~ , 18 Figure 6 : Arbre de classification des problhes 34 Figure 7 : Aménagement de cellule robotique "Circulaire" 35 Figure 8 : Aménagement de cellule robotique "d deux robou" 3 7 Figure 9 : Aménagement de cellule robotique "Linéaire" 40 Figure I O : Aménagement de cellule flexible "Simple" 48 Figure I I : Aménagement de cellufe robotique "En Il" 50 Figure 12 : Aménagement de cellule robotique 'd robot transporteur" 51 Figure 13 : Aménagement de c e M e robotique 9 robot mobile" 53 Figure 14 : Aménagement de cellule robotique "A robot centré" 54 Figure 15 : Aménagement de cellule robotique "d robou en ligne" 54 Figure 16 : Aménagement de celluIe robotique "A robot couplé" 58 Figure 17 : Aménagement de cellule robotique sélectionné 65 Figure 18 : Trajectoire théorique d'un robot de manutenh'on 70 Figure 19 : Trajectoire efective d'un robot de mnutenhon 71 Figure 20 : Calcul de la dtktance entre deta stations 72 Figure 21 : Mouvements selon lo séquence 75 Figure 22 : Mouvements selon la séquence S2, 75 Figure 23 : Cellule à trois machines a robot mobile 94 Figure 24 : Mouvements selon la séquence SIaJ 94 Figure 25 : Mouvements selon la séquence SIvj 95 Figure 26 : Mouvements selon la séquence SA 95 Figure 27 : Mouvements selon la séquence S4, 96 Figure 28 : Mouvements selon la s!quence S,,, 96 Figure 29 : Mouvements selon la séquence S63 97 Figure 29 : Passage de detu à troir machines pour 1 'algorithme de fohmon 124 Figure C-1 : Axes de mouvement du robot KarelS-300 150 Figure C-2 : Zone de m i l du rohr Karel S-300 151 Figure C-3 a : Zone de travail du robot CRS Plus A460 (we en plan) 153 Figure C-3 b : Zone de navail du robot CRS Plus A460 (me en élévation) 113 Figure C-4 : Mouvements possibles du manipulateur 155 Figure C-S : Espace de travail du modèle IBM 7576 136 Figure D-1 : Graphe non orienté initialpur I'exemple 1 161 Figure D-2 : Nouveau graphe non onénté pour l'exemple 1 Id2 Figure 0-3 : Diagramme de Gantt potn le robot GME? (exemple 1) 1 64 Figure 0-4 : Calcul du rayon de la cellule 167 Figure D-5 : Graphe non orienté initial pour l'exemple 2 171 Figure D-6 : Nouveau graphe non orientépour l'exemple 2 172 Figure 0-7 : Diagramme de Gantt pour le robot GMF (exemple 2) 173 Figure D-8 : Diagramme de Gan# pour le robot CRS (exemple 2) 1 76 Figure D-9 : Représentation de la cellule à robot centré 177 Figure D-IO : Graphe non orienté initial pour 1 'exemple 3 181 Figure D-11 : Nouveau graphe non orienté pour l'exemple 2 181 Figure D- 12 : Diagramme de Gantt pour le robot GMF (exemple 3) 183
1. INTRODUCTION GÉNERALE
Les clients changent et avec eux, la nature de leur demande. Elle devient spécialisée,
sinon carrément personnalisée, ce qui amène des variations importantes dans la gamme
de produits offerte par une entreprise. Leur muititude et leur complexité, joint à une
compétitivité internationale toujours plus grande, exercent beaucoup de pression sur la
réduction des coûts de production.
Cela requiert Ie développement de technologies et de méthodes alternatives permettant la
production de petits lots. L'on vise essentiellement a acquérir les avantages de la
production de masse tout en retenant la flexibilité de la production manuelle.
L'implantation et la compréhension des systèmes manufacturiers flexiiles (FMS)
répondent à plusieurs de ces objectifs. L'ordomancement de ceux-ci est cependant l'une
des facettes qui cause le plus de tracas aux chercheurs contemporains.
En effet, la flexibilité aux changements internes et externes est la pierre angulaire du
design des systèmes manufacturiers modernes. Et les FMS onient plus que la flexibilité.
C'est un concept clé qui améliore la productivité à partir d'une situation de volume
moyen et de variété moyenne, mais aussi une stratégie complète pour repenser les
opérations de la compagnie allant de I'approvisio~ement et des procédures de
commande A ta distribution et au marketing.
Les bénéfices résultants de l'implantation d'un FMS transgressent toutes les Eiontières
fonctionnelles d'une organisation. Les principaux sont associés aux caractéristiques de
réceptivité à court terme et d'accommodation a long teme de ia cellule flexible. Ils
touchent différents aspects, autant les machines, que le routage, le volume ou la gamme
de produits, et procurent les bienfaits suivants :
> Réduction des exigences en personnel en enievant de la main-d'œuvre directe
(des opérateurs) aux machines ;
R Hausse du taux d'utilisation des machines à travers la réduction des temps de
réglage, de changements d'outils et de maintenance ;
3 Réduction des inventaires, de l'entreposage intermédiaire (en-cours) et de la
désuétude des pièces par un meilleur roulement ;
3 Meilleur contrôle opérationnel entre autres par des mécanismes defeed-back ;
3 Diminution des taux de rebut et du prix de revient ;
> Réduction des délais de livraison.
Un seul inconvénient notable : l'investissement initial est élevé. Plusieurs compagnies
ont ainsi priviIégié une soIution médiane soit celle d'un investissement plus modéré pour
une cellule plus petite et moins intégrde. Contenant quelques machines à commande
numérique et un simple robot de manutention, on l'appelle cellule manufacturière flexible
(FMC au Iieu de FMS). Moins drspendieuse donc plus répandue que l'encombrante et
complexe FMS, son opération et sa maintenance sont grandement facilitées, d'autant plus
qu'eue est souvent formée de machines indépendantes converties en FMC. D'ailleurs, de
tels systèmes sont moins susceptibles de briser et c'est pourquoi on la retrouve
communément même chez la moyenne entreprise.
Ainsi, il y a de nombreuses configurations de FMS possibles, dépendant des niveaux de
fiexibiIité désirés et des taux de production visés. De plus, Ie degré d'automatisation des
machines-outiis, des dispositifs de manutention du matériel (robot, véhicule à guidage
automatique ou autre) et des systèmes ordinés (les trois composantes majeures d'un
système manufacturier flexible) peut grandement varier en fonction des buts de
l'organisation et des fonds disponibles. Par contre, toutes sont capables de
s'accommoder des changements de procédé et d'ingdnierie pouvant se produire.
L'industrie des pièces automobiles est actuellement le leader dans l'utilisation des FMS.
Le domaine d'application le plus prometteur est I'assembIage flexible (qui est le plus
grand utilisateur de main-d'œuvre manuelle), où à nouveau des cellules moins intégrées
se tireraient fort bien d'affaire avec un déboursé moindre. Il y a un formidable potentiel
de croissance pour les FMS et les FMC en Amérique du Nord, en Europe et au Japon.
Dans ce mémoire, les aspects planification et aménagement des FMC, seront davantage
discutés, plus spécifiquement l'ordonnancement de ces cellules complexes. Réalisé sous
la direction de Mme Sophie D'Amours et de M. Fayez Boctor, il porte sur
l'ordonnancement de la cellule robotique, c'est-à-dire un FMS décentralisé ou un FMC,
composé d'un certain nombre de machines automatisées et dont un robot programmable
servant au transport des pièces entre celles-ci.
L'ordonnancement est un processus décisionnel se retrouvant dans la plupart des
systèmes de production. En entreprise, des commandes sont reçues et transformées en
ordres de fabrication, qui doivent être traités par des machines selon une certaine
séquence. Rappelons que l'ordonnancement des opérations, une étape importante de la
planification de Ia production, consiste en l'allocation de ressources limitées aux diverses
tâches en fonction du temps. De façon concise, il s'agit de planifier quand et sur queiie
machine les produits sont traités, à quoi nous devons ajouter en cellule robotique,
comment ils y sont transportés. Voici un exemple de cellule robotique :
convoyeur
sortie
convoyeur entrée
Figure 1 : Exemple de cellule robotique
La transition des cel1ules traditiomeiies aux cellules flexibles s'explique par le fait que
les secondes remplacent de plus en plus les premiéres dans l'industrie, car elles en
augmentent la productivité. La productivité de la cellule flexible est cependant
grandement dépendante de la séquence de produits et de la série de mouvements du
dispositif de manutention du matériel (ghéralement un robot). Un ordonnancement
efficace est alors essentiel pour minimiser les temps morts, et ainsi diminuer les délais et
les inventaires.
L'intérêt porté à cette question des plus actuelles date seulement du début des annees
1990. Déjà, le problème de minimisation du temps de cycle de l'atelier mono-gamme a
deux machines approche de son dénouement ; tandis que celui à m machines demeure
rebutant. En fait, on ne peut toujours pas parvenir à une solution optimale pour le cas a
trois machines et plus. Aucun algorithme efficace (au sens de la théorie de la complexité)
n'a encore été proposé non pIus.
La problématique de développement de ces algorithmes provient du fait qu'étant donné la
nature des problèmes considérés, la majorité des chercheurs ont jusqu'ici ndgligé certains
éléments opérationnels de la cellule manufacturière (entre autres, les dates dues des
ordres de fabrication, les coûts encourus par leur traitement, les réglages des machines,
etc.). Cela peut cependant conduire B d'importantes pertes de productivité dans un
environnement de production réel. Pour notre part, nous avons porte notre attention sur
Ia mécanique du mouvement du robot qui est à notre avis défaillante. Par exemple, les
travaux font surtout état de mouvements à vitesse constante, alors qu'il n'en est rien pour
les robots de manutention standards.
Ce mémoire est divisé en cinq chapitres principaux qui sont intituiés : Quelques éléments
de la théorie de l'ordonnancement, Revue de la littérature, Révision de la mécanique du
mouvement du robot, Analyse de sensibilité et Extension à trois machines.
Globalement, la méthodologie employée consiste B faire une revue de Littérature portant
sur I'ordomancement d'une cellule robotique afin d'analyser les méthodes que les auteurs
ont proposées jusqu'a maintenant. Nous avons ensuite sélectionné un aménagement de
cellule robotique et développer un modèle mathématique adkquat, puis résolu ce modèle
plus conforme à la réalité industrielle, que ce soit à l'aide d'heuristiques (trois machines)
ou idéalement, par des algorithmes optimaux (deux machines).
Plus en détail, nous introduisons en premier lieu la théorie de base concemant
l'ordonnancement. Nous présentons en fait les éléments qui nous seront utiles lors de
L'analyse des celluLes robotiques faisant l'objet de ce mémoire. Ce sujet étant vaste, le
chapitre est séparé en sept sections, dont une pour chacun des quatre environnements
manufacturiers que l'on rencontre en pratique : une machine, plusieurs machines
identiques en parallèle, atelier mono-gamme et autres ateliers. La notation d'usage y est
également décrite et les définitions classiques énoncées. Une brève conclusion permet de
faire le lien avec le chapitre suivant.
Min de bien situer l'état d'avancement du savoir, nous réalisons par la suite une revue de
littérature approfondie dans laquelle nous exposons un résumé des percées effectuées,
surtout dans la dernière décennie, sur le sujet qui nous concerne. La premikre section est
une mise en situation où l'on explique ce qui a motivé la recherche en ordonnancement
de cellule robotique, principalement que le temps de transfert du dispositif de
manutention du matériel entre les machines n'est pas négligeable. Un tableau
récapitulatif vient clore le chapitre en guise de conclusion.
Après avoir choisi un aménagement de celluIe robotique de même que donné notre
propre notation et nos hypothèses, le troisième chapitre contient les développements dans
la mécanique des mouvements du robot qui mènent à une expression renouvelée des
temps de cycle. Leur structure spéciale nous permet ensuite d'appliquer l'algorithme de
Giimore & Gomory [I l] en O(n1ogn) afin de trouver la séquence optimale des opérations.
La dernière section renferme des remarques sur les temps de chargement et Le passage
d'un cycle unitaire à l'autre.
Puis, dans le quatrième chapitre, nous exposons l'influence des principaux paramètres
(temps de transport et de traitement) sur la solution finale par l'entremise de trois
exemples en considérant trois modèles de robots différents (donc neuf problèmes en
tout). Les spécifications de ces robots sont d'ailleurs fournies en annexe. Nous
effectuons de plus une comparakon avec l'algorithme de Johnson CI91 pour le cas a deux
machines et donnons une extension de l'algorithme de Gilmore & Gomory pour une
application au problème de minimisation de la durée totale des opérations.
Finalement, nous étendons notre modèle au cas à trois machines, en reprenant Ia même
notation et les mêmes hypothèses utilisées avec deux machines, excepté qu'il y a trois
fois plus de cycles unitaires à anaIyser. Des expressions tenant compte de la nouvelle
mécanique du robot sont trouvées pour tous les temps de cycle mais le problème de
minimisation gIobal est démontré NP-dur. Des conditions d'optimalité sont enfin
dérivées ; à travers une application numérique sur l'un de nos robots modèles, nous
montrons cependant qu'il est peu probable qu'elles se réalisent dans la pratique.
Il est noter que partout où vous verrez le signe ' en exposant suite A un mot ou un groupe
de mots mis en gras, cela signifie que le terme rencontré pour la première fois dans le
corps du mémoire se trouve dans le lexique anglais-fiançais des termes
d'ordonnancement à l'annexe A. Ce lexique a été inséré de manière à faciliter le passage
de ce texte à la littérature scientifique générdement rédigée en anglais.
QUELQUES ÉLEMENTS DE LA THÉORIE
D'ORDONNANCEMENT
Nous présentons dans ce chapitre quelques éléments de la théorie d'ordonnancement afin
d'abord, de bien asseoir la base de savoir nécessaire pour entreprendre de plain-pied les
chapitres qui vont suivre, et ensuite, de bien situer l'ordonnancement de cellule robotique
par rapport à un ensemble beaucoup plus vaste qu'est l'ordonnancement tout court. Nous
n'avons pas la prétention de relater ici toute l'histoire de l'ordonnancement depuis ses
débuts il y a un demi-siècle, mais seulement quelques bribes.
2.1 Introduction
L'ordonnancement , une étape importante de la planification de prodiiction, concerne
l'allocation de ressources limitées aux différentes tâches en fonction du temps. Les
ressources et les tâches peuvent prendre diffdrentes formes, bien que dans le cadre de ce
mémoire, ce soient des machines et des opérations manufacturiéres respectivement. De
plus, la classification des problèmes s'effectue selon la co~gucation de la cellule et les
objectifs visés qui peuvent aussi être divers.
De façon concise, l'ordonnancement consiste donc à déteminer quand et sur quelle
machine les produits sont traités. La cédule est souvent donnée sous la forme d'un
diagramme de Gantt, qui possède l'aspect d'un diagramme A barres avec les machines en
ordonnée et le temps en abscisse.
L'ordonnancement est un processus décisionnel se retrouvant dans la plupart des
entreprises etfou systèmes de production. Certaines conditions particulikres a évaluer a
priori sont : la disponibiIité des machines, le processus d'arrivée des ordres de fabrication
(statique ou dynamique) et s'il y a une machine aitemative pour une opération ou une
restriction sur une autre ressource. Elles peuvent simplifier ou compliquer le problème.
Dans un environnemerit manufacturier, des commandes sont reçues et transformées en
ordres de fabrication . Ceux-ci sont traitbs par des machines en atelier dans un certain
enchaînement. Us doivent parfois attendre aux machines occupées, et une
discontinuation des opérations peut parfois survenir lorsqu'un ordre de fabrication
prioritaire arrive à la machine qui les traite. Des événements imprévisibles peuvent aussi
survenir dans l'usine tels que panne et bris de machines.
En général, le choix d'une séquence d'exécution des produits ' a un impact significatif
sur la performance du système. De plus, l'ordonnancement interagit souvent avec
d'autres fonctions de l'organisation : l'on doit considkrer le niveau des inventaires, les
pr6visions de la demande ' , l'aiiocation des ressources i court et long terme (dont on
tente d'optimiser l'utilisation) et la gamme des produits.
D'abord, dans tous les problèmes d'ordonnancement énumérés ici, la nature des temps et
des dates n'est pas probabiliste : c'est le cas déterministe. De plus, le nombre d'ordres de
fabrication et de machines est considéré fini. Le nombre d'ordres de fabrication est
dénoté par n et le nombre de machines par m. L'indice j refëre à un ordre de fabrication
et I'indice i à une machine. La variable pu représente quant à elle le temps de
traitement ' de l'ordre de fabrication j sut la machine i (l'indice i est omis si tous les
produits ont le même temps de traitement sur une machine).
Un problème d'ordonnancement est souvent décrit par un triplet alal y (voir Pinedo
[38]), où a décrit l'environnement manufacturier (une seule entrée), fournit des détails
sur les caractéristiques du procédé et des contraintes (il peut contenir aucune, une seule
ou plusieurs entrées) et ycontient l'objectif à optimiser (habituellement une seule entrée).
Voici les possibles configurations de cellule spécifiées dans le champ a :
P Une seule machine (1) : C'est le plus simple de tous les cas et un cas spécial de
tous les autres environnements plus complexes ; la minimisation de la dur&
totale des operations ' y est entre autres triviale car la séquence des ordres de
fabrication est sans importance, nous y reviendrons.
3 Msichines identiques en parallèle (Pm) : il y a m machines identiques en parallèle ;
les ordres de fabrication requièrent une unique opération et peuvent être traités en
théorie par n'importe quelle machine. Celles-ci peuvent cependant avoir des
vitesses différentes vi (à l'opposé des vitesses uniformes).
P Atelier mono-gamme ' (Fm) : Chaque ordre de fabrication doit être traité par
chacune des m machines en série, et ce, dans Ie même ordre. Tous les produits
ont donc le même routage . En temps normal, toutes les fles d3attente des
machines (le cas échéant) opèrent selon la règle premier rendu premier servi
(FCFS), ce qui signifie qu'une pièce ne peut pas en dépasser une autre. Si tel est
le cas, il est convenu de l'appellation atelier mono-gamme à permutation et l'on
inscriraprmu dans le champ P.
3 Atelier mono-gamme flexible (FFs) : C'est une généralisation de I'atelier mono-
gamme et des machines parallèles en ce sens qu'au lieu de m machines en série, il
y a s stages en série contenant des machines en pardèIe. Chaque ordre de
fabrication traverse les stages dans le même ordre, en utilisant une seuie machine
par stage. Les files d'attente fonctionnent généralement selon la discipline FCFS.
3 Atelier ouvert (Om) : Chaque ordre de fabrication doit être par traité par les m
machines. Cependant, il n'y a aucune restriction quant au routage emprunté par
les produits, même que certains peuvent avoir des temps de traitement nuls à des
machines en particulier.
3 Atelier multi-gammes ' (Jm) : Chaque produit possède ici son propre routage,
bien que certains puissent avoir a visiter une même machine plus d'une fois.
C'est le phénomène de recidat ion et l'inscription r e m apparaît alors dans le
champ P.
D'autres inscriptions possibles dans le champ P sont :
3 Divisibilith des opkrations ' @mp) : Celle-ci implique qu'une opération peut
être interrompue à n'importe quel moment avant sa complétion. Ce travail n'est
cependant pas perdu puisque lorsque la pièce est remise sur la machine, elle n'a
besoin que du temps de traitement restant,
3 Permutation @mu) : Cette inscription peut apparaître dans le cas de I'atelier
mono-gamme, indiquant que les ordres de fabrication en attente sont procédés
selon la règle du premier rendu premier servi. Cela implique que la séquence de
produits sur la première machine est maintenue tout au long du système.
3 Contraintes de précédente (prec): Eues peuvent apparaître dans un
environnement à une seule machine ou à machines identiques en parallèle, et
signifient que certains ordres de fabrication doivent 8h.e compIétés avant que
d'autres puissent débuter.
3 Blocage (block) : Ii peut apparaître dans l'atelier mono-gamme si ce dernier a un
espace d'entreposage intermédiaire limité. Le blocage survient plus
précisément quand la zone tampon de stockage en aval d'une machine est
pleine. La pièce doit alors demeurer sur la machine en amont jusqu'à ce que de
I'espace y soit libéré. Le cas le plus fidquent de blocage est celui OU il n'y a
aucun espace d'entreposage intermédiaire. A ce moment, un produit ne peut
quitter une machine tant que la suivante n'est pas libre.
P Contrainte de non-attiente (nwt) : Les produits qui y sont soumis ne peuvent
alors pas se permettre d'attendre entre deux machines successives sans quoi des
défectuosités pourraient en résulter.
Dans le champ y, les critères à optimiser dépendent habituellement du temps de
cornplétion, qui bien sûr est fonction de la séquence choisie. Celui que L'on rencontre le
plus régulièrement est sans contredit la minimisation du temps de cycle ' qui équivaut ai
somme à la minimisation de la durie totale des opérations en r6gime permanent ' (ou si
l'on préfère dans l'hypothèse d'un contexte cyclique) et la maximisation du rendement
de la cellule . En pratique, c'est I'intervalle entre deux événements identiques à se
produire dans le système. On retrouve aussi parfois le retard maximum et ie temps de
présence moyen en atelier .
2.3 Une seule machine
Le cas le plus simple est évidemment celui du problème avec une celiule d'une seule
machine. On peut la représenter comme suit :
machine u t rn produits
Figure 2 : Cellule B une seule machine
Si les hypothèses sont :
chaque ordre de fabrication est composé d'une seule opération
rn tous les ordres de fabrication sont disponibles en début de période
il n'y a pas de temps mort ' entre les ordres de fabrication
Alors, les théorèmes suivants s'appliquent :
le temps de cycle est toujours le même quel que soit l'ordre d'exécution
la règle du temps de traitement le plus cuwi (SPT) minimise le temps de
présence moyen en atelier (que les opérations soient divisLbles ou non)
la règle de la duîe due ta plus tôt (EDD) minimise le retard maximal
minimiser la moyenne pondérée des retards est déjà un problème NP-dur '
' Pour plus de détails sur la théorîe de la complexit8. voir le livre de Gany 8 Johnson [9].
2.4 Plusieurs machines identiaues en paralléle
En ce qui a trait à la situation ou il y a plusieurs machines identiques en paraUle, la
représentation de cette cellule est la suivante :
machine 1
machine 2
machine 3
produits
Figure 3 : Cellule A 3 machines en paralléle
Si les temps de traitement sont déterministes et les opérations indivisibles, les théorèmes
suivants servent A sa résoIution :
Le problème de minimisation du temps de cycle est NP-dur, mais la règle du
temps de traitement le plus long + (LPT) de même que l'heuristique Multifit
donnent des résultats satisfaisants, Cette demière affecte les opérations, dans
l'ordre décroissant de leur durée, à la première machine capable de la finir
avant une certaine date cible.
Pour minimiser le temps de présence moyenne en atelier, on utilise une régle du
temps de traitement le pIus court (SPT) modifiée, où l'on affecte les opérations
dans les positions i, m-ti, 2m+iy . . . du classement par ordre croissant des temps
de traitement sur la machine i (i = 1 à m).
2.5 L'atelier mono-gamme
Dans plusieurs usines ou cellules de travail, un certain nombre d'opérations ont à être
réalisées sur tous les produits, et ce, dans un ordre unique et établi, ce qui implique que
tous les ordres de fabrication ont le même routage. Cet environnement se nomme
I'atelier mono-gamme, le voici :
Figure 4 : Atelier mono-gamme B trois machines
0 0 t 4
À l'intérieur de celui-ci, les espaces d'entreposage intermédiaire peuvent être
virtuellement infinis (surtout quand les produits sont petits) ou bien limités (surtout quand
les produits sont gros) ce qui peut causer du blocage. La même séquence doit alors être
maintenue dans toute la cellule, de sorte que les files d'attente des machines fonctionnent
selon le principe premier rendu premier servi (FCFS).
Par ailleurs, les résultats concernant la minimisation du temps de cycle ou de la durée
totale des opérations étant déjà assez ardus à obtenir, nous porterons davantage notre
attention sur ceux-ci. Ainsi, il existe un ordonnancement optimal pour le cas a deux
machines où la même séquence est maintenue tout au long des machines (donc à
permutation).
produits machine 3 machine2 4 4 machine 1
2.5.1 Atelier mono-gamme a deux machines
Considérons le problème de minimisation de la durée totale des opérations pour l'atelier
mono-gamme à deux machines F ~ ~ ~ T I ~ U ~ C , , , avec un espace d'entreposage
intermédiaire infini entre celles-ci : c'est le cas le plus simple. ii y a n ordres de
fabrication et l e u temps de traitement sur les machines 1 et 2 est respectivement pi J et
pli . La règle qui minimise la durée totale des opérations est communément appelée la
règle de Johnson [19] et fonctionne comme suit atin d'obtenir la séquence optimale :
Séparer les ordres de fabrication en deux groupes Jt et JR , le premier contenant ceux dont pii 5 pz, et le second ceux dont pl > pzi . Les ordres de fabrication du groupe JL sont ordonnancés en ordre croissant de p t ~ (donc selon la règle SPT), et ceux du groupe JR en ordre décroissant de pl, (donc selon la règle UT), Alors, la séquence optimale d'exécution est celle obtenue par JL , JR .
La séquence obtenue est la seule qui soit optimale pour F2 1 prmu 1 Cm si tous les temps
de traitement sont différents. Malheureusement, cette méthode ne peut être généralisée
au cas à plus de deux machines. Il a aussi été démontré par Gilmore & Gomory [I l ] que
le problème de minimisation de la durée totale des opérations de l'atelier mono-gamme à
deux machines sans zone tampon de stockage est équivalent au probleme du commis
voyageur ' (TSP) à n+l villes, où la distance entre les villes j et k est donnée par :
Dans ce cas, la distance totale correspond à la durée totale des opérations. De plus,
minimiser la somme de tous les temps morts revient aussi à un TSP a n+l villes. La
version à trois machines ne peut quant A eIIe Stre ddcnte comme un problème du commis
voyageur et il a été démontré dans la littérature qu'elle est NP-dur (voir Garey et al.
[ l O l > -
2.52 Atelier mono-gamme à m machines
Le cas avec plus de deux machines est éminemment plus complexe. Même si la règle de
Johnson ne s'étend pas au cas à plus de deux machines, le problème de minimisation de
la durée totaie des opérations pour l'atelier mono-gamme à pennutation à m machines
~ r n l prmu 1 C, peut toutefois être formulé en un programme ünéaire mixte (MIP).
Nous vous en épargnerons la longue formulation ; sachons cependant que Ia variable de
décision binaire x,k est égale h 1 si I'ordre de fabrication j est réaiisC 6 la Pm' position de
la séquence et O autrement. Il est a noter que l'objectif de minimisation de la durée totale
des opérations est ici équivdent à celui de Ia minimisation du temps mort totai sur la
dernière machine. Toutefois, le fait que le problème puisse être formulé sous fome de
programme linéaire mixte ne signifie en rien qu'il ne soit pas NP-dur.
Soit une séquence d'ordres de fabncation jk à j,, pour un atelier mono-gamme a
permutation a m machines. le temps de compI6tion ' de l'ordre de fabncationh à la
machine i peut aussi être calculé a l'aide d'un groupe dYÇquations récursives :
La valeur de Ia durée totaie des opérations sous une certaine séquence peut aussi être
trouvée en déterminant le chemin critique du graphe orienté lui correspondant qui est
construit de la manière suivante : pour chaque opdration, disons le traitement de l'ordre
de fabrication j k par la machine i, il y a un nœud (i&) dont le poids est égal à son temps
de traitement pi,j, . Les nœuds ( i j t ) tek que i e [t ,m-l] et k E [LJI-Ilont des arcs aiiant
aux nœuds (i+l&) et ( i jbt) , tandis que les nœuds correspondant à la machine m ou a
l'ordre de fabrication j, ont un seuI naud sortant, et Ie nœud (mi,,) aucun.
Figure 5 : Graphe orienté de Fm
Source : Pinedo [38]
Le poids total maximum du nœud (1 J i ) au nœud (mjn) conespond à la durée totale des
opérations sous la cidule jl , j2 , ... , jn . Il est à noter que celle-ci ne change pas si les
ordres de fabrication traversent l'atelier mono-gamme à l'envers et selon Ia séquence
opposée. C'est le théorème de réversibilité.
Un cas spécial de Fm 1 prmul C, est celui de l'atelier mono-gamme A permutation
proportionnel, où les temps de traitement de l'ordre de fabrication j sont les mêmes sur
toutes les machines, c'est-à-dire p, = pj V j . La durée totale des opérations est alors
Le précédent modèle peut aussi être généralisé pour inclure les machines à vitesses
variables. Si la vitesse de machine i est v i , alors le temps de traitement du produit j sur la
machine. i est pc = pfii . La machine la plus lente est le goulot ' et la durée totale des
opérations dépend maintenant de la séquence sur cette machine. En effet, si la première
(dernière) machine de la séquence constitue le goulot de l'atelier mono-gamme
proportionnel, alors la règle LPT (SPT) minimise la durée totale des opérations.
Les choses se compliquent légèrement si nous considérons ensuite l'atelier mono-gamme
à m machines sans espace d'entreposage intermédiaire entre les machines. Si une
machine donnée termine le traitement d'une pièce avant que la machine en aval ne se
Iibère, ladite pièce doit patienter ce qui cause un temps mort sur la machine en amont. On
désirera alors réduire l'en-cours (WIP) pour diminuer les possibilités de blocage.
Par ailleurs, il est démontré que l'atelier mono-gamme avec un espace d'entreposage
intermédiaire limité entre les machines est mathématiquement équivalent à celui sans
espace d'entreposage intermédiaire, car une telle zone tampon de stockage peut être
considérée comme une machine sur laquelle les temps de traitement de tous les produits
sont nuls. Pour ce modèle, la durée totale des opérations selon une certaine séquence
peut être calculée encore une fois en déterminant le chemin critique du graphe orienté qui
lui est associé, à la différence près que cette fois, ce sont les arcs qui portent les poids ou
distances. Ici, les nczuds (i jk) possèdent deux arcs sortants : l'un va au nœud (i+l,jk) et a
un poids pi+,,j, , et l'autre au nœud (i-ljk) et a un poids nul. Les nœuds (ij,) et (mik) ont
donc un seul arc sortant, tandis que le nœud (mj,) n'en possède aucun.
La durée totale des opérations sous la séquence j i , j2 , .. . , jn est à nouveau égale au poids
maximal de (O Ji) à (mjn), et la propriété de réversibilité s'étend à l'atelier mono-gamme
sans zone tampon de stockage.
Enfin, considérons le cas où il y a une contrainte de non-attente, c'est-à-dire que dès
qu'une machine termine le traitement d'un produit, ce dernier doit immédiatement être
transféré à la prochaine machine sans quoi des dommages peuvent être causés aux pièces.
En contraste avec le cas du blocage où les ordres de fabrication sont poussés sur la ligne
par les machines en amont, ici les ordres de fabrication sont tirés sur la ligne par les
machines en aval.
Ainsi, il a été démontré que les problèmes F2 lblock( Cm et ET 1 nwtl Cm sont
équivalents. Cependant, ils sont différents à plus de deux machines, car le premier peut
encore être formuié comme un problème du commis voyageur (TSP) contrairement au
deuxième.
2.5.3 Heuristiques
Depuis une trentaine d'années, plusieurs auteurs ont développé des heuristiques, donnant
des solutions sous-optimales, mais qui se sont montrés fort acceptables pour résoudre le
cas général Fm 1 pmul Cm . La liste des méthodes ne se veut pas exhaustive, ce qui
signifie qu'il en existe plusieurs autres qui ne sont pas mentionnées ici.
L'une des toutes premières heuristiques est celle de Palmer qui classe les ordres de
fabrication selon l'ordre décroissant de l'indice suivant (dope index) :
L'heuristique de Dannenbring ramène le tout à un problème fictif a deux machines
auquel on applique la méthode de Johnson. Le temps de traitement de l'ordre de m
fabrication sur la machine fictive 1 est a = (m -i+ l)pg , tandis que celui sur la i-l
machine fictive 2 est bj = ig, .
L'heuristique de Hundal et Rajgopal choisit la meilleure des trois solutions obtenues en
classant les ordres de fabrication selon l'ordre décroissant de :
i) l'indice de Palmer 4
La méthode de Nawaz, Enscore et Ham consiste à résoudre le problème des deux
premiers ordres de fabrication et à trouver la meilleure position pour incorporer les ordres
de fabrication suivants (j = 3 à n) dans la séquence partielle.
La méthode de Campbell, Dudeck et Smith (CDS) consiste quant à elle à résoudre ni-1
probIèmes fictifs à deux machines, où les temps de traitement de l'ordre de fabrication
considéré (j = 1 à n) pour le problème k sont :
auxquels on applique la règle de Johnson comme dans l'heuristique de Dannenbring. On
choisit la meilleure des m-1 solutions.
Une autre heuristique populaire pour le probléme de minimisation de la durée totale des
opérations de l'atelier mono-gamme à m machines est celui de l'ajustement du profil
(PF) qui fonctionne comme suit :
On sélectionne d'abord un ordre de fabrication pour débuter la séquence, par exemple celui dont la somme des temps de traitement est la moins élevée. Évidemment, il ne rencontre aucun blocage dans son passage d'une machine à l'autre, générant ainsi un profil. Pour déterminer quel sera le deuxième ordre de fabrication à procéder, chaque ordre de fabrication restant est testé. Pour chaque candidat, l'on calcule la somme des temps morts aux machines (ou la somme des temps de blocage des produits). Le candidat au plus bas total est sélectionné, créant un nouveau profil. On répète ensuite la procédure pour trouver les troisième, quatrième, jusqu'au nemc ordre de fabrication de la séquence.
On peut de plus accorder un poids plus grand au temps mort sur une machine goulot, car
il est évident que ce temps perdu est plus critique que sur une autre machine moins
occupée. Pour ce faire, l'on multipiiera les temps morts par un coefficient de congestion
de la machine pour obtenir le temps mort total. L'expérience a montré qu'une telle
version pondérée de l'heuristique de I'ajustement du profil fonctionne très bien (voir
Pinedo [3 81).
2.5.4 Ordonnancement cyclique
Considérons le cas d'une production cyclique, c'est-à-dire où la séquence utilisée se
répète périodiquement dans te temps. Il est faux de prétendre que de tels
ordonnancements ont te meilleur rendement possible ; elles ont cependant l'avantage
d'étre simples et c'est pourquoi elles sont largement répandues.
Soit la demande prévue d'une gamme de L produits Nl , N2 , . . . , NL pour une certaine
période, si q est leur plus grand commun diviseur, alors I'ensemble minimal de pièces
(MPS) est :
et le nombre total d'ordres de fabrication est : L L
n = - x ~ , . 4 i-i
On fait clairement ici la distinction entre produits et ordres de fabrication.
Habituellement confondus, iIs n'ont plus la même valeur (sauf cas exceptionnel où tous
les produits ont Ia même prévision de demande) en ordonnancement cyclique car il y a L
produits et n L L ordres de fabrication.
Ainsi, un ordonnancement cyclique est spécifié par la séquence des n ordres de
fabrication dans l'ensemble minimal de pièces. Le fait que les ordres de fabrication
contiennent parfois le même produit n'affecte ep rien le processus : par exemple, les
ordres de fabrication 1 et 2 peuvent contenir le même produit P, ce qui cause des temps
de traitement identiques aux machines. De plus, l'heuristique de I'ajustement du profil
(PF) décrite auparavant pour résoudre Ie problème de minimisation de la durée totale des
opérations de l'atelier mono-gamme A m machines avec possibilitb de blocage
Fm 1 block 1 Cm est à nouveau tout UidiquCe pour minimiser Ie temps de cycle en rbghe
permanent, qui est le temps qui s'écoule entre la répétition de deux événements
identiques.
En considérant que le premier ordre de fabrication à procéder dans la celIule crée un profil sans rencontrer de blocage (ce qui en rialit6 n'est pas impossible car, en régime permanent, il suivrait le dernier ordre de fabrication du MPS précédent), il génère ainsi un profil. L'on sélectionne ensuite le deuxiéme ordre de fabrication à procéder parmi tous ceux restants, soit celui dont la somme des temps morts aux machines minimale. Un nouveau profil est créé et l'on repète la procédure jusqu'à ce que tous Ies ordres de fabrication du MPS soient ordonnancés.
L'expérience a montré que l'heuristique PF performait trés bien, surtout lorsque les
temps morts sur les machines étaient multipliés par un facteur de congestion de la
machine, dans le but d'éviter l'attente a u goulots (voir Pinedo [38]).
2.6 Autres ateliers
La description des ateliers mono-gamme flexible, mdti-gammes, multi-gammes flexible,
ouvert et ouvert flexible est foumie à l'annexe B, ces éléments n'étant pas strictement
nécessaires à la compréhension du mémoire.
2.7 Conclusion
En résumé, résultant de la complexité de ces problèmes d'ateliers - la plupart des
problèmes de minimisation de la durée totale des opérations ou du temps de cycle sont
NP-dur comme le montrent les tableaux ci-dessous - , les chercheurs proposaient
auparavant des algorithmes exacts qui sacrifiaient des éléments techniques de la cellule
manufacturière concrète (transport, chargementldéchargement ' , réglage , etc.). Le
meilleur exemple est sans doute le fameux article de Johnson [19] paru en 1954.
Cependant, ignorer ces éléments pouvait parfois conduire a d'importantes pertes de
productivité comme nous le verrons plus loin.
Tableau 1 : Problémes résolubles en t e m ~ s ~olvnomial
r Type d'environnement Problème 1 1
1 Atelier mono-gamme F2 1 block 1 Cm 1
I Source : Pinedo [38] qui fournit toutes les références de ces rksultats
Atelier ouvert 1
I
Tableau 2 : Problémes NP-durs
021 km Atelier multi-gammes
1 Type d'environnement 1 Probléme 1
I ~ 2 1 km.~
1 Atelier mono-gamme F ~ I Ic, 1
I
I
Source : Pinedo [38] qui fournit toutes les références de ces résultats
Atelier multi-gammes J2 1 recrc 1 C,
Ce chapitre retrace l'accumulation du bagage scientifique en ordonnancement de cellule
robotique sur une période d'environ une décennie. Nous débutons par les articles
novateurs qui ont pavé la voie à I'obtention des connaissances actuelles, puis finissons
par les parutions les plus récentes qui nous encouragent à persévérer dans notre
recherche.
3.1 Mise en situation
Le hic avec les élégants modèles mathématiques est qu'ils font, à notre grand désarroi,
abstraction d'une foule de phénomènes que l'on ne peut négliger en réalité lorsque l'on
résout de « vrais » problkmes d'ordonnancement. Parmi ceux-ci mus retrouvons
notamment :
a) Les modèles théoriques admettent normalement que les n ordres de fabrication B être
ordonnancés sont connus dès le départ. En pratique, le processus se déroule de façon
continue, de sorte que des ordres de fabrication s'ajoutent pendant que d'autres se
réalisent. L'ordonnancement doit donc être fait à prime abord sans une connaissance
exacte du futur. C'est pourquoi la nature dynamique du probI8me requiert du jeu
pour accommoder, par exemple, une a u e n c e inattendue ou une panne.
b) Les modèles théoriques ignorent les réalités du monde du travail que sont les quarts
de travail et le temps supplementaire , tout comme les phénomènes
d'apprentissage et de détérioration dans la distribution des temps de traitement. En
effet, si une tâche répétitive est réalisée par un être humain, ce dernier présentera
probablement une amélioration de sa pwformance (une réduction du temps de
traitement moyen) grâce à l'amélioration de ses méthodes de travail. A l'opposé, si
une machine réalise l'opération, l'âge et l'usure de celie-ci pourraient entraîner une
augmentation de son temps de traitement des produits.
c) Les modèles théoriques ne tiennent pas compte des contraintes de disponibilité des
machines : on pose simplement l'hypothèse qu'elles sont toujours disponibles.
Pourtant, des bris de machines (nécessitant des réparations) surviennent aussi
aléatoirement et remettent en cause cette simplification.
d) Les modèles théoriques ont surtout mis le focus sur des problèmes à objectif unique,
alors qu'en réalité, le planificateur doit jongler avec plusieurs objectifs dont
l'importance réciproque est souvent variable dans le temps.
Le principal élément déclencheur de la recherche dans le domaine de l'ordonnancement
de la cellule robotique est néanmoins autre. Il s'agit de l'omission d'inclure des temps
de transport ' et de déplacement entre les machines les considérant négligeables. Dans
une cellule robotique, ces mouvements requièrent pourtant un temps substantiel si on les
compare aux temps de traitement. C'est donc une carence laquelle les chercheurs
tentent de remédier depuis maintenant une décennie en proposant des modèles qui
incluent cette importante variable.
Ainsi, traditionnellement, l'ordonnancement signifiait planifier quand et sur quelle
machine Ies produits sont traités ; maintenant, en ceIlule robotique, nous devons ajouter à
cela comment ils y sont transportés.
Cette transition s'explique par le fait que les cellules flexibIes automatisées remplacent de
plus en plus la ceIlde traditionnelle en int~strie. On peut définir celle-ci comme un
regroupement de postes de travail reliés entre eux par un dispositif de manutention du
materiel , qui peut être un véhicule P guidage automatique (AGV) un robot ou un
pont roulant . Or, il a été démontré dans la littérature que de tels systèmes augmentent
la productivité.
L'objectif de base du concept du systéme manufacturier flexible ' (FMS) est d'atteindre
l'efficience et les niveaux d'utilisation de la production de masse tout en retenant la
flexibilité des opérations manuelles. L'idée sous-jacente à la production en cellule
robotique est d'identifier des familles de produits qui requièrent des opérations similaires
et confier celles-ci à un nombre restreint de machines spécialisées. La manutention à
l'intérieur de la cellule peut alors être effectuée par un robot de façon très efficace.
Dans la cellule flexible, comme plusieurs machines peuvent requérir les services du
dispositif de manutention, il y aura inévitablement des conflits à résoudre au détriment
d'une machine qui devra attendre qu'une autre soit servie en premier. Ces temps morts
aux machines peuvent diminuer gravement l'efficacité de la cellule s'ils ne sont pas g&6s
correctement. En fait, l'efficacité de Ia cellule dépend grandement (pour ne pas dire
principalement) du juste ordonnancement des mouvements ou tâches du robot.
Leur ordonnancement est cependant plus complexe car il y a deux types de ressources
dont il faut s'occuper: les machines et le robot. Ainsi, le nombre de séquences de
mouvements ou de cédules possibles augmente de façon factorielle avec Ie nombre de
machines (en fait, il y en a exactement m!). Et le fait que les contraintes different
substantiellement des problèmes conventionnels d'ateliers indique qu'il faut être
extrêmement prudent avant d'appliquer des algorithmes de résoiution classiques à ces
nouveaux systèmes : les résultats pourraient alors s'avérer fort décevants.
Comme les règles de contrôle traditionnefles ne font qu'amener le robot à réagir aux
requêtes de service qui lui sont adressées sur la base du premier rendu premier servi
(FCFS), des modèles concurrents doivent être développés afin de faire un meilleur usage
de l'équipement de manutention. Un ordonnancement efficace est donc essentiel afin de
réduire le blocage (c'est-à-dire les temps morts), l'en-cours et les delais de rhlisation ' .
Il y a toutefois certaines hypothèses simplificatrices qu'il nous faut maintenir:
l'introduction d'ordres de fabrication dans le système se fait toujours a coup de n la
fois, tous les temps de traitement sont considérés déterministes, on suppose que toutes les
ressources sont disponibles en tout temps. L'on considère donc un modèle d'atelier
classique mais requérant un temps de déplacement significatif entre les machines, que ce
soit avec ou sans pièce à transférer. Cela se veut plus réaliste, mais complique
évidemment le problème.
Ainsi, ce sont les chercheurs américains Gilmore & Gomory [ I l ] qui, peut-être sans le
savoir, ont ouvert la marche avec un fameux article p a n il y a près de 35 ans. Leur
algorithme exact ramène Le probléme de l'atelier mono-gamme à deux machines avec
contrainte de non-attente B celui du commis voyageur a n+l villes.
Ils y considèrent une machine dont une seule variable décrit l'état. Le problème consiste
a y ordonnancer les ordres de fabrication JI (i J, , chacun requérant un état initial Ai et
final Bi . Le coût suivant est associé au changement d'état de la machine pour que le
prochain ordre de fabrication puisse débuter :
où f(x) et g(x) sont deux fonctions intégrables qui satisfont f(x) + g(x) 2 0.
En fait, c'est la un cas spécial du problème du commis voyageur (TSP), où les Ji jouent le
rôle des nœuds (viIles) et les cg le poids des arcs les reliant. Ainsi, nous sommes à la
recherche du chemin a coût minimum (que l'on déduit par l'entremise de i'arbre de
recouvrement à poids minimum), et cet article fournit une méthode pour y parvenir, soit
trouver la séquence optimale des J;: . D'ailleurs, tout son développement, d'une rudesse
mathématique éprouvante, ne sert qu'à justifier les diverses étapes de l'aigorithme
proposé.
Il est à noter que le « célébre » algorithme de Gilmore & Gomory que voici est à la base
des récents progrès en matière d'ordomancernent de la cellule robotique. Son temps de
résolution est fonction du nombre de produits au carré (0(n2)).
É t a ~ e 1 : classer les Bi (i = 1 à n) en ordre croissant et renuméroter les ordres de
fabrication en accord avec ce classement
É ta~e 2 : classer les Ai (i = 1 a n) en ordre croissant et déduire la permutation 4 telle que #@) = q tel que A, est le plus petit élément des Ai
Étaue 3 : construire un graphe à n muds avec des arcs non orientés reliants la rh"c nœud au P nœud ; si le graphe n'a qu'une seule composante, passer à l'étape 9
Étape 4 : calculer le coùt des arcs Ri,+l (i = 1 à n-1) reliants deux nœuds
consécutifs selon q i + i = max (0, (min {Ber , h+ll) - max {Bi , AwO)))
Étaoe 5 : ajouter les arcs RLHl à tour de rôle selon l'ordre croissant de leur coût,
jusqu'à ce que Ie graphe n'ait qu'une seule composante connexe
É t a~e 6 : diviser les arcs ajoutés a l'étape 5 en deux groupes ; ceux dont Unu 2
appartiennent au groupe 1, et ceux dont 2XK4 < Bi appartiennent au groupe 2
Étape 7 : trouver le plus grand indice il tel que Ri,J,+, appartient au groupe 1, le
deuxième plus grand indice i2 ... jusqu'à il en considérant qu'il y a I éléments
dans le groupe 1
Étaue 8 : trouver Ie plus petit indice ji tel que Rjtdrl appartient au groupe 2, le
deuxiéme plus petit indice j z . .. jusqu'a j, en considérant qu'il y a m éléments
dans le groupe 2
É t a~e 9 : Ia tournée minimale est obtenue en faisant suivre le Pm ordre de
fabrication par l'ordre de fabrication bv+(i), ou
* ('1 = &i,.ï, *t (ail*il+l -*-(a, .&+i (ff j,.i,+l (a jz.i2+~ ...(aj-,jm+I (O))))))
avec a-@) = q , a,(q) = p et = i (Pour i #p,q)
L'article présente ensuite la variante du cas du goulot où seul le coût des arcs change : il
passe de cdai,+i) à Ci#i+l) = A u ï ~ ) - Br.
Pour terminer, un exemple numérique à sept ordres de fabrication, fort instructif, est
donné pour illustrer la procédure, de même que d'autres types d'application.
Deux autres chercheurs américains ont posé les premiers pas dans le domaine en
montrant la dépendance de la performance d'un système en terme de rendement envers
les stratégies de chargement des machines et les politiques de contrôle des opérations.
Stecke & Solberg [47] analysent l'effet des po titiques de contrôle et de chargement sur le
rendement d'un système manufacturier flexible réel. Ce dernier est composé de neuf
machines, un poste d'inspection, une zone centralisée d'entreposage et un dispositif
automatique de manutention. Comme les machines sont versatiles et capables de réaliser
plusieurs types d'opérations, il peut atteindre un haut niveau d'efficacitk tout en
demeurant flexible.
Plusieurs programmes linéaires mixtes (MIP) ont étt formulés, mais Qaient trop gros
pour être résolus de manière optimale en un temps raisonnable, de sorte que seule une
simulation détaillée sur ordinateur a pu vraiment tester les différentes options. Le critbre
utilisé par les auteurs pour les évaluer est la productivité du système.
Les données de base du problème sont les temps de traitement des produits aux machines
et les temps de d4placement ' entre les postes. Us sont tous déterministes, bien qu'en
réalité, le système est sujet à d'innombrables dérangements. Les contraintes à respecter
sont évidentes :
Chaque opération (et ses outils) doit être assignée à une machine capable de
réaliser la tâche
Les outils requis pour t'ensemble des opérations assignées B une machine (de
formats variés et certains servant pour plus d'une tâche) ne doivent pas excéder
la capacité de son magasin.
Les objectifs, parfois conflictuels, d'équilibrer la charge de travail entre les machines
pour éviter les goulots, d i i u e r le mouvement des pièces dans la celiule et accroître la
flexibilité du système, ont ensuite conduit à cinq politiques de chargement :
Ia politique originale qui assigne chaque opération à une seule machine en
équilibrant la charge de travail pour un routage fixe
un regroupement de deux des trois types de machines pour une charge de travail
moins balancée
même chose que la deuxième, mais davantage flexible en terme de routage
une assignation des opérations dans le but de minimiser le mouvement des
pièces, c'est-à-dire donner autant que possible des opérations consécutives a
une machine, résultant en un fort déséquilibre dans la charge de travail
un regroupement des trois types de machines (infaisable à cause de la contrainte
sur les outils mais gardé tout de même dans un but de comparaison)
Celles-ci, associées à 16 règles de priorité différentes, ont donné 80 scénarios qui ont été
testés à l'aide d'une simulation informatique couvrant 48 heures. Le temps de caicul
varie de 260 à 410 secondes par scénario.
Enfin, les résultats démontrent que, pour ce système, la règle SPTITOT (temps de
traitement le plus court + temps de traitement total pour ce produit) et les politiques 4 et 5
sont les plus performantes. On obtient en les conjuguant une hausse de productivité de
24.3% par rapport à la situation ayant cours dans la cellule avant ces tests, et ce, même si
les charges de travail sont très inégales. Xi serait donc préférable de diminuer les
mouvements de pièces, surtout lorsque les temps de traitement sont failes
comparativement aux temps de transport, quitte à débaiancer la charge de travail.
Puis ont suivi toute une lignée de chercheurs de partout dans le monde qui, un à un, ont
apporté leur précieuse contribution à ce champ de recherche toujours en pleine ébullition.
Nous vous les livrons dans les chapitres qui suivent.
3.2 Caractérisation des ~roblémes étudiés
Cette zrction retrace la progression de la recherche dans le domaine de l'ordonnancement
de la cellule robotique à travers les articles scientifiques qu'elle a produit, de ses percées
il y a plus de 10 ans jusqu'à ses plus récentes parutions. Elle est organisée selon l'arbre
de ~Iassification des problèmes, c'est-à-dire en fonction des principales divisions du
sujet, que voici :
1 Ordonnancement d'une b cellule flexible
Cas déterministe ( Cas stochastique h
Atelier multi-gammes i?
Figure 6 : Arbre de classification des problèmes
3.2.1 Cos stoclrastique
Liu & Lin [3 11 utilisent les réseaux Petri pour la modélisation des têches d'une cellule
manufacturière car ils permettent l'analyse du comportement du système, de même que
son design.
Le système considéré est une cellule robotique circulaire qui comprend quatre machines
(sans zone tampon de stockage) et un robot à deux prises (il peut donc avoir deux pièces
en sa possession) :
outils El
robot 6 Figure 7 : Aménagement de ceiiule robotique "Circulaire"
En plus d'aIimenter les machines, le robot remplace aussi les outils brisés ou usés. Les
temps de traitement des produits par les machines suivent une distribution normale,
tandis que les temps de déplacement du robot sont déterministes.
Trois modèles sont développés de concert avec les réseaux Petri pour indiquer au robot
quelle requête choisir, soit le modèle réactif (FCFS), le modéle anticipatif (Ie robot
anticipe la prochaine requête) et le modele prédictif (le robot prédit les prochaines
requêtes sur un certain horizon). Dans tous les cas, l'objectif est de minimiser le temps
de cycle moyen, et la priorité est donnée à la pièce dans la prise tampon du robot.
Soit , Tm2 et Td désignant respectivement les temps totaux d'opération des modèles
réactif, anticipatif et prédictit il est démontré que, n'eut égard au temps de calcul :
Leurs résultats confmnent que le cas déterministe surpasse le cas stochastique et que
l'utilisation de la prise tampon sur le robot est profitable, surtout lorsque les machines
sont fortement utilisées. Évidemment, ie modèle d'ordonnancement et la vitesse du robot
sont influents, quoique la position du goulot importe peu vu la faible variabilité des temps
de traitement.
3.2.2 Ateliers ouvert et multi-gammes
A notre comaissance, il n'y a pas d'articles qui traitent de ces problémes. À la décharge
des auteurs, ces problèmes sont rencontrés beaucoup moins fréquemment en pratique.
3.2.3 Atelier mono-gamme avec un serrlpwduit
Rabinowitz et al. [39] proposent un modèle de programmation linéaire mixte (MIP) pour
l'ordonnancement répétitif d'une cellule d'assemblage à plusieurs robots. La formulation
est monolithique, soit en un seul gros programme héaire. Voici la cellule :
Figure 8 : Amhagement de cellule roboîique "À deux robotst'
Les données du probIème sont les opérations i requises, leurs modes possibles et les
temps de traitement q , associés. Ici, comme plus d'un robot peut parfois accomplir une
tâche 1, les machines concernées et l'espace physique au-dessus d'elles sont dénommées
une ressource r, au même titre que les robots. Ainsi, dans l'exemple donné, il y a deux
robots et quatre machines, chacun des robots pouvant servir trois machines, donc deux de
manière commune. Chaque opération-mode utilise par ailleurs une certaine ressource I f entre les temps connus t i , , r et 4,, .
Soit la variable de décision suivante :
1 si l'opération-mode (i,m) constitue la 1 tâche de la ressource r Xi.rn.r.~ =
O autrement
Le programme linéaire permet optimiser quatre fonctions objectifs, soit minimiser le
temps de cycle, maximiser la performance, minimiser le coût d'utilisation des ressources,
et équilibrer la charge de travail entre les robots.
En assumant qu'une seule pièce est traitée à la fois, il y a deux types de contraintes dans
ce problème, dont on peut heureusement réduire le nombre étant donnéles
caractéristiques du problème : les contraintes de sélection de tâche et les contraintes de
temps. Pour l'exemple étudié, les quatre fonctions objectif donnent des réçultats
semblables. Pour terminer, les auteurs suggèrent d'ajouter des contraintes budgétaires et
de fiabilité des systèmes afin d'améliorer leur formulation
Dans un autre article, Ioachim & Soumis [16] analysent l'efficacité d'un ordonnancement
de cellule robotique à robot centré. ï i n'y a pas de zone tampon de stockage et les
machines ne peuvent traiter qu'une piéce à la fois. Les opérations sont indivisibles. Le
temps de mouvement nécessaire au robot pour parcourir le rayon du cercle est alors 6
tandis que le temps de chargemenVdéchargernent d'une pièce est E.
Soit une cellule à m machines, on dénote pl , pz , ... , p, les temps de traitement du
produit unique sur chacune des machines. Une séquence de mouvements Sr est associée
a un temps de cycle T?. Le cas le plus simple est celui a deux machines. Deux
séquences sont alors possibles, si2 et St', et leur temps de cycle sont :
où wi est le temps d'attente du robot à la machine i :
wl = max (0, pl - 46- 2.5- wz}
wz = max (0, pz - 46- 2&}
donc, 2': = mur @I,JQ, 46+ 24 + 4(6+ E)
Pour une cellule à m = 3 machines, il y a six séquences, mais une seule est considérée
(sans doute celle qu'ils considèrent la plus probable d'être optimde). Ici, T~~ = 126+ 8&
+ I V ! + w2 + w3
où wl = max {O, pl - 86- 48- w3 - wz)
W Z = max {0 ,p2 - 86- 4s- w3)
wg=rnax ( 0 , ~ ~ - 8 6 - 4 & - w l )
Après maints calculs et simpIifications, on trouve :
T: =4(b+ E) + max {86+ 4cypi,p2,p3).
On s'aperçoit aisément que la difficulté d'évaluer le temps de cycle augmente rapidement
avec le nombre de machines. C'est pourquoi on nous introduit ensuite le réseau des
mouvernene pour faciliter la tAche. Les nauds sont les points visités en ordre. Pour q
pièces produites par cycle, il y a N = 2q(m + 1) + 1 nmds. Il y a de plus deux types
d'arcs : les arcs de mouvement (il y en a N-1) et les arcs de traitement (au nombre de qm).
La longueur des arcs de mouvement est tj-1 j , tandis que celle des arcs de traitement est
soit piol , soit pio, - T", dépendemment de leur orientation.
L'évaluation du temps de cycIe T" revient à ce moment à trouver la durée minimale qui
satisfait toutes ies contraintes de précédence du réseau. On peut d'abord utiliser la
programmation linéaire, la fonction objectif étant de minimiser le temps de cycle. Une
méthode moins exigeante cependant consiste à identifier le chemin le plus long. Elle
procure un algorithme plynomial d'évaluation du temps de cycle, et même une
expression analytique de ce dernier. Le point de départ en est l'évaluation d'une borne
inférieure :
La complexité de cet algorithme est
On étend ensuite les méthodes au cas de plusieurs produits et de plus d'un robot.
Quelques exemples d'application sont donnés au surplus.
Su & Chen [50] étudient Ie problème d'ordonnancement d'un robot mobile à deux prises
monté sur un pont roulant. Iî œuvre sur une ligne de production à temps de traitement
déterministes, d'abord à deux machines puis généralisé à m machines. Leur cellule
ressembre donc à ceci :
r )pi- prise
~-p+-*-***p+ ------- { - q . - S
Figure 9 : Amhagement de cellule robotique "Lindaire"
Notons qu'il n'y a pas de zone tampon de stockage entre les stations de travail. De plus,
le pont roulant a un temps de transport 6entre deux points de s e ~ c e adjacents et un
temps de chargernent/déchargement constant. On pose l'hypothèse que celui-ci ne brise
jamais. Chaque pièce doit prockder de manière séquentielle a travers Ia cellule. Les
opérations sont indivisibles et un seul produit peut occuper un poste la fois.
En considérant que l'on veut utiliser le pont roulant A sa pleine capacité, réduire ses
déplacements, garder les machines occupées et diminuer les temps morts, cinq cédules
sont potentiellement optimales. Le temps de cycle est défini comme le délai entre la
répétition de deux états identiques et l'une des cinq cédules est prouvée optimde pour
deux machines par une analyse mathématique. Même en prenant un temps d'attente
initial t , a l'entrée, elle le demeure.
Le précédent résultat est par la suite étendu à m machines. II est démontré que le temps
de cycle optimal est :
~ = a t m a x ( , B , t , , t ,,..., t , ]
où a = 2 ~ et p = 2(m+1)6 + 2mc
Enfi, l'efficience du robot à double prise est discutée, en comparant ses perfonnances
avec celles d'un robot à simple prise. En assumant les mêmes temps de
chargernenVdéchargement, l'amélioration du temps de cycle, et ainsi du rendement de la
cellule, varie de 10 à 35 % selon les conditions.
Par ailleurs, les auteurs indiquent qu'il serait intéressant de généraliser leur approche à
tous les équipements de manutention.
Crama & Van de Klundert [8] généralisent des résultats antérieurs (principalement ceux
de Sethi et al. [42]) en prouvant que le problème d'ordonnancement cyclique de pièces
identiques peut être résolu de façon polynomiale. Plus pr6cisément, l'on présente une
approche de programmation dynamique qui minimise le temps de cycle. Le temps de
résolution est de 0(m3).
Le problème considéré est le cas général à m machines et un robot, qui transporte les
pièces une à une entre les postes de travail. II n'y a pas de zone tampon dans la cellule
pour du stockage intermédiaire (en-cours). L'objectif est de déterminer la séquence selon
laquelle les pièces procéderont, en privilégiant le cycle unitaire ' . Lep temps de
traitement pi , les temps de déplacement di. et les temps de déchargement E;: des activités i
sont connus.
Il est ensuite démontré que calculer un cycle unitaire optimal revient à caiculer une
permutation optimale des activités. Or, le calcul du temps de cycle d'une permutation
d'activités peut être formulé comme la solution d'un programme linéaire de chemin
critique. Des bornes sont d'abord données au temps de cycle L(@ de la permutation
optirnale n. Dans le cas où 6;: = Set 4 = E t/ i , on a :
max (2(m + l)(b cg), maxi pi +4(6 + E)) s L(n) S max (4m6 + 2(m + l ) ~ , maxi p, + 4(6 + E))
Les permutations pyramidales sont ensuite définies et il est démontré que l'ensemble de
celles-ci contient nécessairement un cycle unitaire optimal, car il est dominant. Il y a 2"'
permutations pyramidales par cellule, où m est le nombre de machines.
Un algorithme qui calcule le temps de cycle d'une permutation pyramidale est ensuite
présenté. Son temps de calcul est O(m). L'algorithme procède par récurrence arrière en
retranchant des activités de la séquence complète et il les ordonne sans temps d'attente.
Par Ia suite, comme un cycle hamiltonien correspond à une permutation à temps de cycle
minimal, un algorithme similaire au plus court chemin du commis voyageur est présenté.
Basé sur une formulation de programmation dynamique ' , une séquence optimale
répétitive peut être obtenue.
Ici, la complexitk de la procédure ne croit pas exponentiellement comme ta simple
énumération de toutes les permutations pyramidales. Le temps de résolution de la
version a reconnaissance n du problème d'ordonnancement cyclique de pièces identiques
est plutet 0(m2) ; tandis que celui de la version (( optimisation » est 0(m3).
Pour terminer, une extension intéressante pour les auteurs concernerait le cas à plusieurs
produits, bien que le concept des permutations pyramidales n'y soit plus applicable.
Levner et al. [28] proposent un algorithme d'ordonnancement cycIique pour un seul
produit. Le nombre de machines rn est arbitraire et la cellule ne contient qu'un seul
robot. Le but est de trouver la séquence de mouvements du robot qui minimise le temps
de cycle sujet à une contrainte de non-attente. Cela signifie que les pièces doivent être
transférées à la prochaine machine immédiatement à la fin d'une opération, sans quoi une
défectuosité surviendrait.
Soit les temps de traitement aux machines tk , les temps de mouvement du robot chargé dk
et à vide entre deux points r, , une borne inférieure au temps de cycle Test:
Selon l'algorithme propos& le problème revient à trouver le T minimal qui n'appartient
pas a u intervalles :
Le temps de résolution est 0(m3loW). L'algorithme, assez lourd, est ensuite appliqué à
un exemple de m = 5 machines.
Pour terminer, les auteurs concluent qu'il serait sûrement possible de simplifier leur
algorithme, de même que d'explorer les problèmes a plus d'un robot, à plus d'un produit
etlou dans d'autres environnements.
Kats & Lemer [20] présentent un algorithme polynomial qui minimise le temps de cycle,
Le problème considéré est celui de l'ordonnancement cyclique d'une cellule robotique
produisant un seul produit de manière répétitive. La cellule contient m machines et un
robot. ii est à noter que chaque machine peut survenir plus d'une fois dans la séquence
de traitement, de sorte que le nombre d'opérations est en général plus grand que le
nombre de machines. C'est le phénomène de recirculation.
De plus, il n'y a pas de zone tampon de stockage dans ta celluie. Une condition de non-
attente est imposée sans quoi cela créerait une défectuosité. Seuls les cycles unitaires,
plus simples, sont examinés et le système est assumé en régime permanent.
Chaque opération k de la séquence S est caractérisée par le temps de traitement tk , le
temps de transport d'une pièce (incluant le temps de chargemenUdéchargement) dk et le
temps de déplacement à vide du robot du point i au point j rv .
Un algorithme dont le temps de résolution o(m4) est ensuite fourni. Ii calcule d'abord les
bornes inférieures :
Et supérieure :
puis le problème de minimisation du temps de cycle revient à un programme linéaire.
Enfin, un exemple iIIustratif a m = 4 machines et K = 5 opérations est donné et résolu.
Selon les auteurs, une extension possible à leurs travaux serait de remplacer la séquence
de traitement par un réseau PERT d'opérations reliées entre elles. Le cas à plus d'un
robot, de même que les cycles à pièces muhiples (h l'opposé d'unitaires) vaudraient aussi
la peine d'être scrutés.
3.2.4 Atelier mono-gamme avec plusieurs produits
Stem & Vitner [48] proposent un dgorithme polynomial sous-optimal. Le problème est
une généralisation du cas de l'atelier mono-gamme et il est formulé selon un problème du
commis voyageur à structure spéciale. L'algorithme de Gilmore & Gomory [I l ] peut
donc lui fournir une borne inférieure.
La cellule considérée possède deux machines en série et un dispositif de manutention du
matériel (robot ou autre) qui lui est dédié pour transporter les pièces d'une machine à
l'autre. Il n'y a pas de zone d'entreposage intermédiaire et le robot et les machines ne
peuvent traiter qu'un produit à la fois.
La notation suivante est utirisée :
ai et bi = temps de traitement du produit i sur les machines A et B respectivement
t i = temps de transport du produit i de la machine A a la machine B
r = temps de déplacement à vide de la machine B A la machine A
4 = temps mort a Ia machine B juste avant le produit à la rmc position de la
séquence
n
L'objectif est de minimiser la durée totale des opérations M = x ( 1 , + 4 ) . Cela revient i- 1
à trouver la séquence ITqui minimise
qu'on peut formuler comme un problème du commis voyageur asymétrique h n+l villes
où le coût de transport des nœuds i à j est donné par :
R
Une séquence optimale est alon celle qui minMise le coüt Z(n) = c,,, + C c , , . Elle ) k r l
k=l
correspond à celle dont le temps mort total S est minimal, c'est-à-dire :
où 4 et 4 sont les séquences des problèmes Pi et Pt . Le temps de résolution de la
procédure proposée est de O(n1ogn) où n est le nombre de produits. Des
expérimentations numériques ont été effectuées sur 12 cas à 25 essais chacun et les
résultats démontrent que l'algorithme s'éloigne de la solution optimale avec une erreur
maximale d'à peine 3 %.
Pour terminer, les auteurs suggèrent de généraliser leur intervention au cas à plus d'un
robot, plus de deux machines et avec entreposage intermédiaire.
Panwalkar [37] traite du problème classique d'ordonnancement de l'atelier mono-gamme
à deux machines avec la contrainte additionnelle suivante : un temps de transport non
négligeable est nécessaire entre Ies machines.
On considère le cas à n produits qui sont traités consécutivement sur les machines A et B.
Les temps de traitement sont respectivement Ai et Bi (i = 1 à n). L'objectif est de
minimiser la durée totale des opérations.
Il n'y a qu'un transporteur dans le systkrne (appelé AGV pour v6hicule B guidage
automatique) qui amène les piéces de A à B en T unités de temps, puis les Livre a la sortie
et revient à la machine A en T unités de temps. Les temps de chargement/déchargement
sont négligeables et il y a des zones tampon de stockage illimitées aux machines.
Il est à noter que si T = T' = O , l'on revient au fameux cas analysé par Johnson [19]. Un
algorithme optimal est ensuite proposé ; son temps de résolution est de o(n3. Voici son
fonctionnement :
Étape 1 : soit A i 1 = max (Ai, T + T t ) V i
Étape 2 : soit l'ensemble U = ( i 1 Ai' c Bi) classé en ordre croissant de Ai', et
l'ensemble V = {i ( Ai ' 2 Bi) classé en ordre décroissant de B i .
Étaue 3 : la séquence Si est U,V ; calcuier sa durée totale des opérations.
Étape 4 : V i 1 Ai c Ar', déplacer le produit i de la fm position B la première
position de la séquence S, et calculer sa durée totale des opérations.
tape 5 : choisir la séquence dont la durée totale des opérations est minimale.
Un exemple numérique a huit produits est enfin fourni pour une meilIeure
compréhension.
Kise et al. [24] proposent un algorithme exact pour l'ordonnancement dans un atelier
mono-gamme où n produits passent par deux machines, MA et Mg, dans cet ordre. Le
transport entre les machines et Ia station d'entrkelsortie ' est effectué par un véhicule a
guidage automatique (AGV). La cellule, dont la représentation suit, ne contient pas de
zone tampon pour l'entreposage d'en-cours.
Figure 10 : Amkaagement de cellule flexible "Simple"
L'objectif est de minimiser la durée totale des opérations. Chaque machine ainsi que
I'AGV ne peuvent traiter qu'un seuI produit à la fois. Les opérations sont quant à elles
indivisibles. La notation suivante est utilisée :
P,U) et P&] = temps de traitement du produit j sur les machines A et B
respectivement, incluant les temps de réglage et de chargementldéchargement
T, , Tb et Tc = temps de transport des produits respectivement de la station
d'entrédsortie à la machine A, de la machine A à la machine B et de la machiue B
à la station d'entréehortie
pc = temps de chargement/déchargernent des produits à la station
d'entrédsortie
Il est ensuite démontré que le moment de complétion du dernier produit, donc la durée
totale des opérations, est donné par :
qui correspond à un cas spécial du problème du commis voyageur étudié par Gihore &
Gomory [ i 11.
Le temps de résolution de l'algorithme proposé est de 0(n3). Un exemple numérique est
enfin donné dans le but de comparer les résultats de l'algorithme optimal avec des
séquences au hasard et selon l'algorithme de Johnson.
Pour terminer la station d'entrédsortie est séparée pour donner :
Les auteurs concluent en suggérant qu'une étude ultérieure porte sur le cas de machines à
zone tampon de stockage de capacité finie.
King et al. [22] développent une approche de séparation et évaluation successive
@&B) alimentée par deux groupes d'heuristiques rapides. La meilleure du premier
groupe fournit la limite supérieure de départ. Le choix se fait entre FCFS et pas de file
pas de disette (NQNS), tandis que l'intrant est préalablement classé ii l'aide d'un
algorithme de Johnson modifié ou d'une combinaison SPT/Johnson. Le deuxième fournit
pour sa part des limites inférieures de façon dynamique.
La cellule considérée est composée de deux machines et un robot. Chaque machine
possède une zone tampon d'attente théoriquement de Iongueur infinie, et les temps de
traitement sont connus (cas déterministe) :
1 I Move 2 1 1 I
Move 1 t
file mlc 2
file mlc 1
robot O Move 3
r
sortie .le u
Figure 11 : Aménagement de cellule robotique "En Ut'
L'objectif est donc de déterminer la séquence de mouvements (les tâches JI que le robot
doit accomplir dans le but de minimiser la durée totale des opkrations. Le modèle est
formulé sous la forme d'un programme linéaire mixte (MïP).
Soit la variable de décision suivante :
1 si la tâche j du produit u suit la tâche m du produit v &,vm =
O autrement
Étant donné le caractere binaire du programme linéaire, la procédure de séparation et
évaluation successive s'applique bien, ce qui nous amène à un sous-problème dont la
structure a la forme d'un problème du chemin le plus long. On obtient ainsi un bon
compromis entre le temps de calcul et L'exactitude de la solution. Ainsi, une simulation a
été réalisée sur 4000 exemples numériques [!], avec une Limite de temps de calcul d'une
minute.
Tel que prévu, les résultats obtenus démontrent que l'efficacité de la routine
heuristiquelB&B est directement proportionnelle à la déviation 6 permise par rapport à
l'optimum et inversement proportionnelle au nombre d'opérations. Entre autres, la
séparation et l'évaluation successive deviennent inefficaces avec plus de 15 opérations
différentes. Par ailleurs, l'heuristique FCFS s'est avéré plus appropriée que NQNS,
tandis que les deux méthodes de classement de I'intrant donnent des résultats similaires.
Une extension de l'étude serait sans doute utile pour tenir compte des pannes et de la
maintenance préventive. On pourrait pour ce faire simplement ajouter une opération.
Levner et al. [30] étudient la celIuIe robotique a deux machines, sans zone tampon de
stockage. Il y est démontré que le problème d'ordonnancement avec des temps de
réglage et de transport dépendants du produit peut être résolu de façon exacte en utilisant
la structure délicate de l'algorithme de Gilmore & Gomory [Il].
Soit une cellule robotique composée de deux machines, un robot transporteur, plusieurs
systémes de stockage et de retrait automatisis (ASRS) à l'entrée et un seul à la sortie
que voici :
AWRS AsCRS ASIRS d'entrée d'enae de scrrüe
Robot transporteur
Figure 12 : Aménagement de cellule robotique "A robot transporteurw
Un ensemble de n ordres de fabrication doivent être traités sur les machines A et B, dans
cet ordre. Le transport entre l'entrée et la sortie de la cellule est effectué par un robot,
celui-là même qui charge et décharge les produits sur les machines. Le robot et les
machines ne peuvent traiter qu'une pièce à la fois et les opérations sont indivisibles.
Le problème consiste à déterminer l'ordre dans Iequel les ordres de fabrication vont être
traités (le même pour les deux machines), de façon a minimiser la durée totale des
opérations. Pour ce faire, un ensemble d'ordres de fabrication est donné, en plus de la
notation suivante :
Lu = temps de chargement du produitj sur le robot à l'AS/RS d'entrée spécifique
T / ~ l ( j ) = temps de transport du produit j de l'AS/RS d'entrke à la machine A par le robot
CAO') et C&) = temps d'ajustement ou de changement d'outil pour le produit j
respectivement sur les machines A et B
LAO') et L&) = temps de chargement du produit j sur les machines A et B respectivement
PAU) et PsO] = temps de traitement du produit j sur les machines A et B respectivement
UA et Ua = temps de déchargement des produits sur les machines A et B respectivement
TA* Bo et = temps de déplacement entre les machines A et B respectivement à vide et
avec un produit
Ta,:@ = temps de déplacement de la machine B à 1'AStRS d'entrée pour cueillir le
produit j
TB,: = temps de transport des produits de la machine B a I'ASIRS de sortie
Uo = temps de déchargement des produits à l'AS/RS de sortie
TO..? = temps de déplacement B vide de 19AS/RS de sortie à la machine A
Les auteurs proposent donc une représentation graphique comprenant trois parties :
initiale (Go), intermédiaire (Gr à Gn-[) et finaie (G,,). Selon celle-ci, la durée totale des
opérations est égale à la longueur de son chemin le plus long, pour laquelle une
expression mathématique est dérivée. Après quelques simplifications, le problème est
réductible a un cas spécial du probIème du commis voyageur étudié par Gilmore &
Gomory. Leur algorithme peut alors être modifié pour un temps de résolution de q n 3 ) .
Ensuite, un exemple numérique est donné pour faciliter la compréhension. La preuve est
aussi faite qu'indure les temps de transport et de rdglage dans ceux de traitement peut
mener à d'importantes erreurs Qusqu'a 10 %), m5me dans le cas d'un petit nombre de
produits.
Finalement, les auteurs proposent de générdiser au cas de plus de deux machines ou plus
d'un robot.
Logendran & Sriskandarajah [32] proposent des méthodes analytiques pour déterminer
une séquence optimale des produits et des mouvements du robot afin de minimiser le
temps de cycle. Trois arrangements de celIuIe robotique à deux machines sont
considérés, soit à robot centré, a robot mobile et à robots en ligne :
rail convoyeur k conmyeut sortie entrée
1
Figure 13 : Aménagement de cellule robotique "A robot mobilett
convoyeur
=Ofie Q robot a Figure 14 : Aménagement de cellule robotique "A robot centrét*
+ Y
I + I 4- 1
/ convoyeur
Figure 15 : Aménagement de cellule robotique "A robots en üpet '
11 n'y a pas de zone tampon de stockage aux postes de travail. Le problhe est montré
équivalent à celui du commis voyageur traité par Gihore & Gomory [Il] et résolu a
l'aide de leur algorithme.
D'abord, le problème a un seul produit est investigué. Pour la c e M e à robot centré, la
notation suivante est utilisée : soit a et b, le temps de traitement sur Ia machine 1 et 2
respectivement, ~i (i = 1 à 6), les temps de chargemenû'déchargement entre l'entrée, les
machines et la sortie, et 6;: (i = 1 à 3), les temps de déplacement entre les m6mes stations.
Il est à noter qu'une constante y est soustraite entre chaque station pour le transport à
vide.
Pour la cellule à robot mobile, la notation est la même, excepté qu'on ajoute une
composante linéaire 4 aux temps de déplacement. Pour la cellule a robots en ligne, un
convoyeur amène les pièces aux postes de travail (distants de Y) où ils sont traités par des
robots fixes.
Il n'y a que deux séquences Si et S2 qu'il est pertinent d'analyser pour les celIules à robot
mobile et centré, ce qui implique que l'une d'elles est optimale. La séquence So de la
cellule à robots en ligne est quant à elle triviale.
Les temps de cycle des séquences SI et Sz pour la cellule A robot mobile sont donnés par :
Or, Si est optimale si a ' + b ' S p et Sz , si a' + b ' 1 p . Bien sûr, ces résultats sont
valables pour le robot centré en posant & = O .
Pour la cellule à robots en ligne, Le temps de cycle est donné par :
To = S+ max {a,bj
Avec plusieurs produits, l'ensemble minimal de pièces (MPS) est obtenu en divisant la
demande prévue d'un produit Li pour une certaine période par le plus grand commun
diviseur d de tous les Li (i = 1 B k). Ainsi, ri = Lid et le nombre total d'ordres de k
fabrication est n = Cr, . On cherche toujours à minimiser le temps de cycle t . Selon i-l
n
la séquence si , T, = na + C (ai ' + bfq) ; selon ia sdquence s2 , i- 1
En ce qui concerne la cellule à robots en ligne : T, = n 6 + 2 maxb,,, ,bu,, ) i=l
On peut alors appliquer l'algorithme de GiImore & Gomory [Il] pour minimiser ces
termes. D'ailleurs, un exemple à cinq produits est donné pour illustrer la procédure. Le
temps de résolution est de l'ordre O(nlogn).
II est enfin démontré que la solution non cyclique optimale surpasse n'importe quelle
solution cyclique sur la base du temps de cycle. De plus, une hausse de la productivité
attribuable a la production de plusieurs MPS dans un cycle est réalisée aux dépens de
l'entreposage d'en-cours, ne rencontrant donc pas Ia demande de façon juste-à-temps.
Pour terminer, les auteurs souhaitent étendre leurs travaux au cas de trois, puis m
machines, toujours à l'aide de mtthodes analytiques.
Hall et al. [14] démontrent d'abord que fa solution optimale d'ordonnancement d'une
cellule à deux machines et un robot produisant plusieurs pièces n'est ghéralment pas
donnée par un cycle unitaire. On y propose ensuite un complexe algorithme (nommé
Mincycle) qui minimise le temps de cycle de façon optimale. Son temps de résolution
est de 0(n4) et on remarque qu'il est moins élevé avec de gros temps de traitement. ii
s'est ainsi révélé efficace pour des problèmes jusqu'à 50 produits.
Le cas général étudié est celui d'un robot dont les temps de déplacement ont des
composantes linéaire et radiale, c'est-à-dire Ia cellule à robot mobile reprise de
Logendran & Snskandarajab [32]. Conune il n'y a pas de zone tampon de stockage sur
les machines, les pièces sont toujours en traitement ou en transit.
Puis, il est démontré que la répétition de cycles unitaires simples domine toute autre
politique pour la production d'un seul article, et ce, pour toute valeur du nombre de
machines m, même si les temps de déplacement sont inégaux. Ainsi, la recherche de la
séquence optimale de mouvements du robot est restreinte aux m! cycles unitaires
possibles. La preuve en est faite a I'aide d'un programme héaire mixte 0).
Ensuite, il est démontré que l'ordonnancement d'une cellule à bois machines et un robot
produisant plusieurs produits, peut être résolu de façon optimale pour quatre des six (3!)
cycles unitaires possibIes, sous certaines conditions mathématiques précises. Le temps
de résolution est alors O(n1ogn). Pour les deux autres séquences, le problème est
cependant NP-complet.
Enfin, il est démontré que toute cellule atteint un régime permanent en un certain nombre
de cycles qui dépend de ses données. La convergence est plus ou moins rapide selon Ie
cas.
Pour terminer, le cas stochastique serait aussi d'intérêt de l'avis des auteurs, de même que
la situation où il y a des zones tampons de stockage aux machines. La possibilité
d'étendre l'étude à tout matériel de manutention serait de plus pertinente.
Kogan & Levner [25] considèrent le problème d'ordonnancement de l'atelier mono-
gamme à n ordres de fabrication. La cellule qui suit possède deux machines avec robot
couplé. On y suggère un modèle graphique qui incorpore tous les éléments majeurs
d'une cellule robotique complète, à savoir le transport, le chargementldéchargement et le
réglage des produits.
Figure 16 : Aménagement de cellule robotique "A robot couplP
Les convoyeurs qui alirneatent les machines ont une capacité d'entreposage
théoriquement infinie. Parmi les opdrations qu'ils réalisent, les temps de transport des
produits aux machines A et B et entre celles-ci sont respectivement donnés par TA , TB et
TAB . Les autres paramètres inhérents à la cellule sont :
PA(i) et PB(i) = temps de traitement du produit i respectivement aux machines A et B
LA(i) et LB(i) = temps de chargement du produit i respectivement aux machines A et B
UA(i) et UB(i) = temps de déchargement du produit i respectivement aux machines A et B
SA(i) et SB(i) = temps de réglage requis pour le produit i respectivement sur les
machines A et B
FA(i) et Fe(i) = temps d'installation du produit i respectivement sur les machines A et B
L'objectif est d'ordonnancer les ordres de fabrication en minimisant la durée totale des
opérations. Pour ce faire, le processus est présenté sous la forme d'un graphe orienté, un
réseau de type PERT. Les arcs représentent les opérations et les nœuds leur départ ou
leur frn. Évidemment, le poids des arcs est la durée des opérations. Pour montrer une
relation de précédence, on utilise des activités N fictives )) de longueur nulle. Par ailleurs,
l'on remarque que le graphe consiste en un sous-graphe initial Gt, suivi de n-2 sous-
graphes intermédiaires G2 à G,,., et d'un sous-graphe terminal G, .
Selon ce graphe, pour une séquence fixe P, la durée totale des opérations M(P) est alors
égale à Ia longueur du chemin critique L,&P), qu'il faut minimiser tout en respectant Ies
contraintes de précédence. Le tout est réductible à n-2 problèmes de Mitten avec les
paramètres suivants :
A(i) et B(i) = temps de traitement du produit i respectivement aux machines A et B
C(i) et D(i) = intervalle de temps respectivement entre le début d'une opération sur
les machines A et B, et la iin d'une opération sur les machines A et B
Ainsi, la procédure de Mitten (pour plus de détails voir Mitten 1351) donne :
mm[mUi9sn [ f, A ( j k 1 + W, 1 + 2 B G ~ + ~ 1) rniscitt [& AU^-[ 1 + Wr 1 + 2 Nik 1 k=l h r k=I k-r
L'algorithme ensuite développé permet de réduire la complexité de l'énumération de
0(n310gn) à 0(n2) où n est le nombre de produits.
Enfin, un exemple numérique à sept ordres de fabrication est donné. Les auteurs
proposent aussi de limiter i'espace d'entreposage intermédiaire des convoyeurs.
3.3 Conclusion
En guise de conclusion au chapitre sur la revue de la littérature, nous vous présentons un
tableau qui résume les contributions des principaux articles discutés auparavant.
Tableau 3 : Réca~itulatü des contributions dans la littérature
Auteurs
Rabinowib et al.
1391
Ioachim &
Soumis [la
Crama & Van de
Klundert [8]
Problème Principal résultat .
trait6
4 machines, 1 Programme linéaire mixte
produit optimal (MIP)
2 et 3 machines, Méthodes d'évaluation du
1 produit temps de cycle
m machines, 1 Ordonnancement optimal
produit par voie d'analyse
mathématique
m machines, 1 Algorithme optimal 0(m3)
produit basé sur la programmation
dynamique
2 robots, 4 fonctions
objectifs
Robot à double prise
Permutations
pyramidales
Levner et al. 1281 1 m machiaes, 1 1 Algorithme optimal 1 Contrainte de non-
produit 0(m310gm) attente
Kats & Levner m machines, 1 Algorithme optimal 0(m4) Contrainte de non-
1201 1 produit 1 1 attente, recircuiation 1 1
Stern & Vitner 2 machines, n 1 Algorithme sous-optimal 1 id81 produits O(nlW)
Panwalkar [37] 2 machines, n Algorithme optimai O(nZ) AGV
produits
Kise et al. [24] 2 machines, n Algorithme optimal 0(n3) AGV, ajout d'une
produits station entréelsortie
King et al. [22] 2 machines, n Méthode B&B + 1 produits 1 heuristiques sous-optimale 1
Levner et al. [30j
Logendran &
jriskandarajah
3all et al. [14]
Kogan et Levner
P l
2 machines, n
produits
2 machines, 1 et
n produits
2 et 3 machines,
1 et n produits
2 machines, n
produits
Modèle graphique et
algorithme optimal 0(n3)
Algorithme optimal O(nlog
n)
Algorithme optimal 0(n4)
(2 machines, cycles non
unitaires), algorithme
optimal O(n1ogn) sous
conditions (3 machines,
cycles unitaires)
Méthode graphique et
algorithme optimal 0 ( n 2 )
3 aménagements de
cellule
2 aménagements de
cellule
Cellule a robot
couplé
4, Révision de la mécanique de mouvement du robot
Ce chapitre représente l'élément clé de notre contribution à l'ordonnancement de celIuIe
robotique, soit la révision de la mécanique des mouvements du robot. C'est s u lui que se
basera tous les développements subséquents que sont le calcul des temps de cycle,
I'évaiuation de la performance de notre nouvelle méthode et l'extension de notre modèle
dans le cas a trois machines.
4.1 Sélection d'un aménagement de cellule robotiaue
Lors de l'analyse des aménagements de cellule robotique proposés par Ies divers auteurs,
deux types ont attiré notre attention étant d o ~ é leur représentativité et leur précision
dans la description des phénomènes impliqués. ii s'agit en premier lieu de la cellule
tandem, c'est-à-dire qui possède un robot transporteur et des robots couplés aux
machines ; en second lieu, de la cellule à robot mobile (qu'on peut aisément ramener à
robot centré).
Le premier système (la cellule tandem), davantage dépendant de l'ordre de fabrication ' et introduit par Levner et al. [30], se généralise plus difficilement à m > 2 car il necessite
l'addition de plusieurs variables ce qui complexifie passablement I'analyse du problème.
Les produits sont initialement stockés dans plusieurs AS/RS dédiés à t'entrée de la
cellule ; en fin de cycle, ils sont déposés aléatoirement dans un AS/RS à la sortie de la
cellule. Dans le cas de deux machines MA et Mg , sa notation (très inconstante d'un
article à l'autre) est la suivante :
2 Cela signifie que la valeur des variables utilisths change d'un produit à l'autre (par exemple ici, les temps de chargement, de traitement et de rQlage, ainsi que certains temps de transport et de déchargement) : en anglais, on qualifie un tel systdme de job dependent.
j = indice de I'ordre de fabrication
L ) = temps de chargement du produit j sur le robot ri L'Mm d'entrée spécifique
L,&] et Leb] = temps de chargement du produit j sur les machines A et B respectivement
Wu = temps de déchargement des produits à L'ASiRS de sortie par le robot
UAG) et Uem = temps de déchargement des produits sur les maches A et B
respectivement
&O) et SBu) = temps de réglage du produit j respectivement sur les machines A et B
PAU) et Psi') = temps de traitement du produit j respectivement sur Ies machines A et B
T~,: = temps de déplacement a vide du robot entre les machines A et B
T..~' = temps de transport des produits entre les machines A et B par le robot
qA1(,] = temps de transport de l'ordre de fabrication j de L'ASRS d'entrée spécifique à
MA par Le robot
~ 0 . : = temps de déplacement à vide de la sortie a la machine A
4,; (j) = temps de déplacement à vide de la machine B A i'AS/RS d'eniréée spkifulue au
produit j
~ ~ 0 ' = temps de transport des produits de la machine B à I'ASIRS de sortie par le robot
Le second système (la cellule à robot mobile), plutôt indépendant de l'ordre de
fabrication (bb-independent) et suggéré par Logendm & Sriskandarajah [32], se
généralise facilement à m > 2 par l'addition de quelques variables. L'on peut ainsi
ajouter un grand nombre de machines quitte A ce que la ceiide devienne circulaire, ce qui
constitue un avantage majeur. Dans le cas de deux machines MA et MB , sa notation est
Ia suivante :
j = indice de l'ordre de fabrication
& = temps de déplacement héaire du robot sur le rail
SI: = temps de déplacement rotationne1 du robot entre deux stations adjacentes (i = 1
d e I à A , i = 2 d e A à B e t i = 3 d e B à O )
Y = temps sauvé par le robot pour l'arrêt évité à un point intermédiaire du trajet
E Z ~ = temps de chargement d'une pièce à une station par le robot (i = 1 pour A, i = 2
pour B et i = 3 pour O)
EZ~-1 = temps de déchargement d'une pièce a une station par le robot (i = 1 pour 1, i = 2
pour A et i = 3 pour B)
ab] et b(j) = temps de traitement de l'ordre de fabrication j sur les machines MA et Me
respectivement
Très simple étant donné qu'on peut se la reprisenter visuellement, la cellule est facile à
décortiquer. Son traitement mathématique s'en voit donc d'autant facilité. Voici, en
rappel, ce a quoi elle ressembie :
convoyeur convoyeur sortie (O) entrée (1)
Figure 17 : Aménagement de cellule robotique sélectionné
Soit t12 le temps de déplacement entre les stations 1 et 2, l'on voit aisément que :
selon la notation énoncée ci-haut. Lorsque le robot emporte une pièce (seulement d'une
station à la station successive), l'on ajoute les temps de chargement et de déchargement
appropriés pour déterminer le temps total de transport.
Ainsi. Dour des raisons de clarté. de consistance et sa possibilité d'extension a
d'éventuelles eénéralisations, ce second svstème est uréféré au urernier.
On considère d'abord le problème d'ordonnancement de plusieurs produit. dans un
atelier mono-gamme a deux machines. L'environnement n'est pas nécessairement
cyclique, c'est-à-dire que l'on ne produit pas toujours un ensemble minimal de pièces
W S ) de façon répétitive. L'on attend plutôt soit d'amasser n ordres de fabrication., soit
une certaine période de temps (par exemple, une journée) avant de résoudre le problème
d'ordonnancement. Les produits sont traités sur les machines A et B, dans cet ordre.
L'objectif est de minimiser fe temps de cycle ou, de façon équivalente, la durée totale des
opérations en régime permanent, ce qui revient à maximiser le rendement de la cellule.
Les hypothèses initiales sont :
1) Chaque machine ainsi que le robot sont continuellement disponibles ;
2) La même séquence de produits a lieu sur Ies deux machines (on est donc dans
un ateIier mono-gamme à permutation) ;
3) Tous les ordres de fabrication sont soumis au temps zéro (processus d'arrivée
des ordres de fabrication statique) ;
4) Les machines ne sont pas pourvues de zone tampon de stockage intermédiaire
pour l'entreposage d'en-cours ;
5) Le robot ne peut transporter qu'une sede pièce à la fois (il n'a qu'une prise) ;
6) Les machines ne peuvent traiter qu'une seule pièce à la fois ;
7) Les opérations sont indivisibIes (non-preemptiuus).
Premièrement, nous désirons décrire la mécanique du mouvement du robot, car celle qui
a été proposée jusqu'a maintenant est A notre avis défaillante (voir les sections 4.1 et
3.2.4), c'est-à-dire trop spécifique au système manufacturier îlexibIe (FMS) très intégré
et donc peu généraIisable. En effet, les systèmes de production que l'on retrouve en
pratique dans l'industrie ne sont souvent pas aussi automatisés. Ainsi, les travaux dans la
littérature font surtout état de mouvements a vitesse constante dans un plan horizontal,
alors que dans la majorité des cas, pour les ceiiules manafacturiéres flexibles ' (FMC)
utilisant de simples robots de manutention, il n'en est rien,
En réalité, le mouvement du robot possède bien plus de facettes que l'unique composante
rotationnelle (4) suggérée. Il s'exécute dans les trois dimensions et en six phases :
1) p k de la pièce
2) dégagement du manipulateur
3) montée
4) descente
5) positionnement ou approche du manipulateur
6) dépôt de la pièce
Il est à noter que les deux premières et les deux dernières phases sont réalisées B basse
vitesse, tandis que la montée et la descente se font à haute vitesse (même s'ils comportent
une rotation). Par aiIleurs, la premiére et la demière p h e peuvent respectivement être
associées au déchargement (a1) et au chargement (QJ d'une pièce à une station, même
si en fait le dépôt de la pièce devrait dépendre de l'ordre de fabrication (job dependent).
Ainsi, le temps de chargement d'un produit sur une machine ne peut être le même pour
tous, ne serait-ce qu'à cause de leur spécificité géométrique, chacun nécessitant un
réglage distinct. Nous avons cependant rencontré des difliicuités arithmétiques
(présentées à la section 4.4) qui nous ont empêchés de réaliser cette insertion. Nous
avons donc été contraints de poser i'hypothèse, nous aussi, que ces temps étaient hes .
Une autre N irrégularité » de la représentation de hgendran & Snskandarajah 1321 réside
dans le fait que lorsqu'un mouvement du robot est réalisé entre deux stations non
successives, celui-ci passe par les stations intermédiaires. En pratique, ce n'est pas le
cas : le robot de manutention va directement de la station de départ à la station d'arrivée,
ce qui diminue évidemment le temps de déplacement. Certes, l'ajout de la variable y à
leur modèle est un pas dans la bonne direction, car on soustrait une constante à chaque
station intermédiaire où un arrêt est évité, mais le principe reste erroné à la base.
4.3.1 Cellule à robot centré
Considérons la celluIe à robot centré. En tenant compte des remarques précédentes, le
temps de déplacement du robot entre les stations X et Y s'exprime comme suit :
OU td&aSement = temps de dégagement du robot
t ~ o n ~ i c x y = temps de montée du robot entre les stations X et Y
t h , $ ' = temps de descente du robot entre les stations X et Y
tappmC,,, = temps d'approche du robot
Or, les temps de dégagement et d'approche sont égaux peu importe la paire de stations
entre lesquelles ils se déroulent. Us se divisent en deux segments de mouvement vertical
selon l'axe des z. La première partie est d'environ 50 mm à 10 % de la vitesse maximale
en z et la seconde est d'environ 250 mm à 30 % de la vitesse maximale en z. Donc, en
négligeant les stades d'accélération et de décélération :
- - 250 + 50 - - 400 ' digagemcnr - ' a P P m ~ r - = 1333 / v,, 093~:- O,lv,,, 093v,,
avec la vitesse verticale maximale, v, ,, , en mmk. Pour la plupart des robots à six axes
de rotation, elle est égale B la vitesse linéaire maximale qui varie de 800 ii 2000 d s .
Pour ceux qui nous serviront de référence, soit Ie Karel S-300 de Gli4F Robotics et le
A460 de CRS Plus, dont les spécifications sont fournies en annexe, eues sont
respectivement de 1800 et 1002 d s .
Il faut mentionner que l'hypothèse des accélérations et décélérations négligeables est tout
à fait justifiée puisque, même si en théorie la trajectoire du robot est rectiligne et
découpée, en pratique elle est plutôt fluide et raccordée. Les figures ci-dessous ilIustrent
bien ces phénomènes.
En théorie :
= arrêt
Figure 18 : Trajectoire théorique d'un robot de manutention
En pratique :
= arrêt
Figure 19 : Trajectoire effective d'un robot de manutention
Ainsi, seule une légère pause de une a deux secondes est nécessaire entre la fin de la
descente et le début de l'approche. Elle permet d'amortir les petites oscillations du
manipulateur causées par le passage du mouvement i haute vitesse au mouvement a
basse vitesse.
De plus, les temps de montée et de descente sont aussi égaux si le point de passage se
trouve à mi-chemin entre les deux machines, comme nous le supposons. Celui-ci est
d é M comme l'intersection des trajectoires théoriques de descente et de montée. Ainsi,
ces temps sont donnés par(toujours en négligeant les stades d'accélération et de
décélération) :
avec la vitesse linéaire maximale, vlh ,,a , en mmk Rappelons que cette vitesse est
comprise entre 800 et 2000 mmls pour les robots à six axes de rotation. Pour ceux qui
nous serviront de référence, soit le Karel S-300 et le CRS Plus A460, elles sont à nouveau
respectivement de 1800 et 1002 &S. Ici, sxr est la distance linéaire en mm entre Ie
point final du dégagement (ou le point initial de l'approche) et le point de passage. Selon
la règle de Pythagore, s , ~ , , = - + 01 dxr , la distance entre les stations X et
Y, varie en général entre 500 mm et 2 ml tandis que h, l'élévation d'évitement requise, se
situe habituellement entre O et 500 mm dépendemment de l'encombrement de la cellule.
Figure 20 : Calcul de la distance entre deux stations
Si h = O (pas d'obstacle), on peut alors utiliser avantageusement un robot de type SCARA
(Selecrive Compliance Assembly Robot Ann) à quatre degrés de liberté pour effectuer un
mouvement circulaire en deux dimensions a trés grande vitesse (-5000 mm/). A moins
que la distance à parcourir ne soit grande, les composantes de montée et de descente
deviennent pratiquement négligeables. Surtout qu'il est à noter que ce type de robot - prenons le IBM 7576 comme modèle, dont les spécifications sont fournies en annexe - possède en plus une vitesse maximale moins élevée selon l'axe des z (verticale), soit
d'environ 600 mm/s. Cela augmente d'autant plus Ia part des composantes d'approche et
de dégagement. Dans ce cas,
avec la vitesse circulaire maximale, v& ,, , en &S. Ici, S X , ~ est la longueur de l'arc de
cercle à parcourir entre le point finai du dégagement et le point initiai de l'approche. Or,
s x ~ = rexr où ex . y est la distance anguiaire en radians entre les stations X et Y, et r, le
rayon de la cellule, ne dépasse généralement pas 1500 mm. Ainsi, dans les pues
conditions (r = 1500 mm et 8 = R), notre robot-modèle que constitue le IBM 7576,
prendrait moins d'une seconde (précisément 0.94 s) pour accomplir la montée la
descente. Parallèlement, il prendrait plus de deux secondes (précisément 2.22 s) pour
accomplir l'approche 3 le degagement.
En résumé, lorsqu'il y a un ou des obstacles à éviter, donc que la montée et la descente
sont nécessaires,
S'il n'y a pas d'obstacle et qu'on utiIise un robot SCARA,
- 2667 r9x.y r , ~ , ~ - 2tdigagem,, +rduem& +Pause=-+- + pause
"r- '"rçimir
4.3.2 Cellule à robot mobile
Pour la cellule à robot mobîie, i'addition d'un dépIacement sur rail simplifie légèrement
le problème. En effet, les robots malgré leur apparente robustesse ne peuvent soutenir de
grandes accélérations ou décélérations qui leur causeraient des chocs, si bien que ledit
mouvement linéaire (4) doit être exécuté à très basse vitesse pour éviter de les
endommager. Toutefois, il peut se réaiiser pendant la montée et la descente
(contrairement à la représentation de Logendran & Sriskandarajah [32]), si bien que le
temps de déplacement serait donné par l'expression qui suit entre les stations où le
mouvement linéaire sur le rail est nécessaire. Pour les autres combinaisons de stations,
eIle reste la même que dans le cas à robot centré.
où & = temps de déplacement linéaire du robot sur le rail
Or, la durée du mouvement linéaire sur rail 4 surpasse à coup sûr celle des phases de
montée et de descente réunies, à moins que le mouvement linéaire soit fait sur une très
courte distance, ce qui ne comporterait aucun avantage. Cela s'explique par le fait que
les vitesses de déplacement linéaire sur un rail sont de l'ordre de 200 à 300 mm/s
comparativement à 800 à 2000 mm/s pour celles du robot à pleine vitesse, soit environ de
trois à dix fois moins élevées ; et plus le robot est lourd, plus ce rapport croit. Donc, pour
la cellule à robot mobile :
Y = tdigngemeni + & + tappm&e + pause
À nouveau, les temps de degagement et d'approche sont égaux et se divisent ni deux
segments de mouvement vertical (selon l'axe des 2). Iis sont encore donnés par :
Donc, dans une cellule à robot mobile :
et ce, pour quelque robot que ce soit.
4.4 Calcul des temm de cvcle
Toujours en référence aux travaux de Logendran et Sriskandarajah [32], il a été démontré
par Sethi et al. [42] qu'uniquement les séquences SiJ et SzJ , présentées ci-dessous,
pouvaient être optimales pour une cellule produisant un seul produit. Ces séquences sont
des cycles unitaires, ce qui signrfie que la cellule retourne au même état après la
production d'une unité. Ils sont faciles a comprendre et à implanter, d'où leur large
utiIisation. Il est à noter que dans un cycle unitaire, chaque activité doit être réalisée
exactement une fois.
Figure 21 : Mouvements selon la séquence Sis
Figure 22 : Mouvements selon la séquence SzJ
Tout comme Sethi et al. [42], Ioachim et Soumis 1161, hgendran et Srkkandarajah [32],
Hall et al. [14 et 151 et Sriskandarajah et al. [45], nous allons considerer les mêmes
séquences pour le cas à plusieurs produits. La notation utilisée sera la suivante :
a, et bj = temps de traitement du produit j sur les machines A et B
respectivement
ui = temps de déchargement des produits a la machine i (i = 1 pour 1, i = 2
pour Aet i = 3 pourB)
li = temps de chargement des produits à la machine i (i = 1 pour A, i = 2
pour B et i = 3 pour O)
wi = temps d'attente du robot à la machine i
a = séquence de pièces quelconque
4.4. I Celluie à robot centré
Alors, dans une celluIe a robot centré, l'intervalle entre la répétition de deux événements
identiques pour la séquence S L j est domé par :
Soit p = ur + 12 + Z r k B , a j = aj + U I + I I + t l ~ + t 3 , ~ - ~ A , B et b j = bj + ~3 + 13 + te.0 +
- ~ A . J , Ie temps de cycle est :
qui ne dépend pas de la séquence de pieces.
À partir du moment où la pièce j vient juste d'être chargée sur Me , l'intesvalle entre la
répétition de deux événements identiques pour Ia séquence Szz est quant à lui donné par :
Soit ,U = trl + I I + u3 + 13 f ~ I . A + ~ B . O + ~ B , I + t o , ~ , le temps de cycle est :
En introduisant ces expressions, l'on obtient :
Soit fa = max {p. b et e ~ + i ) = a 'a+~) , le temps de cycle est :
Comme np est constant, on peut l'éliminer, et le problème est alors réductible à un cas
spécial du problème du commis voyageur étudié par Gilmore & Gomory [Il], dont on
utilise l'algorithme que voici pour résoudre de manière optimale. Son temps de
résolution est de O(n1ogn).
3 Algorithme :
Étape 1 : classer les4 (j = 1 a n) en ordre croissant et renuméroter les ordres de
fabrication en accord avec ce classement
Étape 2 : classer les e, (j = 1 à n) en ordre croissant et déduire la permutation $I
telle que #@) = q où AA, est Ie plus petit élément des A,
É t a ~ e 3 : construire un graphe à n nœuds avec des arcs non orientés reliants Ie
jikm nœud au nœud ; si le graphe n'a qu'une seule composante connexe,
passer à l'étape 9
É t a ~ e 4 : calculer le coût des arcs (j = 1 a n-1) reliants deux nœuds
consécutifs selon
GI =max (0, (min a+*, e&+ii) -max G, em})}
É t a ~ e 5 : ajouter les arcs à tour de rôle selon l'ordre croissant de leur coût,
jusqu'a ce que le graphe n'ait qu'une seule composante connexe
Étape 6 : diviser les arcs ajout& a l'&tape 5 en deux groupes ; ceux dont Zem 2 4 appartiennent au groupe 1, et ceux dont Zém < LJ appartiennent au groupe 2
Étape 7 : trouver le plus grand indice il tel que Ri,,fl+, appartient au gmupe 1, le
deuxième plus grand indice i2 . . . jusqu'a it en considérant qu'il y a L éléments
dans le groupe 1
É t a ~ e 8 : trouver le plus petit indice jL tel que Rjl,j,+, appartient au groupe 2, le
deuxième plus petit indice jz ... jusqu'à j~ en considérant qu'il y a M éIérnents
dans le groupe 2
4.4.2 Cellule à robot mobile
En ce qui concerne la cellule à robot mobile, l'intervalle entre la répétition de deux
événements identiques pour la séquence Si1 est cette fois donné par :
où t = 2trlcSngemen, + & + pause = ~ A . B = ta, = t ~ , , = t o , ~ , soit enire chaque paire de
stations ou il y a déplacement sur le rail
qui ne dépend pas de la séquence de pièces.
Toujours a partir du chargement de la pièce j sur Me , Pintervalle entre la répétition de
deux événements identiques pour la séquence SZ3 est ici donné par :
Soit p = U I + 11 -t u3 + 1, + t [ ~ + t ~ , o + 2 t , le temps de cycle est :
où w1 (j+ 1) = rnax {O, aq+,) - w2(I] - 2t - tg.0 - 243 - 13) = max {O, a 'N+ll - p - w&])
etw2(j)=max {O, b N 1 - 2 t - t L A - u ~ - l ~ ) = m a x {O,b'al-,u)
En introduisant ces expressions, l'on obtient :
Soit fa = rnax {fi ba) ') et e w l ) = alw(I+l) , le temps de cycle est :
Comme np est constant, on peut l'éliminer, et le problème est encore une fois réductiile à
un cas spécial du problème du commis voyageur étudié par Gilmore & Gomory [Il],
dont on utilise l'algorithme décrit auparavant pour résoudre de manière optimale.
4.5 Remarques
Comme la répétition d'un cycle unitaire n'est généralement pas optimale dans le cas à
plusieurs produits, il y a possibilité de passer de Siz à Szt quand le robot termine le
chargement d'une pièce à la machine Me (le seul état commun) pour améliorer la durée
totale des opérations. Par exemple, on peut utiliser une seule séquence (S12 ou S2j) pour
traiter un premier ordre de fabrication sur les deux machines, mais ensuite SIJ sur une
machine et S21 sur l'autre machine pour un deuxième ordre de fabncation, et enfin
l'inverse pour un troisième ordre de fabrication.
Pour parvenir à optimiser la suite de mouvements de robots et la séquence de pièces à
traverser, l'idée de base est celle-ci : commencer par trouver une séquence de pièces
arbitraire avec le robot n'utilisant que StJ et une séquence de pièces optimale avec le
robot n'utilisant que S2j , l'optimum se trouve quelque part entre ces deux extrhnes.
C'est ce que se propose de f& le complexe algorithme MinCycle développé par
Snskandarajah et al. [45]. Son temps de calcul est 0(n4) - plus tard ramené à O(n1ogn)
par Aneja et Kamoun [2] en reprenant la notation simplifiée (sans yni indices aux 6et E),
qui nivelle tous les temps de transport et de chargement / déchargement.
Par ailleurs, nous avons précédemment abordé l'intérêt de rendre le temps de chargement
d'une pièce à une machine dépendant de i'ordre de fabrication : li + l,o] (i = 1 pour A, i
= 2 pour B et i = 3 pour O). Voici quelles sont les difficultés arithmétiques qui devront
être surmontées afin d'y parvenir.
Considérons la cellule à robot centri. Si j venait d'être charge sur MB , i'intetvaiie entre
la répétition de deux événements identiques pour la séquence StJ serait maintenant donné
par:
En introduisant ces expressions, l'on obtient :
Sauf qu'on ne peut plus poser fe3 = rnax {p, b&]' - 11(/+1)) et ewi) = a*+rl' - f30') y car
ces termes ne peuvent dépendre de deux ordres de fabrication (i et j+l) à la fois étant
donné qu'on ne connaît pas la séquence de pièces a prime abord. Ainsi, nous ne pouvons
pas rendre le déchargement li dépendent de l'ordre de fabrication j selon cette
représentation analytique.
En bref, pour clore ce chapitre, on retrouve certes la même formulation finale que
Logendran & Sriskandarajah [32], mais le calcul des paramètres (entres autres les ej /fl est totalement différent dû au fait que nous avons incorporé de nouvelles facettes dans le
déplacement du robot. Cela a eu pour effet d'ajouter de nouvelles variables dès le départ,
compliquant ainsi l'atteinte de la forme requise pour être en mesure d'appIiquer
l'algorithme de Gilmore & Gornory [Il].
5. ANALYSE DE LA PERFORMANCE
Nous nous intéressons dans ce chapitre à l'évaluation de la performance de la méthode
développée au chapitre précédent. Malgré le nombre restreint d'exemples numériques
considérés, on peut tout de même tirer quelques conclusions ici. Puisque l'algorithme de
Gilmore & Gomory [I I l est optimal en ne considérant que les cycles unitaires, on peut
comparer notre soIution avec celle obtenue par Logendran & Sriskandarajah (l'une des
seules disponibles dans la littérature pour un cas semblable) sur la base commune du
temps de cycle. On peut de pIus l'utiliser comme point de référence dans l'analyse d'une
méthode heuristique alternative.
5.1 Premier exemple
Comme exercice, reprenons l'exemple à huit ordres de fabrication résolu par Logendran
& Sriskandarajah [32] pour une cellule à robot mobile. Les données initiales tirés de leur
article sont :
Tableau 4 : Tem~s de traitement des ordres de fabrication de l'exemple 1
Les détaiIs et caiculs de cet exemple sont donnés à l'annexe D. En résumé, voici un
tableau comparatif de leur résultat et des nôtres, obtenus avec trois robots différents.
Tableau 5 : Com~araison des résultats de l'exemple 1
Modéle de robot
axes de rotation 1 I Gros robot h six
Temps de cycle selon la
axes de rotation 1 l
Temps de cycle selon la
séquence SI (kart avec L&G)
Tl = 62.5 min (-26.6 %)
Petit robot il six
séquence S2 (écart avec L&G)
T2 = 36.0 min (-35.3 %)
5.1.1 Discussion
Ti = 61.4 min (-27.8 %)
Robot de type
Les conclusions que l'on peut tirer de cet exemple sont multiples. D'abord, étant donné
que sous certaines conditions comme c'était le cas ici, la séquence optimale de pi6ces ne
change pas, cela signifie que l'amélioration de la mécanique des mouvements du robot ne
cause pas une altération profonde au processus de résolution développé par Logendran &
Sriskandarajah [32].
T2 = 34.9 min (-37.2 %)
Ensuite, que les temps de dépIacement du robot que nous avons calculé sont plus faibles
que ceux qu'ils s'étaient arbitrairement donnés dans leur application numérique. Cela
s'explique de deux façons : d'abord, les robots de manutention modernes sont très rapides
et très précis dans l'exécution de leurs mouvements ; puis, tel que mentionné plus tôt, le
robot va directement de la station de départ à la station d'arrivée, sans passer par les
stations intermédiaires.
Tl = 61.9 min (-27.3 %)
Cela a évidemment eu pour effet de diminuer nos temps de cycle, en moyenne de 27 %
selon la séquence Si et 36 % selon la séquence S2 , ce qui n'est certes pas négligeable. De
T2 = 35.4 min (-36.3 %)
plus, la variance d'un robot à l'autre est faible, ce qui signifie que des performances
semblables sont atteintes peu importe que l'on soit dans une grosse cellule ou une petite
cellule. Bien sûr, les robots doivent être sélectionnés en conséquence, afin d'être en
mesure d'accomplir la tâche qui leur est demandée.
Nous ne croyons pas par ailleurs que les temps de chargement et de déchargement
(respectivement li et ui), que nous avons repris de Logendran & Sriskandarajah [32] sans
les retoucher, soient sous-estimés. Variant de 0.05 à 0.3 minute (3 A 18 s) pour 1 et de 0.1
à 0.2 minute (6 à 12 s) pour u, nous considérons que pour un procédé manufacturier bien
maîtrisé et des pièces à géométrie relativement simple, ceux-ci sont réalistes. Rappelons
que les temps de chargementfdéchargement dépendent principalement de trois choses : la
géométrie et le matériau de la pièce (surtout sa dureté), la dextérité du robot (deux ou
trois doigts, présence de capteurs ou non), ainsi que la complexité de l'opération à
effectuer.
Nous réitérons par contre notre désir de voir les temps de chargement devenir dépendants
de l'ordre de fabrication même si nous n'avons pas pu y parvenir mathématiquement (voir
la démonstration à la section 4.5). Pour amoindrir la difficulté, nous pourrions alors
égaler les temps de chargement et de déchargement pour une même pièce sur une même
machine, ce qui est vrai la plupart du temps (1,Ci) = u&), i = 1 à m, j = 1 A n).
L'on note de plus que le robot de type SCARA (iBM 7576) n'est pas approprié pour la
cellule A robot mobile, puisque l'on perd dans ce cas tout l'avantage du mouvement
circulaire à haute vitesse en deux dimensions qui est "camouflé" par le déplacement du
robot sur le rail. Au surplus, ce type de robot est plus lent en approche et en dégagement,
mais comme sa vitesse linéaire maximale est plus grande que celIe du petit robot à six
axes de rotation (CRS Plus A460), cela n'a causé qu'un mince écart entre leurs résultats
réciproques (moins de 2 %). On aurait toutefois obtenu une différence plus substantielle
avec le robot CRS Plus si on s'était trouvé dans une cellule a robot centré sans rail, où les
temps de transport du robot IBM 7576 auraient été pratiquement négligeables.
Enfin, nous désirons souligner que la simplification du diagramme de Gantt, soit le
passage de trois ressources (deux machines et un robot) vers deux (deux machines
(( virtuelles D Mi' et M2') exécuté par Logendran & Sriskandarajah [32] en utilisant les
valeurs de e, et& pour le tracer, n'est vaEde que pour le calcul du temm de cvcle de la
solution optimale donnée par lL'algorithme de Gilmore & Gomory [Il]. Mais encore, les
variables ûj ', b, ', p et p doivent-ils constituer des expressions particulières, soit la somme
de termes bien précis qui dépeignent la suite des mouvements accomplis par le robot et
mis en évidence par le diagramme de Gantt complet.
Nous basons la précédente affirmation sur la validation numérique que nous avons
réalisée en traçant plusieurs diagrammes de Ganrt complets, où nous avons seulement pu
vérifier l'équivalence des deux méthodes dans le cas cité plus haut. Ainsi, cette réduction
n'est applicable pour toute autre solution non optimale ni pour le calcul de la durée - totale des opérations.
Cela peut s'expliquer comme suit : les problèmes d'ordonnancement ne possèdent pas
vraiment la structure des problèmes du commis voyageur (TSP) et, par le fait même, leur
solution ne constitue pas un cycle hamihonien. En effet, il faut se trouver dans la
situation idéale, la solution optimale du cas cyclique (OU Ies mêmes ordres de fabrication,
qui font office de nœuds dans le graphe, se répètent) pour que la notion de tournée
requise à l'algorithme de Giimore & Gomory [il] soit envisageable. Comme ces
derniers l'ont démontré, il est en effet considérablement plus facile de minimiser le coût
d'une séquence sur une tournée. Pour ce faire, on répète le premier ordre de fabrication
- qu'on laissera tomber plus tard - en fin de parcours pour qu'il incarne dès lors un état
initial et final connu.
Le hic, c'est que l'exemple résolu par Logendran & Snskandarajah [32] est un peu biaisé
en ce sens qu'il y a plusieurs solutions optimales à leur problème. Cela est dû au fait que
la valeur de p étant très élevée et les temps de traitement sur les machines aj et b, plutôt
raisonnables, p vient niveler les ej et$ pour ne laisser que deux faibfes écarts en faveur de
e, entre les paires associées. La deuxième machine n'étant pratiquement plus contrainte,
nous obtenons donc beaucoup d'amplitude dans l'ordonnancement, d'où plusieurs
solutions optimales car plusieurs alternatives équivalentes.
Enfin, l'algorithme de Gilmore & Gomory [Il] tel qu'énoncé dans plusieurs articles
consultés n'est pas optimal lorsque l'objectif est la minimisation de la durée totale des
opérations - contrairement au temps de cycle. Par contre, l'addition de deux étapes l'en
approcherait, sans toutefois assurer qu'il donne forcément l'optimum. Nous avons pu
faire ce constat en comparant les solutions de notre exercice avec celles obtenues en
débutant la séquence de pièces par un ordre de fabrication autre que JI. Par exemple, la
durée totale des opérations selon Sz pour la séquence J4 - Js - J6 - J7 - J5 - Jt - J3 - JI avec
le premier robot est égale à 37.0 minutes, inférieure aux 38.7 minutes de la séquence Ji - Jq - J g - J6 - J7 - J5 - J2 - J3 .
En fait, il y a n séquences possibles, une pour chaque ordre de fabrication en première
position (en conservant ensuite l'ordre dicté par la fonction Pm). Ii ne reste qu'à trouver
la meilleure en calculant leur durée totale des opérations (makespan) respective. Ainsi,
les étapes 11 et 12 de l'algorithme de Gilmore & Gomory devraient se lire comme suit.
Leur ajout ne change en rien son temps de calcul qui demeure a O(n1ogn).
Étape 11 : essayer chacun des n ordres de fabrication à la première position et
calculer la durée totale des opérations des séquences résultantes
Étarie 12 : choisir la séquence dont le makespan est minimal
Une autre remarque digne de mention est qu'en appliquant la méthode de Johnson aux
paires e, / A pour la séquence S2 (OU plus simplement encore aux paires a, ' 1 bj ' si bj' 2 p
Q j), on obtient de très bons résdtats. En effet, toujours dans les mêmes conditions,
l'algorithme de Johnson - dont le temps de calcul est seulement O(n) - d o ~ e la séquence
J3 - J4 - J7 - J8 - J6 - JS - JZ - JI . Son temps de cycle est T2,== 36.7 minutes pour le robot
Karel S-300, supérieur à l'optimum trouvé par celui de Gilmore & Gornory d'un maigre
2 %.
5.2 Deuxiéme et troisième exem~les
Mais quoi donc peut faire changer la séquence optimale, si une méthodologie
complètement renouvelée pour le calcul des temps de déplacement et de transport avec
trois modèles différents de robot n'a pas été suffisant ? Comme nous i'avons souligné en
analysant plus en profondeur l'aigorithme de Gilmore & Gomory (voir annexe D), la
séquence optimale de pièces est majoritairement dictée par les arcs ajoutés au graphe à
l'étape 5. Or, ceux-ci sont déterminés par leur coût qui doit être minimal (qui dépend de
A ,hi , e&) et eei)) et les arcs déjà en pIace sur le graphe (qui dépendent principalement
du classement des&).
Reprenons le premier exemple, en lui apportant les changements suivants pour le rendre
plus plausible :
3 comme nous ne produisons pas de MPS, toutes les pièces à traiter sont différentes
et donc tous leurs temps de traitement sur les machines le sont aussi ;
3 nous utilisons Ie robot SCARA que sur une cellule à robot centr6 ; sur la cellule à
robot mobile, seuls les robots à six axes de rotation sont employés.
Nous avons considéré deux cas pour iîIustrer notre conception de la problématique, soit
un premier où les temps de traitement sur les machines sont très bas avec une variance
faible, et un deuxième où tout est substantiel~ement plus élevé. Cela nous a permis entre
autres d'évaluer l'influence de la variabIe fi et des temps de transport du robot en général
sur le résultat final. Dans la premiére et la seconde variante, les données de base
deviennent respectivement :
Tableau 6 : T e m ~ s de traitement des ordres de fabrication de I'exem~le 2
Tableau 7 : T e m ~ s de traitement des ordres de fabrication de I'exem~le 3
Pour les détails et calculs des exemples 2 et 3, se référer à l'annexe D. Les tableaux qui
suivent contiennent un sommaire des résultats obtenus en comparaison avec ceux du
premier exemple.
Tableau 8 : Com~araison des résultats de I'exem~le 2
Modéle de robot Temps de cyck selon la
~ Gros robot iî six
axes de rotation
SCARA (cell. iî
sequence Si$ (écart avec ex. 1)
Ti = 32.6 min (-47.8 %)
axes de rotation
Petit robot it six
robot centré) I
Ti = 31.5 min (-48.7 %)
Temps de cycle selon la
sequence Su (&art avec ex, 1)
T2 = 20.7 min (-42.5 %)
T2 = 34.9 min (-43.8 %)
Tt = 19.2 min (-45.8 %)
Tableau 9 : Com~araison des rCsultato de 19exemrle 3
5.2.1 Discussion
Modéle de robot
Gros robot 4 six
axes de rotation
Petit robot a six
axes de rotation
Robot de type
SCARA (cell. ib 1 robot centre)
Pour clore cette série d'exemples qui constituait en fait l'étude de la performance, nous
désirons attirer votre attention sur quelques points. D'abord, en changeant la structure des
temps de traitement (suout la parmi ceux-ci), on paMent a des séquences
optimales distinctes d'un problème à l'autre (exemples 2 et 3), ce qui n'était pas le cas
lors du passage des d ~ m é e s de Logenkari & Sriskandarajah aux nôtres (exemple 1).
Cela paraît maintenant trivial, mais ne l'était pas au début de L'exercice.
Ensuite, les temps de trahment sur les machines ont une grande influence sur la
performance de la cellule. Némoins, celle-ci est toujours amoindrie par le robot qui
invariablement joue un rôle "d'amortisseur". A b i , en diminuant la somme des temps de
traitement de 60 % dans le premier cas, cela n'a eu pour effet que de réduire notre temps
de cycle en moyenne de 49 % selon la séquence SI et 44 % selon la séquence S2 . Dans le
second cas, en augmentmt la somme des temps de traitement de 96 %, le temps de cycle
n'a grimpé en moyenne que de 76 % selon la séquence Si et 66 % selon la séquence SI .
- Temps de cycle selon la
sequence Sis @art avec ex. 1)
Tl = 110.1 min (+76.2 %)
Tl = 109.0 min (i77.5 %)
Tl = 108.7 min (+75.6 %)
Temps de cycle selon la
sCquence Su (Ccart avec ex. 1)
T2 = 59.6 mlli (+65.6 %)
T2 = 58.5 min (+67.6 %)
T2 = 58.2 min (+64.4 %)
On voit que c'est toujours la séquence Sr , plus simple donc plus Milnérable, qui fluctue
davantage.
Par ailleurs, le fait d'utiliser le robot de type SCARA dans une cellule à robot mobile fait
du iBM 7576 le modèle le plus performant, bien que l'écart avec les rédtats de ses
« compétiteurs » demeure ténu (moins de 3 %). On cesse alors de dissiper le mouvement
circulaire à haute vitesse en deux dimensions en déplacement du robot sur le rail, c'est-b
dire que l'avantage que procure le mouvement circulaire à haute vitesse n'est plus
neutralisé par le déplacement sur le rail.
Enfin, en appliquant la méthode de Johnson aux paires ej /j pour la séquence Sz , on
obtient à nouveau des résultats satisfaisants, mais d'autant plus loin de la sohtion
optimale que la variance des temps de traitement est grande. Cela est dvident quand on
pense que si tous les temps de traitement étaient identiques, chaque solution serait
excellente ! L'exemple de Logendran & Sriskandarajah [32] en est une bonne preuve,
car pour huit ordres de fabrication, il y a seulement cinq produits, donc cinq paires de
temps de traitement. Au surplus, la variance entre ces cinq produits est faible.
Mais étonnamment, le fait que les temps de transport prennent une place plus ou moins
importante (Le. si p > b,+' 3 j] affecte peu la performance de l'algorithme de Johnson au
temps de calcul inférieur. Par exemple, il donne la séquence Jz - J6 - J j - J7 - Ja - J4 - J3 - Ji pour le cas des bas temps de traitement. Le temps de cycle de celle-ci est Tz,, = 21.6
minutes pour le robot GMF Karel S-300, supérieur à l'optimum trouvé par celui de
Gilrnore & Gomory d'un minime 4 %. Pour le cas des hauts temps de traitement, le
temps de cycle de la séquence Ja - Jd - J7 - J6 - J8 - IS - J3 - JI est T2,== 64.8 minutes pour
le même robot, juste à 9 % du minimum.
6. EXTENSION A TROIS MACHINES
La contribution de ce chapitre réside dans l'adaptation du modèle développé avec la
nouvelle mécanique du robot à un environnement manufacturier plus complexe (3
machines), surtout que cette extension n'a étk faite que dans très peu d'articles à notre
connaissance pour n produits. Nous démontrons ensuite la faible probabilité de trouver
une solution optimale parmi les quatre cycles unitaires sur six qui ne sont pas NP-dur, ce
qui nous onente dorénavant vers la recherche d'algorithmes sous-optimaux.
6.1 Calcul des temps de cvcle
Le problème d'ordomancement de la cellule robotique à trois machines constitue une
extension intéressante car le nombre de cycles unitaires potentiellement optimaux se
chiffie maintenant à 3! = 6. Outre ce fait, nous verrons que l'approche est très similaire
avec le problème à deux machines, c'est-à-dire que l'on tente de ramener l'expression du
temps de cycle sous la forme d'un cas spécial du problème du commis voyageur. On
traite à nouveau plusieurs produits de façon non cycIique. Les hypothèses énoncées au
chapitre 4 restent identiques. Voici une cellule à trois machines B robot mobile :
convoyeur sortie (O)
convoyeur cntr6c (0
Figure 23 : Cellule h trois machines ii robot mobile
Pour continuer dans la même veine, Seîhi et al. [42] ont aussi démontré qu'uniquement
les séquences Sit a S6,3 définies ci-dessous pouvaient être optimales pour une cellule à
trois machines produisant un seul produit. Ce sont encore une fois des cycles unitaires.
Figure 24 : Mouvements seton la sbquence SIs
Séquence SIJ :
Figure 25 : Mouvements selon la skquence Su
Figure 26 : Mouvements selon la séquence SS3
Figure 27 : Mouvements selon la séquence Sd3
Figure 28 : Mouvements selon la sequence Sss
Séquence S6 7 :
Figure 29 : Mouvements selon la séquence SsJ
Considérons à nouveau les mêmes skquences pour le cas a plusieurs produits, de même
que la notation suivante :
a, , bj et cj = temps de traitement du produit j sur [es machines A, B et C
respectivement
ui - temps de déchargement des produits A la machine i (i = 1 pour 1, i = 2
pour A, i = 3 pour B et i = 4 pour C)
li = temps de chargement des produits à la machine i (i = 1 pour A, i = 2 pour
B, i = 3 pourCeti=4pourO)
wj = temps d'attente du robot à la machine i
O= séquence de pièces quelconque
6.1.1 Cellule à robot centrt!
Alors, dans une cellule a robot centré, i'inte~alle entre la répétition de deux événements
identiques pour la séquence SiJ est donné par :
4
Soit p, = (ui +l I )+ t IUA +tAJ +rd,= +tCBO +tg,, , le t m p s de cycle est : i-l
qui ne dépend pas de !a séquence de pièces.
A partir du moment où la pièce j vient d'être chargée sur Me contient la pièce J-1 et
MA est libre), l'intervalle entre la répétition de deux événements identiques pour la
séquence SzS est quant à lui donné par :
= (0, b2.*1- P2 - WV-1)) W.
et w3 (/- 1) = max {O, c*- 1) - wi 01 - ~ A , B - IB, c - ~ C J - uz - 12) = 11lilX {O, CZ. aÿ-1) - P2 - ~101)
En introduisant ces expressions, l'on obtient :
Or, dû au caractère récursif des temps d'attente, le temps de cycle n'est pas de la forme :
Cela signifie qu'on ne peut pas appliquer l'algorithme de Gilmore & Gomory [Il] pour
résoudre de manière optimale. En fait, ce problème n'est réductible a aucun autre
problème connu comme le TSP ou le problème de Mitten [35], où l'on pourrait appliquer
un algorithme de résolution polynomial. II s'agit d'un problème NP-dur. Cela a été
démontré sans équivoque par Hall et al. 1141. De plus, l'algorithme FindTime2
développé par Hall et al. [15] ne nous est pas utile car il ne génère aucune séquence : il
déduit seulement les temps d'attente et le temps de cycle pour une séquence donnée. De
plus, contrairement à leur contexte, nous ne produisons pas continuellement le même
« ensemble minimal de pièces D (MPS).
En partant du moment ou la pièce j vient d'être chargée sur M, (MA et Me sont libres),
l'intervalle entre la répétition de deux événements identiques pour la séquence S3J est
pour sa part donné par :
En introduisant ces expressions, l'on obtient :
Soit fNl = ~ 3 . 4 , ~ et ewi) = max {p3 + a,,pil,b3,el) + a w r ) ) , le temps de cycle est :
Comme np3 est constaat, on peut l'éliminer, et le probléme est alors réductible B un cas
spécial du problème du commis voyageur étudié par Gilmore & Gomory [L 11, dont on
utilise l'algorithme présenté au chapitre 4 pour résoudre de manikre optimale. Son temps
de résolution est O(n1ogn).
En partant du moment où la pièce j vient d'être chargée sur M, (MA et Mg sont libres),
l'intervalle entre la répétition de deux événements identiques pour la séquence Sh3 est
pour sa part donné par :
En introduisant ces expressions, l'on obtient :
Comme n p + Xb, est constant, on peut l'éliminer, et le problème est alors réductible a un
cas spécial du problème du commis voyageur pouvant être résolu par l'algorithme de
Gilrnore & Gomory [ I l ] tel qu'énoncé plus haut.
En partant du moment où la pièce j vient d'être chargée sur Me (MA et Mc sont libres),
l'intervalle entre la répétition de deux événements identiques pour la séquence SSJ est
pour sa part donné par :
En introduisant ces expressions, l'on obtient :
C o r n e nps est constant, on peut l'éliminer, et le problème est dors réductible à un cas
spécial du problème du commis voyageur pouvant être résolu par l'algorithme de
GiImore & Gomory [I 11 tel qu'énoncé plus haut.
En partant du moment OU la pièce j vient d'être chargée sur MA (Me et Mc sont
respectivement occupées par j-1 et j-2)' l'intervalle entre la répétition de deux
événements identiques pour la séquence Ssa est pour sa part donné par :
En introduisant ces expressions, l'on obtient :
Or, dû au caractère récursif des temps d'attente, le temps de cycle n'est pas de la forme :
Cela signifie qu'on ne peut pas appliquer lYaIgorithme de Gihore & Gomory [Il] pour
résoudre de manière optimale. A nouveau, Hall et al. [14] ont prouvé que le probléme
d'ordonnancement selon la séquence Sas était NPdur. De même, l'algorithme
FindTime6 donné par Hall et al. [15] qui trouve les temps d'attente et le temps de cycle
pour une séquence donnée ne nous est à nouveau d'aucun secours, parce qu'il faut
I'alimenter avec une séquence préétablie que nous ne possédons pas. De toute façon,
nous ne produisons pas un MPS de façon répétitive.
6.1.2 Conditions de récurrence
Cela rejoint 1'afKrmation de Sriskandarajah et al. [45] comme quoi, sur les m! séquences
potentiellement optimales, 2m-2 sont résolubles à I'aide de l'algorithme de Gilmore &
Gomory (incluant SI, qui est toujours tnvide), où m est le nombre de machines dans la
cellule. La différence, soit deux séquences dans Ie cas à trois machines, ne l'est pas.
Cela rend donc le problème générai d'ordonnancement de la cellule robotique à trois
machines (et supérieur) NP-dur. Ce que nous pouvons faire cependant est de déduire des
conditions bien spécifiques où iI est résoluble en temps polynornial selon notre notation.
C'est l'exercice que nous nous proposons maintenant de faire.
En premier lieu, notons qu'il y a deux séries de conditions qui pourraient nous sortir de
l'impasse : celles qui font qu'une autre séquence que S2j OU SgJ est optimale (soit S13 , S3,3 , S4,3 OU S5 f) et celles qui font que la récurrence des termes d'attente du robot aux
machines disparaît (c'est-à-dire que w30] = O V j selon Sz2 et que WIO] = O V j selon &3).
L'on débutera par ces dernières, que nous appellerons N condition de récurrence ». Les
autres, que nous nommerons K conditions d'optimalité », viendront après la prochaine
section portant sur la cellule a robot mobile.
Selon les expressions déveIoppées plus haut,
Soit w3(j-1) = O ; pour que w303 soit nul, il faut que :
en remplaçant,
et pour SsB3 :
Soit w1 (j-1) = O ; pour que w i O soit nul, il faut que :
en remplaçant,
Or, a moins que les temps de traitement sur la demière machine (pour S2,3) et la première
machine (pour SsJ) soient vraiment bas, ces conditions ne seront vraisemblablement pas
remplies avec la rapidité des robots modernes. Nous avons en effet réalisé avec les
exemples résolus lors de l'analyse de sensibilité que les temps de transport et de
déplacement étaient relativement faibles comparés aux temps de traitement.
Il est de plus évident que ces inégalités ne peuvent pas être vérifiées au complet sans
connaitre la séquence au préalable. On y retrouve en effet des termes qui dépendent de
deux ordres de fabrication (j et j+l) dans l'expression provenant de w30] pour S2j , et
même de trois ordres de fabrication Ci, j-1 et j-2) dans l'expression provenant de wl@
pour SsJ . Ainsi, nous ne pouvons pas parvenir à des conditions mathématiques
(( probables » qui élimineraient la récurrence des temps d'attente aux robots pour les
séquences 2 et 6 selon cette représentation analytique.
6.1.3 Cellule à robot mobile
Pour la cellule à robot mobile, l'on applique le même raisonnement que dans le cas à
deux machines, c'est-à-dire que le mouvement linéaire du robot surpasse les temps de
descente et de montée rdunis. Le dégagement et l'approche à basse vitesse sont encore
essentiels pour un positionnement exact, de même que la pause pour permettre au robot
d'être complètement à t'arrêt après ie déplacement sur le rail. Les sdquences SIJ it S6,3
sont encore une fois les seuls cycles unitaires pertinents (voir Sethi et al. (421).
L'intervalle entre la répétition de deux événements identiques pour la séquence Sla est
cette fois donné par :
OÙ t = 2td&ngemcnt + & + pause = t d . ~ = ~B,c= t & ~ = t0.a soit entre chaque paire de stations
où il y un déplacement sur le rail
et t' = 2tdigngeInurt + 24 + pause = t d . ~ = = ~ C J = t0.1 , soit entre chaque paire de
stations où il y deux déplacements sur le rail
4
Soit p, = (u, + 1,)c t,, + 2t + r , , +t' , le temps de cycle est : i i l
qui ne dépend pas de la sdquence de pièces.
A partir du moment où la pièce j vient d'être chargée sur Ms (Mc contient la pièce j-1 et
MA est libre), l'intervalle entre la répétition de deux événements identiques pour la
séquence S2,3 est quant à lui donné par :
4
Soit p, = 2 t c t 1 , p, = ~ ( t ~ i + l i ) + t , , + 2 t + t c , o +t t , i- l
où wl(j+l) = rnax {O, ad+,, - wzO) - 2t - r ' - u3 - i 3 ) = rnax {O, az,,(,+,) - pz - wz(j]),
= rnax {O, bal - ~ I . A - 2t - tc.0 - t ' - U I - I I - us - L - w3(i-1))
= rnax {O, b ~ , ~ , - - w3(i-1))
et w3(j-1) = rnax {O, CWI, - WIQ] - 2r - t '- uz- l z ) = rnax {O, c2,4-1) - p2 - wim)
En introduisant ces expressions, l'on obtient :
Or, dû au caractère récursif des temps d'attente, le temps de cycle n'est pas de la forme :
Cela signifie qu'on ne peut pas appliquer l'algorithme de Gilmore & Gomory [ I l ] pour
résoudre de manière optimale puisque ce problème est NP-dur.
En partant du moment où la pièce j vient d'être chargée sur M, (MA et Me sont libres),
l'intervaILe entre la répétition de deux bvénements identiques pour la séquence &J est
pour sa part donné par :
où wz(i+l) = rnax {O, b@+,, - w3(7) - 2t - tc.0 - u4 - 14) = rnax {O, b ~ . ~ l ) - p3 - wj(I]) et w3(I] = rnax {O, c q l - sel) - 2t - t ' L LA - ui - 11 - u2 - Iz) = rnax {O, c3.m - aw~) - p3)
En introduisant ces expressions, l'on obtient :
Comme nm est constant, on peut 1'éIiminer, et le problème est encore une fois réductible
à un cas spécial du probième du commis voyageur étudié par Gilmore & Gomory [Il],
dont on utilise l'algorithme décrit auparavant pour résoudre de manière optimale.
En partant du moment où la pièce j vient d'ètre chargée sur Mc (MA et Mg sont libres),
l'intervalle entre la répétition de deux événements identiques pour la séquence S4,3 est
pour sa part donné par :
Soit p, =u2 +11 +u3 +13 +2tt , p4 =u! +II +u4 +1, +2t+t'+tr,A + f C e O ,
= a j +u, + i l + t , , +2t-t' et c , , =ci +u, +14 + 2 1 + t , , -t'
et w303 = max {O, c*, - 2t ' - II,A - U, - II) = max {O, ~4.41- M)
En introduisant ces expressions, l'on obtient :
Soit fa, = max {M, ~ 4 , ~ ) et e w ~ ) = a4,a(i+l) , le temps de cycle est :
Comme npg + Cb, est constant, on peut l'éliminer, et le problkme est alors réductible a un
cas spécial du problème du commis voyageur pouvant être résolu par l'algorithme de
Gilrnore & Gornory [I l] tel qu'énoncé plus haut.
En partant du moment où la pièce j vient d'être chargée sur Ma (MA et Mc sont libres),
i'intervalle entre la répétition de deux événements identiques pour la séquence SsJ est
pour sa part donné par :
En introduisant ces expressions, l'on obtient :
Soit fa? = max {p5 + CM), bsmay) -t cw)) et emi) = a5,+1, , le temps de cycle est :
Comme n p ~ est constant, on peut I'éIiminer, et le problème est alors réductible A un cas
spécial du problème du commis voyageur pouvant être résolu par l'algorithme de
Gilrnore & Gomory [II] tel qu'énoncé plus haut.
En partant du moment où la pièce j vient d'être chargée sur MA (Mg et MC sont
respectivement occupées par j-1 et j-2), l'intervalle entre la répétition de deux
événements identiques pour la séquence est pour sa part donné par :
où w1w = rnax {O, a@, - wtu-1) - w30-2) - 2t' - tco - 2r - u3 - I3 - u4 - Id) = rnax {O, a , j ~ , - - w2(f-1) - w30-2)) ,
w20-l)=max {O, b ~ - l l - 2 t - t i A - t ' - t c o - u l -1, -u4-14-w3Cj-2))
= rnax (0, bsji1) - - w3U-2))
et w3(j-2) = rnax {O, ce21 - wI(i-1) - 2f ' - 2t - t l ~ - ui - Il - riz - 12) = rnax {O, ~ g , ~ ( i . 2 ) - - wt(j-1))
En introduisant ces expressions, l'on obtient :
Or, dû au carac tere récursif des temps d'attente, le temps de cycIe n'est pas de la forme :
Cela signifie qu'on ne peut pas appliquer l'aigorithme de Giimore & Gomory [I l] pour
résoudre de manière optimale puisque ce problème est NP-dur.
6.1.6 Conditions d'opîimalilé
Pour revenir aux conditions qui nous permettent de résoudre le cas à trois machines
optimalement, nous avons vu que Ies conditions de récurrence ne nous aident pas
beaucoup. Toutefois, en se basant su l'article de Hall et al. (141, on peut déduire quatre
autres conditions, c'est-à-dire une condition pour que le temps de cycle de chacune des
quatre séquences résolubles par algorithme polynomial (Si3 , S3J , S.J et SSJ ) soit
inférieur a celui des séquences 2 et 6. Soit la prémisse suivante :
preuve : T, =np, +g(o, +bj + c i ) j-l
T,., 5 n(u, +[, t 2t -tceo)+
u, +Il +u, f l , +u4 +14 +2t+2t'+tf,, +2t ,,,, u4 +la +2t+2t, +u, cf, +u2 +1, 12rV+t ,,,,
j-i u , +1, SU, f i t +tl,, +2t+2tV+u4 +14 f
T,,, < n(u, +1, +u , + l , + 2 t + t 1 ) +
i u, +Il + u , +1, +2t+t1+t, , , +cc*, Z m a x 2t1+tC,, +il, + 1 , +u, i l , cc,, +2r-r', j-i
2t1+tl,, +u, +Il i u , +1, +2t+tC, , - tg
T,,, <n(u, + l , + u , +1, +2t+r8)+
U, +1, +u, +1, +21 t t l+ t , , , +rc,,,
u, + l i + u , + l , +2 t+ t '+ t , , + t a , j-1
U , +Il t r i , C I , + 2 t + t 1 t t , , , +tcqo
iv) ~ ~ ~ i ~ ~ S ~ ~ + l ~ + ~ ~ + 1 ~ + 2 t + 2 t ' + t ~ ~ ~ , b ~ I ~ ~ + l ~ + 2 t + t ~ ~ ~ e t ~ ~ I t '
Q j alors Ts,o S Z,, et Ta,a
Du moment que l'une de ces conditions est remplie, on calcule Ti , puis on applique
l'algorithme de Gilmore & Gomory [ I I ] aux cycles S3,3 , S ~ J et SSJ . On choisit la
séquence au temps de cycle minimd.
Cependant, il est encore moins probable que les conditions énonctes ci-haut soient
respectées en pratique, spécialement ü), iii) et iv), où respectivement, aj I t ', bj 5 2t - t '
et ci 5 t ' . C'est simple, il nous faudrait pratiquement des temps de traitement nuls pour
les remplir. La condition i) n'est pas d'une grande utilité non plus, sachant que la somme
de tous les temps de traitement sur les machines doit être inférieure ou égale à n(2t - r i ) pour qu'elle soit respectée.
C'est donc due qu'avec Ia nouvelle génération de robots de manutention, les séquences
optimales risquent beaucoup pIus d'être celles, pour employer les termes de
Sriskandarajah et al. [45], qui appartiennent aux classes V2 et W. Ce sont évidemment
celles avec plusieurs temps d'attente de type 2 - où le robot effectue d'autres activités
pendant le traitement de la piéce sur une machine, en opposition au type 1 où il l'attend
sans bouger. En bref, tous les cycles unitaires potentiellement optimaux des problémes
d'ordonnancement de ceilule robotique font partie de l'une des trois classes suivantes : U,
V et W, la classe Y étant divisée en deux sous-classes Yi et Pî.
Ainsi, les séquences S2,3 et S6,3 appartiennent toutes deux à la classe qui est NP-dur . La classe Y poss6de pour sa part une structure TSP. La classe V1 est résoluble en temps
polynomial par l'algorithme de Gilmore & Gomory (Szz , S33 , SeJ et Ss3 y appartenant)
tandis que la classe U est triviale (Sir et Sz2 y appartenant). ii est à noter qu'il n'y a
aucun cycle de classe V2 (séquences non résolubles par l'algorithme de Gilmore &
Gomory [Il]) dans le cas à trois machines ; ils n'apparaissent qu'à partir de quatre
machines.
Pour terminer, nous illustrerons les affinnations faites un peu plus tôt avec un exemple
numérique que vous trouverez à l'annexe D. On y voit qu'avec des temps de traitement
des produits tout à fait normaux, notre exemple ne répond à aucune condition pour que le
problème soit résoluble par la voie d'un algorithme polynomial : il est NP-dur. De plus,
le fait de changer de robot n'améliorerait en rien la situation car, nous l'avons vu dans les
exemples préckdents, les temps de transport sont relativement équivalents d'une ceUule 1
l'autre. Même que le robot IBM 7576 de type SCARA utilisé dans une cellule à robot
centrk donnerait sûrement de N pire )> résultats.
Ainsi, cela causera plusieurs problèmes réels à trois machines à devenir insolvable de
façon optimale et nous forcera i employer des heuristiques pour parvenir à une solution
acceptable, mais sous-optimale, heuristiques qu'il reste par ailleurs à développer. Nous
désirons néanmoins apporter la suggestion suivante : utiliser l'algorithme de Johnson a
trois machines comme solution initiaie @a version à deux machines s'étant déjà montrée
efficace) et, à l'aide de ce que nous appellerons (( graphes des possiiilités binaires D de
chacun des six cycles unitaires, choisir en continu le prochain mouvement du robot à
faire. Ii reste à cependant tout un bavai1 a faire pour déterminer les règles de
changements d'état du robot, soit Ie passage d'une position à l'autre, en plus de leur
impact sur le système. Voici les graphes de possibilités pour les six séquences
potentiellement optimales à trois machines :
Tableau 10 : Graube des uossibilités selon la seauence Su
Tableau 11 : G r a ~ h e des possibilités selon la séauence Su
Tableau 12 : Gra~be des ~ossibilith selon la s6auence Su
Tableau 14 : Gra~he des ~ossibiütés selon la séauence Ssa
D e l à
1
MA
MB
Mc
O
1
-- O
O
1
O
MA
1
O
O
O
1
MB O
1
1
O
O
Mc
O
1
1
O
O
O
O
O
O
1
--
Notons qu'ici, contrairement au cas B deux machines entre SiJ et SzJ , il y a beaucoup
plus qu'un point en commun entre les séquences Si3 à S6,3 où l'on peut faire le passage de
l'une à l'autre. Le chiffre 1 dans le graphe signifie que le mouvement en partance de la
case de gauche vers la case de droite est "permis" pour cette sequerice ; le chiffre O, le
contraire. Le chiffre 1 entre deux postes identiques (par exemple de Me à MB pour Sd3)
signifie que l'attente du robot il ce poste est possible selon ce cycle.
Par ailleurs, l'algorithme de Johnson A trois machines fonctionne de la même façon que
celui à deux machines (voir section 2.5.1), excepté que le temps de traitement sur la
première machine est remplact par la somme des temps de traitement sur la premiére et
la deuxième machine, tandis que celui de la seconde machine est remplacé par la somme
des temps de traitement sur la deuxihe et la troisième machine. La figure ci-dessous
illustre ce passage :
Figure 29 : Passage de deux trois machines pour l'algorithme de Johnson
Ce mémoire vise à offiir une vision réaliste du problème de l'ordonnancement d'une
cellule robotique et de quelques-uns des défis auxquels les chercheurs sont confrontés.
II permet de cerner les enjeux, d'abord par un approfondissement de la théorie de
l'ordonnancement, son vocable, sa portée, ses limites. Étant donné la complexité des
problèmes considérés, nous avons été à même de constater que les modèles de résolution
classiques ne s'attaquent à ceux-ci qu'au prix de concessions sur l'entièreté fonctionnelle
de la ceIIule (simplifications, hypothèses). Cela peut maiheureusernent conduire à une
perte de productivité en environnement de production concret.
Par l'examen des plus récentes parutions scientifiques dans le domaine de
l'ordonnancement de Ia cellule robotique, nous sommes parvenus à mieux circonscrire
l'étendue des connaissances acquises, les avenues explorées et celles toujours vierges.
Ainsi, le problème de minimisation de la durée totale des opérations de l'atelier mono-
gamme à deux machines approche de son dénouement ; tandis que celui a m machines
demeure encore rebutant, car seul le cycle unitaire a été exploré.
Nous avons ensuite adopté un aménagement de cellule robotique dit à robot mobile,
semblable à celui de Logendran & Sriskandarajah [32] et facilement ramenable à robot
centré en éliminant le mouvement linéaire sur le rail, de même qu'une notation
appropriée après avoir approfondi la mécanique des mouvements d'un robot de
manutention. Puis, nous avons résolu de façon optimale le problème d'ordonnancement
de plusieurs produits d'une cellule robotique à deux machines sans entreposage
intermédiaire ainsi posé, à l'aide du fameux algorithme de Gilmore & Gomory [Il].
Par la suite, nous avons identifié deux opportunités d'extension dignes d'intérêt en regard
des résultats obtenus en comparaison avec ceux d'autres auteurs, la première étant l'étude
de la performance sur les paramètres cruciaux dans la solution d'ordonnancement et la
seconde, le problème à trois machines.
L'étude de la performance a été réalisée afin d'évaluer l'infiuence des temps de transport
et de traitement aux machines sur les résultats de l'ordonnancement. Nous avons pour ce
faire décortiqué l'algorithme de Gilmore & Gornory [I l ] pour définir ce qui influençait la
solution finale et lui avons aussi proposé deux étapes supplémentaires quand l'objectif est
de minimiser la durée totale des opérations. On voit que ces «transformations )) ne
causent pas de grave entorse au processus de résolution de Logendran & Sriskandarajah
[32] car, avec des temps de traitement identiques, nous obtenons la même séquence
optimale pour l'exemple qu'iIs ont résofu. Malgré cela, nos résultats montrent une nette
diminution du temps de cycle, de I'ordre de 30 %, dû au fait que les temps de transport
réels sont plus faibles.
Des performances semblables sont atteintes pour divers robots dans des cellules qui leur
conviennent, le robot SCARA étant mieux adapte pour la cellule à robot centré. C'est
principalement la variance des temps de traitement aux machines qui fait changer la
solution d'un probléme d'ordonnancement de cellule robotique, quoique le robot joue un
rôle atténuateur. Ii est à noter par contre, que l'incidence est toujours plus prononcée
pour une séquence simple comme Sij . De plus, Ia mithode de Johnson appliquée aux
paires e, /J donne des résultats satisfaisants, seuiernent de 2 à 10 % supérieurs à la
solution optimale.
Toujours pour la cellule à robot mobile ramenable à robot centré, le cas à trois machines
a quant à lui été démontré NP-dur car deux des six cycles unitaires potentiellement
optimaux sont intraitables à cause de la récurrence des termes d'attente aux machines. La
nouvelle représentation mathématique des mouvements du robot développée dans ce
mémoire ne change donc rien aux condusions de Hall et al. [14]. Tout comme eux, nous
avons émis des conditions pour que ce ne soit pas un de ces deux cycles qui soient
optimaux ou pour éliminer la récursivité. Nous avons toutefois constaté, à i'aide d'une
application numérique, qu'elles &aient très improbables de se produire, A moins que les
temps de traitement aux machines soient presque nuls.
Plusieurs points restent encore a éclaircir et d'intéressants résultats sont toujours à venir,
entre autres, en ce qui concerne les différentes hypothèses simplificatrices posées a priori
que sont la disponibilité continuelle des machines et le processus d'anivée des ordres de
fabrication statique. Tel que mentionné plus tôt, nous souhaiterions rendre les temps de
chargement dépendants des ordres de fabrication, ce qui à notre avis, collerait davantage
à la réalité industrielle. Eniin, une extension de notre modèle a quatre puis m machines,
ainsi que la génération d'algorithmes sous-optimaux pour le cas à trois machines et plus,
commanderont des efforts de recherche supplémentaires.
8. BIBLIOGRAPHIE
1. Agnetis, A., Schedulinn no-wait robotic cells with two and three machines, European
Journal of Operational Research, Vol. 123, pp. 303-3 14,2000.
2. Aneja, Y.P. et Kamoun, H., ScheduIing Parts and Robot Activities in a Two-machine
Robotic Cell, Cornputers and Operations Research, Vol. 26, No. 4, pp. 297-312,
1999.
3. Bedini, R., Lisini, G.G. et Sterpos, P., Optimal Promamming of Working CvcIes for
industrial Robots, Journal of Mechanical Design, Transactions of the ASME, Vol.
101, No. 2, pp. 250-257, 1979.
4. Boctor, F.F., Svstèmes manufacturiers, notes de cours, Université Laval, 1997.
5. Chen, H.G., Pull-~ush Heuristic for Robot Cvclic Walk-oath Develooment in Flexible
Manufacturine CelIs, Journal of Manufacruring Systems, Vol. 13, No. 1, pp. 31-36,
1994.
6. Chen, H.X., Chu, C.B. et Proth, J.M., Seauencing of Parts in Robotic Cells,
International Journal of Flexible Manuficruring Systemr, Vol. 9, No. 1, pp. 81-104,
1997.
7. Cheng, J.L., Kise, H. et Karuno, Y,, Outimal Schedulin~ for an Automated m-
machine Flowsho~, Journal of the Operations Research Sociew of Japan, Vol. 40,
pp. 356-372, 1997.
8. Crama, Y. et Van de Klundert, J., Cvclic Schedulina of Identicai Parts in a Robotic
Cell. Operalions Research, Vol. 45, No. 6, pp. 952-965, 1997.
9. Garey, M.R. et Johnson, D.S., Cornputers and htractibilitv - A Guide to the Theow
of NP-ComuIeteness, KH. Freeman & Co., USA, 1979.
IO. Garey, M+R., Johnson, D.S. et Sethi, R., Corn~Iexitv of Flowsho~ and Jobshop
Schedulin~, Mathemutics of Operulions Raearch, Vol. 1, pp. 117-129,1976.
1 1 . Gilmore, P.C. et Gomory, R.E., Sequencing a One-state Variable Machine. a SoIvable
Case of the Traveline Salesman Problem, Opemtions Rwearch, Vol. 12, pp. 655-679,
1964.
12. Giordano, M. et Lottin, J., Cours de robotiaue : Descn~tion et fonctionnement des
robots industriels, Éditions A. Colin, France, 1990.
13. Hall, N.G. et Sriskandarajah, C., A Survev of Machine Scheduling Problems with
BIockina and No-wait in Process, Operations Research, Vol. 44, No. 3, pp. 510-525,
1995.
14. Hall, N.G., Karnoun, H. et Sriskandarajah, C., Schedulin~ in Robotic cel1s :
Clasification, Two and Three Machine CelIs, Operations Research, Vol. 45, No. 3,
pp. 421-439, 1997.
15. Hall, N.G., Kamoun, H. et Sriskandarajah, C., Scheduling in Robotic Celis :
Corn~lexitv and S teadv State Anaivsis, European Journal of Operufional Research,
Vol. 109, No. 1, pp. 43-65, 1998.
16. loachim, 1. et Soumis, F., Schedde Efficiencv in a Robotic Production Ce&
International Journal of Flexible Mmufactrtring Systemr, Vol. 7, No. 1, pp. 5-26,
1995.
17. Jawahar, N. Aravindan, P., Ponnarnbalan, S.G. et Karthikeyan, A.A., A Genetic
Ainorithrn-based Scheduler for Set-UD Constrained FMC, Computers in Induse, Vol.
35, No. 3,1998.
18. Jeng, W.-D., Lin, J.T. et Wen, U.-P., Akorithms for Seauencing Robot Activities in a
Robot-centered Parallel Processor, Computers and Operations Research, Vol. 20, No.
2, pp. 185-197, 1993.
19. Johnson, S.M., ûptimal Two and Three Staae Production Schedules, Naval Research
Logistics Quarterly, Vol. 1, pp. 61 -68, 1954.
20. Kats, V. et Levner, E., A Stronglv Polvnomial Akorithm for No-wait Cvclic Robotic
Flowsho~ Scheduling, Operations Research Letters, Voi. 21, No. 4, pp. l? 1-179,
1997.
21. Kats, V. et Levner, E., Cvclic Scheduling of Cberations in an FMS Handled bv a
Single Robot : a Parameûic Critical-uath Ap~roach, Internaiional Journal of Flexible
Marzllfacfuring Systems, Vol. 10, NO. 2, pp. 129-138, 1998.
22. King, R.E., Hodgson, T.J. et Chafee, F.W., Robot Task Scheduiin~ in a Flexible
Manufacturing. Cell, IIE Transactions, Vol. 25, No. 2, pp. 80-87, 1993.
23. Kise, H., On an Automated Two-machine Fiowsho~ Scheduling ProbIem with
Infinite Buffer, Journal of the Operations Research S o c i e ~ ofJapan, Vol. 34, No. 3,
pp. 354-361, 1991.
24. Kise, H., Shioyama, T. et Ibaraki, T., Automated Two-machine Flowshog
Scheduline : a Solvable Case, IIE Transactions, Vol. 23, No. 1, pp. 10-16, 1991.
25. Kogan, K. et Levner, E., A Polynomial Algorithm for Scheduling Small-scale
Manufacturina Cells Served bv Multi~le Robots, Cornputers & Operations Research,
Vol. 25, NO. 1, pp. 53-62,1998.
26. Kuriyan, K. et Reklaitis, G.V., Seauencing Network Flowshops so as to Minimize
Makes~an, Cornputers and Chernical Engineering, Vol. 13, No. 112, pp. 187-200,
1989.
27. L'Ecuyer, P., Maycand M. et Dror, M., Dynamic Scheddina of a Robot Servinq
Machines on a One-dimensiona1 Line, IIE Transactions, Vol. 23, No. 4, pp. 371-382,
1991.
28. Levner, E., Kats, V. et Levit, V.E., An ïm~roved Algorithm for Cvclic Flowsho~
ScheduIina in a Robotic Cell, European Journal ofOperationa1 Research, Vol. 97,
No. 3, pp. 500-508, 1997.
29. Levner, E., Kats, V. et Levin, L, ScheduIina a Two-machine Robotic Ce11 : a Solvable
Case, Annals of Operations Research, Vol. 57, No, 1, pp. 217-232,1995.
30. Levner, E., Kogan, K. et Maimon, O., Flowshou Scheduiing of Robotic Cells with
Job-dependent Transportation ans S et-UD Effects, Journal of the Operational
Research Society, Vol. 46, No. 12, pp. 1447-1455, 1995.
3 1. Liu, S.-C. et Lin, L., Dvnamic seauenciua of robot moves in a manuf'acturing cell,
European Journal of Operational Research, Vol. 69, No. 3, pp. 482-497,1993.
32. Logendran, R. et Sriçkandarajah, C., Seuuencing of Robot Activities and Parts in
Two-machine Robotic CelIs, International Journal of Production Research, Vol. 34,
No. 12, pp. 3447-3463,1996.
33. Matsuo, H., Cvclic Seauencina Problems in a Two-macbine Permutation Flowshou :
Comulexitv, Worst Case and Average Case Analvsis, Nmal Research Logistia, Vol.
37, pp. 679-694, 1990.
34. McCormick, S.T., Pinedo, ML., Shenker,S. et WoIf, B., Seauencing in an Assembly
Line with Blocking to Minimize Cvcle Time, Operations Research, Vol. 37, No. 6,
pp. 925-935, 1989.
35. Mitten, L.G., A Schedulinn Problem, Journal of Industrial Engineering, Vol. 1, No.
3, pp. 131-135, 1959.
36. Noh, Y.D. et Herring,B., Simulation Mode1 for an Individual Robotic Manufacturing
Ce11 International Journal of Production Research, Vol. 26, No. 1, pp. 63-79,1988. -Y
37. Panwaikar, S.S, Scheduling of a Two-machine Flowshou with Travel Times between
Machines, Journal of the Operational Research Society, Vol. 42, No. 7, pp. 609-613,
1991,
38. Pinedo, M., Schedulin~ : Theorv. Alnorithm and Svstems, Prentice-Hall, USA,
1995.
39. Rabinowitz, G., Mehrez, A. et Samaddar, S., A Scheduline; Mode1 for Multirobot
Assemblv Cells, International Journal of Flexible Manufacruring Systems, Vol. 3, pp.
149-180, 1991.
40. Sabucuoglu, 1. et Homrnertzheim, D.L., Exuerimental Investiaation of an FMS Due-
date Scheduling, Problem : Evaiuation of Machine and AGV Scheduling Rules,
International Journal ofFlexible Manufücturing Systems, Vol. 4, pp. 301-323,1993.
41. Schilling, R.J., FundamentaIs of Robotics : Anal~sis and Contro!, Prentice-Hall,
USA, 1990.
42. Sethi, S.P., Snskandarajah, C., Sorger, G., Blazewicz, J. et Kubiak, W., Seauencing
of Parts and Robot Moves in a Robotic cell, International Journal of Flexible
Manufacturing Systems, Vol. 4, No.3/4, pp. 33 1-358,1992.
43. Singh, N., Systems A~proach to Cornputer Intecrrated Desien and Manufachng,
John Wiley & Sons, USA, 1996.
44. Sriskandarajah, C. et Sethi, S.P., Scheduling Algorithm for Flexible Flowsfio~s :
Worst and Average Case Performance, European Journal of Operational Research,
Vol. 43, NO. 2, pp. 143-160, 1989.
45. Sriskandarajah, C., Hall, N.G. et Kamoun, H., Scedulin~ Large Robotic Cells without
Buffers Annals of Operations Research, Vol. 76, pp. 287-321,1998. -9
46. Sriskandarajah, C., Performance of Scheduling AIgorithms for No-wait Flowshop
with Parallel Machines, European Journal of Operational Research, VoI. 70, No. 3,
pp. 365-378, 1993.
47. Stecke, K.E. et Solberg, J.J., Loadinp: and Control Policies for a Flexible
Manufacturing System, International Journal of Production Research, Vol. 19, No. 5,
pp. 481-490, 1981.
48. Stem, H.I. et Vitner, G., Scheduling Parts in a Combined Production-trans~ortation
Work Cell, Journal of the Operationa1 Research Society, Vol. 41, No. 7, pp. 625-632,
1990.
49. Stnisevich, V.A., Two-machine Rowshou Scheduline Problem with No-wait in
Process : Controllable Machine S~eeds, Discrete Applied Mathematim, Vol. 59, pp.
75-86, 1995.
50. Su, Q. et Chen, F.F., ûutirnal Seuuencing: of DoubIe-mi~~er Gantrv Robot Moves in
Tightlv-cou~led Senal Production Svstems, IEEE Transactions on Robotics and
Automation, Vol. 12, No. 1, pp. 22-30,1996.
ANNEXE A
LEXIQUE ANGLAIS-FRANÇATS DES
Étant donné que plusieurs des termes fiéquernment utilisés en ordonnancement sont issus
de la langue de Shakespeare (car c'est aussi la langue de la publication scientifique), nous
avons cru bon d'inclure ce bref lexique afin que le lecteur soit en mesure de rapidement
faire le lien entre l'expression française et son équivalent anglais. Tous les termes en
gras (d'un ou de plusieurs mots) qui avaient le sigle à leur suite se retrouvent dans ce
lexique.
Expression française
Ajustement du profil
Atelier mono-gamme
Atelier multi-gammes
Atelier ouvert
Borne inférieure
Cédule
Cellule manufacturière flexible
C hargementfdéchargement
Chargement d'une ligne flexible
Chemin critique
Contrainte de non-attente
Cycle unitaire
Date due la plus tôt
Délai de réalisation
Dépassement
Dispositif de manutention du matériel
Divisibilité des opérations
Durée totale des opérations
En-cours
kquivalent anglais
Profile fitting (PF)
Flowshop
Jobshop
Openshop
Lower Bound
Schedule
Flexible Manufachiring Ce11
W C )
Loading/ünloading
Flexible Flow Line Loading
(FFW
Critical Path
No-wait Constraint
One-unit Cycle
Earliest Due Date (EDD)
Lead Time
Bypass
Material Handling Device
Preemption
Makespan
Work in Progress (WP)
Expression française +
Ensemble minimal de pièces
Espace d'entreposage
File d'attente
Goulot
Heuristique du goulot changeant
Ordonnancement
Ordre de fabrication
Panne
Pas de file pas de disette
Pièce
Plus grand nombre de successeurs
Pont roulant
Premier rendu premier servi
Prévisions de la demande
Problème du commis voyageur
Produit
Programmation dynamique
Programme linéaire mixte
Quart de travail
Régime permanent
Réglage
Rendement ou productivité de Ia cellule
Réseau Petri
Retard maximum
Équivalent anglais
Minimal Part Set (MPS)
Storage Area
Queue
Bottleneck
Shifiing Bottieneck Heuristic
Scheduling
Job
Breakdown
No Queue No Starve (NQNS)
Part
Greatest Number of
Successors (GNS)
Gantry
First Corne First Served
WFS)
Demand Forecasts
Traveling Salesman Problem
(TSF')
Part Type
Dynamic Programming
Mked Integer Problem (ME)
Shift
Steady State
Set-up
Ceii Throughput
Petri Net
Maximum Lateness
(ou Tardiness)
Expression française -+
Routage -b
Séparation et évaluation successive -B
Station d'entrédsortie + Système de stockage et de retrait automatisé*
Système manufacturier flexible +
Temps de complétion -b
Temps de cycle -P
Temps de démarrage -b
Temps de déplacement -B
Temps de présence moyen en atelier -+ Temps de traitement + Temps de traitement le plus court +
Temps de traitement le plus long +
Temps de traitement alternatif te plus long -,
Temps de traitement restant le plus long -B
Temps de transport
Temps mort
Temps supplémentaire
Travail restant maximum
Véhicule à guidage automatique +
Équivalent anglais
Routing
Branch and Bound @&B)
input/Output Station
Automated Storage and
Retrieval System (ASRS)
Flexible Manufacturing
Systern (FMS)
Completion Time
Cycle Tirne
Starting Time
Travel Time
Mean Flow T h e
Processing T h e
Shortest Processing Time
(SPT)
Longest Processing Time
Longest Alternate Processing
T h e (LAPT)
Longest Remaining Processing
Tirne (LRPT)
Transportation T h e
Idle Tirne
Overtime
Maximum Remaining Work
(MRW)
Automated Guided Vehicle
(AGV)
Expression française
Zone tampon de stockage
kquivalent anglais
Buffer
ANNEXE B
ANALYSE DES AUTRES ATELIERS
A TELIER MONO-GAMME FL-LE
L'atelier mono-gamme flexible est un environnement manufacturier à s stages. Au stage
1, il y a mi machines identiques en parallèle ; au stage s, il y en a m, . Les ordres de
fabrication j l à j,, ont besoin d'être traités par une machine de chaque stage, et
habituellement, n'importe quelle machine fait l'affaire. Les temps de traitement de
l'ordre de fabrication j aux divers stages sont pl^, pu , . . . , prj .
S'il y a des espaces d'entreposage i n t e d i a i r e illimités entre les stages, le cas sptcial
proportionnel (pi = p 2 ~ = . . . - - p , ~ = pi) est d'intérêt. Donc, pour le problème de
minimisation de la durée totale des opérations de l'atelier flexible proportionnel
FFs Ipi=P,I Cm y les règles du temps de traitement le plus long @PT) et du temps de
traitement restant le plus long (LRPT) fonctioment bien, respectivement pour le cas
d'opérations indivisibles et divisibles, mais elles ne donnent pas de résultats optimaux.
Considérons ensuite le cas avec zone tampon de stockage limitée entre les stages et
possibilité de dépassement en ordoonancernent cyclique. Ainsi, un ordre de fabrication
peut bien ne pas avoir besoin d'être traité a un certain stage : le matériel de manutention
fera alors ((sauter » ce stage à I'ordce de fabrication en question. L'algorithme de
chargement d'une Ugne flexible ' (FFLL) tend a minimiser le temps de cycle d'un
ensemble minimal de pièces (MPS) dans le but de maximiser le rendement de la ligne.
L'algorithme FFLL consiste en trois phases :
i. phase d'allocation
ii. phase d'ordonnancement
iii. phase de distribution des lancements
La hase d'allocation des machines assigne chaque ordre de fabrication à une machine en
particulier. Cette phase est réalisée en premier Iieu parce que la charge de travail des
machines doit être connue préalablement aux deux autres phases. Pour obtenir une
charge de travail balancée, on utilise la régie du temps de traitement le plus long 0.
La phase d'ordonnancement détermine l'ordre dans lequel les ordres de fabrication du
M P S sont lancés dans le système, sans affecter la charge de travail des machines. Pour
minimiser le temps de cycle en régime permanent, l'algorithme FFLL utilise L'heuristique
du balancement dynamique qui est basé sur l'observation intuitive que les ordres de
fabrication tendent à s'accumuler dans la file d'attente si une lourde charge de travail est
envoyée à une machine dans un court laps de temps.
La phase de distribution des lancements part du principe que la machine avec la plus
grosse charge de travail constitue le goulot du système. Posons l'hypothèse que les
temps de dkmarrage et h temps de complétion sur la machine goulot sont fixes.
D'abord, considérons les machines qui sont positionnées en aval du goulot et retardons au
maximum le traitement de tous les ordres de fabrication sur celles-ci sans altérer la
séquence. Ensuite, considérons les machines qui sont positionnées en amont du goulot et
devançons au maximum le traitement de tous les ordres de fabrication sur celles-ci,
toujours sans altérer la séquence.
L'expérience a montré que cette methode était efficace. 11 est à noter que cela peut
prendre quelques MPS à atteindre le régime permanent.
Enfin, considérons le cas avec zone tampon de stockage infinie et réglages. Ici, un stage
(parfois deux) constitue le goulot du système et le procédé manufacturier n'est pas
répétitif. C'est donc dire que le groupe d'ordres de fabrication à ordonnancer change
d'une fois à l'autre. Pour débuter le traitement d'un produit, les machines requièrent un
réglage. Le temps de réglage dépend de l'ordre de fabrication considéré et de son
prédécesseur sur la machine, en particulier, des similarités physiques entre les deux.
Si on désire maximiser le rendement de la cellule, cela revient à minimiser la somme des
temps de réglage, spécialement au stage goulot. Un autre objectif louable peut être de
minimiser l'en-cours (WIP). L'algorithme comporte cette fois cinq phases :
i. phase d'identification du goulot
ii. phase de calcd de la fenêtre de temps du stage goulot
iii. phase de calcul de la capacité des machines du stage goulot
iv. phase d'ordonnancement du stage goubt
v. phase d'ordonnancement des autres stages
D'abord, le gouIot est identifié d'après les charges de travail. S'il y a plus d'un goulot,
I'on débute avec le stage le pIus en aval. Ensuite, l'on détermine une fmêtre de temps
pour chaque ordre de fabrication, soit une date de lancement et une date due, durant
laquelle celui-ci doit être traité par le stage goulot, On pose l'hypothèse qu'après avoir
quitté ce stage, les ordres de fabrication ne rencontrent pas d'attente notable aux autres
stages. Le temps qu'ils y passent est donc Ieur temps de traitement multiplié par un
certain facteur de sécurité. Par Ia suite, basé sur sa vitesse, le nombre de quarts de travail
qu'on Iui assigne et un estimé des temps de réglage requis, ta capacité de la machine est
calculée sur l'horizon de planification. Enfin, on séquence les ordres de fabrication selon
les résultats précédents, en premier lieu sur le stage goulot, en second lieu sur Ies autres
stages.
LES ATEUERS OUVERTETMUZll-GAMMES
Dans l'atetier mono-gamme, tous les produits suivent le même routage. En pratique
toutefois, il revient souvent au planificateur de décider des routes, car ils peuvent être
quelconques. C'est ce qu'on appelle l'atelier ouvert.
Quand les routages sont fixes mais qu'ils changent avec les produits (l'ordre est établi
mais multiple), on est en présence d'un atelier multi-gammes. Et si un certain ordre de
fabrication visite une ou des machines à plus d'une reprise, il y a recirculation.
Considérons le problème de minimisation de la durée totale des opérations pour l'atelier
ouvert a deux machines 0 2 1 1 C,, . Il y a n ordres de fabrication qui peuvent procéder
sur la machine 1 d'abord et Ia machine 2 ensuite, ou vice versa. Il est clair que
parce que la durée totale des opérations ne peut être inférieure A la charge de travail de
chacune des machines de l'atelier ouvert. Et l'on pourrait s'attendre en effet ce qu'une
solution optimale donne l'égalité.
Considérons la règle de priorité suivante : dés qu'une machine est libérée, sélectionner
l'ordre de fabrication ayant le plus haut temps de traitement sur l'autre machine. On
nomme cette règle de priorité temps de traitement akernutv le plus long W T ) . Conformément à celle-ci, dès qu'une machine est libérée, les ordres de fabrication qui ont
déjà complété leur kaiternent sur l'autre machine ont une priorité nuUe, sans distinction
entre eux. ii a ensuite été démontré d m Ia littérature que la règie de priorité LAPT
donne une séquence avec une durée totaie des opérations :
L'on sait aussi que le probléme de minimisation de la durée totale des opérations de
l'atelier ouvert à trois machines est NP-dur.
Cependant, la règle LAPT est l'un des seuls algorithmes polynomiaux pour les problèmes
d'atelier à opérations indivisibles. Seul le problème de minimisation de Ia durée totale
des opérations pour l'atelier ouvert à m machines dont les temps de traitement sont
binaires (O ou 1) en possède aussi une. Considérons la règle qui classe les ordres de
fabrication en ordre décroissant du nombre d'opérations restantes :
Des ordres de fabrication non assignés au temps t, sélectionner celui ayant le plus grand nombre d'opérations restantes et l'assigner à la machine (parmi celles qu'il lui reste à visiter bien sQr) qui a le plus grand nombre d'ordres de fabrication à traiter. On pourrait appeler cette règle job with larges? number of operations on the machine with the largesr number of operations (JLNO-MLNO).
il peut par ailleurs être démontré que cette règle mène à un résultat optimal, tout comme
la règle inverse MLMO-JLNO.
Lorsque la division des opkrations est permise, la tâche est d'autant plus kilitée et le
problème de minimisation de la durée totale des opérations de l'atelier ouvert m
machines 0m 1 pnnp 1 C,. peut alors être rCsolu en temps polynomial. D'abord, la règle
LAPT est optimaIe pour le cas à deux machines ; pour le cas a m machines :
ce qui signifie que la durée totale des opérations est au moins aussi grande que Ia charge
de travail maximale des rn machines et que la somme des temps de traitement des n
ordres de fabrication. Ii s'avère de plus assez commode d'atteindre cette borne
inférieure.
Considérons le problème de minimisation de la durée totale des opérations pour l'atelier
multi-gammes à deux machines J2 1 1 Cm . Il y a n ordres de fabrication, dont certains
vont visiter la machine 1 en premier et d'autres la machine 2 en premier. Ce problème
peut être ramené à F2 1 1 Cm aisément, comme suit, par la méthode de Jackson.
Soit JXu l'ensemble des ordres de fabrication qui passent sur la machine X puis sur la machine Y, ordonnés selon la méthode de Johnson ; et Jx l'ensemble des ordres de fabrication qui ne requièrent que ta machine X, ordonnés de n'importe quelle façon. Pour accélérer l'exécution, les ordres de fabrication du groupe J l j ont une priorité plus élevée que ceux du groupe Jlpi sur la machine 1 et le contraire est vrai sur la machine 2. Aiors, la séquence optimale d'exécution estJi2 , JI , Jzi sur la machine 1, et Jzl , Jz , JI2 SUT la machine 2.
Néanmoins, le problème à deux machines est l'un des seuls qui puisse être résolu à l'aide
d'un algorithme polynomia1. Les seuls autres probkmes de cette catégorie ayant aussi
cette possibilité sont ceux dont les temps de traitement sont binaires (O ou 1). Minimiser
la durée totale des opérations pour un atelier rnulti-gammes a m machines peut cependant
être représenté par un graphe orienté ou tes nœuds correspondent aux opérations
effectuées sur les ordres de fabrication, et les arcs les relations de précédente entre les
opérations d'un même ordre de fabrication. La durée totale des opérations est déterminée
par la distance parcourue selon le chemin critique de la source au puits.
Le problème de minimisation de la durée totaIe des opérations pour un atelier multi-
gammes à m machines (Jm 1 1 Cm), étant une généralisation de celui de l'atelier mono-
gamme à m machines, est donc fortement NP-dur. Les procédures de solution sont alors
basées sur l'énumération ou des heuristiques. Des techniques fréquemment utilisées sont
la séparation et l'évaluation successive (B&B), ainsi que l'heuristique du goulot
changeant dont la cornplexit6 nous laisse toutefois perplexe ! L'expérience a demontré
qu'elle donne de très bons résultats.
Différentes règles de priorité simples peuvent aussi être utilisées, que ce soit temps de
traitement le plus long, temps de traitement le plus court, plus grand nombre de
successeurs ' (GNS) qui donne la priorité à la tâche ayant le plus de successeurs, travail
restant tnauiniuni (MRWK) qui donne la priorité à la tâche dont la somme des durées
des successeurs est la plus élevée, ou d'autres. Il faut alors effectuer des essais pour
vérifier laquelle convient le mieux A notre cas, c'est-à-dire donne les résultats les plus
probants.
LES ATELIERS OUVERT ET MULn-GAMMES FLEXTBLES
De la même façon que l'atelier mono-gamme peut être généralisé à un atelier mono-
gamme flexibIe, les ateliers ouvert et multi-gammes peuvent aussi l'être. Excepté qu'il
est encore moins évident d'obtenir des résultats concrets en ce qui les concerne : même le
cas proportionnel (pu =pi) est difficile d'analyse.
Par ailleurs, le graphe de c ml Cm s'étend cependant a ~ r n l r e m 1 Cm et l'heuristique du
goulot changeant peut même y être adapté ce à quoi nous ne nous aventurerons point ici.
m m C
DESCRIPTION DES ROBOTS
D'abord, le premier modèle de robot est Ie GMF Robotics Karel S-300 m. Iî peut manier
des pièces pesant jusqu'à 60 kg selon six axes de contrôle. Son profil élancé l'avantage
lors de la manutention des pièces. Son système de vision lui permet par ailleurs de sentir
la présence d'un objet, détexminer son orientation, compter et mesurer les pièces. Ses
autres caractéristiques incluent notamment :
un système de coordonnées cartésien
un contrôle continu de la trajectoire
des vitesses constantes
Les figures qui suivent présentent respectivement ses axes de mouvement et son champ
d'action qui en découle.
90 DEG
Figure C-1 : Axes de mouvement du robot Karel S-300
Source : GMF Robotics Description Manual, 1986
Figure C-2 : Zone de travaii du robot Karcl S-300
Source : GMF Robotics Description Manual, 1986
Les tableaux qui suivent constituent quant a eux sa fiche technique.
Tableau C-1 a : S~écifications eénérales du modèle Karel S-300
Longueur
Item
Hauteur
Spécification
2219 mm
Largeur
Conditions d'opération
810 mm
Masse
Température ambiante : 0-45 OC
-1000 kg
1 Humidité relative : 20-90 %
Tableau C-1 b : Caractéristiaues cinématiaues du modéle Karel S-300
Répétabilité - -
f 0.5 mm
Source : GMF Robotics Description Manual, 1986
Étendue de mouvement
Vitesse maximale
Ensuite, le deuxième modèle de robot étudié est le CRS Plus A460. De taille plus
modeste, il peut manier des pièces pesant jusqu'à 3 kg et posséde aussi six degrés de
liberté. Les figures qui suivent présentent respectivement son espace de travail en plan et
en élévation.
Vitesse maximale liniaire 1800 mm/s
Axe8
-150 à
+150°
90 OIS
Source : GMF Robotics Description Manual, 1986
Axe y
-180 à
+180°
120 "1s
Axe fl -120 à
+120°
120 O i s
Axe W
-45 à
+4S0
90 '1s
AxeU
-90 a
+90°
90 O i s
Figure C-3 a : Zone de travail du robot CRS Plus A460 (vue en plan)
Source : CRS PIus A460 Specifications, 1990
Figure C-3 b : Zone de travail du robot CRS Plus A460 (vue en élhtion)
Source : CRS PIUS Performance Specifications, 1990
Les tableaux qui suivent constituent quant ii eux sa fiche technique.
Tableau C-2 a : Spécifications ~énérales du modèle CRS Plus A460
I Longueur l 483 mm I
Item
Hauteur
1 Largeur 1 546 mm 1
Spklflcadon
222 mm
I Masse 1 93 kg 1
Tableau C-2 b : Caract6rSstiaues cinématiaues du modèle CRS Plus A460
Répétabilit6 k 0.05 rnm
Enfin, le troisième modèle de robot est le iBM 7576. Un peu plus gros que le précédent,
il peut manier des pièces pesant jusqu'à 10 kg selon quatre axes de contrôle cette fois.
De conception simpIe (il n'a que deux axes de rotation), ses mouvements sont plus faciles
à modéliser. Ainsi, I'espace de travail de ce robot, qui est légkrement inférieure à la zone
de dégagement du bras, est décrite par un plan horizontal X-Y et un axe verticai Z. De
plus, le manipulateur peut effectuer une rotation sur Iui-même, jusqu'a dix tours dans les
deux sens (horaire et ad-horaire), comme le montre la figure ci-dessous.
I Source : CRS PIUS Performance Specifications, 1990
Étendue de mouvement
Vitesse maximale lioeaire
Source : CRS Plus Performance Specifications, 1990
Are 1
-175 à
+l7S O
LOO2 d s *
Axe-2
-105 a
+lOSa
Are3
-90 11
+go O
Axe4
-180 a
+180°
:Axe5 '
-110
+11O0
h e 6 -
-180 A
+180°
Figure C-4 : Mouvements possibles du manipulateur
Source : IBM Operator's Guide, 1988
L'espace de travail qui en résulte est donc représenté dans la figure que voici.
Figure C-5 : Espace de travail du modéle IBM 7576
Source : IBM Operator's Guide, 1988
Le tableau qui suit présente pour sa part sa fiche technique.
Tableau C-3 a : Soécificatiuns eénérales du modéle IBM 7576
1 Hauteur 1 1050 mm
1 Largeur 230 mm
Longueur 990 mm
I
I Couditions d'opération 1 Température ambiante : 0-40 O C
Masse
t 1
1 Humidité relative : 10-80 %
74 kg
L 1
Source : IBM Operator's Guide, 1988
Tableau C-3 b : Caractéristiaues cinémati~ues du modèle IBM 7576
I 1
Vitesse maximale 1 2695 d s 12260 m d s 1 4955 mm/s
Etendue de mouvement
I I Source : IBM Operator's Guide, 1988
Il est à noter qu'a l'exception des segments d'accblérationdécélération, le mouvement se
fait à vitesse constante.
Axe & -120 à
Axegr.
-136 à
Plan X-Y
d a
ANNEXE D
DETAILS ET CALCULS DES EXEMPLES
EEMPLE 1 - GROS ROBOTÀ SIXAciiESDE ROTATION
Les données initiales sont :
Tableau D-1 : Temm de traitement des ordres de fabrication de Pexem~le 1
De plus, 41 = 0.55 min = 33 s, 4 =0.4 min= 24 s, 6; = 0.45 min =27 s, 6 =0.5 min =
30s ,y=0.2min= 1 2 s , 4 = O . l r n i n = u ~ , ~ ~ = 0 . 3 m i n = l ~ , ~ j=0 .2min=u2 ,a=0 .25
m i n = 1 2 , ~ ~ = 0 . 1 5 r n i n = ~ , ~ = O . O 5 m i n = I ~ .
Auxquelles nous ajoutons de notre côté :
Prenons notre premier robot de référence, le GMF Karel S-300, pour lequel v,,~, =
,, = 1800 mm/s et v , ~ = 200 mmis :
4 B 6, = - = 8 s = 0.133 min et dont la pause est de 1.85 S. Alors, ' m i l
De même, a,' = aj -t ui + Il + t , , ~ = aj + 0.5 et bj' = bj + u3 + l3 + t8.o = bj + 0.3 , soit :
Tableau D-2 : Données intermédiaires Dour le robot GMF (exem~le 1)
Donc, = np + 2 (a, '+bj ')= 8(0.828)+ (28.5 + 27.4) = 62.5 minutes peu importe la j-1
séquence de pièces, soit une réduction de 22.6 minutes par rapport à la solution de
Logendran & Snskandarajah [32].
Ce qui suit constitue l'application de l'algorithme de Gilmore & Gomory [ I l ] à cet
exemple pour la séquence . Ii requiert un temps de calcul de O(n1ogn).
Tableau D-3 : É t a ~ e 1 de I'al~orithme de Gilmore & Gomorv Dour I'erern~le 1
i j initial
ej
8
5
7
4.5
3.8
1
3
3 .O
1.3
6
8
4.5
3.8
2
4
3.5
2.3
7
5
4.0
4.3
3
1
2.5
3.8
8
6
4.0
4.3
4
2
2.5
3.8
Car ej = ai' et 4 = max { y bj3 ; or, 6,' > p 'd j , d'où4 = bjl .
Tableau D-4 : Étapes 2 et 3 de I'aleorithme de Cilmore & Gomorv Dour i'exem~le 1
i f i e ~ n &) arc
1 1.3 2.5 3 RU
2 2.3 2.5 4 R2.4
3 3.8 3 .O 1 R3.1
4 3.8 3.5 2 R42
5 3.8 4.0 7 R5,7
6 3.8 4.0 8 R6,8
7 4.3 4.5 5 Ri$ 7
8 4.3 4.5 6 R8,6
Explications : - 401 correspond au classement des el au tableau D-3. Par exemple, e ~ , , etait a fa
position j = 3, d'où ~ 1 ) = 3
- Les arcs se définissent comme suit : Ri.&,
Voici le graphe non onenté initial :
Figure D-1 : Graphe non orienté initial pour l'exemple 1
Tableau D-5 : kta~es 4 et 5 de I1aborithme de Cilmore & Gomorv Dour l'exemple 1
Explications : - Le coût d'ajout des arcs C,J+~ est égaI a la différence entre l'expression de la
deuiéme colonne et celle de la troisième colonne du tableau D-5.
- Les arcs sont ajoutés seuIement entre nœuds successifs sans induire de cycle, et
ce, en ordre croissant de leur coltt.
Voici le nouveau graphe non orienté :
Figure D-2 : Nouveau graphe non orienté pour l'exemple 1
Étaue 6 : les arcs (I,2) et (5,6) appartiennent au groupe 1 ; l'arc ( 4 3 , au groupe 2
Étapes 7 et 8 : i l = 5 , iz = I ; ji = 4
Étape 9 : la tournée minimale est obtenue en faisant suivre le fm ordre de
fabrication par l'ordre de fabrication w * (j) = (alq2 (arr ( j ) ) ) ) d'où,
Tableau D-6 : Valeurs de la fonction P[fi Dour I'exem~le 1
En commençant par JI , la séquence optimale est donc :
JI - J4 - Jg - J6 - J7 - JS - J2 - J3 , qui revient a J3 - J2 - J6 - Ja - Js - J7 - J4 - JI selon l'ordre
initial
Il est à noter que cette solution est identique à cetie trouvée par Logendran &
Snskandarajah [32], malgré que l'arc (1,2) soit passé du groupe 1 au groupe 2. En fait, la
position du terme a dans I'équation (donc i'appartenance au groupe 1 ou 2) ne change
rien du moment que les arcs ajoutés demeurent Ies mêmes et que l'arc ainsi déplacé n'a
pas de nœud commun avec un autre arc. A la limite, si tous les indices des termes a
étaient différents, leur ordre d'apparition dans la fonction n'aurait aucune
importance. En effet, toute permutation des a donnerait alors les mêmes résultats dû à la
nam de I c i # ( ( 1 . 2 ( 4 , ) # ( 5 , c a s ) car la
précédente de a56 sur as5 est conservée. Le seul nœud commun étant le nœud 5, al2
peut être déplacé à volonté sans aucune influence.
Par ailleurs, quelles sont les conditions pour conserver les mêmes arcs ajoutés ? D'abord
que leurs coûts Gr demeurent les plus bas et que Ies mêmes arcs ne soient pas créés a
l'étape 3 (on ne peut ajouter que les arcs qui n'existent pas déjà). Pour ce faire, sed le
classement des 4 a une influence car celui des ej est uniquement fonction des ajl . Or,
I'ordre de ces derniers ne d6pend que des temps de traitement à la première machine (q'
= aj + cst) et ne peut donc pas changer pour un même problème. Par contre, comme
f, = maxb, b j l ] , son classement peut changer si une variation de p vient chambarder
l'ordre des4 . Ce qui n'est pas le cas ici bien que ,u devienne inférieur à tous les bj' . Ii est à noter que tout comme celui des ai1 , I'ordre des bjl ne dépend que du temps de
traitement à la seconde machine (bit = b, f cst).
Étaue IO : Voici le diagramme de Gantt de la séquence optimale :
Figure D-3 : Diagramme de Gantt pour le robot GMF (exemple 1)
Ici, Mi' et M i constituent deux machines ((virtuelles N combinant une machine et une
partie des mouvements du robot, puisque le diagramme est tracé en utilisant les valeurs
de e, et4 .
Ainsi, le temps de cycle T,,, = np + T, '= 8 0.828 + 29.4 = 36.0 minutes, soit une
réduction de 19.6 minutes par rapport à la solution de Logendm & Sriskandarajah.
Comme T2,0 < Tl , la séquence SZJ est préférée à SI1 .
Considérons maintenant un autre robot a six axes de rotation, mais moins rapide et moins
lourd. Prenons par exemple le CRS PPLus qui possède les caractéristiques suivantes :
vz ,,, = v/[,, ,,,= = 1002 d s , v , ~ = 275 mm/s et dont la pause est de 1.65 S. Sa portée
étant plus faible, on doit aussi rajuster h, dAbB et d8.0 = dIA à la baisse (par convenance,
nous les diminuons de moitié) pour que le robot puisse atteindre les machines.
puis t = 266$t- + 6, +pure = t,, = t,. = t,,, = t,,,
Or, e, = ajr et A = max {p,b,3 = bj' à nouveau car bj' > p V j .
Tableau D-7 : Données intermédiaires ~ o u r le robot CRS lexemple 11
Donc, T, = n p t 2 (a j ' tb j ' )= g(0.69) + (28.5 t 27.4) = 61.4 minutes, peu importe la j-l
séquence de pièces, soit une réduction de 23.7 minutes par rapport à la solution de
Logendran & Sriskandarajah [32].
1 j initial
ajr= ej
bjr =fi
De plus, les conditions nécessaires pour conserver la même solution étant respectées
(mêmes arcs ajoutés et position relative des nœuds communs inchangée dans l'équation
de y*o) car classement identique des e, etfi, la séquence optimale de pièces demeure Ia
même pour le cycle S2,2 . On a donc Tz,, = 8r0.69 + 29.4 = 34.9 minutes, soit une
réduction de 20.7 minutes par rapport ii la solution de Logendran & Sriskandarajah.
Comme Tzar < Tl , la séquence SzJ est préférée à SIJ encore une fois.
1
3
2.7
1 .O
2
4
3.2
2 .O
-
3
1
2.2
3.5
4
2
2.2
3.5
5
7
4.2
3.5
6
8
4.2
3.5
7
5
3.7
4 .O
8
6
3.7
4 .O
LE 1 - ROBOT DE TYPE S M
Enfin, considérons qu'il n'y a pas d'obstacle à éviter (donc que h = O) et qu'on utilise un
robot SCARA à quatre axes de rotation, par exemple le IBM 7576. Ce dernier est
beaucoup plus rapide en rotation, quoique plus lent en mouvement vertical. ii est aussi
moins lourd que le Karel S-300. Plus en détail, voici ses caractéristiques :
v: ,,,, = 574 rnmls, vCim ,, = 4955 mm/s , v d = 250 mm/s et dont la pause est de 1.25 S.
Si h = O puis dASB et ~ B . O = conservent les mêmes valeurs (la portée du IBM 7576 et
du CRS Plus A460 sont semblables), alors
dB.0 SBSO =SI," = - - 4, -200 mm et 6, =-- - 3.2 s = 0.053 min ,
2 'rail
A l'aide de la règle des sinus, et sachant qu'un triangle construit dans un cercle est
180-8
toujours isocèle, l'on trouve r = . Soit 0 = 45 O, comme on suppose sin 0
dB,, sin 67,S0 que c'est le cas ici, r = = 523 mm.
sin 4 5 O
Figure D-4 : Calcul du rayon de la cellule
t=9.1 s=O.l52 min
d'où p = uz + l2 + 2t = 0.754 min = 45 s
et p = ul + I I + t i ~ + i3 + te.0 + LA + 2t = 1.10 min = 66 s
Tel qu'auparavant, a,' = a, + ui + Il + t l ~ = aj + 0.5 et bj' = b, + u3 + I3 + ho = bj + 0.3,
d'où T, = np + (a, '+bj ')= g(0.7~4) + (28.5 + 27.4) = 61.9 minutes peu importe la j-1
séquence de pièces, soit une réduction de 23.2 minutes par rapport à la solution de
Logendran & Sriskandarajah.
Comme tous les ej e t 5 sont identiques à ceux de premier cas (robot GMF), le résultat ne
peut être que la même, et ce, malgré que le temps de déplacement t du robot SCARA soit
différent. Ceux qui importent dans les équations de ai' et bjf sont plutôt les temps t ~ , o et
[I.A (qui sont pour les trois robots a O. 1 min), en autant bien sûr que bjJ soit plus grand que
p pour tous les ordres de fabrication.
Ainsi, T,., = np +Tu '= 8 0.754 + 29.4 = 35.4 minutes, soit une réduction de 20.2
minutes par rapport à la solution de Logendran & Sriskandarajah [32].
Comme TL, < Ti , la séquence S2,2 est préférée à Sis encore une fois.
Revenons-en à l'exemple ii huit ordres de fabrication de Logendran & Snskandarajah [32]
pour une ceIlule i robot mobiIe. Pour la première variante, les temps de traitement sur les
machines deviennent :
Tableau D-8 : Temps de traitement des ordres de fabrication de l'exern~le 2
Les temps de chargement / déchargement demeurent quant à eux les mêmes : ul = 0.1
min , Il = 0.3 min, Q = 0.2 min, 1, = 0.25 min, u3 = 0.15 min, h = 0.05 min ; ainsi que
les dimensions physiques de la cellule : h = 300 mm , d A . ~ = 1600 mm et de.* = dASI = 800
m .
Donc, pour le premier robot de référence (GMF Karel S-300) dont la pause est de 1.85 S.:
t,,, = r,,, =3.9 s = 0.065 min
De même, a,' = a, + ul + 11 + t l ~ = aj + 0.5 et bj' = 6,- + s + l3 + ts.0 = bj + 0.3 , soit :
Tableiiu D-9 : Donnees intermédiaires Dour le robot GMF fexem~le 2)
Donc, T, = np + 2 (a ,lcb,')= 8(0.828)+(~3.0 + 13.0) = 32.6 minutes peu importe la /-1
séquence de pièces, soit une baisse de 29.9 minutes par rapport à la solution précédente.
Ce qui suit constitue l'application de l'algorithme de Gilmore & Gomory [Il] à cet
exemple pour la séquence Sz2 . ii requiert un temps de calcul de O(n1ogn).
Tableau D-10 : É t a ~ e 1 de I'd~orithme de Gilmore & Gomow Dour le robot GMF
(exem~le 2)
Car ej = ai1 et J = max {bbj") .
j
j initial
9
fi
1
2
2.5
1.1
2
5
1 .O
1.1
3
7
1.5
1.1
4
3
2.0
1 .S
5
1
1.5
2.0
6
8
1 .O
2.0
7
4
1.5
2.5
8 .
6
2.0
2.5
Tableau D-11 : Étapes 2 et 3 de I'aleoritbme de Gilrnore & Gomorv pour l'exem~le 2
Voici le graphe non orienté initial :
Figure D-5 : Graphe non orienté initial pour l'exemple 2
i 1
2
3
4
5
6
7
8
e(lo
1 .O
1 .O
1.5
1.5
1.5
2.0
2.0
2.5
f i 1.1
1.1
1.1
1.5
2.0
2.0
2.5
2.5
Ml 2
6
3
5
7
4
8
1
arc
Riz
R2,6
R31
h s R s , ~
R6,4
R7,8
R8.i
Tableau D-12 : Étapes 4 et 5 de I'aleorithme de Gilmore & Gomorv pour I'exem~le 2
Voici le nouveau graphe non orienté :
Figure D-6 : Nouveau graphe non orienté pour l'exemple 2
Étaue 6 : l'arc (2,3) appartient au groupe 1
É t a~e 9 : la tournée minimale est obtenue en faisant suivre le jh ordre de
fabrication par l'ordre de fabrication y * ( j ) = ((a,, (j)) d'où,
Tableau D-13 : Valeurs de la fonction P ( A Dour I'exemple 2
En commençant par Ji , la séquence optimale est donc :
Enfin, cette solution est différente de celle trouvée par Logendran & Sriskandarajah ! II
faut mentionner qu'ici un unique arc (2,3) a été ajouté : c'est là que se trouve la majeure
distinction. Évidemment, son appartenance au groupe 1 ou 2 ne change strictement rien,
puisqu'il est seul. D'où émane cette situation ? Essentiellement, du fait que le graphe
initial était déjà presque complet dû à la structure des temps de traitement. En effet,
contrairement au cas de Logendran & Sriskandarajah [32] où tous les arcs étaient
réciproques (RxJ et RH), ici tous les arcs sont uniques excepté RJs , qui en réalité n'en est
pas un. Il ne reste donc qu'un seul arc à ajouter pour raccorder le nœud 3 et ainsi rendre
le graphe complet. Et comme la variance des temps de traitement est basse, tous les coGts
sont nuls, ce qui nous laisse le plein choix.
É t a ~ e 1 O : Voici le diagramme de Gantt de la séquence optimale :
Figure D-7 : Diagramme de Gantt pour le robot GMF (exemple 2)
Ainsi, T,,, = np + Tm '= 8 0.828 +14.1= 20.7 minutes, soit une baisse de 15.3 minutes
par rapport a Ia solution précédente.
Comme Tl,, < Tt , la séquence SZ3 est préférée à SiJ .
Prenons maintenant le deuxième robot, le CRS Plus A460 dont la pause est de 1.65 S.
Les dimensions physiques de la cellule sont à nouveau divisées par deux compte tenu de
sa portée moindre : h = 150 mm, dAhB = 800 mm et dBSO =dlA = 400 mm .
a t = 7.2 s = 0.120 min
- tBSo - t , , , =4.8 s=0.080 min
Ici encore, a,' = aj + u1 + il + t l . ~ = aj + 0.5 et bjr = bj + s + I3 + tg.0 = bj + 0.3 , soit :
Tableau D-14 : Données intermédiaires Dour le robot CRS lexern~le 2)
Donc, T, = np + 2 (a ,'+bjl)= 8(0.69)+(13.0+13.0) = 31.5 minutes, peu Unporte la hi
séquence de pièces, soit une baisse de 29.9 minutes par rapport la solution précédente.
Cette fois,
Tableau D-15 : Étape 1 de l'aleoritbme de Gilmore & Gomorv pour le robot CRS
(exemple 2)
Car ej = a,' et = rnax {fibj') .
j
j initial
el
f i
De plus, l'unique arc ajouté étant toujours R2,3 , VU que le classement des ej et 5 est
identique, la séquence optimale de pièces demeure la même. Voici son diagramme de
Gantt :
Figure D-8 : Diagramme de Gantt pour le robot CRS (exemple 2)
1
2
2.5
1 .O
Comme tous les ej e t 5 sont identiques, le résultat ne peut être que Ie même. On a donc
Tz,, = 800.69 + 14.0 = 19.5 minutes, soit une baisse de 15.4 minutes par rapport k la
solution précédente.
Comme Tr , < TI , la séquence Szj est préférée à Sis encore une fois.
2
5
1 .O
1 .O
3
7
1.5
1 .O
4
3
2.0
1.5
S
1
1.5
2.0
6
8
1 .O
2.0
7
4
1.5
2.5
8
6
2.0
2.5
EXEMPLE 2 - ROBOTDE TYPE SCARA
Enfin, considérons qu'il n'y a pas d'obstacle B éviter et qu'on utilise le robot IBM 7576 a
quatre axes de rotation dans une celluls & robot centré. En rappel, ses caractéristiques
sont :
vz ,,,, = 574 m d s , v, ,, = 4955 d s , v,d = 250 mm/s avec une pause de 1.25 S.
Même si on passe d'une cellule a robot mobile A robot centré, le rayon et l'angle de
rotation peuvent très bien conserver Ia même valeur (r = 523 mm et 8,9~ = BIA = 45 O),
sauf qu'il n'y a pas de mouvement linéaire sur le rail.
Figure D-9 : Représentation de la cetlule h robot centré
raR.E D'où f,, = 2 6 6 , + /"- +pame=6.1 s =0.101 min ", m
- t ~ . ~ - ' 0 . A =2667/ Pz OPX +'@,;/ VChiilu t pause =6.15 s = 0.102 min
d'où p = uz + l2 + 2 t A , ~ = 0.652 min = 39 s
et p = u~ + 11 + u3 + 13 + t i ~ + t8.0 + ~ B J + t0.0,~ = 1.00 min = 60 s
Ici, ai' = a + 111 + 11 + t1.0,~ + ~ B J - ~O,A,B = aj +- 0.5 et bjr = b + ~3 + l3 + tbO + tOA - tASB = bj
+ 0.3, d'où T, =n(p+tA,a -ta,, - ta, +t , , )+ t (a , '+b , ' ) j=i
1; =8(0.652+0.101-2*0.102+0.104)+(13.0+13.0)=31.2 minutes peu importe Ia séquence
de pièces, soit une baisse de 30.7 minutes par rapport à la solution précédente.
Comme tous les ej e t4 sont identiques à ceux du deuxième cas (robot CRS), le résultat ne
peut être que la même, et ce, malgré le fait que le robot SCARA soit utilisé dans un autre
type de celIuIe. Ceux qui importent dans les équations de aj' et b,' sont phtôt les temps
t ~ , * et q~ (qui sont pour les deux robots 0.1 min), en autant que p conserve la même
valeur car bjl ne lui est pas supérieur pour tous les ordres de fabrication.
Ainsi, T,., = np + T, '= 8 0.652 + 14.0 = 19.2 minutes, soit une baisse de 16.2 minutes
par rapport à la solution précédente.
Comme Tz.,< Ti , la séquence SZt est préférée à Sib encore une fois.
EXEMPLE 3 - GROS ROBOT A SNAXES DE ROTATION
Pour la seconde variante, les temps de traitement sur les machines deviennent :
Tableau D-16 : T e m ~ s de traitement des ordres de fabrication de Iyexemple 3
Les temps de chargement / déchargement et les dimensions physiques de la cellule
demeurent encore une fois les mêmes. Donc, pour le premier robot de référence :
t , , =t , , , 13.9 s=0.065 min
d'ou p = u2 + l2 + 21 = 0.828 min = 50 s
et p = ui + 11 + u3 + l3 + t8.0 + + 2t = 1.1 1 min = 66 s
De même, aif = aj + U I + I l + t r ~ = aj + 0.5 et bjf = bj + 243 + l3 + t ~ , g = bj + 0.3 , soit :
Tableau D-17 : Données lotermddiaires Dow le robot GMF (exem~le 3)
Car ej = a,' et J = max {fi bj') ; or, bjl > p V j , d'oùj = bit .
Donc, T, = np+ 2(a j1+bj ' )= 8(0.828)+(53.0+50.5) =110 minutes peu importe la j-i
séquence de pièces, soit une hausse de 47.6 minutes par rapport à la sohtion de
l'exemple 1.
Ce qui suit constitue l'application de l'algorithme de Gilmore & Gomory [I l ] à cet
exemple pour la séquence Sz2 . ii requiert un temps de calcul de O(n1ogn).
Tableau D-18 : Éta~e 1 de Italeorithme de Gilmore & Gomorv mur le robot GMF
(exemple 3)
TabIeau D-19 : Éta~es 2 et 3 de Italeorithme de Gilmore & Gomorv Dour I'exemle 3
j
j initial
el
f i
1
5
7.5
3 .O
i 1
2
3
2
8
3.5
4.0
f i 3.0
4.0
4.5
4
5
6
e~lo
3.5
4.5
5.0
3
2
11.0
4.5
7 8.5 9.0 5 R75
8 10 Il 3 Rs3
6.0
7.0
7.5
4
7
4.5
6.0
M) 2
4
7
8
4
6.5
10
5
1
9 .O
7.0
arc
RI s
R2.4
R3.7
6.0
6.5
7.5
6
3
6.0
7.5
6
8
1
7
6
5 .O
8.5
R46
RS,B
%,I
Voici le graphe non orienté initial :
Figure D-10 : Graphe non orient6 initial pour l'exemple 3
Tableau D-20 : Étapes 4 et 5 de Italporithrne de Gilmore & Comorv Dour l'exemple 3
Voici Ie nouveau graphe non orienté :
Figure D-11 : Nouveau graphe non orienté pour l'exemple 2
Étaue 6 : I'arc (2,3) appartient au groupe 1
Étapes 7 et 8 : il = 2
Étape 9 : la tournée minimale est obtenue en faisant suivre !r f'"' ordre de
fabrication par l'ordre de fabrication y * (j) = #(a,, (j)) d'oh,
Tableau D-21 : Valeurs de la fonction P(13 Dour I'exern~le 3
En commençant par Ji , la séquence optimale est donc :
j1 - J2 - 5, - JS - j8 - J3 - J4 - J6 , qui revient a Js - J8 - J6 - 34 - J2 - J1 - J7 - J3 selon l'ordre
initial
Voilà une deuxième solution différente de celle trouvée par Logendran & Sriskandarajah
[32]. À nouveau, seul l'arc (2.3) a été adjoint au graphe initial. L'explication fournie au
problème précédent s'applique encore, soit que le graphe initial était déjà presque
complet dû à la structure des temps de traitement. Sauf qu'ici tous les arcs sont bel et
bien uniques mais séparés en deux ((sections » (1-2-4-6 et 3-5-7-8). Ii ne reste donc
qu'un seul arc à ajouter pour les raccorder et ainsi rendre le graphe complet. Cette fois,
la variance des temps de traitement étant plus grande, un seul cotit est nul, et c'est cet arc
que l'on choisit précisément d'ajouter.
Étape 1 O : Voici le diagramme de Gantt de la séquence optimale :
Figure D-12 : Diagramme de Gantt pour le robot GMF (exemple 3)
Ainsi, T,, = np + T, '= 8 r 0.828 +53.0 = 59.6 minutes, soit une hausse de 23.6 minutes
par rapport à la solution de l'exemple 1.
Comme TL,= < Ti , la séquence S2,2 est préférée à SiJ .
EXEMPLE 3 - PETIT ROBOTA SIX AXES DE ROTA TION
Pour le deuxième robot, toujours en divisant les dimensions de Ia cellule de moitie :
t = 7.2 s = 0.120 min
Ici encore, ai1 = Uj + ür + 1, + t~~ = al + 0.5 et bj' = bj + u3 + f3 + t ~ , o = bj + 0.3 , soit :
Tableau D-22 : Données intermediaires pour le robot CRS (exem~le 3)
Car e, = ujl et 5 = max {fibj3 ; or, bi'> p V j , d'où4 = bj' .
j
a/'=ej
bj' =jj
Donc, T, = n p + 2 (a '+bjl)= 8(0.69)+(~3.0+~0.~) = 109.0 minutes, peu importe la j - 1
séquence de pièces, soit une hausse de 47.6 minutes par rapport à la solution de
l'exemple 1.
De plus, l'unique arc ajouté étant toujours RzJ , vu que le classement des ej et$ est
identique, la séquence optimale de pièces demeure la même. On a donc Tz, = 800.69 + 53.0 = 58.5 minutes, soit une hausse de 23.6 minutes par rapport à la solution de
l'exemple 1.
1
9.0
7.0
2
11.0
4.5
3 4 5
6.0
7.5
7.5
3.0
6.5
10
6
5.0
8.5
7 8
4.5
6.0
3.5
4.0
Comme TL,< TI , la siquence SÎf est p r é f h à Si2 encore une fois.
EXEMPLE 3 - ROBOT DE TYPE SCARA
Enfin, pour Ie troisième robot de référence utilisé dans une cellule a robot centré, En
gardant les mimes dimensions de ceIlde mais sans mouvement linéaire sur le rai1 :
r ~ , ~ = tod = 6.15 s = 0.102 min t ~ , o = t l . ~ = 6.0 s = 0.100 min
Ici, a,' = a + U , + li + + IB,J - t A , ~ = aj + 0.5 et bj4 = b + ~3 + 1, + t g . ~ + t o ~ - t * . ~ = bj
108.7 minutes peu importe la séquence de pièces, soit une hausse de 46.8 minutes par
rapport A la solution de l'exemple 1.
Comme tous les ej et 5 sont identiques, le résultat ne peut être que le même. Ainsi,
T,,, = np t T, ' = 8 0.652 t 53.0 = 58.2 minutes, soit une hausse de 22.8 minutes par
rapport à Ia solution de i'exemple 1.
Comme TLp < Ti , la séquence SZJ est préférée à Sif encore une fois.
EXEMPLE 4 - CONDITIONS DE RÉCURRENCE ET D B ~ ~ ~ w É
Soit les données initiales suivantes :
Tableau D-23 : Temps de traitement des ordres de fabrication de I'exem~le 4
De plus, t q = 0.1 rnin , li = 0.3 min , uz = 0.2 min , lz = 0.25 min , u3 = 0.15 min, l3 =
0.05 min ,244 = 0.25 min, l4 = 0.15 min.
Auxquelles nous ajoutons de notre côté :
Prenons notre premier robot de référence, le GMF Karel S-300, pour lequel v,,,,, = v,fR - = 1800 mrnls et Vmil = 200 mmls :
4, 6, = - = 8 s = 0.133 min et dont la pause est de 1-85 S. Alors, Y,,
t = 11.3 s = 0.189 min
r' = 2667 + 26, +pause = r A , = t,,, = t , , = t , , Am t' = 19.3 s = 0.322 min
2sc.o r c , = t1.A = 266y + Ah- +pause = 3.9 s = 0.065 min V: mu
vérification de la récurrence :
d'où on ne peut pas éliminer la récurrence des temps d'attente aux machines pour les
séquences Szt et S63 .
condition i)
condition ii)
ûj > r ' = 0.32 min V j , b, > u4 f 14 + 2r + tc.0 = 0.84 min kf j
e t c p u l + 1 1 f u z + 1 ~ + t ~ ~ + 2 ~ + 2 t ' = 1 . 9 4 m i n V j
i condition iii)
a ~ > u ~ + I ~ + c ~ ~ + 2 t ' = l . l l m i n V j ,
b j > 2 t - t1=0.06min QJ
et cj > U I +II + tlA + 2t '= 1.11 min V J
condition iv)
aj>u3 + 1 3 +u~+I~+2t+2t '+ tC0=1 .69 tr i in V j \ j = 2 ,
b, l u i + 11 + 2t + t r ~ = 0.84 min V j
et c, I f ' = 0.32 min V j
d'où on ne peut pas prétendre qu'un autre cycle unitaire que St3 ou SSJ est optimal pour
cet exemple.
Recommended