3e Conférence Francophone de MOdélisation et SIMulation “Conception, Analyse et Gestion des Systèmes Industriels”

MOSIM’01 – du 25 au 27 avril 2001 - Troyes (France)

MODELISATION ET RESOLUTION D’UN PROBLEME

D’ORDONNANCEMENT DANS UNE CELLULE DE PRODUCTION

A. SOUKHAL et P. MARTINEAU

Laboratoire d'Informatique
Ecole d'Ingénieurs en Informatique pour l'Industrie
64 avenue Jean Portalis, 37200 Tours, FRANCE
{soukhal,pmartineau}@[Link]

RESUME : Nous étudions la résolution des problèmes d'ordonnancement dans des ateliers flexible de production.
Nous proposons une approche originale composée, pour la première partie d'une identification précise du problème
d'ordonnancement avec un minimum d’hypothèses simplificatrices. Nous illustrons sur un exemple d'atelier de
production réel comment par étape successives, nous transformons un problème simple, bien connu, mais au
hypothèses simplificatrices fortes, en un problème plus complexe mais plus réaliste. Puis dans une deuxième partie,
nous proposons une résolution par une métaheuristique bien adaptée: le Recuit Simulé (RS). Adapter le RS à notre
problème nécessite la définition d'un voisinage adéquate et un certain réglage des différents paramètres. Nous étudions
la résolution des problèmes d'ordonnancement dans des ateliers flexible de production. Nous proposons une approche
originale composée, pour la première partie d'une identification précise du problème d'ordonnancement avec un
minimum d’hypothèses simplificatrices. Nous illustrons sur un exemple d'atelier de production réel comment par étape
successives, nous transformons un problème simple, bien connu, mais au hypothèses simplificatrices fortes, en un
problème plus complexe mais plus réaliste. Puis dans une deuxième partie, nous proposons une résolution par une
métaheuristique bien adaptée: le Recuit Simulé (RS). Adapter le RS à notre problème nécessite la définition d'un
voisinage adéquate et un certain réglage des différents paramètres.

MOTS-CLES : Atelier Flexible de Production, Ordonnancement, Notation, Recuit Simulé

• les zones de livraison ou d’enlèvement ne sont

1. INTRODUCTION pas gérées en exclusion mutuelle. Ce qui sous-
entend qu’un nombre infini de transporteurs
Les problèmes d’ordonnancement constituent une bran- peut se positionner devant la machine sans pro-
che de la Recherche Opérationnelle. On rencontre des blème.
problèmes d’ordonnancement dans toutes nos activités • les temps de chargement ou de déchargement ne
quotidiennes : dans la gestion de notre emploi du temps, sont pas pris en compte. On peut signaler que
dans les ateliers de production, dans les systèmes les travaux menés dans le cadre des HSP trai-
d’exploitation, … Face à un système de production, un tent parfois cette contrainte lorsqu’elle ne peut
responsable peut avoir du mal à identifier la classe de plus être négligée.
problème à laquelle il est confronté. • …
Toutes ces hypothèses écartent le problème résolu de
Depuis plusieurs années, des hypothèses fortes, souvent celui réellement présent dans l’atelier. Il devient alors
très restrictives, permettent des avancées dans la Recher- illusoire de reprendre la séquence produite lors du calcul
che en ordonnancement. Mais ces hypothèses restrei- de l’ordonnancement et de la faire appliquer au supervi-
gnent le champs d’application des résultats, ainsi on seur de l’atelier. Prenons le cas d’un atelier avec deux
suppose que : machines reliées par un chariot. Les ressources sont de
• les stocks amont et aval d’une machine sont de capacité unitaire et il n’y a pas de stock intermédiaire.
capacité infinie. Il n’y a donc pas de blocage Que se passe-t-il quand le chariot transportant une pièce
possible sous prétexte qu’il n’y a plus de place arrive devant la deuxième machine qui vient de terminer
dans un stock. son traitement sur une autre ? La plupart des calculs
• les transports sont immédiats. On ne se préoc- d’ordonnancement négligent ce cas de figure. Comme
cupe pas, ni de la capacité des transporteurs ni d’autres situations, les négliger, lors du calcul de
du temps qu’ils mettent pour transférer une l’ordonnancement provoque des lacunes et incohérences
pièce d’une machine à une autre. au moment de la mise en œuvre de ces séquences
d’ordonnancement dans un atelier réel.

- 525 -
 MOSIM’01 – du 25 au 27 avril 2001 - Troyes (France)

