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.