pose d’un ensemble de machines connectées par un seul

Dans cet article, nous proposons une approche originale moyen de transport (chariot, bras de ro-
composée, pour la première partie, d’une identification bot,…)[MacCarthy et al.92].
précise du problème avec un minimum d’hypothèses Cet atelier à été introduit par Asfahl en 1985 [Asfahl, 85]
simplificatrices [Soukhal et al., 00 a et b], puis, dans une avec un bras de robot comme moyen de transport. Les
deuxième partie, d’une résolution par le recuit simulé gammes des produits sont toutes identiques. Appelé
adapté [Soukhal et al., 99] (OCEA (Outil de Comparai- Flow-shop robotisé, le problème est NP-difficile au sens
son et d’Elaboration d’Algorithmes) [Collectif, 98] per- fort. Dans [Brauner, 99] l’auteur s’intéresse à la domi-
met une identification des algorithmes de résolution s’il nance des k-cycles (pendant un cycle de production on
en existe [Tacquard et al., 00]). L’intérêt sera, par la fabrique k pièces) et en particulier les permutations py-
suite, une traduction directe des résultats du calcul ramidales (des 1-cycle particuliers).
d’ordonnancement en consignes de conduite [Martineau
et al., 99]. Par étapes successives, nous allons déterminer les diffé-
rentes contraintes imposées par le système ce qui nous
Après avoir présenté le problème, nous illustrerons notre conduit à une notation de base. Cette notation sera com-
approche sur un atelier particulier en montrant comment, plétée par les contraintes liées à l’exécution des tâches
par étapes successives, nous transformons un problème (temps de préparation des machines, les contraintes de
simple, bien connu, mais aux hypothèses simplificatrices précédence, …). Par rapport aux hypothèses implicites
fortes, en un problème plus complexe mais plus réaliste. rappelées dans le paragraphe précédent, deux sont ici
On se référera systématiquement à la notation en trois relaxées. On se place donc dans le cas où :
champs α|β|γ de [Blazewicz and al., 94]. Notre approche les temps de transport des pièces ne sont pas négligea-
permet d’identifier des contraintes spécifiques aux ate- bles
liers de productions. La seconde partie est dédiée à la et les stocks intermédiaires ne sont pas de taille infinie
résolution du problème identifié. Nous présenterons la mais nulle.
complexité de quelques problèmes adjacents qui nous
permettront d’établir la complexité de notre problème. 2.1.1 Prise en compte d’un moyen de transport
Nous proposerons par la suite un recuit simulé bien Dans cette sous-section, nous allons déterminer les
adapté pour la résolution de ce problème. contraintes induites par la prise en compte d’un moyen
de transport. Les temps de transport entre les machines
2. IDENTIFICATION DU PROBLEME peuvent être déterminés : le temps de transport entre les
D’ORDONNANCEMENT machines Mj et Mj+1 sera noté tj. M0 et M4 correspondent
respectivement à l'Entrée et à la Sortie du système. tj
Nous proposons de détailler toutes les contraintes peut être considéré indépendant de la charge du chariot.
présentes dans les systèmes de production [Soukhal et Pour simplifier nous supposons que le temps de transport
al., 00b]. Pour illustrer notre démarche, nous entre Mj et Mj+1 est identique et constant dans les deux
développons un exemple simple. sens (cette hypothèse ne change pas la complexité du
problème).
2.1. Cellule de production avec un seul moyen de
transport On modélise un chariot comme une machine à part en-
tière, les tâches sont de durées égales aux temps de
MacCarthy et Liu présentent une nouvelle classification transport des pièces de la machine Mj à Mj+1.
des ateliers flexible de production. Ils identifient quatre Les travaux ont la même gamme opératoire (M0, C, M1,
types d’ateliers. Pour illustrer notre approche, nous étu- C, M2, C, M3, C et M4) où C représente le chariot (fig2).
dions un atelier de base de type FMC (Flexible Manu-
facturing Cell) (fig1). La cellule de production se com-

la gamme des pièces est M1 M2 M3

M2

M1 M3
Chariot

Sens de déplacement
Entrée Sortie
fig 1 : cellule de production à 3 machines et un chariot

- 526 -
 MOSIM’01 – du 25 au 27 avril 2001 - Troyes (France)

T1 T2
T1 M1

M1
M2
M2
M3
M3

C C
t0 t1 t1+t0 t0 t1 t2 t2+t1 t1 t2 t3

Fig2 : diagramme de Gantt illustrant le

cheminement des opérations d’un travail Fig3 : diagramme de Gantt illustrant les temps de

si u = v alors Ssd = 0, où u (respectivement v) est

Ce cheminement est caractéristique d'un flow-shop de l’indice de la machine où se trouve (il doit se rendre) le
recirculation [Billaut, 99]. Il ne semble pas nécessaire de chariot.
prendre en compte des machines virtuelles d'Entrée et de
Sortie dans la modélisation : aucune contrainte ne porte [Link] en compte de l’absence de stocks
sur elles et leurs temps de traitement sont nuls. C'est La conséquence immédiate de l’absence de stock est
donc un problème à 4 machines, 3 machines réelles et qu’une machine n’est pas disponible dès la terminaison
une machine particulière représentant le chariot. d’une opération. Dans la notation on utilise le terme
Dans la notation, on utilisera le terme « recrc » pour “block” : la contrainte block porte sur toutes les machi-
indiquer cette contrainte de recirculation. nes (fig4). C’est le cas lorsqu’une machine (respective-
ment un chariot) a terminé sa tâche et attend la disponi-
Avant d’effectuer l’opération de transport, le chariot doit bilité du chariot (respectivement machine) pour se libé-
se positionner au pied de la machine adéquate. Toute rer.
opération sur la machine « chariot » a donc un temps de
préparation ; sa valeur vaut le temps nécessaire au cha- Dans la notation, afin de modéliser l’échange de pièce
riot pour revenir devant cette machine. Ce temps dépend entre le chariot et la machine quand chacune des deux
de la séquence car la position du chariot est déterminée ressources est en possession d’une pièce, nous proposons
par la dernière opération effectuée : on le note Ssd. d’utiliser le terme swap. Le terme swap indique que la
Le diagramme de Gantt (fig4) montre la séquence des configuration présentée dans la figure 5 est autorisée. Ce
opérations dans l’atelier : le chariot dépose une pièce T1 qui peut être expliqué par le fait qu’on dispose dans
sur la machine M1 puis il la transporte jusqu’à la machine l’atelier, au pied de chaque machine, une zone d’échange
M2 ; le chariot quitte la machine M2 pour se placer à temporaire(fig5). Sinon, nous proposons d’utiliser le
l’entrée du système pour déposer la pièce T2 sur M1. Le terme no-swap : permet d’indiquer qu’il faut prendre en
temps du retour est égale à t1+t0 (voir fig3 en gras). considération le risque d’existence d’interblocage dans la
cellule lors du calcul de l’ordonnancement. Pour lever
La formule générale pour calculer Ssd est la suivante : cette contrainte, le chef de production dispose d’un
v −1 moyen technique lui permettant de vérifier que la ma-
si v > u alors Ssd = ∑t
uj−=1u
j chine suivante dans la gamme a été libérée avant de lui
transférer une nouvelle pièce (par exemple, l’attribution
si u > v alors Ssd = ∑t
j=v
j de priorités par le logiciel de supervision) .

T1 T2 T1 T2
blocking blocking
M1 M1

M2 M2

M3 M3
blocking
C C

Fig4 : diagramme de Gantt illustrant blocage des Fig 5 : le swap entre une machine et un transporteur
machines. chargés tout les deux d’une pièce

- 527 -
 MOSIM’01 – du 25 au 27 avril 2001 - Troyes (France)

2.1.3. Bilan : sont des cas particuliers de notre exemple. Celui-ci est
Nous avons identifié le problème et les contraintes : il donc NP-difficile (dans [Soukhal et al., 00b], le lecteur
s'agit d'un flow-shop de recirculation à m+1 machines. Il intéressé trouvera la démonstration détaillée).
est noté :
F4/ recrc, block, Ssd, swap /F(x) [Link]émentation du Recuit Simulé
Où F(x) est la fonction objectif à optimiser.
Afin de résoudre le problème dans le cas d’un seul cha-
riot dans l’atelier, nous avons implémenté un Recuit
[Link] de la cellule : Simulé (RS) selon le plan simple [Soukhal et al., 99].
Cette méthode de résolution est facile à mettre en oeu-
vre, nécessite le réglage de peux de paramètres et donne
a) Dans le cas de plusieurs machines m dans l’ateliers
une solution rapidement. Le lecteur intéressé peut se
et sous les mêmes hypothèses, nous retrouvons les
reporter à [Soukhal et al., 99] pour une étude compara-
mêmes contraintes. En effet, ces contraintes ne dé-
tive de plusieurs métaheuristiques.
pendent pas du nombre de machines dans l’atelier,
La valeur initial t0 est calculée par la formule sui-
d’où la notation :
∆C
Fm+1/ recrc, block, Ssd, swap /F(x) vante: t 0 =
ln( χ 0−1 )
b) Nous considérons le cas où l’opération de transport
peut être effectuée par un chariot d’un ensemble Où ∆C est une moyenne des variations positives de la
(fig.6). Nous parlerons alors d’un pool de machines
chariots. C’est un problème où une tâche peut être fonction de coûts. Le calcul de ∆C se fait à partir des
exécutée par une des machines constituant l’étage voisins qui n’améliorent pas le Cmax.
avec contrainte de recirculation. Comme dans le cas Nous avons fixé χo à 0.7, ce qui correspond à 70%
d’un seul chariot dans l’atelier, nous retrouverons d’acceptation d’un mouvement augmentant la fonction
les mêmes contraintes, à savoir : blocking, temps de de coût.
préparation de la machine (chariot) dépendent de la La valeur final tf correspond au critère d’arrêt.
séquence Ssd (voir les résultats précédents) et le L’algorithme s’arrête quand tf<0.001. D’autre part, si
après un certain nombre d’itérations sans amélioration du

M2
M1 M3

Chariot1

Entrée Sortie

Fig6 :Cellule de production à plusieurs chariots.

swap, d’où la notation suivante : Cmax l’algorithme s’arrête. Ce nombre à été fixé arbi-
FH(PMi)i=1m+1 / recrc, block, Ssd, swap/F trairement à 1000.
En ce qui concerne le nombre de transitions acceptées à
Cette identification ne prend pas en compte une température t, il a été fixé à 1000.
l’encombrement des chariots dans l’ateliers ni la zone Selon [Kirck ] la loi de décroissance de la température
d’exclusion mutuelle au pied de machines ; ainsi, est une constante en fonction d’un paramètre alpha. Nous
plusieurs chariots « prêts à charger ou décharger » avons fixé alpha à 0.95. Expérimentalement celui-ci
peuvent être, en même temps, devant une machine offre le meilleur rapport qualité/temps.
particulière.
[Link] de voisinage et graphe disjonctif
[Link]
Le choix de la fonction de voisinage est très important.
Dans cette partie, nous nous attachons à résoudre le Nous considérons l’approche de Nowicki et Smutnicki
problème modifié, noté F4|block, Ssd, recrc, swap, pour la résolution du problème FH(PMi)i=1LCmax
stock=0| Cmax. On choisit le critère Cmax parce que basée sur les graphes disjonctifs [Nowicki et al., 98].
c’est le plus courant dans les systèmes de production. En partant d’une configuration quelconque, l’ensemble
Il faut tout d’abord déterminer la complexité de ce pro- de voisinage est défini par l’insertion d’une opération sur
blème : On sait que les problèmes F3|SSD|Cmax et la même machine ou une autre de l’ensemble des machi-
F3|block|Cmax sont NP-difficiles [Hall et al., 93]. Ors ce nes appartenant au même étage. Afin d’accélérer en

- 528 -
 MOSIM’01 – du 25 au 27 avril 2001 - Troyes (France)

probabilité la convergence de la solution vers l’optimum,

nous considérons uniquement les opérations qui forment La résolution passe donc par l’utilisation de méthodes
un « bloc » : ce sont les opérations critiques exécutées adaptées aux problèmes NP-difficile. Nous utilisons une
par la même machine dans un étage quelconque. métaheuristique parce que ces algorithmes permettent
d’obtenir une « bonne » solution en un temps raisonna-
D’autre part, Nowicki et Smutnicki interdisent certains ble [Soukhal et al., 99]. En particulier, dans cet article,
mouvements et montrent que le graphe obtenu est on utilise un Recuit Simulé (RS), rapide à implémenter
connexe. Les règles d’interdiction de mouvement sont : et permettant donc d’illustrer efficacement l’intérêt de
on ne prend pas en compte les opérations qui notre démarche. On ne cherche pas la meilleure solution
n’appartiennent pas au bloc ; au problème mais une solution suffisamment bonne pour
si un bloc est définit par une seule opération alors ce bloc montrer l’intérêt de préciser autant le modèle.
n’est pas pris en considération ; On propose deux exemples montrant l’intérêt de préciser
les mouvements qui consistent à insérer une opération les contraintes du problème.
appartenant à un bloc à l’intérieur du même bloc sont 1. O2Cmax. Dans le cas d’un open shop, les tâ-
interdits ; ches doivent passer les machines dans un ordre
la première (respectivement la dernière) opération d’un quelconque. Soit un problème à deux machines
bloc n’est jamais insérée à gauche (respectivement et deux travaux T1 (resp. T2) avec 2 la durée
droite) du bloc ; opératoire sur M1 (resp. 1) et 3 sur M2 (resp. 2).
soit B1 (respectivement Bf) le premier (respectivement le Pour produire le temps total d’exécution, un
dernier) bloc du chemin critique. La première (respecti- bon algorithme donne : fig7(aI). La mise en œu-
vement la dernière) opération de B1 (respectivement Bf) vre de cette séquence dans un atelier réel
ne doit pas être insérée à droite (respectivement gauche) conduit à un interblocage s’il n’y a pas de stock
à l’intérieur de ce bloc. entre M1 et M2. Notre démarche identifie un
Dans le cas particulier où il y a recirculation, il peut y O2no-swap, blockCmax et conduit à une ré-
avoir plusieurs blocs critiques sur une machine quel- solution fig7(a1I). La mise en œuvre de cette sé-
conque. En effet, le fait de considérer la contrainte de quence est possible et permet d’obtenir un
recirculation entraîne qu’entre deux tâches critiques, Cmax de 6.
peuvent se trouver des tâches non critiques (en attente de 2. Soit un F2 sans stock intermédiaire mais avec
M1

M2
Cmax=5 M1

M2
M1
Cmax=6
M2 Interblo-
Cmax→∞
(aI ) (aII )
Fig7 : (a) interblocage : Open shop O2
la disponibilité de la prochaine ressource). Le graphe un moyen de transport permettant de transférer
ainsi obtenu reste connexe. De plus, on améliore la solu- une pièce de M1 sur M2 en temps constant. On
tion renvoyer par ce voisinage en avançant l’opération modélise classiquement ce problème par
permuttée le plus tôt possible et en rendant ainsi F2no-waitCmax. La séquence illustrée dans
l’ordonnancement actif. fig8(bI) est une solution à ce problème. On peut
De plus, comme nous avons une contrainte de recircula- appliquer la séquence obtenue dans l’atelier en
tion, on doit respecter la contrainte de précédence entre reportant les dates de début des opérations sur
les opérations du même travail. la machine M1 et en intégrant le transporteur.
En identifiant plus précisément le problème
[Link] F3stock=0, blockCmax on peut obtenir la
solution fig8(bII). Celle-ci met à profit le trans-
Il convient de montrer l’intérêt de notre démarche qui porteur comme zone de stockage intermédiaire
consiste initialement à ajouter des contraintes au pro- et permet de gagner une unité de temps dans
blème et donc à le compliquer en vue de sa résolution. l’exemple.
Cette attitude n’aura pas manqué de surprendre le lecteur Dans les FMS il est fréquent de trouver plus de trois
attentif. L’objectif est d’avoir une solution plus facile à machines et de nombreux transporteurs. Les cas de figu-
mettre en œuvre et plus réaliste. A titre indicatif, nous res que nous venons d’exhiber se rencontrent donc sou-
étudions deux exemples montrant l’apport de nos tra- vent.
vaux, puis, dans une seconde phase, nous détaillons les
résultats d’une campagne de tests.

- 529 -
 MOSIM’01 – du 25 au 27 avril 2001 - Troyes (France)
t1 t2=3 t3=7
M1

t1 t2=2 t3=6
M2
2 3 7 9 10 Cmax=13 M1
bI1) no-wait sans chariot C

M2
t1 t2=3 t3=7 2 3 8 10 Cmax=13
M1
bII) block, stock=0 avec chariot
C

M2
2 3 8 10 11 Cmax=14
bI2) no-wait avec chariot
Fig8 : flow shop à deux machines : blocage et no-wait avec ou sans chariot
Nous proposons de mener une campagne de tests mon- soit est bloquée en attente de la libération d’une autre
trant l’apport d’une modélisation sur la séquence réalisa- ressource. Ainsi la valeur de la durée totale de
ble dans l’atelier et en étudiant expérimentalement si une l’ordonnancement, notée Cmaxπ, est donnée par la date à
telle précision dans l’identification des contraintes, à un laquelle la dernière tâche quitte le système, lors de la
coût de calcul sans doute important, améliore sensible- mise en œuvre de la séquence donnée par G&G comme
ment la séquence produite lors de sa mise en œuvre en séquence de contrôle du système.
tant que séquence de contrôle. On ne compare pas les
ordonnancements obtenus mais ce qu’ils deviennent lors 4.2. Résolution sur le modèle précis
de leur mise en œuvre sur le système de production.
D’autre part, en utilisant notre approche, on identifie le
Pour cela, on examine le cas simple à deux machines. En problème F3/block, no-stock/Cmax. Le problème est
supposant l’absence de transporteurs, le problème se NP-difficile, on applique un recuit simulé, tel qu’il a été
note F2/blocking/Cmax, sa résolution est équivalente à présenté précédemment, avec les paramètres suivants :
celle du F2/no-wait/Cmax. Sur ce problème, on va donc • Une solution initiale est générée aléatoirement ;
comparer une méthode classique de résolution sur le • La température initiale T à été fixée à 1000 ;
problème tel qu’il est initialement identifié à une mé- • Selon le plan simple, le coefficient α a été fixé
thode de résolution sur le problème modifié. On s’appuie à α=0.95 ;
sur le F2 de permutation car il met à égalité les deux • Le nombre d’itérations nécessaires avant
méthodes puisqu’il ne peut pas y avoir d’interblocage. l’abaissement de la température T a été fixé à
100 ;
4.1 Résolution classique
• Pour le test d’arrêt, deux conditions ont été im-
posées : le nombre d’itérations sans améliora-
Le problème flow shop à deux machines sans attente (la
tion du résultat (fixé à 1000) et la valeur mini-
deuxième opération d’une tâche commence exactement à
male de la température T = 0.01.
la date de fin d’exécution de la première) est polynomial,
On obtient une autre permutation πRS avec CmaxRS.
une solution est l’« algorithme G&G » [Gilmore et al.,
64]. Nous avons implémenté celui-ci pour résoudre le
4.3 Résultats
problème F2/blocking/Cmax sans transporteur. On note
π la permutation optimale obtenue par G&G.
Le nombre de machines est fixé à 2 pour n tâches n∈{50,
Pour la mise en œuvre de la permutation π en tant que
100}. Les durées opératoires pij sont générées dans
séquence de contrôle, il faut déterminer la séquence des
l’intervalle [1, 10] selon la loi uniforme. Les durées de
tâches sur le chariot (sans modifier la permutation des
transport tj avec j=1,..,3 sont générées aléatoirement dans
tâches π). Cela se fait suivant les dates de début [1, 3]. tj correspond à la durée de transport entre les ma-
d’exécution des opérations sur les machines données par chines Mj-1 et Mj.
G&G, c’est-à-dire l’opération la plus prioritaire est celle Nous avons généré 50 jeux de données pour (n, m). Pour
qui a la plus petite date de début d’exécution sur les deux chaque jeu, nous avons appliqué l’algorithme G&G et 20
machines confondues tout en respectant les contraintes fois le RS. Les résultats sont présentés dans le tableau 1.
de non stocks et swap. D’autre part, en considérant la Les valeurs aléatoires suivent une loi uniforme, certains
nouvelle ressource qu’est le chariot, le problème ne peut jeux peuvent donc être particuliers. Il est intéressant
pas être considéré comme sans attente (no-wait). En d’examiner les résultats pour chaque jeu et y détecter
effet, à un instant t, une machine, soit exécute une pièce, éventuellement des cas particuliers. Le tableau 1 donne

- 530 -
 MOSIM’01 – du 25 au 27 avril 2001 - Troyes (France)

les résultats des 20 premiers jeux sur les 50 comparés. avons un coût de calcul en moyenne sur tous les tests
Les valeurs obtenues pour une application du RS peu- confondus de 1804 secondes pour une amélioration en
vent être améliorées par l’application de plusieurs RS moyenne de 17,01%. La première solution obtenue par le
(initialisés à des solutions initiales différentes) pour un RS est nettement améliorée par l’exécution de 20 RS. On
coup, en temps de calcul, non négligeable : passe d’une amélioration de 10,51% à 17,01%.
• 1ère colonne : numéro du jeu de données ;
• 2ème colonne : la valeur du Cmax obtenue à par- N° du Cmaxπ ∆π RS(1) ∆πRS Tps de calcul de 20
tir de la permutation π de G&G ; jeu (%) (%) exécutions (sec.)
• 3ème colonne : amélioration relative par 1 755 7,549 9,898 4296
l’application d’un RS sur un jeu de test 1; 2 757 10,189 10,189 4654
• 4ème colonne : amélioration relative par 3 755 2,721 7,244 4334
l’application de 20 RS sur un jeu de test ; 4 764 7,152 12,187 4491
• 5ème colonne : temps cumulé sur les 20 applica- 5 764 2,826 4,945 4391
tions du RS. 6 762 2,281 10,434 4571
7 752 9,461 10,914 4473
N° du Cmaxπ ∆π RS(1) ∆πRS Tps de calcul de 20 8 752 5,915 10,425 4428
jeu (%) (%) exécutions (sec.) 9 751 3,159 8,526 4309
1 362 11,325 16,850 1904 10 742 12,594 12,594 4637
2 386 11,139 19,170 1846 11 775 5,874 9,929 4305
3 370 10,810 14,594 1507 12 771 5,184 9,361 4795
4 378 11,111 15,608 1751 13 747 9,370 12,330 4915
5 387 12,661 17,054 1846 14 769 4,911 9,544 4318
6 376 17,287 17,287 1531 15 783 8,298 8,298 4877
7 363 14,876 15,977 1971 16 741 4,809 8,970 4396
8 372 12,634 16,935 1804 17 762 6,128 11,894 4652
9 394 8,1218 17,258 1808 18 773 5,457 13,177 4396
10 383 18,015 19,321 1742 19 773 8,567 13,011 4569
11 371 8,8948 18,059 1770 20 747 7,020 11,659 4262
12 360 13,888 16,388 1786 Table 3 : résultats pour 20 jeux de données avec 100
13 383 15,143 18,015 1969 tâches et deux machines.
14 389 11,825 18,508 1952 Cmaxπ ∆π RS(1) ∆πRS Tps de calcul
15 372 11,827 16,397 1596 (%) (%) moyen
16 365 10,684 15,068 1896 758,348 8,186 10,546 4503
17 390 15,128 15,128 1877 Table 4 : Moyenne sur les 50 jeux générés avec 100
18 368 17,663 17,663 1967 tâches.
19 389 13,624 16,709 1872
20 407 6,8796 15,479 1510 Sur l’ensemble des tests effectués, pour le cas de 100
Table 1 : résultats pour 20 jeux de données avec 50 tâ- tâches et 10 machines (table 4), on constate une amélio-
ches et deux machines. ration par la première solution générée par le RS de
8,19% en moyenne. D’autre part une, après 20 itérations,
Cmaxπ ∆π RS(1) ∆πRS Tps de calcul une différence moyenne de 10,55% est à signaler entre la
(%) (%) moyen. meilleure solution et celle basée sur l’algorithme de
367,849 10,512 17,013 1804 G&G. Bien évidemment pour un coût de calcul de 4503
Table 2 : Moyenne sur les 50 jeux générés avec 50 tâ- secondes.
ches. On retrouve donc des résultats similaires à ceux obtenus
pour les tests précédents. Le RS apparaît relativement
On analyse ensuite sur des moyennes (sur les 50 jeux de plus performant dans ce second cas lors de sa première
test) l’apport du modèle détaillé (table 2). Dans tous les exécution. Cette observation doit être relativisée car elle
cas, les résultats sont meilleurs lors d’une mise en œuvre dépend de la valeur absolue du Cmax.
de la solution du RS plutôt que celle d’un modèle simpli-
fié. Bien évidemment, le coup de calcul ne sera pas né-
gligeable lorsqu’on s’intéressera à chercher la meilleure [Link] ET PERSPECTIVES
solution en laissant le recuit simulé tourné plus long-
temps. Avec les paramètres définis précédemment nous La Recherche en ordonnancement a beaucoup approfon-
di ses résultats ces dernières années. Les contraintes
prises en compte dans les travaux récents sont de plus en
1
On note ∆x1x2, l’amélioration relative (en pourcentage) plus complexes. Nous montrons dans cet article qu’il
de x2 par rapport à x1. ∆x1x2=100*(Cmaxx1- convient d’utiliser ces avancées pour préciser les modè-
Cmaxx2)/Cmaxx2. les simplifiés qui étaient utilisés.

- 531 -
 MOSIM’01 – du 25 au 27 avril 2001 - Troyes (France)

Un modèle plus réaliste amène à l’obtention d’un résultat manufacturing systems”, Edition Springer-Verlag,
plus fiable que l’on peut utiliser directement en consigne 1994.
de pilotage du système de production. [Brauner, 99] N. Brauner, “Ordonnancement dans des
L’ordonnancement prévisionnel peut alors servir de cellules robotisées, Analyse de la conjecture des
consigne au contrôle réactif. un-cycles”, Thèse du Laboratoire Leibniz-IMAG,
Nous proposons une approche originale composée, pour Grenoble 1er, Décembre 1999.
la première partie d'une identification précise du pro- [Collectif, 98] Equipe Ordonnancement – Conduite «Un
blème d'ordonnancement avec un minimum Outil de Comparaison et d'Elaboration d'Algorith-
d’hypothèses simplificatrices. Classiquement, sous quel- mes (OCEA) : synthèse. » Rapport interne LI /
ques hypothèses fortes, les chercheurs identifient des E3I / Université François Rabelais n°209, 22 pages,
problèmes très spécifiques. Dans le but de montrer notre Novembre 1998.
approche, nous l’avons développé sur quelques cellules [Kirkpatrick et al., 83] S. Kirkpatrick, C.D. Gelatt, M.P.
de production réel. Nous montrons que la notation de Vecchi “Optimisation by simulated annealing”,
base doit contenir les termes suivants : Science (220), pp: 671-680, Mai 1983.
• si la capacité de stockage est limitée alors nous [Martineau et al., 99] P. Martineau, C. Tacquard et A.
proposons de rajouter dans le champ β les ter- Rouillon, “Génération automatique de la conduite
mes : “block” and “swap”. d’un système flexible de production”, APII – Jour-
• de même, l’utilisation d’un moyen de transport nal Européen des Systèmes Automatisés, 33(7)
ou plusieurs dans la cellule implique des temps pp:815-854, 1999
de préparation de la machine (dépendant de la [Nowicki et al.,98] E. Nowicki et C. Smutnicki. “The
séquence ou pas) qui représentent le mouve- flow shop with parallel machines : A tabu search
ment du transporteur à vide : “Ssd” (Snsd) doit approach”, Eur. J. Op. Res. (106) : pp 226-
apparaître dans le champ β. 253,1998.
Nous avons montré, d’abord sur des exemples d’école [Soukhal et al., 99] A. Soukhal, P. Martineau et J.-C.
puis par une campagne de tests, qu’il est intéressant de Billaut, “Présentation générale de trois algorithmes
préciser les modèles des ateliers pour calculer un ordon- de voisinage appliqués au Flowshop Hybride”,
nancement. La séquence obtenue peut alors être utilisée Rapport Interne n°221 de LI/E3i/ Université Fran-
directement dans l’atelier comme consigne de pilotage. çois Rabelais Tours, 60 pages, Septembre 1999.
Ce modèle plus précis est, il est vrai, plus complexe. Il [Hall et al., 93] N.G. Hall, H. Kamoun et C.
est donc toujours nécessaire de travailler à améliorer les Sriskandarajah.“ Scheduling in robotic cells. Large
performances des algorithmes de résolution. Les méta- cells”, Working Paper 93-07, University of To-
heuristiques sont bien adaptées à l’obtention de ronto, 1993.
« bonnes » solutions dans ce contexte très contraint. [Soukhal et al., 00b] A. Soukhal et P. Martineau
“Identification des problèmes d’ordonnancement
RÉFÉRENCES dans quelques ateliers flexible de production”,
Rapport Interne n°221 de LI/E3i/ Université Fran-
[Asfahl, 85] C.R. Asfahl, “Robots and manufacturing çois Rabelais Tours, 60 pages, Septembre 1999.
automation”, John Wiley & Sons, New York, NY, [Soukhal et al., 00a] A. Soukhal et P. Martineau
1985. “Résolution du flow shop hybride par le recuit si-
[Billaut, 99] J-C. Billaut, « Recherche opérationnelle et mulé”, ROADEF 2000, Nantes Janvier 2000.
aide à la décision pour les problèmes [Tacquard et al., 00] C. Tacquard et P. Martineau
d’ordonnancement », Habilitation à diriger les re- “Automatic Notation of the Physical Structure of a
cherches, Université François Rabelais de Tours, Flexible Manufacturing System”, submitted to the
237 pages, 18 janvier 1999. Int. Journal in Production and Economics, 2000
[Blazewicz and al., 94] J. Blazewicz, K.H. Ecker, G.
Schmidt, J. Weglarz, “Scheduling in computer and

- 532 -