Thèse
Thèse
Thèse
Thèse Doctorale
Par :
Karla Quintero
Pour obtenir
LE GRADE DE DOCTEUR
Jury
M. Eric NIEL Directeur Professeur (INSA Lyon)
M. José AGUILAR Directeur Professeur (ULA Mérida, Venezuela)
M. Philippe JEANNIN Tuteur Industriel Ing. Développement (Thales Group - TCS)
M. Sébastien LAHAYE Rapporteur Professeur (Université d'Angers)
M. Hassane ALLA Rapporteur Professeur (Université de Grenoble)
Mme. Audine SUBIAS Examinateur MCF HDR (INSA Toulouse)
M. Addison RIOS Examinateur Professeur (ULA Mérida, Venezuela)
M. Juan CARDILLO Examinateur Professeur (ULA Mérida, Venezuela)
20 juillet 2015
Résumé
Cette thèse porte sur l'optimisation d'opérations dans un terminal maritime pétrolier en vue
d'assister les opérateurs de supervision. L'objectif est de fournir des solutions candidates pour la
d'un réseau à ressources limitées et conictuelles. La prise de décision doit être réalisée en fonc-
tion des disponibilités des dispositifs, de la capacité opérative du réseau, d'aspects nanciers
L'optimisation est abordée par des approches tropicales du fait que ces techniques appréhendent
ici commencent par des modèles d'optimisation algébriques mono-objectif et se complexient, lors
objectif hybrides par approches d'intelligence articielle et algébriques. Dans un premier temps,
un modèle d'optimisation mono-objectif est proposé en algèbre (max,+) pour minimiser les
pénalités, intégrant des phénomènes de nature diérente dans une contrainte générique unique.
Ce modèle est non linéaire, considère des alignements dénis au préalable, et sa validation est
Dans un deuxième temps, la linéarisation est résolue par une priorisation des opérations en
conit. Dans ce contexte, deux critères de linéarisation sont considérés : le premier concernant
les pénalités potentielles pour les clients, et le deuxième concernant la criticité des opérations.
Le modèle (max,+) non linéaire minimisant les pénalités est étendu pour la prise en compte
et des systèmes (max,+) linéaires est ensuite discutée. Enn, dans un cadre plus formel, un
nouveau produit synchrone exploitant les phénomènes de parallélisme au plus tôt est déni pour
Les propositions sont validées par des données industrielles recueillies auprès de l'entreprise pé-
linéaires exploitant les avantages de recherche distribuée des approches de l'intelligence arti-
cielle avec les modèles concis issus de l'algèbre (max,+), et de la dénition d'un nouveau produit
synchrone d'automates tropicaux par une exploitation des phénomènes de parallélisme pour un
Abstract
This thesis addresses operations optimization in an oil seaport with the fundamental purpose
of assisting supervision operators. The objective is to provide candidate solutions for pipeline
alignment (path) selection and for scheduling of oil transfer operations, as well as maintenance
operations, considering that the system has limited and conicting resources. Informed decision
making should consider operations scheduling and alignment selection based on : devices avai-
lability, operative capacity of the network, nancial aspects (penalties) due to late service, and
The optimization problem is addressed by tropical approaches given their potential for yielding
concise and intuitive representations when modeling synchronization phenomena. The proposals
become more complex, as new aspects are included, leading to the formulation of hybrid multi-
system theory.
Firstly, a mono-objective optimization model is proposed in (max,+) algebra for penalty mi-
nimization. This model integrates dierent nature phenomena into one single constraint. It is
nonlinear, considers predened alignments for transfer operations and is validated through an op-
timization solver (LINGO). Secondly, linearization of such model is introduced for prioritization
of conicting operations. Within this context, 2 criteria are addressed : potential penalties for
clients and, on the other hand, operations criticality. The nonlinear (max,+) model minimizing
penalties is extended in order to consider alignment search and delay minimization for mainte-
nance operations. In order to address the multi-objective nature of the problem, an approach
Finally, in a more formal framework, a new synchronous product for tropical automata exploiting
parallelism phenomena at the earliest is dened in order to minimize the makespan. The proposed
models and methods herein have been validated by industrial data gathered from the oil company
The main contributions of this research are, rstly, the application of tropical approaches to
this specic optimization problem, yielding concise and potentially linear models. Secondly, the
proposal of a hybrid approach based on genetic algorithms and (max,+)-linear systems, which
exploits the advantages of the distributed search of articial intelligence approaches and the
conciseness of the models stemming from (max,+) algebra. The nal contribution focuses on the
Je tiens à remercier Dieu tout d'abord pour les parents et les opportunités que j'ai eu. Merci
à mes parents pour les valeurs apprises, le soutien et l'exemple de croissance qui m'a inspiré et
continuera à m'inspirer toute la vie. À mon père, merci de m'avoir toujours poussé à obtenir
des meilleurs résultats et à repousser mes limites. À ma mère, merci de ton dévouement et
Aux 3 directeurs de cette thèse: M. Eric NIEL (INSA de Lyon), M. José AGUILAR (ULA) et M.
Philippe JEANNIN (Thales Group), un grand merci pour votre orientation et pour la conance
que vous avez déposée sur moi, cela m'a permis de me connaître vraiment en tant que chercheuse.
Grâce à l'autonomie que vous m'avez permis de développer, aujourd'hui je suis sûre que ma vraie
À mon époux Carlos, qui m'a toujours soutenu lorsque j'ai décidé d'entreprendre mes travaux
À l'Université des Andes (ULA: Universidad de Los Andes ), et à tous ses professeurs et collabo-
rateurs qui m'ont formé en tant qu'ingénieur; ils m'ont donné des bases professionnelles solides
À l'équipe de Thales pour m'avoir accueilli avec les bras ouverts, pour tous ces moments convi-
viaux que l'on a partagé ensemble et qui m'ont permis d'avoir une transition très agréable au
milieu industriel. Spécialement à Sylvie MARQUER, merci de ton soutien et merci d'être comme
tu es.
Finalement, à toute ma famille et amis qui m'ont toujours soutenu, spécialement à Geraima
MEDINA, toujours très impliquée dans mes projets et réussites malgré la distance.
Résumé i
Abstract iii
Remerciements v
1 Introduction 1
1.1 Contexte de la Recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2.2.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
d'Opérations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
d'Alignements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
vi
gorithmes Génétiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.5 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Automates (n = 3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Glossaire 118
Bibliographie 121
1.2 Éléments identiables dans le problème du plus court chemin à travers d'une
1.4 Éléments identiables dans le problème des chemins les plus ables à travers d'une
1.5 Dynamique d'un système à événements discrets par rapport à sa valeur propre. . 15
2.1 Alignements indépendants (a) et en conit (b) pour les opérations de transfert . 27
2.5 Ordonnancement optimal pour le système (max,+) linéaire basé sur le TPP . . . 41
3.2 Workow général pour la formulation du problème multi-objectif par une approche
d'algorithmes génétiques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
turés. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.6 Mutation des gènes de contrôle et propagation vers les gènes de paramétrage -
exemple. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.7 Opération de croisement avec des parents ayant des structures diérentes appli-
3.8 Flux d'exécution de l'algorithme SPEA2 avec des opérations en algèbre (max, +). 78
viii
3.11 Solutions représentées par les individus non dominés dans la Fig. 3.10. . . . . . . 81
états. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
et b). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.4 Exemple de modélisation des conits par automates tropicaux mono-état : les
du même état. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
rence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.8 Représentation du produit synchrone G1 ||G2 ||G3 pour l'exemple de la Fig. 4.7. . 95
4.9 Ordonnancements qualitativement optimaux pour des systèmes avec une paire
4.12 Ordonnancement qualitatif optimal pour n=4 et (G1 , G2 ) comme la seule paire
en synchronisation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.13 Exemple pour 4 automates locaux (représentation simpliée à un seul état pour
3.2 Données d'entrée pour les opérations de transfert dans l'instance de la Fig. 3.9. . 79
Pays des gens les plus joyeux du monde malgré les adversités.
xi
Introduction
Préambule
Ce premier chapitre introduit le contexte des travaux et la problématique soulevée au regard
maintenance, les requêtes clients et les pénalités potentielles pour retard de service. Les verrous
scientiques qui émergent de ce projet de recherche sont exposés ainsi que les approches
proposées par la communauté ad hoc pour pallier ces verrous. Un état de l'art argumente la
motivation d'exploiter des approches tropicales, telles que l'algèbre (max,+) et les automates
tropicaux.
Sommaire
1.1 Contexte de la Recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Cette thèse doctorale est développée dans le cadre du programme de coopération post-gradué
projet implique la collaboration entre les institutions académiques : Universidad de Los Andes
à Mérida, Venezuela et INSA Lyon en France, et les partenaires industriels PDVSA et Thales
Group. PDVSA (en espagnol : Petróleos de Venezuela Sociedad Anónima ) participe en tant
que société vénézuélienne d'exploitation pétrolière et Thales Group en tant que fournisseur de
Le nancement de la thèse relève d'une convention CIFRE avec le soutien nancier de l'Asso-
de réservoirs de stockage reliés à un ensemble de bras de chargement positionnés sur des quais
au travers d'un réseau de pipelines. Les caractéristiques générales du système ont été recueillies
dans les travaux de [1] et ont été fournies par l'entreprise pétrolière vénézuélienne PDVSA. Les
bras de chargement permettent de fournir le pétrole aux tankers (i.e. des navires) qui arrivent au
terminal. Dans ce système, les tankers sont assimilés à des clients. Chaque client, demande un
batch de pétrole, i.e. une quantité de barils de spécications données. Ce batch doit être délivré
seul bras de chargement est considéré par quai pour les modèles réalisés. Cette hypothèse peut
être facilement levée si, pour un système spécique, plusieurs bras de chargement sont placés sur
un seul quai mais le temps de traitement de la requête de transfert peut être estimé, ce qui est
La Fig. 1.1 illustre un exemple simple de l'abstraction à retenir par rapport aux éléments du
terrain applicatif considéré qui sera appelé dorénavant système. Dans la Fig. 1.1b), les vannes
sont identiées par des arcs labellisés et les segments de pipeline, par des n÷uds. Les vannes
Chaque opération de transfert ou requête (termes utilisés de manière indistincte) est réalisée en
choisissant un alignement de pipelines dans le réseau reliant les éléments source (réservoirs) aux
éléments puits (bras de chargement) à considérer. Un alignement est déni comme un chemin
pétrole est supposé s'écouler par gravité, comme c'est le cas dans certains terminaux maritimes
Figure 1.1: Schématisation d'un terminal maritime pétrolier (a) et son modèle sous forme de
graphe non orienté (b).
au Venezuela. Un alignement est alors habilité lorsque toutes les vannes rattachées au parcours
considéré commutent vers un état `ouvert' et toutes les vannes adjacentes commutent vers un
état `fermé', pour isoler l'alignement du reste du réseau et ainsi éviter le mélange de batch
diérents.
ce qui pourrait être étudié pour d'autres contextes de fonctionnement. Ici, le contexte retenu
indique que le produit demandé par le client sera prélevé dans un réservoir unique et, an
d'interdire tout mélange de produit, deux alignements habilités simultanément seront toujours
disjoints.
Les investigations ici s'inscrivent dans la poursuite de travaux précédents [1], [2], [3] et [4]. Les
travaux réalisés [1], dénissent la capacité opérative du réseau comme le nombre maximum d'ali-
la capacité opérative en reliant le maximum des chemins disjoints entre l'ensemble de réservoirs
et l'ensemble de bras de chargement. Des chemins minimisant les interférences avec des chemins
déjà envisagés ont été recherchés pour répondre simultanément à d'autres opérations de transfert
[2]. Les travaux de [3] augmentent la diculté de l'approche en considérant des chemins à sens
de ux imposé par une pompe intermédiaire. Enn, l'approche maximisant la capacité opérative
proposée dans [1] est étendue par la minimisation des risques de défaillance des dispositifs de
Dans un contexte d'application proche au cas d'étude, les travaux de [5] présentent un position-
nement intéressant sur l'ordonnancement d'opérations dans le cadre d'une ranerie pétrolière
par des approches relevant de la Recherche Opérationnelle. Sont considérés, le transfert de pé-
trole brut des pipelines de ravitaillement aux réservoirs de stockage, le transfert de ces réservoirs
vers des réservoirs de chargement (pour des opérations de mélange de pétrole), et de ces derniers
Les références dans la littérature sont peu nombreuses pour l'assistance à la supervision des
terminaux maritimes. Néanmoins, la section 1.3 donne un état de l'art sur les travaux de modé-
Ici, il est considéré que des opérations de maintenance peuvent être eectuées sur certaines
vannes, et pour chacune de ces opérations, toutes les vannes adjacentes à la vanne en maintenance
devront être fermées pour permettre l'isolement nécessaire à l'intervention. Ces dernières vannes
Ainsi, le cas d'étude se rapporte à un réseau de pipelines piloté par des dispositifs de contrôle
de ux (i.e. des vannes) et où des opérations de maintenance peuvent être eectuées sur ces
dispositifs. D'ores et déjà, trois types de conits de partage de ressources sont à considérer : le
premier entre les requêtes clients (sélection d'un alignement, imposant un ux au travers des
ux), et le troisième entre les opérations de transfert et de maintenance. En outre, le service tardif
des clients entraîne des pénalités pour le terminal qui peuvent varier selon certaines priorités.
Hypothèse 1.1 . Les canalisations sont considérées comme toujours pleines de pétrole. Ce pétrole
stocké dans les canalisations est le produit résiduel des opérations de transfert précédentes.
Hypothèse 1.2. La quantité du produit résiduel stocké dans les canalisations est considérée comme
négligeable par rapport aux quantités transférées aux clients. Ainsi, elles n'altèrent pas les spé-
Hypothèse 1.3 . Les vannes de ux possèdent deux états possibles : ouverte ou fermée (i.e. on/o ).
En termes de notation, dans les sections qui suivent, les ressources représentent les moyens
physiques pour eectuer les opérations. Notamment, lorsque le contrôle de ux est réalisé par la
commutation des vannes, l'ensemble de vannes dans le réseau représente l'ensemble de ressources
à gérer. Lorsqu'une vanne est aectée à une opération de transfert, elle ne pourra pas être aectée
1. i.e. phénomène de surpression dans les canalisations dû à des commutations brusques des vannes.
à une autre opération si les états atteints après les commutations sont diérents ou si cette
La recherche est motivée par le besoin de fournir une assistance à la décision pour les opérateurs
chacune d'entre elles, dans un réseau automatisé de pipelines où les ressources sont contraintes,
et les retards dans les opérations impliquent des coûts nanciers importants (i.e.pénalités).
L'intérêt majeur de ce travail est donc de déterminer une allocation de ressources pour satis-
ces travaux réside sur l'exploitation des informations de supervision au travers des approches
algébriques tropicales. Telles approches, permettent d'obtenir des modèles non linéaires concis
et intuitifs et, dans certaines conditions, facilement linéarisables. En outre, une telle diversité
d'informations est à l'origine d'une prise de décision optimisée en accord aux objectifs globaux
de performance du système.
Dans de nombreuses applications, les opérateurs de supervision réalisent une décision basée
sur une expertise chèrement acquise et parfois trop focalisée sur la productivité. Ici, la prise
de décision se veut multivariée, elle implique des informations de disponibilité des dispositifs,
de l'ordre d'arrivée des clients, des planications de maintenance, des pénalités subies dans
L'intégration de l'ensemble de ces contraintes est hautement complexe pour un opérateur de-
vant réagir en temps réel. Il s'agit alors de proposer une démarche d'optimisation de la prise de
décision des opérateurs leur permettant d'inclure la valeur ajoutée de leur expertise. Cela est
réalisable en lui permettant de choisir, parmi plusieurs alternatives représentant des diérents
compromis parmi les objectifs, l'alternative la plus adéquate par rapport aux conditions d'exploi-
tation en temps réel. L'opérateur pourra ainsi prendre en compte toute information non prévue
survenant en temps réel, ainsi que tout aspect supplémentaire de subjectivité pour décider parmi
Dans ce cadre, les travaux académiques ont répondu au développement des approches formelles et
heuristiques, PDVSA fournit des données industrielles liées au fonctionnement de ses terminaux
industrielle.
Les propositions et résultats obtenus sont susamment génériques pour qu'ils soient applicables
Ainsi, l'objectif général est de proposer une démarche d'assistance permettant d'optimiser l'al-
location de ressources auprès des opérateurs de supervision dans un terminal maritime pétrolier
maintenance, et en cohérence avec une minimisation des pénalités nancières. Ces pénalités
seront encourues par l'exploitant du terminal dans les cas de retards dans le service des clients.
Analyser les opérations de transfert du terminal maritime et identier les besoins d'op-
Dénir des modèles d'intégration considérant les diérents besoins d'optimisation (tels
Développer des tests de validation des modèles d'optimisation, et aboutir à une formu-
sélection d'alignements.
Sur la base des données industrielles liées aux terminaux maritimes réels, valider les
propositions retenues.
Les principaux verrous identiés concernent l'intégration, au niveau de la modélisation, des in-
formations de chacun des axes de l'optimisation tels que la sélection d'alignements, l'ordonnance-
ment d'opérations de transfert et les aspects de disponibilité liés aux opérations de maintenance.
Les approches abordées par la communauté scientique pour pallier ces verrous et les approches
Cette section présente un panorama sur des approches classiques abordant des problèmes d'op-
d'opérations et que, pour les propos des investigations, les dates de début et de n des opérations
sont recherchées, les axes sur lesquels se centre l'état de l'art relèvent des systèmes à événements
discrets. Ainsi, les approches liées aux réseaux de Petri, automates conventionnels, automates
(max,+), théorie des jeux, algèbre (max,+), théorie des graphes et intelligence articielle, seront
abordées. En outre, des aspects d'intégration et/ou transposition entre les diérentes techniques
seront présentés du fait que, dans la recherche actuelle, elles peuvent être complémentaires.
Le problème abordé relève des systèmes à événements discrets (SED) du fait que, d'un point de
vue macro (système), les opérations dans le réseau s'exécutent à des instants de temps précis,
pour une durée déterminée. Dans un point de vue micro (éléments), chacune des opérations
résulte de la commutation des vannes entre deux états possibles : ouverte/fermée. Ainsi, les
dates de début d'opérations peuvent être considérées comme des événements suivis par des
événements de n d'opération après une certaine durée. Aussi, l'habilitation d'un alignement
pour une opération résulte de plusieurs événements de commutation des vannes impliquées.
Dans un cadre général, l'intérêt se focalise sur la recherche des dates d'engagement de ressources
classique d'allocation de ressources déjà abordée dans des secteurs aussi variés que le transport
[6], la production manufacturière [7], l'énergie [8], et l'hospitalier [9]. La particularité dans
ces travaux repose, d'une part sur une plate-forme de supervision où les opérateurs prennent
des décisions en temps réel et, d'autre part, sur les caractéristiques de fonctionnement du
des informations connues par l'opérateur (i.e. topologie et opérations de maintenance) avec des
informations connues par des niveaux de planication et management telles que les pénalités
Comme représenté dans la Fig. 1.1, le cas d'étude est facilement transposable sur la forme de
graphe. La théorie des graphes est une des approches naturelles pour la recherche de chemins
optimaux. Les travaux dans [1] se basent sur cette théorie pour maximiser la capacité opérative
du réseau. Toujours en référence à la théorie des graphes, les approches les plus classiques,
comme la recherche du chemin le plus court ou de abilité maximum, sont sources d'inspiration
pour établir des analogies par rapport à des systèmes de diverses natures. Les travaux de [10],
[11] et [12] décrivent des techniques classiques de recherche de chemins basées sur la théorie
des graphes. Notamment, dans [10], la recherche du chemin le plus court est abordée avec des
préférences fournies par l'utilisateur, ce qui montre le besoin naturel de conjuguer plusieurs
objectifs en une formulation unique ; dans ce cas : une distance et des préférences rapportées
sur les liens du graphe. Les travaux de [11] abordent la recherche des chemins disjoints inspirés
par des réseaux de télécommunication où une bande passante minimale doit être assurée pour
traiter des requêtes en maximisant le nombre de requêtes traitées. [12] aborde la recherche du
La théorie des graphes représente ainsi un cadre de référence classique pour la recherche de
théorie des graphes sera alors exploitée pour transposer la topologie du réseau vers d'autres
approches tels que les automates et les approches algébriques et heuristiques plus adéquates à
dynamique est décrite par une commutation d'état sur événements ou combinaison logique
briques, sont utilisées selon les objectifs. En outre, la notion du temps peut être également
intégrée dans le modèle et des indicateurs de performance peuvent être obtenus par résolu-
tion d'équations d'états ou à l'aide de simulations. Parmi ces outils de modélisation classiques
dédiés à ce type de systèmes les plus répandus sont les réseaux de Petri et la théorie des langages.
(vannes) qui sont sollicitées par un nombre important d'opérations. Ce phénomène de partage
de ressources est classique pour les SED et a été abordé amplement dans la littérature à l'aide des
réseaux de Petri qui, par des représentations intuitives, permettent d'obtenir, au travers d'ex-
à base des réseaux de Petri dont la modélisation des systèmes de production. Ces systèmes ont
tendance à comporter de nombreux phénomènes facilement représentables par les réseaux de Pe-
indépendantes et la dépendance des matières premières, parmi d'autres. Tous ces phénomènes
sont représentables intuitivement à l'aide des réseaux de Petri et les simulations qui en dérivent
permettent une estimation des indicateurs les plus pertinents de performance (e.g. délais, coûts).
[13] aborde une application dans le domaine chimique en permettant d'établir des transpositions
entre le modèle de production en réseaux de Petri et des algorithmes dédiés appelés PNS (en
anglais : Production Network Synthesis ) pour la détermination de l'aectation optimale des res-
sources. Par contre, les travaux dans [14] se centrent sur la modélisation et l'analyse d'inventaires
dans les systèmes de production à l'aide d'une composition de diérents sous-modèles basés sur
les réseaux de Petri tels que : des sous-modèles d'entrée, de sortie, d'inventaire, et de liaison. Des
aspects liés à l'incertitude de certaines mesures peuvent être intégrés à ce type de modèles par
des approches stochastiques ou de logique oue. Un exemple comportant les deux conforme les
travaux de [15] qui renforcent l'intérêt de ces approches en faisant appel à la crédibilité. Dans le
cadre du partage de ressources, les réseaux de Petri avec conits sont d'intérêt particulier.
Étant donné que la notion du temps est intrinsèque pour les problèmes d'ordonnancement, les
outils de modélisation discrète à considérer doivent pouvoir intégrer cette notion temporelle. Les
réseaux de Petri temporisés (en anglais Timed Petri Nets ) ou TPN et les automates temporisés
répondent bien à cette extension. Notamment, les réseaux de Petri temporisés avec conits
abordent quelques aspects fondamentaux ici. Des analogies entre ce type de modèles et les
automates conventionnels ou les automates (max,+) peuvent également être établies. Dans les
travaux de [16], la modélisation par TPN analysés à temps discret détermine des dates minima
et maxima de franchissement des transitions. Dans ce contexte, les TPN sont transformés sous
la forme d'automates. Les travaux de [16] donnent une vue d'ensemble sur diérentes techniques
Les relations mathématiques décrivant le comportement dynamique représenté par les réseaux
de Petri sont souvent hautement non linéaires dû aux phénomènes de synchronisation. Notam-
ment, lorsque deux opérations a et b doivent se synchroniser, celle qui s'achève la première
doit attendre à ce que la deuxième s'achève également pour enchaîner sur d'autres activités.
Ainsi, au niveau temporel, la détermination du maximum des deux dates d'achèvement, i.e. la
fonction max(a, b) est non linéaire. Les travaux de [17], [6] et [18] illustrent cette application
des réseaux de Petri pour la modélisation des systèmes à événements discrets, ainsi que le be-
soin de représenter de manière linéaire ces types de comportement. L'algèbre (max,+) paraît
dans ce contexte, très adéquate. Sans fournir de suite une description formelle et détaillée de
cette algèbre, il peut être indiqué qu'elle permet d'obtenir des représentations algébriques li-
néaires directes pour la manipulation des phénomènes de synchronisation. Ainsi, dans le cadre
des graphes à événements (réseaux de Petri sans conits), une équation linéaire basée sur les
opérateurs de maximisation et d'addition peut être dénie pour chacun des franchissements des
transitions du réseau. La résolution d'un système linéaire d'équations est alors très directe. En
outre, comme dans l'algèbre conventionnelle, au travers d'un système d'équations linéaires, des
d'une (ou plusieurs) solution(s), ainsi que la détermination des valeurs propres des matrices,
et de résolution de cet outil mathématique est évidente ; néanmoins, le challenge fondamental lié
peut être résolu dans les réseaux de Petri par un choix de franchissement d'une seule transition
parmi l'ensemble possible. Dans la littérature, de nombreux travaux, en particulier dans le do-
maine du transport, appliquent des techniques de modélisation basées sur des réseaux de Petri
déterminant des politiques de routage pour résoudre les phénomènes de conit, et rendre ainsi
les modèles linéaires. Une politique de routage dénit essentiellement un critère de choix entre
Les approches classiques par réseaux de Petri ne seront pas retenues pour cette recherche de
manière directe. Néanmoins, les formulations mathématiques pouvant dériver de ces modèles
seront exploitées dans le cadre des algèbres tropicales, notamment, l'algèbre (max,+). L'intérêt
réside alors dans l'exploitation des modèles mathématiques de référence. La notion de politique
de routage, classique dans les réseaux de Petri pour dénir un critère de résolution de conits,
sera conservée.
Concernant l'exploitation de l'algèbre (max,+) pour la gestion de conits, les propositions de [6]
établissent de manière convaincante une modélisation par systèmes d'équations linéaires (max,+)
des tableaux horaires d'un réseau de transport routier. Les conits sont gérés par une politique
de routage avec l'établissement de préférences a priori. Des cas type sont dénis et lorsqu'un
conit survient entre deux opérations `a' et `b', `a' aura toujours la priorité. Dans d'autres ap-
plications, telle priorité ne peut être connue et d'autres approches doivent être prises en compte
(e.g. l'aectation aléatoire de priorité). Les travaux de [18] abordent une application d'interaction
de services où une modélisation croisée réseaux de Petri et algèbre (max,+) traite des conits
par une politique d'alternance à chaque itération périodique. Ainsi, à l'itération 1 la première
riodique. Les travaux de [17] préconisent aussi une modélisation à l'aide des réseaux de Petri et
Dans ces travaux, les phénomènes de synchronisation, i.e. début d'une opération dépendant de
l'achèvement de plusieurs, sont étudiés à l'aide des graphes d'événements (i.e. réseaux de Petri
où chaque place a au plus une transition entrante et une sortante) et de l'algèbre (max,+). Les
conits sont modélisés à l'aide des graphes d'états (i.e. réseaux de Petri où chaque transition a
au plus une place entrante et une sortante). L'intérêt de l'application de l'algèbre (max,+) pour
la description des phénomènes de synchronisation réside dans l'obtention des systèmes d'équa-
tions linéaires qui peuvent être analysés et résolus à l'aide des techniques algébriques classiques
de produits matriciels. Autrement, le modèle serait hautement non linéaire et son analyse de-
algèbre classique ne sera pas retenue pour modéliser la problématique d'ordonnancement avec
système.
L'algèbre (max,+) appartient à la classe des algèbres tropicales exposées dans les travaux de
Imre Simon (voir [19]). Ces méthodes de modélisation sont de plus en plus courantes et couvrent
plusieurs domaines de recherche scientique visant à exploiter leur caractère intuitif et concis
Au préalable, il s'agit d'utiliser une structure algébrique reposant sur deux opérateurs de base, et
plus simples et intuitifs. Un large spectre d'applications est alors ouvert, dépendant de l'algèbre
tropicale
2 choisie. Par exemple, l'algèbre (min,+), basée sur les opérateurs de minimisation et
addition, est exploitée pour des applications du plus court chemin (ou des analogies qui peuvent
en dériver telles que le chemin le moins coûteux) dû au fort lien existant entre les algèbres
tropicales et la théorie des graphes. Considérant que dans un graphe orienté pondéré, le poids
peut être associé à une durée de parcours, un temps, un coût, ou toute autre pondération, le
problème de trouver le chemin le plus court, i.e. plus ecace, entre toute paire de n÷uds peut être
formulé avec l'algèbre (min,+). Cette algèbre possède comme opérations de base la minimisation
(représentée par l'opérateur ⊕) et l'addition (représentée par l'opérateur ⊗), comme élément nul :
ε = +∞, et comme élément neutre : e = 0. Un réseau peut être alors représenté par une matrice
A où chaque entrée aij représente l'arc doté d'un poids minimal du n÷ud i vers le n÷ud j et si
plus de détails) et, comme dans l'algèbre conventionnelle, l'opérateur ⊗ peut être omis, e.g.
a ⊗ b ⇔ ab. La Fig. 1.2 illustre le lien entre le modèle du graphe, sa matrice d'adjacence, et la
détermination des plus courts chemins à travers d'un produit matriciel dans l'algèbre (min,+).
chemins les plus courts entre toute paire de n÷uds i, j . Dans la gure, les entrées égales à ε sont
dénotées avec
0 .0 pour soulager la lecture. Les chemins les plus courts entre toute paire de n÷uds
i et j comportant au plus n arcs sont alors représentés par A ⊕ A2 ⊕ · · · ⊕ An . Ainsi, avec une
technique algébrique formelle, les plus courts chemins pour toute paire de n÷uds sont obtenus
d'autres algèbres. Par exemple, l'algèbre (max,min), aussi nommée `algèbre goulot' (en anglais :
2. Dans la littérature, des confusions peuvent survenir sur la dénition d'algèbre tropicale. Ici, les algèbres
tropicales sont toute une classe d'algèbres groupant les algèbres (max,+) et (min,+), parmi d'autres.
Figure 1.2: Éléments identiables dans le problème du plus court chemin à travers d'une
représentation (min, +).
neutre sont ε = 0 et e = +∞, respectivement. Comme dans toute algèbre, ces éléments sont
distributivité, en cohérence avec les opérateurs mathématiques de base. Dans cette algèbre,
comme dans l'algèbre conventionnelle, l'addition d'un élément avec l'élément nul donne comme
donne comme résultat l'élément nul, i.e. a ⊗ ε ⇔ min(a, ε) = min(a, 0) = 0. Les travaux de [21]
peuvent être consultés pour une description plus détaillée de la théorie. Dans [22], la pertinence
de l'application de l'algèbre (max,min) pour les problèmes de cheminement est présentée ainsi :
Le débit d'une canalisation étant limité par le minimum des débits des tuyaux qui la composent,
calculer An dans l'algèbre max-min revient à trouver les canalisations de débit maximal parmi
celles de longueur n.". La Fig. 1.3 présente un exemple illustratif où C(DebM ax)ij dénote une
canalisation à débit maximal entre les n÷uds i et j. Parmi les 3 canalisations reliant le n÷ud 1
au n÷ud 4, une comporte 2 sections à des débits de 5 et 8 m3 /min, la deuxième comporte une
de ces canalisations ou chemins est physiquement restreinte par la section de débit minimal.
La canalisation de débit maximal possible entre les n÷uds 1 et 4 est celle passant par le n÷ud
2. Cela est directement calculé par le produit matriciel pour toute paire de n÷uds. La gure
montre qu'aucune canalisation à 2 arcs ne permet de relier les n÷uds 3 et 4 (voir matrice A2 ).
Figure 1.3: Éléments identiables dans le problème des canalisations au débits maximaux à
travers d'une représentation (max,min).
Néanmoins, pour le scenario plus général avec au plus 2 arcs dans la canalisation, le résultat
optimal obtenu est une canalisation à 1 arc, ce qui est directement trouvé avec A ⊕ A2 .
Les algèbres tropicales s'appliquent également pour la recherche des chemins les plus ables à
l'aide des opérateurs de base de maximisation et multiplication dotés des éléments nul et neutre :
segments reliant une paire de n÷uds dans un graphe, permet d'obtenir l'ensemble des chemins
les plus ables reliant toute paire de n÷uds. La Fig. 1.4 illustre ce principe en considérant un
réseau de canalisations où les poids sur les arcs représentent la abilité de chaque section, et
C(F iabM ax)ij dénote la canalisation de abilité maximale entre les n÷uds i et j.
Un des travaux précurseurs pour l'exploitation des algèbres tropicales pour la modélisation des
procédés industriels est présenté dans [23]. Les travaux de [22] montrent que lorsque ces systèmes
atteignent un régime `périodique', les transitions (qui modélisent le passage d'une phase de pro-
duction à l'autre dans un réseau de Petri) sont franchies à des intervalles temporels égaux. La
valeur de l'intervalle est la valeur propre du système d'équations linéaires. Sans simulation, et
avec une approche analytique, les valeurs et vecteurs propres du système peuvent être obtenus
grâce à la linéarité du modèle donnée par l'algèbre. Cela permet d'estimer des indicateurs de per-
formance tels que le taux de production en régime `périodique'. Connaissant les valeurs propres,
des cycles critiques (i.e. circuits avec les taux de production les plus bas) peuvent être identiés
permettant de cibler les phases dans lesquelles des ressources peuvent être ajoutées pour amélio-
rer la performance globale du système. La Fig. 1.5 montre un exemple d'un réseau de transport
Figure 1.4: Éléments identiables dans le problème des chemins les plus ables à travers d'une
représentation (max, ×).
reliant 3 villes où chaque parcours a une durée déterminée, e.g. le trajet de la ville `1' à la ville
`2' est de 2 heures. Ainsi, le système est représenté avec un modèle (max,+) linéaire de la forme
X(t) = AX(t − 1) où X(t) = (x1 (t), x2 (t), x3 (t))T représente les dates de départ de chaque
ville, qui dépendent des dates des dernières correspondances dans la même ville. Ainsi, en sup-
posant que la date initiale pour chaque parcours est xi (0) = 0, alors X(1) = AX(0) = (2, 3, 2)T ,
X(2) = A2 X(0) = (5, 6, 4)T , etc. Après la 5-ème itération, le système atteint un régime pério-
dique remarqué par les expressions de A6 , A7 , et ainsi de suite. Notamment, X(5) = (14, 15, 13)T ,
X(6) = (17, 18, 16)T = 3 ⊗ X(5), et X(7) = (20, 21, 19)T = 3 ⊗ X(6). Le système évolue vers un
régime périodique de 3 unités de temps obtenu par la valeur propre de la matrice A où λ = 3.
Les travaux [24] et [25] constituent des références pédagogiques pour les bases et méthodes liées
au calcul algébrique de λ, et [26] peut être consulté pour une application à la modélisation et
La notion d'indépendance linéaire tropicale pour les matrices (max,+) est exploitée dans les
travaux de [27] pour l'étude d'existence des solutions pour certains problèmes d'optimisation
Pour plus d'information sur l'algèbre (max,+) pour la modélisation des chaînes de production
ainsi que des réseaux de transport, le lecteur se rapportera à la référence [22]. Les travaux de
[20] et et [28] des excellentes références de base sur la théorie des systèmes (max,+) linéaires.
[29] peut être consulté pour la théorie (max,+) appliquée au contrôle du trac, et [30] pour une
application de maintenance.
Figure 1.5: Dynamique d'un système à événements discrets par rapport à sa valeur propre.
sation conventionnelles. Par exemple, les travaux de [27] portent sur les transpositions entre
ane, respectivement, dans le sens (max,+)) et la théorie des jeux. Notamment, ces travaux
démontrent que ces problèmes de décision, modélisés à l'aide de l'algèbre (max,+), peuvent être
transposés vers des modèles de la théorie des jeux. De manière générale, la théorie des jeux est
l'étude formelle des situations de prise de décision entre joueurs de manière stratégique. Pour
le cas le plus simple de 2 joueurs, chacun peut à son tour prendre une décision qui peut lui
rapporter un bénéce quantiable. Ensuite, son opposant eectue sa man÷uvre avec aussi une
conséquence quantiable et le but du jeux pour chacun est de maximiser le bénéce acquis. Pour
une description des principes de la théorie des jeux, le lecteur peut se rapporter à [31]. Dans
les investigations ici, aucune interaction de stratégies n'est considérée, notamment la prise de
décision s'eectue dans un seul sens : prise de décision de l'opérateur de supervision. Ainsi, les
formulations mathématiques deviennent plus simples et, par conséquent, des approches de la
Les travaux de [7] portent sur l'optimisation de l'ordonnancement d'opérations dans les systèmes
manufacturiers, et représentent une référence très intéressante ici. Une analogie peut eective-
ment être déduite du comportement aux réseaux de ux ; ainsi, l'algèbre (max,+) fera partie de
Par ailleurs, la transposition des réseaux de Petri vers des représentations sous forme d'auto-
mates a toujours été de grand intérêt dû au cadre formel des langages. L'ouvrage [32] est une
Les automates temporisés ([33] et [34]), conçus à l'origine pour résoudre des problèmes de véri-
cation, sont bien entendu aptes à procurer des modèles pour la détermination d'ordonnancement
([35], [36]). Les travaux de [37] illustrent le lien entre la théorie de langages et l'analyse des sys-
tèmes de commande, en traduisant des formules de logique temporelle propositionnelle vers des
modèles à base d'automates pour dénir des spécications de commande. Ainsi, la théorie de
langages, très riche formellement, représente un corpus consistent au niveau mathématique pour
D'autres techniques alternatives qui n'ont pas été détaillées dans cette étude incluent les au-
tomates cellulaires, pour lesquels le lecteur peut se rapporter à [38] et [39]. Notamment, ces
communicantes, chacune avec un état qui évolue selon les états des cellules dans son voisinage
par rapport à certaines règles prédénies. [39] aborde une application à l'ordonnancement de
des règles d'évolution est souvent coûteuse. Quelques approches considèrent l'application d'al-
gorithmes évolutionnaires comme prometteuse dans la détermination des meilleures règles tel
que des instances similaires pour le même modèle d'automates cellulaires puissent converger
Ici, les automates cellulaires n'ont pas été retenus du fait de la disposition de techniques plus
intuitives de représentation permettant d'éviter une détermination coûteuse des règles d'évo-
lution. Néanmoins, l'exploitation de cette technique pour des problématiques similaires à celle
adressée ici pourrait être envisagée pour comparaison de résultats, ainsi que pour exploration
Les automates temporels utilisés dans [17] résultent d'une transposition entre les réseaux de Petri
et les automates type tas (en anglais : heaps of pieces ). Ces automates permettent de représenter
des opérations ou engagement de ressources sur des créneaux disponibles. Une pièce à traiter est
alors placée dans un créneau si telle machine est aectée à cette opération. La représentation
considère un empilement des pièces lorsque les opérations sont exécutées dans le temps, et cette
hauteur de tas de pièces (i.e. heaps ) permet de déterminer le makespan pour le système.
Ces représentations sous forme d'automates conduisent à une modélisation formelle et exacte.
Notamment, ils conjuguent une représentation à l'aide de la théorie classique d'automates pour
portement temporel. À ce jour, un eort considérable porte sur le développement de cette théorie
et l'application à des systèmes de diérente nature. Quelques références fondamentales [40] dé-
nissent les bases pour l'application des automates (max,+) pour la modélisation des systèmes
à événements discrets. Les travaux [41], [42] et [43] peuvent être consultés pour des développe-
ments sur la modélisation modulaire à base d'automates (max,+), ainsi que des compositions
d'automates vise à obtenir une représentation de chaque sous-système en termes d'un auto-
mate (max,+). Des événements communs reètent l'interaction des sous-systèmes au travers
étudiés pour générer un comportement global. Ainsi, ces approches visent à faciliter la modélisa-
tion par modularisation. Sur le modèle global obtenu, des contrôleurs peuvent être synthétisés.
Considérant les automates (max,+), une approche de commande juste-à-temps consiste ainsi à
rant un système contrôlé tel que chaque opération est réalisée au plus tard, tout en satisfaisant
des dates limites pour des séquences d'opérations, e.g. des dates limites d'achèvement.
La proposition dans [44] est fondamentale ici, elle apporte la dénition d'un produit synchrone
d'automates (max,+). L'aspect primordial de ce travail se centre sur des modèles considérant
l'exécution parallèle d'opérations où le produit synchrone est déni sur une extension de l'alpha-
Le modèle global de [44] dénit que les opérations exécutées en parallèle parviennent à une date
d'achèvement égale au maximum des chacune des dates d'achèvement locales. Cette approche
est concise et directe ; néanmoins, la synchronisation de deux (ou plusieurs) opérations en pa-
rallèle implique que si l'une d'elles s'achève, les ressources qui lui sont dédiées à cet instant
resteront oisives jusqu'à l'achèvement des autres. Le besoin de pallier cette limite, a inspiré ici
L'intérêt des approches formelles à l'aide d'automates, liées à une modélisation algébrique en
vue d'obtenir des modèles linéaires est clair. Néanmoins, l'usage des méthodes approximatives
reste importante et parfois nécessaire. Ainsi, les modèles linéaires algébriques ne peuvent être
obtenus que si des priorités sont établies a priori pour les conits de partage de ressources.
Cela n'est pas toujours le cas dans la réalité de l'exécution des opérations industrielles et
des heuristiques doivent être établies pour déterminer des solutions lorsque aucune autre
heuristiques est justiée lorsqu'il est nécessaire de réduire le temps de recherche de solution et
trouver une solution aux modèles (max,+) non linéaires puisque des solutions analytiques ne
sont pas possibles. Les approches approximatives réduisent également la taille et la complexité
L'usage des approches approximatives reste appréciable. Dans la pratique, une de ses avantages
est qu'une fois réalisée la transposition du problème au contexte heuristique (i.e. techniques
basées sur les algorithmes génétiques, colonies de fourmis ou autres), l'obtention de la solution
est transparente pour le modélisateur puisqu'il s'agit d'un ajustement des paramètres d'évolution
qui sont liés à la technique de résolution. Cette avantage peut aussi devenir un inconvénient si
De nombreuses contributions dédiées aux systèmes de production présentent des analogies di-
rectes avec la problématique abordée ici. À titre d'exemple, [45] présente une approche basée sur
colonie de fourmis pour l'optimisation d'ordonnancement dans un job shop. [46] présente une
application d'optimisation par colonie de fourmis et par essaims particulaires à l'intégration des
modèles de manufacture exible et les modèles de gestion de matériaux. Les travaux de [47]
portent sur l'optimisation des coûts dans la conception d'un atelier de production.
Les techniques approximatives sont très bien adaptées pour aborder des problèmes d'optimisation
multi-objectif. Dans [48], les bases de l'optimisation multi-objectif sont présentées : les approches,
Les approches évolutionnaires se basent sur une émulation de l'évolution naturelle des espèces
en abordant une résolution au travers d'une vue de populations qui évoluent dans le temps.
Au début, une population est générée où chaque individu représente une solution au problème.
Ensuite, une sélection et des modications génétiques, telles que la mutation et le croisement, sont
n'est plus identique et les meilleures solutions (i.e. individus) ont été conservées par ce processus
d'évolution. An d'illustrer le principe, dans un contexte binaire, si une solution à un problème
quelconque est identiée comme P1 = ‘1 0 1 1 1', où 5 variables prennent des valeurs 0 ou 1, et une
autre solution est représentée comme P2 = ‘1 1 0 0 0', une opération de mutation de la première
solution par exemple dans la position 4 donnerait comme résultat P1M = ‘1 0 1 0 1'. D'autre part,
le croisement des solutions P1 et P2 dans la position 3 donnerait comme résultat deux solutions,
aussi appelées descendants en sachant que P1 et P2 jouent le rôle de parents, qui correspondent
de modication des solutions et d'évaluation de leur qualité pour que le processus converge vers
un ensemble de solutions avec une qualité optimale. Les travaux de [49] et [50] peuvent être
consultés pour une introduction aux algorithmes génétiques et ses applications parmi lesquelles
Lorsque plusieurs objectifs sont considérés, une solution optimisant tous les objectifs n'est pas
forcément garantie, i.e. un objectif est amélioré au détriment d'un autre. Ainsi, la prise de décision
implique la considération d'un compromis dans la qualité obtenue pour tous les objectifs. Cette
approche s'adapte aux spécicités de notre problématique puisque les objectifs d'intérêt (i.e.
conictuels) sont non commensurables ; i.e. n'ont pas une même mesure et, par conséquent, ne
peuvent pas être évalués de manière groupée. D'autres approches non retenues abordent une
intégration de tous les objectifs dans une seule fonction objectif dont une des plus connues est
les objectifs sont composés considérant qu'ils sont commensurables et que chacun a un poids
associé αi par rapport à son importance dans l'objectif global. Ainsi, le problème est réduit à
un de type mono-objectif ; néanmoins, le choix des poids pour chaque objectif n'est pas évident.
D'autres méthodes connues dans le traitement des problèmes multi-objectif incluent la méthode
d'optimisation par contraintes, connue en anglais par ε-constraint, qui vise à retenir un seul
objectif en transformant tous les autres sous forme de contraintes, i.e. fk (x) ≤ εk où εk ∈ R p .
Des méthodes hybrides proposent une fonction objectif représentant la somme pondérée des
objectifs avec des contraintes sur chacun. La méthode des contraintes élastiques exibilise les
contraintes sur les objectifs en permettant d'être violées et en pénalisant ces violations dans
modéliser des objectifs incommensurables où, pour des raisons qui ne dépendent pas du décideur,
ces objectifs sont classés de manière hiérarchique. Pour plus de détails sur ces méthodes et autres
nalité des travaux est de permettre une prise de décision parmi plusieurs solutions candidates
représentant des compromis entre les objectifs. Une technique courante est la frontière de Pareto.
Dans [48] et [53], une description des bases de cette approche est présentée. Notamment, une
notion de dominance est dénie pour comparer des individus (i.e. solutions). Un individu est
dénoté comme `non dominé' si aucun autre individu n'arrive pas à améliorer certains objectifs
sieurs individus peuvent être non dominés. Ils représentent diérents compromis ou solutions
optimales pour la problématique. L'ensemble d'individus non dominés est nommé la frontière de
Pareto.
Plusieurs techniques permettent de gérer l'évolution des individus en vue de trouver la frontière
de Pareto : MOMGA (en anglais : Multi-objective Messy Genetic Algorithm ), PAES (en
anglais : Pareto Archived Evolution Strategy ), PESA (en anglais : Pareto Envelope-based
Selection Algorithm ) et SPEA (en anglais : Strength Pareto Evolutionary Algorithm ) sont
quelques exemples. Le lecteur se rapportera à l'ouvrage [54], et aux travaux de [55] et [56],
pour une description générale de ces techniques qui se diérencient dans la manière dont elles
gèrent l'évaluation des individus au cours des générations. Par exemple, l'algorithme SPEA,
travail dans [57], et propose l'évaluation de chaque individu par rapport à sa force ( `strength' ).
Pour chaque individu, cet indicateur comptabilise le nombre d'individus dominés par l'individu
en question. Dans le contexte applicatif, [58] aborde le SPEA2, qui est une amélioration du
SPEA pour la recherche du chemin le plus court. La dénition ou amélioration des techniques
évolutionnaires est un large domaine de recherche actuel. Ici, le SPEA sera considéré largement
Conclusions Partielles
par un service tardif a été présentée. La littérature identie de nombreuses approches relevant des
SED pour aborder des problèmes similaires. Les approches tropicales sont exploitées du fait de
leur potentiel de modélisation apportant des résultats concis et formels permettant l'exploitation
Le document comporte cinq chapitres dont le premier est introductoire. Le chapitre 2 se centre
sur la modélisation à l'aide des algèbres tropicales, et présente plusieurs modèles mono-objectif
l'optimisation multi-objectif minimisant les pénalités et les retards dans les opérations de
Le chapitre 4 propose une modélisation à base d'automates tropicaux pour la recherche d'un
ordonnancement optimal pour un comportement au plus tôt motivant la dénition d'un nouveau
Préambule
Ce chapitre aborde la modélisation des problèmes d'ordonnancement dans un réseau de
pipelines à l'aide des algèbres tropicales. Il présente les modèles et les résultats obtenus validant
pénalités subies par le terminal maritime pour un ensemble d'opérations de transfert à traiter.
Une synthèse est présentée sur les algèbres tropicales en vue de répondre à la problématique de
datation abordée. Ensuite, le système est modélisé à l'aide de cette formalisation en explorant
des représentations (max,+) non linéaires, puis linéarisés, pour des alignements connus a priori.
Le chapitre se termine par la proposition d'un modèle étendu permettant également d'optimiser
la sélection d'alignements.
Sommaire
2.1 Algèbres Tropicales - Motivation et Cadre Théorique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
21
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
avant d'aborder les étapes de commande et d'optimisation. Dans le cadre des systèmes à évé-
nements discrets, de nombreux phénomènes ne peuvent pas être décrits de manière linéaire ou
même intuitive à l'aide de l'algèbre conventionnelle (en se limitant aux opérateurs d'addition et
propriétés formelles, telles que la linéarité par rapport à certaines variables décrivant son évolu-
tion, à travers d'opérateurs qui leur sont dédiés. L'exploitation des algèbres tropicales fournit les
moyens de transposition pour modéliser ce type de systèmes par des expressions mathématiques
Avant de présenter une description formelle mathématique, la motivation pour l'utilisation des
Le potentiel applicatif des algèbres tropicales a été présenté dans [22]. Notamment, ces tra-
vaux abordent `une nouvelle manière de compter', i.e. une structure algébrique diérente, pour
modéliser des systèmes dynamiques. Un exemple très intuitif présenté dans cette référence est
le suivant : pour l'employé d'une boulangerie qui fabrique des sandwichs jambon-fromage, un
morceau de baguette `plus' une tranche de jambon `plus' une lamelle de fromage font un sand-
wich. Dans cette situation, l'addition de trois quantités de natures diérentes donne un résultat
aussi de nature distincte. Selon cette opération, `1 ⊕ 1 ⊕ 1 = 1'. De surcroît, si l'employé garnit
le sandwich de deux tranches de jambon au lieu d'une, le résultat reste un sandwich unique.
Ce genre d'abstraction est l'origine de l'usage des algèbres tropicales basées sur deux opérateurs
discrets de divers points de vue tels que le comportement temporel et la gestion de ressources.
Le même type d'abstraction (i.e. un sandwich ne peut être produit que si ses ingrédients sont
disponibles) peut être représenté par des réseaux de Petri. Néanmoins, c'est la formalisation par
l'algèbre (max,+) qui exploite explicitement des propriétés mathématiques issues de l'algèbre
linéaire conventionnelle (e.g. existence de solution pour des systèmes d'équations, valeurs propres,
produits matriciels) pour décrire un comportement dynamique souvent basé sur des phénomènes
de synchronisation.
1. où les opérateurs de base ⊕ et ⊗ décrivent directement les phénomènes fondamentaux du système étudié.
Dans l'exemple présenté, l'objet produit (i.e. 1 sandwich) résulte du minimum des opérandes.
C'est un concept bien appréhendé par l'algèbre (min,+) dotée des 2 opérateurs de base que
sont la minimisation et l'addition. Par contre, pour l'appréhension des phénomènes de synchro-
ensemble d'exécution simultanée, l'algèbre (max,+) est plus adaptée. Cette algèbre est basée sur
de cette algèbre est la gestion ferroviaire où le départ d'un train est conditionné aux arrivées
d'autres trains dont les passagers doivent eectuer une correspondance. Ceci est évidemment
Dans le même esprit, d'autres règles peuvent émerger selon les besoins, par exemple l'algèbre
(max,min) ou l'algèbre (min,+). L'ouvrage [20] donne une introduction complète, ici sont rap-
L'algèbre (max,+) est une structure mathématique dénotée comme Rmax , formée par l'ensemble
S
R {−∞} et deux opérations binaires ⊕ et ⊗, qui correspondent à la maximisation et l'addition,
respectivement (voir (2.1)).
a ⊕ b = max(a, b)
∀a, b ∈ Rmax , (2.1)
a ⊗ b = a + b
propriété d'idempotence. Pour l'exemple précédent concernant le trac ferroviaire, les dates de
départ peuvent être notées par x1 et x2 pour les trains 1 et 2 (arrivant en gare), et x3 pour
le train 3, qui est conditionné par l'arrivée des deux premiers. La durée de chaque parcours
(incluant le temps pour eectuer les correspondances) pour les trains 1 et 2 est notée par τ1
et τ2 , respectivement. Ainsi, la date de départ du troisième train peut être décrite en algèbre
(max,+) par x3 = x1 ⊗ τ1 ⊕ x2 ⊗ τ2 . Par conséquent, il s'agit d'un simple produit scalaire dans
le sens (max,+) des vecteurs (x1 , x2 ) et (τ1 , τ2 )T . Si la date de départ du troisième train est
imposée, comme une constante b par exemple, alors les dates de départ des autres deux trains
peuvent être déterminées telles que b soit respectée. Ce résultat est obtenu en résolvant la simple
équation (max,+) linéaire : x1 ⊗ τ1 ⊕ x2 ⊗ τ2 = b. Dans le cadre (max,+), xi est dénoté comme
[20], un semi-anneau K est un ensemble doté avec deux opérations de base : ⊕ et ⊗, qui respectent
certaines propriétés algébriques classiques. L'élément nul est ε = −∞, et l'élément neutre est e =
0. Les principales propriétés de cette structure (similaires à celles de l'algèbre conventionnelle)
Opération ⊕ :
Opération ⊗ :
a ⊕ b ⇔ max(a, b) a⊗b⇔a+b
a ⊕ ε ⇔ max(a, ε) = a a⊗ε⇔a+ε=ε
a ⊕ e ⇔ max(a, e) = a a⊗e⇔a+e=a
dépendances temporelles entre diérents constituants du système. Ceci fait l'objet de la section
suivante.
gestion des pénalités, ainsi que des aspects de partage de ressources, permettant de déterminer
des modèles basés sur l'algèbre (max,+) représentant ces aspects de fonctionnement.
Dans le cadre de la gestion de pénalités, chaque client contractualise une date limite d'achève-
ment de service. En cas de dépassement de cette date, des pénalités nancières sont adressées
à l'exploitant du terminal maritime. Le coût de la pénalité par heure de retard est spécié par
client, et la pénalité globale subie par le terminal pour chaque client est proportionnelle au re-
tard total du service. Ainsi, l'objectif majeur de l'exploitant du terminal est de minimiser les
D'autre part, s'il est fait référence à la disponibilité des moyens de transfert impactant les retards,
Pour chaque client, une négociation est conclue au préalable avec l'exploitant du terminal pour
s'accorder sur la date de traitement de la commande. Le client dénit (dans des conditions qui
ne sont pas pertinentes dans ce rapport) la pénalité par heure de retard de remplissage de son
tanker. Le terminal propose une fenêtre de temps de trois jours dans laquelle le tanker peut
arriver. En cas d'arrivée tardive, le terminal sera exempt de toute pénalité en cas de retard de
service. Par contre, si le client arrive dans la fenêtre de temps prédénie, le client `a le droit'
d'être servi immédiatement. Dans la pratique, une pénalité sera exigée si le terminal n'a pas
eectué le service dans les 36 heures. Plus précisément, les délais maxima de service sont de 36
heures pour chargement et de 4 heures pour documentation administrative. Ici, seule la phase de
chargement est considérée dans l'ordonnancement sans aucune perte de généralité. Aucune autre
information n'est retenue concernant d'autres scénarios d'arrivée des tankers. Cependant, si le
service est retardé (i.e. dépasse les 36 heures) du fait du tanker, une pénalité de sur-occupation
de quai peut être demandé au client et si, par contre, le service est retardé du fait de conditions
météorologiques aucune pénalité n'est exigée pour l'une ou l'autre des parties.
Selon le type et le séquencement des alignements demandés, les vannes, ressources du réseau,
seront sollicitées de manière diérente. Les alignements réservoir-tanker sont obtenus du fait
des états d'ouverture/fermeture des vannes du pipeline. Des conits surviennent lors de leur
Ces notions sont pertinentes pour une large gamme de systèmes interconnectés et pose des
Dénition 2.1. Plusieurs alignements aectés à des opérations de transfert sont dits en conit
s'ils partagent pendant une même période au moins une vanne ouverte commune ou si cette
vanne doit commuter vers un état diérent pour l'ensemble des alignements à considérer.
Autrement dit, si une vanne commune pour diérents alignements doit commuter à l'état de
fermeture pour tous les alignements considérés aucun conit n'est identié car cette commutation
permet d'exécuter les opérations de manière simultanée. Dans tout autre cas, un conit de
partage de ressources existe. La Fig. 2.1a) présente deux alignements disjoints visant à satisfaire
les requêtes (R1 et R3 ). Les lignes continues dénotent les vannes qui doivent être ouvertes et les
2. cet ordonnancement est stratégique à résoudre et il n'est pas l'objectif de cette recherche.
Figure 2.1: Alignements indépendants (a) et en conit (b) pour les opérations de transfert
lignes segmentées les vannes qui doivent être fermées pour isoler les alignements. Par exemple,
pour habiliter l'alignement pour R1 les vannes 1, 4, 10, et 16 doivent être ouvertes et les vannes
5, 6, 8, 12, 11, et 13 doivent être fermées. Sur la Fig. 2.1a) aucun conit n'existe car les ressources
partagées par les opérations (i.e. vannes 5, 8, 12 et 13) sont toutes des vannes à fermer ; par
conséquent, elles peuvent permettre l'habilitation des deux alignements simultanément. Sur la
Fig. 2.1b) une troisième requête est rajoutée et des conits surviennent pour les vannes 10 et 16,
puisqu'elles doivent être ouvertes pour deux opérations de transfert (conduisant à un mélange
des produits) et pour les vannes 4 et 6 puisque les commutations requises sont diérentes pour
les deux opérations (ce qui est physiquement impossible). Par conséquent, R1 et R2 ne peuvent
être traitées simultanément. Naturellement, il est primordiale de servir autant de clients que
possible au plus tôt, ce qui se traduit par l'exécution simultanée d'opérations chaque fois que
Dénition 2.2. Une vanne est dite en conit si habilitant le ux de produit sur un alignement
Dans la Fig. 2.1b), si la vanne 6 était l'objet d'une opération de maintenance, cela entraînerait
un conit avec l'opération R1 (la vanne doit être exploitée en état de fermeture) et aussi avec
l'opération R2 (la vanne est requise en état d'ouverture). Ainsi, en aucun cas une même vanne
Pour qu'une vanne puisse être mise en maintenance, elle doit être isolée du reste du réseau en
impliquant la fermeture de toutes les vannes adjacentes. Dans cette situation, il faut garan-
tir qu'aucun conit n'existe entre les vannes d'isolement pour l'opération de maintenance, et
les vannes d'ouverture pour un alignement d'une opération de transfert. Cela est garantie en
Dénition 2.3. Pour une vanne, le conit entre sa sollicitation comme vanne d'isolement pour
une opération de maintenance et comme vanne ouverte pour une opération de transfert générera
toujours un conit entre la vanne en maintenance et une vanne d'isolement pour l'opération de
transfert.
Pour illustrer le principe de la dénition 2.3, sur la Fig. 2.1b) si la vanne 7 devait être mise
cette opération et, par exemple, la vanne 2 ne pourrait pas être sollicitée simultanément pour
satisfaire R2 . Néanmoins, ce conit d'opérations entraîné par la vanne 2 (de type fermeture pour
maintenance / ouverture pour opération de transfert) est implicitement modélisé par le conit
entraîné par la vanne adjacente 7 (de type fermeture pour l'opération de transfert R2 / mise en
maintenance). Ce dernier type de conit a déjà été décrit dans la dénition 2.2.
Comme mentionné dans le chapitre 1, de nombreuses approches relevant des SED pourraient
modéliser ces phénomènes. Dans ce contexte, les réseaux de Petri permettent une représentation
Dans la Fig. 2.2, deux phénomènes de base (synchronisation et conit) sont représentés à l'aide
des réseaux de Petri. Graphiquement, les réseaux de Petri sont constitués par d'éléments in-
terconnectés de type `place' et `transition'. Les jetons dans les places peuvent s'assimiler à des
ressources ou des étapes en cours de traitement dans un système quelconque lorsque les transi-
dans les systèmes de production, ou des phénomènes similaires transposables à d'autres problé-
disposées dans les places en amont. Dans le cas considéré, la transition n'est pas franchissable
puisqu'une place en amont ne contient pas de ressources disponibles. Ainsi, ce modèle représente
peut être représenté comme une contrainte mise sous la forme d'une équation ou inéquation
temps de séjour n'est exigé dans les places en amont. En l'algèbre conventionnelle, la fonction
de maximisation est une fonction non linéaire, qui dans l'algèbre (max,+) devient linéaire, i.e.
3. des modèles plus élaborés basés sur les réseaux de Petri peuvent inclure des temporisations, le déplacement
de plusieurs jetons lors du franchissement d'une transition, des phénomènes stochastiques ou des contraintes
supplémentaires. La nalité de cette étude n'est pas une analyse exhaustive dans ce sujet et, ainsi, la version la
plus simple de ce type de modèle est abordée pour l'illustration sans perte de généralité.
et présentent de nombreuses non linéarités, des heuristiques sont utilisées pour leur résolution
permettant d'obtenir des solutions approximées acceptables dans un délai raisonnable. Le phé-
nomène de conit, représenté dans la Fig.2.2b), modélise le fait que si la place P4 contient un
jeton, une seule des transitions en aval peut être franchie avec cette ressource. Néanmoins, ce
choix n'est pas évident. Le choix correspondra mathématiquement à l'aectation d'une variable
de décision jugé sur un critère spécique. Pour ces deux phénomènes, les avantages d'une modé-
lisation basée sur l'algèbre (max,+) seront une représentation mathématique simple et concise
tions
Ce modèle, basé sur l'algèbre (max,+), décrit de manière intuitive et concise les conits de
partage de ressources ainsi que la dépendance des dates d'arrivée des tankers sur la forme d'une
synchronisation.
Pour le terminal maritime, chaque alignement (réalisé par la commutation de plusieurs vannes)
répond à une opération de transfert. Dans un horizon de temps donné, l'exploitant du terminal
peut être amené à gérer simultanément n opérations de transfert (soit n alignements). Ainsi,
en terme d'allocation de ressources puisqu'il s'agira de répondre aux requêtes dans les temps
impartis, les principes du modèle se basent sur une représentation de type dateur par vanne ou
de type dateur par opération de transfert. Par la suite, le modèle d'un dateur par transfert sera
retenu. La représentation d'un dateur par vanne a par ailleurs été objet de publication dans [59].
Ces deux représentations sont équivalentes, donnent les mêmes résultats, et les diérences se
situent au niveau de granularité retenu qui peut s'ajuster de manière plus adéquate en fonction
Hypothèse 2.1 . L'alignement aecté à chaque opération est connu au préalable, et, par consé-
Le dateur pour une opération de transfert est dénoté par xi où i est la requête à traiter.
Le dateur pour une opération de maintenance est dénoté par xmk où k est la vanne à être
si une vanne k doit subir une opération de maintenance, alors k ∈ M), I dénote l'ensemble
des opérations de transfert (i.e. si i est une opération de transfert à être exécutée, alors
i ∈ I), et nalement ISOk dénote l'ensemble des vannes d'isolement permettant d'exécuter la
maintenance de la vanne k.
xi = max t0 ; ui ; maxk xmk + tmk + ztmk + Vi,k ; maxi0 xi0 + pi0 + zpi0 + zci0 + Vi,i0
0 0
∀ i, i ∈ I|i 6= i , ∀k ∈ M
(2.2)
L L
xi = t0 ⊕ ui ⊕ xmk ⊗ tmk ⊗ ztmk ⊗ Vi,k ⊕ i
0 xi0 ⊗ pi0 ⊗ zpi0 ⊗ zci0 ⊗ Vi,i0
k
∀ i, i0 ∈ I|i 6= i0 , ∀k ∈ M
(2.3)
de transfert. Elle est représentée par (2.2) en algèbre conventionnelle et (2.3) correspond à son
équivalent en notation d'algèbre (max,+). Dans ce qui suit, la notation (max,+) sera employée et
dans le cas contraire il sera précisé. Cette contrainte détermine la date de début xi , aussi nommée
`dateur' dans le contexte (max,+), pour l'opération i de transfert de pétrole qui s'exécute sur
un alignement qui est supposé comme connu au préalable. La connaissance de l'alignement pour
vanne sont réalisées pour habiliter l'alignement dans le réseau en cohérence avec l'hypothèse 2.2.
Hypothèse 2.2. Toutes les vannes dans chaque alignement commutent simultanément.
xm k : dateur pour une opération de maintenance sur la vanne k . Cette opération de maintenance
est en conit avec l'opération de transfert i si la vanne k est commune aux deux opérations.
Vi,k : variable de décision binaire qui résout le conit d'aectation de ressources entre les opé-
dit, dans (2.3), si Vi,k = ε = −∞ alors le terme (xmk ⊗ tmk ⊗ ztmk ⊗ Vi,k ) tend vers −∞ et,
par conséquent, il est négligeable dans l'équation (puisqu'il s'agit d'une maximisation). Cela im-
k, i.e. l'opération de transfert i s'exécutera avant. Le cas opposé est représenté pour Vi,k = e.
Pour toute variable Vi,k il existe une variable complémentaire Vk,i .
Vi,i0 : variable de décision binaire qui résout le conit d'aectation des ressources entre les
opérations de transfert en conit i et i0 . Vi,i0 ∈ {ε, e}. Son impact temporel est identique au cas
ztmk , zpi0 , et zci0 représentent respectivement les retards possibles dans l'opération de mainte-
nance, dans le service au client dû à des dicultés techniques dans le terminal, et dans le service
Enn, les paramètres : t0 , tmk , et pi0 correspondent respectivement à la date de début de l'horizon
transfert. Ici, t0 prend sa valeur par défaut, i.e. t0 = 0 dans tous les modèles.
L'équation (2.3) modélise que le fait d'habiliter un alignement pour répondre à une opération
doivent s'exécuter avant l'opération ciblée i). Ainsi, le dateur xi dépend du fait que toutes ces
conditions aient eu lieu, il faut donc attendre que la dernière des conditions soit vraie pour
La structure de la contrainte de date (2.3) est la base de la modélisation. Les valeurs aectées aux
variables de décision permettent de quantier les dateurs, qui équivalent aux ordonnancements.
L'équation est ainsi non linéaire dans l'algèbre (max,+) étant donné qu'il existe un produit des
variables de décision et des dateurs ([7]), i.e. le produit du type dateur-variable de décision, e.g.
xi0 ⊗Vi,i0 .
Lors de l'exécution de l'opération i, plusieurs types d'interruption dans le service peuvent avoir
lieu et permettront d'ajuster les données dans le modèle et de recalculer l'ordonnancement par
Les variables de décision sont binaires et peuvent prendre les valeurs nulle (ε = −∞) ou neutre
(e = 0) dans l'algèbre (max,+). En vue de valider le modèle, les valeurs gérées sont e et B, tel
que B soit un nombre réel grand et négatif (i.e. B → −∞). En outre, il est rappelé que chaque
variable de décision a une variable complémentaire (i.e. si Vi,i0 = e, alors Vi0 ,i = B ou vice
versa). L'eet des contraintes par rapport aux valeurs des variables de décision est le suivant :
dans (2.3), si Vi,k = B alors le 3eme terme de la maximisation devient négligeable, ce qui implique
que l'achèvement de l'opération de maintenance n'a aucune inuence sur le début de l'opération
maintenance, ce qui implique que l'opération i dépend de cette date, i.e. l'opération i s'exécute
après l'opération k.
L L
xmk = xf ixedk ⊕ i xi ⊗ pi ⊗ zpi ⊗ zci ⊗ Vk,i ⊕ k0 xmk0 ⊗ tmk0 ⊗ ztmk0 ⊗ Vk,k0
∀i|i ∈ I, ∀ k ∈ M, ∀ k 0 ∈ ISOk
(2.4)
De manière analogue, l'expression (2.4) permet de déterminer le dateur pour une opération de
maintenance. Le résultat est le maximum de trois termes, dont le premier est une date (xf ixedk )
supposée xée pour l'activité de maintenance (échéancier). Dans le meilleur des scénarios, l'or-
donnancement global d'opérations permet l'exécution des activités de maintenance dans les dates
de maintenance avec des opérations de transfert sollicitant des ressources communes, et dont
les commutations requises ne permettent pas d'eectuer les opérations de manière simultanée.
Le troisième terme représente aussi des conits de partage de ressources ; dans ce cas il s'agit
des conits entre la vanne en maintenance k et les possibles opérations de maintenance sur les
Hypothèse 2.3 . Lorsqu'une opération de transfert débute, le client commence à recevoir le produit
de manière instantanée, puisqu'il est considéré que les canalisations sont toujours pleines de
Dans le cas où un délai important doit être considéré entre l'habilitation de l'alignement et la
réception du produit par le client, il peut être facilement inclus dans les temps de traitement des
Les équations (2.5) et (2.6) restreignent les valeurs des variables de décision à zéro ou B pour
les conits potentiels entre 2 opérations de transfert. De manière analogue, les équations (2.7)
et (2.8) restreignent les valeurs des variables de décision pour les conits entre une activité de
ui ⊗ pmax
∀ i|ui ∈ twi
Di = xi ⊗ pmax ∀ i|ui > utwi (2.9)
ltwi ⊗ pmax ∀ i|ui < ltwi
L'équation (2.9) exprime la date limite de service Di pour une requête i où twi = [ltwi , utwi ]
dénit la fenêtre de temps autorisée pour l'arrivée du tanker correspondant. Si le tanker arrive
dans cet intervalle, sa date limite de service sera de pmax = 36 heures après l'arrivée. Si le tanker
arrive après cette fenêtre, aucune pénalité n'est adressée au terminal pour le temps d'attente,
qui sera recalculé en tenant compte des conditions opérationnelles du terminal. Aucune autre
information supplémentaire n'a été obtenue directement des terminaux visités. Par conséquent,
sans aucune perte de généralité, an de valider le modèle proposé il est supposé que, dans ce
scénario, la date limite de service est de pmax = 36 heures juste après le début de transfert.
Finalement, il est supposé que si le tanker arrive avant la fenêtre autorisée, la date limite de
Le retard par requête dpr, en anglais : delay per request, est déterminé par (2.10). Pour chaque
requête, le dpr est la diérence (opérateur ) entre la date d'achèvement de la requête (consi-
dérant les possibles retards causés par le terminal et/ou le client) et sa date limite de service.
En termes de politique de gestion des pénalités, les actions à appliquer lorsque les deux parties
causent des retards dans le service simultanément ne sont pas encore connues. An de valider
les modèles, l'hypothèse 2.4 est retenue, ce qui permet de modéliser par (2.11) le retard pénalisé
pour le terminal pds, en anglais penalized delay for the seaport, pour chaque requête.
Hypothèse 2.4 . La pénalité de sur-occupation de quai par heure (subie par chaque client) est
considérée égale à la pénalité par heure subie par le terminal pour service tardif pour le même
client.
zui zpi ⊗ zci ⊕ (dpr ) ∀(zui ⊗ zpi ) > zci
i
pdsi = (2.11)
0 sinon
En algèbre conventionnelle, (2.11) indique que si le retard entraîné par le terminal (incluant le
temps d'attente du tanker zui = xi − ui et les interruptions de chargement) est supérieur aux
interruptions causées par le client (i.e. zui + zpi > zci ), alors le terminal encourt une pénalité.
Cette pénalité est calculée comme min((zui +zpi )−zci , dpri ) qui est le minimum entre la mesure
dans laquelle le retard du terminal dépasse le retard du client et la mesure dans laquelle la date
limite de service est dépassée. Cette minimisation est exprimée sous la forme de maximisation
par (2.11) en algèbre (max,+). Si le retard causé par le tanker est supérieur ou égal au retard
O O pdsi
M in T CP = ci ∀i ∈ I (2.12)
i n=1
L'équation (2.12) représente la fonction objectif dans le problème d'optimisation. Le coût total
entraîné par les pénalités T CP , en anglais : Total Cost due to Penalties, est déterminé pour toutes
les requêtes dans l'horizon de temps considéré. L'équation (2.12) décrit en algèbre (max,+) ce
qui en algèbre conventionnelle serait la somme des produits pour chaque retard pénalisé (en
P
heures) et sa pénalité correspondante (en $/heure), i.e. i pdsi × ci .
2.2.2.2 Résultats
Le modèle proposé a été publié dans [59] avec la représentation d'un dateur par vanne (au
lieu d'un dateur par alignement). Les instances ont été considérées sur une topologie simple,
comme celle de la Fig. 1.1, pour une assimilation simple du processus de prise de décision de
l'ordonnancement d'un ensemble d'opérations avec partage de ressources. Ainsi, il est possible
L'instanciation a été réalisée avec le logiciel d'optimisation LINGO (voir [60]). La fonctionnalité
de `solver global' a été choisie pour garantir un optimum global et les contraintes et fonction
objectif ont été directement codées dans cet environnement. Le solver teste des valeurs pour les
variables de décision (qui par conséquent génèrent des valeurs pour les dateurs des opérations),
et évalue la fonction objectif jusqu'à ce qu'elle ne puisse plus être améliorée, tout en respectant
L'instance de la Fig. 2.3, qui correspond à un réseau de topologie simple, représente l'exécution
dénotées par Mk , k = 13, 15, sur les vannes 13 et 15 planiées aux dates t = 100 et t = 130 de
durée de 12 et 10 heures, respectivement. Les alignements considérés sont réalisés par les vannes
qui doivent être ouvertes pour l'écoulement et les vannes isolantes (omises de la gure pour
une meilleure compréhension). Pour les activités de maintenance, les vannes d'isolement sont
également omises. Cette instance couvre l'ensemble des conits possibles et les données d'entrée
Sachant qu'une fenêtre de temps est autorisée pour l'arrivée de chaque tanker (représentée dans
le Tableau 2.1 à partir de t0 = 0), un ordonnancement de référence peut être obtenu en supposant
1 2 3
5 8
6 7
4 R1
9
R2
R3
R4
R5
12 13
15 R6
11 14
R7
10
maintenance
16 17 18
Requête Temps de Traitement (heures) Pénalité ($/ heure) Fenêtre de Temps pour Arrivée (jours)
R1 20 4000 [4,6]
R2 25 2500 [2,4]
R3 20 3000 [2,4]
R4 15 2500 [1,3]
R5 20 2500 [1,3]
R6 15 3000 [2,4]
R7 10 2000 [3,5]
Table 2.1: Données d'entrée pour les opérations de transfert sur la Fig. 2.3.
certaines dates d'arrivée (dans ou hors la fenêtre) et basé sur les estimations actuelles par rapport
aux échanges avec les clients. Pour valider la pertinence du modèle d'optimisation proposé, il
est supposé que tous les tankers, sauf celui qui correspond à l'opération R2 , arrivent dans leurs
fenêtres de temps à la dernière heure du dernier jour permis, ce qui entraîne de nombreux conits.
Il est aussi supposé que le tanker pour R2 arrive après sa fenêtre de temps, à 10 heures du matin
du jour 5. Aucune interruption pouvant entraîner un retard n'est prévue, ce qui implique que
zpi = zci = ztmi = e. Il est supposé que l'horizon de temps pour la planication commence à
t0 = 0.
L'ordonnancement optimum obtenu par LINGO est présenté sur la Fig. 2.4, il implique un T CP
de $137000.
Selon les données du Tableau 2.1, R4 et R5 sont en conit puisque les tankers arrivent simul-
tanément (à t = 71, début de la dernière heure de leur fenêtre) et les ressources communes
qui doivent être sollicitées ne permettent pas une exécution simultanée (voir en référence à la
Fig. 2.3 où la vanne 9 doit être ouverte pour R4 mais fermée pour R5 ). Dans l'ordonnancement
obtenu, il peut être vérié que la résolution optimale de ce conit, minimisant les pénalités, est
d'exécuter R5 avant R4 . Les opérations restantes peuvent être commentées de manière analogue.
Par exemple, en considérant la fenêtre de temps [2, 4] (i.e. arrivée entre les jours 2 et 4) dans le
Tableau 2.1 il peut être identié que les opérations R3 et R6 sont en conit du fait des ressources
communes et du fait que les deux tankers arrivent à t = 95 (dernière heure du dernier jour de
leur fenêtre). R2 n'est pas en conit avec R3 et R6 puisqu'il a été considéré que le tanker arrive
Ainsi, l'instance présentée force le terminal à subir des pénalités étant donné le nombre impor-
tant de ressources en conit, dates d'arrivée dénies et des temps de traitement. Considérant
la topologie relativement simple de la Fig. 2.3, il peut être vérié manuellement qu'aucun autre
pas être exécutées simultanément et les dates des activités de maintenance doivent être respec-
tées. Les requêtes qui entraînent des pénalités pour le terminal sont R3 (retard de 29 heures)
besoin d'ordonnancement des terminaux maritimes. Sa validation a utilisé des données recueillies
modèle algébrique (max,+) proposé est concis puisqu'il permet d'agréger facilement dans une
seule équation une diversité de contraintes. Cependant ce modèle est non linéaire car il n'existe
pas d'a priori, ni sur les clients ni sur les ressources. Dans la section suivante, des modèles
linéaires basés sur cette représentation de base seront proposés pour les cas où des informations
supplémentaires posent des priorisations entre chaque paire des requêtes en conit. Ainsi, à partir
des modèles déjà proposés, une linéarisation résultera de l'aectation des variables de décision.
ment d'Opérations
Dans la section précédente, le modèle d'optimisation a été proposé sous un approche (max,+)
tel que les contraintes fondamentales sont celles de l'aectation de ressources lors d'un conit.
Le modèle est non linéaire du fait du produit entre les dateurs et les variables de décision (voir
(2.3)). Par exemple, le terme (xi0 ⊗ pi0 ⊗ zpi0 ⊗ zci0 ⊗ Vi,i0 ) modélise une non linéarité en sachant
que x i0 et Vi,i0 sont des variables et que pi0 , zpi0 et zci0 sont des paramètres. Ainsi, le produit
xi0 ⊗Vi,i0 rend l'expression non linéaire. Dans ce cas, l'aectation d'une valeur à la variable de
décision Vi,i0 rendrait l'expression linéaire ; i.e. si tous les paramètres sont regroupés dans un seul
paramètre global pg = pi0 ⊗ zpi0 ⊗ zci0 ⊗ Vi,i0 , alors l'expression linéaire est synthétisée comme
pg ⊗ xi0 .
La motivation de cette section est due à l'importance de l'exploitation des propriétés mathéma-
tiques des modèles (max,+) linéaires en général. L'aectation des variables de décision est abor-
dée en considérant certains critères de priorisation des opérations de transfert en conit. Ainsi,
les opérations de maintenance ne sont pas considérées dans cette section. Pour les considérer il
faudrait disposer des informations telles que l'ensemble de conséquences nancières entraînées,
dans la gestion de maintenance, par le décalage d'une opération de maintenance de vanne, in-
formations qui ne sont pas connues dans cette étude. Dans le cas où ces informations seraient
connues, une aectation des variables de décision de précédence entre les opérations de transfert
type X = AX ⊕ b avec X = (Xt , Xm )T où Xt serait le vecteur ligne des dateurs des opérations
L'aectation des variables de décision est traité en terme de politique de routage dans les réseaux
de Petri. Dans ces modèles, le routage xe la priorité d'exécution de opérations qui ne peuvent pas
être exécutées simultanément du fait des ressources partagées. Cette politique de routage peut
résulter d'une intégration de plusieurs critères ou indicateurs liés aux opérations en conit, ou
aux conditions d'exploitation du réseau. Pour explorer des représentations linéaires du modèle
(max,+) proposé, et en analogie avec la terminologie des réseaux de Petri, une politique de
routage sera appliquée pour déterminer la précédence entre deux opérations quelconques en
conit. Deux possibles politiques ont été étudiées, elles sont présentées dans les sections qui
suivent.
Cette représentation linéaire est inspirée par la possibilité d'estimer la précédence entre deux
opérations de transfert en conit référant aux pénalités potentielles que ces opérations pourraient
entraîner pour le terminal. La pénalité totale potentielle ou TPP (en anglais : Total Potential
Penalty ) est déterminée pour chaque opération de transfert comme le produit en algèbre classique
du temps de traitement et du montant de la pénalité par unité de temps en cas de service tardif.
Elle représente la pénalité due par le terminal dans le cas où le traitement de chaque requête
Supposant que les tankers pour deux opérations de transfert en conit i et i0 arrivent simultané-
ment au terminal et, suivant la même notation que précédemment, ui ∈ twi , ui0 ∈ twi0 et ui = ui0 ,
alors la pénalité totale potentielle s'exprime en algèbre conventionnelle par : T P Pi = pi × ci et
Supposant qu'une priorisation peut être réalisée pour toute paire d'opérations en conit, par
exemple en comparant les TPP, l'aectation des valeurs aux variables de décision peut être
teur pour des opérations en conit n'est pas restrictive et peut être ajustée aux critères d'intérêt
selon l'application.
Pour illustrer la propriété de linéarité (max,+) du modèle, le même exemple de la Fig. 2.3 est
considéré où seul les opérations de transfert sont prises en compte. Ainsi, considérant (2.3) et
en supposant que l'horizon de planication est initialisé à t0 = 0, les expressions des contraintes
fondamentales non linéaires de partage de ressources pour cette instance sont dénies par (2.13-
2.19). L'opérateur du produit est omis (comme il est souvent fait dans l'algèbre classique) pour
soulager la notation. Par exemple, dans (2.13), le dateur x1 pour l'opération de transfert R1
dans la Fig. 2.3 dépend de la date d'arrivé du tanker (u1 ), et des conits avec les opérations R2 ,
R6 et R7 , pour lesquels l'aectation des variables de décision V1,2 , V1,6 et V1,7 déterminera les
précédences correspondantes.
Pour illustration et validation, le pire des scénarios est considéré. C'est le cas où les tankers
arrivent tous en même temps et dans leurs fenêtres de temps autorisées, e.g. ui = e et ui ∈
twi ∀i ∈ I. Les données d'entrée sont celles proposées dans le Tableau 2.2. Pour une meilleure
appréhension des résultats, les données ont été nxées telles que ∀i|0 < i < 7 ⇒ T P Pi <
T P Pi+1 . L'aectation des valeurs des variables de décision est établie sur la priorisation des
requêtes avec les TPP les plus importants et par rapport à la capacité opérative du réseau.
Il est rappelé [1] que la capacité opérative représente l'ensemble maximum d'alignements disjoints
simultanés dans le réseau. Puisqu'il est important d'exécuter autant d'opérations simultanément
que possible, les opérations avec un grand TPP et avec des possibilités d'exécution parallèle
R2 20 2000 40000
R3 20 3000 60000
R4 20 4000 80000
R5 20 5000 100000
R6 20 6000 120000
R7 20 7000 140000
Il est facile de déduire que la topologie de la Fig. 1.1 dénit une capacité opérative de 2 ali-
TPP) en parallèle avec l'opération R5 (opération simultanée possible et de TPP élevé), en re-
marquant que si R6 possède un TPP plus grand, elle ne peut être lancée simultanément avec
R7 .
d'aucune autre opération. Cette aectation se propage dans le système d'équations en rappelant
que pour chaque variable de décision Vi,i0 une variable Vi0 ,i prend sa valeur complémentaire. Par
Ensuite, les variables restantes sont déterminées par rapport au critère du TPP. Par exemple,
dans (2.14) V2,6 = e indique que R2 dépend de la date d'achèvement de R6 , puisque T P P6 >
T P P2 , ce conduit à ce que V6,2 = ε dans (2.18). Après l'aectation des variables, le système non
linéaire (max,+) (2.13-2.19) devient le système linéaire (max,+) (2.20-2.26).
x1 = x2 p2 ⊕ x6 p6 ⊕ x7 p7 ⊕ u1 (2.20)
x2 = x5 p5 ⊕ x6 p6 ⊕ x7 p7 ⊕ u2 (2.21)
x3 = x4 p4 ⊕ x5 p5 ⊕ x6 p6 ⊕ x7 p7 ⊕ u3 (2.22)
x4 = x5 p5 ⊕ x7 p7 ⊕ u4 (2.23)
x5 = u5 (2.24)
x6 = x5 p5 ⊕ x7 p7 ⊕ u6 (2.25)
x7 = u7 (2.26)
x1 . p2 . . . p6 p7 e
x . . . . p5 p6 p7 e
2
x3 . . . p4 p5 p6 p7 e
x4 = . . . . p5 . p7 ⊕ e
x . . . . . . . e
5
x6 . . . . p5 . p7 e
x7 . . . . . . . e
def
X = A∗ b A∗ = An .
L
Comme présenté dans [61], satisfait l'équation X = AX ⊕ b, où n∈N
En rappelant que le produit matriciel (max,+) est déni de manière générale comme (A⊗B)ij =
Ln m
k=1 Aik ⊗ Bkj et considérant que pour le système proposé A = ε7×7 ∀m > 3, où ε7×7 est
∗ = e ⊕ A2 ⊕ A3 ,
une matrice avec des entrées égales à ε, alors A 7×7 ⊕ A où e7×7 est la
matrice identité de dimension 7 × 7. Les résultats obtenus, en remplaçant les entrées égales à ε
par `.' pour faciliter la lecture, sont :
. . . . 40 40 40 . . . . 60 . 60
. . . . 40 . 40 . . . . . . .
. . . 40 40 . 40 . . . . . . .
A2 = . . . . . . . ; A3 = . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
Figure 2.5: Ordonnancement optimal pour le système (max,+) linéaire basé sur le T P P
e 20 . . 60 40 60
. e . . 40 20 40
. . e 40 40 20 40
A∗ = . . . e 20 . 20
. . . . e . .
. . . . 20 e 20
. . . . . . e
Ces dateurs minimisent le T CP et sont obtenus par une simple manipulation d'algèbre linéaire.
Le T CP est de $204000, puisque toutes les dates limites de service sont égales à 36 heures, i.e.
valider intuitivement que les résultats obtenus correspondent bien à ceux souhaités. Pour des
systèmes plus complexes, la procédure reste directe et permet d'obtenir facilement des dateurs
(par des produits matriciels (max,+)) pour un large ensemble d'opérations avec des conits de
rique des dateurs pour des systèmes plus complexes n'est pas envisageable par un opérateur de
Ainsi, le modèle présenté exploite une approche intuitive relevant de l'algèbre (max,+), pour
la prise en considération des dates d'arrivée des clients et de nombreux conits de partage de
ressources. Le modèle obtenu intègre ainsi une formulation unique de contraintes. En outre, à
partir d'une estimation des pénalités potentielles, le modèle linéaire réduit le problème d'opti-
misation à un produit matriciel (max,+). La proposition non linéaire nécessite d'un algorithme
déterminant la meilleure aectation des variables par rapport à la fonction objectif. Le logiciel
Les résultats de cette section sur le modèle (max,+) linéaire basé sur le TPP ont été publiés
dans [62].
gnements pour l'aectation des variables de décision visant à linéariser les contraintes exprimées
par (2.3).
Ici, la politique de routage vise à intégrer les conséquences nancières directes induites à la
fois de l'ordre d'exécution d'opérations en conit, mais aussi de la disponibilité des ressources
impliquées. L'indisponibilité de chaque alignement aecté à une opération est considérée pour
estimer les coûts qui pourrait résulter des pénalités potentielles d'un service tardif. Ainsi, une
priorisation pourra être établie entre toute paire d'opérations en conit en se basant sur la
criticité.
[63]. Dans le contexte abordé, la gravité d'indisponibilité d'un alignement (pour une opération
de transfert spécique) dépend des conséquences nancières liées aux pénalités de service tardif
pour cette opération. [63] peut être consulté pour une synthèse sur les notions de abilité, dis-
ponibilité, maintenabilité et sécurité des systèmes industriels. L'intérêt se focalise sur l'aptitude
de l'alignement à fonctionner dans l'instant de temps dans lequel il est sollicité. Notamment, son
aptitude à fonctionner sachant que le système n'est pas dans sa phase initiale d'exploitation ;
la notion de disponibilité asymptotique des vannes appartenant aux alignements en question est
disponibilité instantanée de ses ressources, et par dénition de la qualité et des moyens engagés
pour leur maintenance. La disponibilité peut résulter des conditions opérationnelles, par exemple
dans le cadre d'une `production forcée' où les activités de maintenance sont décalées du fait
disponibilité des ressources. Dans ce contexte, l'indisponibilité d'un alignement aecté à une
opération entraîne un coût en termes du retard occasionné et donc des pénalités pour le terminal.
Cette politique de routage est inspirée des travaux [64], où les activités de maintenance sont
priorisées par rapport à un indicateur basé sur l'indisponibilité de la ressource et des coûts
impliqués. Notamment, dans ces travaux, un indicateur appelé le CBC ou indicateur de criticité
basée sur le coût (en anglais : Cost-Based Criticality ) est utilisé pour classer les opérations de
maintenance. Le CBC est ainsi déni par ressource comme le produit en algèbre classique de
sans exhaustivité : l'impact environnemental, les pertes de production et les pertes de qualité.
Un indicateur similaire est proposé, permettant de réaliser une aectation des variables de déci-
sion au modèle (max,+) non linéaire. Les dateurs restent déterminés alors par des manipulations
comme dans les travaux de [65] et [4]. La conséquence nancière est considérée comme le TPP
pour chaque client. L'indicateur intégrant les aspects de coût et d'indisponibilité proposé est
P CIi = T P Pi × Ai (2.27)
Dans [4], une approche a été proposée pour déterminer le nombre maximum d'alignements
disjoints (capacité opérative) tout en minimisant le risque de non service. Cette détermination
repose sur un algorithme de ux maximum et de coût minimum. Le coût est lié à la disponibilité
des ressources et le ux est considéré comme existant ou inexistant dans les segments de pipeline.
Pour qu'un alignement puisse être habilité pour une opération de transfert, l'ensemble des vannes
d'écoulement doivent commuter vers l'état `ouvert' et les vannes d'isolement, commuter vers
l'état `fermé'. Considérant que la disponibilité lors de chaque commutation de vanne est indé-
pendante de toutes les autres et qu'elle est décrite par une variable aléatoire, une estimation de
la disponibilité d'un alignement peut être décrite comme le produit, en algèbre conventionnelle,
des disponibilités locales. Cet indicateur est déni par (2.28), où v ∈ Algni dénote les vannes
Dans le scénario présenté par la Fig. 2.1a), en considérant l'alignement répondant à la requête
R1 , la disponibilité des ressources (Ai où i = R1 ) est donnée par AR1 = A1 × A4 × A10 × A16 ×
A5 × A6 × A8 × A12 × A11 × A13 . Ceci représente la disponibilité de l'alignement à partir de la
disponibilité des vannes à ouvrir (i.e. 1, 4, 10 et 16) et des vannes à fermer (i.e. 5, 6, 8, 12, 11
Figure 2.6: Exemple pour validation du modèle (max,+) linéaire basé sur le P CI .
Y
Ai = Av (2.28)
(v∈Algni )
Dans la pratique, les valeurs de disponibilité peuvent être issues du monitoring si l'instrumen-
tation le permet. En outre, d'autres niveaux de criticité établis par les requêtes pourraient
également prioriser les opérations de transfert selon les stratégies de maintenance considérées.
Résultats
La Fig. 2.6 reprend l'exemple d'exécution de sept opérations de transfert. Dans cette gure, 3
A priori, les vannes sont aectées d'un niveau de disponibilité asymptotique identique dans leur
zone. Les vannes interzones sont caractérisées de la façon arbitraire suivante : vannes 5 et 13 ∈
Zone A, et vannes 8 et 12 ∈ Zone C. Les contraintes de conits de partage de ressources pour
cet exemple sont les mêmes que dans (2.13-2.19) et l'origine de l'horizon de planication est
considéré à t0 = 0.
Le Tableau 2.3 présente les données d'entrée pour l'exemple considéré où la dernière colonne
de la Fig. 2.6, où il est évident que l'alignement pour R3 se trouve dans la zone avec les dispositifs
Dans ce tableau, les temps de traitement sont supposés être égaux pour l'ensemble des opérations
an d'illustrer plus intuitivement les résultats. Avec ces données d'entrée, le vecteur d'indicateurs
P CI obtenu correspond à : P CI = [154, 2 166, 2 201, 0 126, 0 126, 0 252, 0 236, 8]T .
Supposant le scénario le plus serré, où tous les tankers arrivent en même temps et dans les
fenêtres de temps autorisées, tous les conits potentiels de partage de ressources deviennent réels.
Le P CI permet de résoudre ces conits sur la base d'un système d'équations (max,+) linéaire.
Pour les valeurs de P CI obtenues, l'opération R6 est dénie comme étant la plus critique. Par
conséquent, cette opération doit être lancée le plus tôt possible et ne doit pas dépendre de la
date d'achèvement d'aucune autre opération. Par conséquent V6,i = ε pour toute opération en
conit i.
Ainsi, en sachant que les conits de partage de ressources sont décrits par l'ensemble d'équa-
tions (2.13-2.19), l'aectation des variables de décision pour les conits liés à R6 correspond
à : V6,1 = V6,2 = V6,3 = V6,5 = V6,7 = ε dans (2.18), ce qui entraîne l'aectation des variables
complémentaires dans toutes les autres équations, i.e. V1,6 = V2,6 = V3,6 = V5,6 = V7,6 = e. De
manière analogue, toutes les variables de décision restantes prennent leurs valeurs par rapport
au critère de P CI . Ainsi, dans (2.13) V1,2 = e puisque l'opération R1 dépend de la date d'achè-
vement R2 , du fait que P CI2 > P CI1 , conduisant à V2,1 = ε dans (2.14), et ainsi de suite. Ainsi,
le système (max,+) linéaire suivant est obtenu :
x1 . p2 . . . p 6 p7 x u
1 1
x . . . . . p6 p7 x2 u2
2
x3 . . . . . p6 p7 x3 u3
x4 = . . p3 . . . p7 x4 ⊕ u4
x . p p p . p6 . x5 u5
5 2 3 4
x6 . . . . . . . x6 u6
x7 . . . . . p6 . x7 u7
Pour simplicité de compréhension, si les dates d'arrivée des tankers sont égales à zéro, i.e. ar-
rivée des tankers dès la date au plus tôt, alors u = [e, e, e, e, e, e, e]T et la solution au système
L'aectation de ressources est réalisée par rapport aux conditions d'exploitation du réseau et
aux coûts potentiels dérivant du dysfonctionnement des ressources. Il faut remarquer que pour
des scénarios diérents à celui présenté en Fig. 2.7 certaines opérations pourraient être exécutées
simultanément, ce qui réduirait le temps global d'achèvement des opérations. Néanmoins, cela
serait au détriment de la disponibilité des ressources et le risque pour certaines opérations prio-
ritaires serait accru. Par exemple, dans d'autres scénarios non optimaux par rapport au P CI ,
R4 pourrait être exécutée à t0 = 0 simultanément avec R6 , mais ceci réduirait la disponibilité
Figure 2.7: Ordonnancement optimum pour le modèle (max,+) linéaire basé sur le P CI
L'exploitation d'une modélisation (max,+) reste susamment intuitive pour pouvoir synthétiser
les contraintes fondamentales de fonctionnement en une relation unique. Elle permet d'exprimer
la meilleure politique de priorisation entre toute paire d'opérations en conit sur un compromis
coût/disponibilité. Les résultats de cette approche ont été publiés dans [66].
Les compromis les plus adéquats devront être choisis selon les caractéristiques et conditions
d'exploitation. L'approche (max,+) linéaire, par pré-aectation des variables de décision, permet
ainsi de manipuler des pénalités potentielles, des notions de criticité, ou sur tout autre critère de
priorisation entre deux opérations en conit. Par ailleurs, si aucun critère ne peut être envisagé a
priori on revient vers un modèle (max,+) non linéaire (2.3), pour lequel l'aectation des variables
de décision repose sur des techniques approximatives. À ce titre, une proposition basée sur les
Des modèles (max,+) non linéaires, ainsi que linéaires, ont été proposés abordant le problème
prédénis. La section suivante aborde une extension du modèle (max,+) non linéaire obtenu
lection d'Alignements
que l'alignement pour chaque opération de transfert est connu au préalable (hypothèse 2.1) et
que les variables de décision sont celles liées au partage de ressources. Dans le cadre réel de la
prise de décision dans les terminaux maritimes, l'opérateur de supervision doit également choi-
sir, à partir d'un ensemble d'opérations de transfert, l'alignement adéquat dans le réseau pour
chacune de ces opérations. La sélection d'un alignement pour une opération modie la dispo-
nibilité du réseau pour les opérations restantes. L'ensemble de ces spécications et contraintes
temporelles diérentes, fait que la sélection globale n'est pas évidente. Pratiquement, la sélection
d'alignements résulte de l'expertise de l'opérateur. Pour une prise de décision qui tienne compte
de ces nombreux aspects opérationnels et de leurs conséquences sur les délais de service des
Ce modèle est issu d'une simple mais importante manipulation mathématique qui permet
cements optima qui minimisent les pénalités globales et qui suggèrent les meilleurs alignements
pour l'ensemble des opérations envisagées. Ainsi, un degré de exibilité est ajouté au modèle
initial, puisque chaque opération n'est plus restreinte à être exécutée sur un alignement déter-
miné. Une reconguration du réseau est alors réalisée pour minimiser les coûts de l'ensemble des
opérations.
chaque requête, un alignement est sélectionné parmi un ensemble d'alignements candidats qui
satisfont les spécications de la requête. Un alignement est dit candidat pour une opération de
transfert s'il permet de transférer le type et quantité de pétrole requis à partir des réservoirs
pertinents vers les quais qui peuvent accueillir les gabarits des diérents tankers.
0 0
M
∀ ij, i j ∈ OA
xij = t0 ⊕ ui ⊕ i0 (xi0 j 0 ⊗ pi0 ⊗ Vij,i0 j 0 ) ⊗ Wij (2.29)
sélection d'alignements, et détermine le dateur pour une opération de transfert sur un alignement
OA : ensemble de tous les appariements ij possibles tel que i représente une opération de transfert
et j est un alignement candidat pour satisfaire la dite requête.
Vij,i0 j 0 : variable de décision binaire. Vij,i0 j 0 ∈ {ε, e} détermine la précédence entre 2 alignements
0 0
(j et j ) en conit satisfasant 2 opérations de transfert (i et i ). Pour toute variable Vij,i0 j 0 , il
Wij : variable de décision binaire. Wij ∈ {ε, e} permet de sélectionner l'alignement j pour la
requête i. Cette variable détermine si l'alignement j est sélectionné ou pas pour traiter la requête
s'exécuteraient avant. En connaissant la topologie du réseau, pour toute paire d'alignements, les
conits peuvent être identiés. Ces informations sont alors connues au préalable.
Dans (2.30), les valeurs possibles des variables de décision complémentaires sont restreintes, (pour
(2.29), si Vij,i0 j 0 = B , l'ensemble du terme devient négligeable ce qui implique que l'opération i
exécutée sur l'alignement j ne dépend pas de la date d'achèvement de l'opération de transfert i0
exécutée sur l'alignement j0. Au contraire, si Vij,i0 j 0 = e, alors xij se positionne après x i0 j 0 ⊗ p i0
dans l'axe temporel. D'autre part, dans (2.29), si Wij = B alors la contrainte est négligeable pour
l'appariement ij , i.e. l'alignement j n'est pas sélectionné pour la requête i. Si Ji est l'ensemble
d'alignements candidats pour la requête i, pour tous les appariements possibles ij , il y aura un
et un seul j opt ∈ Ji , pour lequel Wij opt = e, et pour lequel xij = xij opt 6= ε. L'équation (2.31)
garantit cette unicité à l'aide d'un simple mapping Wij → wij , et naturellement xij opt correspond
L
à j xij pour tous les appariements ij pour cette requête.
N L
Vij,i0 j 0 ⊗ Vi0 j 0 ,ij = B; Vij,i0 j 0 ⊕ Vi0 j 0 ,ij = e; j Wij = B; j Wij = e
(2.30)
∀ ij , i0 j 0 ∈ OA
1 if Wij = e O
wij = wij = 1 ∀j ∈ Ji ∧ ij ∈ OA (2.31)
e if Wij = ε j
Les dates limites de service pour les requêtes sont dénies comme dans le modèle non linéaire
proposé par (2.9), i.e. avec un maximum de 36 heures de chargement. Finalement, (2.32) repré-
sente la fonction objectif qui évalue le T CP (Total Cost due to Penalties ) pour toutes les requêtes
dans l'horizon de temps donné. Le terme delay est intuitivement le retard dans le service. Si des
interruptions sont prévues par le terminal ou par le client, elles peuvent être intégrées comme
dans (2.3).
nc O
delay
O
M in T CP = n=1
i
ci ∀i ∈ I (2.32)
i
Pour illustrer les résultats, la Fig. 2.8a) présente une instance pour laquelle 3 opérations de
transfert doivent être exécutées où (Ri , Pj ) dénote une requête Ri pouvant être réalisée par
réseau a une capacité opérative (calculée dans les travaux de [1] par un problème de ux maxi-
mum) égale à 2 et, comme déni dans le chapitre 1, ceci se traduit par la possibilité d'eectuer
Pour la requête R1 , 2 réservoirs contiennent le produit requis et un seul quai est accessible au
gabarit du tanker du client considéré. Ici, les 4 alignements possibles sont soulignés en bleu. Pour
R2 et R3 , un seul réservoir et un seul quai peuvent habiliter le transfert des batch demandés ce
Pour rappel, les seules vannes représentées en couleur sont les vannes d'ouverture habilitant
l'alignement considéré ; les vannes d'isolement sont omises dans la représentation. Supposant
que tous les tankers arrivent en même temps et dans leurs fenêtres de temps autorisées à la date
clients peuvent alors entraîner des pénalités pour le terminal si les dates limites de service sont
dépassées.
Avec le modèle proposé, l'ordonnancement optimum est obtenu tel que les alignements choisis
sont ceux qui permettent de mieux intégrer les opérations en minimisant le T CP . Les Tableaux
2.4 et 2.5 présentent une simulation pour 2 instances diérentes de conguration d'alignements,
pour deux scénarios. L'exemple permet une validation intuitive des résultats.
Dans la première instance, R1 est identiée de priorité forte et R3 de priorité faible. Considérant
qu'au plus 2 requêtes peuvent être traitées simultanément dans la topologie considérée, l'or-
donnancement optimum apparaît dans la Fig. 2.8b). Dans cette gure, R1 et R2 sont exécutées
simultanément avec les alignements disjoints P1 , et P6 (voir Tableau 2.4), respectivement. R3 est
traitée suite à l'achèvement de R2 par l'alignement P7 , ce qui permet une exécution en parallèle
Pour l'instance 2, l'opération R3 est prioritaire en regard de R1 . Dans les instance 2, une recon-
telles que les pénalités potentielles pour chaque client. L'ordonnancement optimum est présenté
Les deux instances permettent d'identier intuitivement les priorités entre les opérations et les
possibles sélections d'alignements pour les satisfaire en minimisant les coûts. Pour des instances
plus complexes, les interactions multiples qui surviennent du nombre de clients, d'alignements
candidats, des dates d'arrivée des tankers et des pénalités, complexient la prise de décision.
Les résultats du modèle proposé ont été publiés dans [67]. Ce modèle permet, à l'aide d'une
Ainsi, en cohérence avec les besoins réels opérationnels des terminaux maritimes, les impacts
(2.29) synthétise les conits de partage de ressources, d'arrivée des clients, et de sélection
d'alignements. Le modèle est non linéaire du fait du produit des dateurs avec des variables de
décision associées aux conits, et de celles associées à la sélection d'alignements. Une aectation
de ces deux dernières rendent le modèle linéaire et permettent de déterminer les dateurs.
Cette première phase d'étude motive l'intégration des aspects de modélisation non linéaire
(max,+) avec des techniques heuristiques pour l'aectation des variables de décision tel que
des sous-systèmes (max,+) soient obtenus à chaque itération et que la résolution matricielle
(max,+) de ces systèmes soit exploitée. Ceci fait l'objet du chapitre suivant.
Conclusions Partielles
en minimisant les pénalités subies par le terminal. Un modèle (max,+) non linéaire a représenté
de manière concise et intuitive les contraintes du problème avec deux considérations : des ali-
gnements prédénis pour les opérations de transfert et des opérations de maintenance xe. Ce
point de départ a motivé l'exploration des modèles linéaires (basés sur le TPP ou le P CI ) pour
obtenir des ordonnancements optima à l'aide de produits matriciels (max,+) pour les opérations
de transfert. Ensuite, un modèle (max,+) non linéaire étendu a permis de gérer la sélection
d'alignements sous la forme d'une contrainte pour la minimisation des pénalités. Cette dernière
représentation motive des représentations plus complexes permettant de minimiser les retards
de ces deux objectifs. À ce titre, un modèle basé sur des contraintes (max,+) et des techniques
Préambule
Ce chapitre présente une extension des modèles (max,+) obtenus précédemment dans le cadre
maintenance), ainsi que la sélection d'alignements, reposent sur une proposition basée sur des
algorithmes génétiques en intégration avec des modèles (max,+) linéaires. Les résultats visent
Sommaire
3.1 Cadre Général de la Problématique d'Optimisation Multi-Objectif . . . . . . . . . . . . . . . . . . . . . . 54
Génétiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.5 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
53
La résolution du problème est abordée par une approche d'algorithmes génétiques exploitant la
modélisation algébrique dans le cadre (max, +) développée dans le chapitre précédent. Dans
pour chaque individu (i.e. génotype), et des opérations génétiques (i.e. sélection, mutation et
Une implémentation d'une approche évolutionnaire basée sur les algorithmes génétiques est
proposée, en intégrant l'exploitation des principes mathématiques des modèles (max, +) linéaires.
un compromis entre deux objectifs visant à assister l'opérateur de supervision dans sa décision
en fonction des résultats fournis et de son expertise. Ainsi, c'est l'opérateur qui nalement décide
Les objectifs d'optimisation considérés sont les pénalités encourues par le terminal dû au service
tardif et les retards des activités de maintenance. Ces deux objectifs sont antagonistes (en conit,
car l'un améliore en détriment de l'autre) ; par conséquent, des diérents compromis entre eux
transfert de pétrole a été représentée par l'indice TCP ( Total Cost due to Penalties ) introduit
dans le chapitre précédent. D'autre part, il est admis qu'un programme de maintenance établi
par une équipe spécialisée doit être respecté, dans les possibilités de fonctionnement du système,
Dans ce qui suit, l'indice TME (en anglais : Total Maintenance Error ) représente la somme des
retards des activités de maintenance. Les dates prévues d'intervention sont données au préalable,
mais la date eective de maintenance dépend des activités de transfert. Ainsi, le lancement
d'une activité de maintenance pourrait entraîner des pénalités du fait d'opérations de transfert
en conit. Par contre, le retard de l'opération de maintenance peut avoir des conséquences sur
la abilité du dispositif en question et/ou sur les coûts d'intervention, qui doivent aussi être
Les approches formelles sont d'usage dicile dans la résolution de problèmes d'optimisation
multi-objectif du fait que l'unicité de la solution ne peut être assurée, que l'espace de recherche
augmente dû aux plusieurs objectifs à gérer, et qu'il doit être parcouru en gérant des compromis
de qualité entre les diérents objectifs. Pour pallier ces dicultés, des approches approximatives
collaboration entre plusieurs entités, chacune recherchant une solution. Ces sont des algorithmes
basés sur des populations. Sans exhaustivité sur le sujet, il peut être signalé que d'autres ap-
proches se centrent sur l'amélioration d'une seule solution comme par exemple des approches de
recherche locale.
L'espace de recherche est alors formé par l'ensemble des aectations possibles pour les va-
être fortement impactée. Ainsi, il s'agit de déterminer des compromis entre les valeurs des deux
objectifs, i.e. un ensemble de solutions optimales qui assistera à l'opérateur de supervision dans la
prise de décision. Chacune de ces solutions est représentée par un élément de type (T CP, T M E)
issu d'une sélection d'alignements pour les opérations de transfert et d'un ordonnancement de
Le choix de la méthode de résolution est motivée par rapport à un état de l'art faisant bien
cas de l'intérêt des techniques évolutionnaires. Ces techniques émulant l'évolution naturelle des
recherche de manière distribuée, sur les bases de la collaboration entre diérentes entités qui
recherchent une solution. Les algorithmes génétiques ont été sélectionnés comme technique de
2) au niveau scientique un eort très important est encore dédié à l'amélioration de ces
techniques ; et
Cette approche de résolution des problèmes d'optimisation multi-objectif est bien connue dans
qu'au laboratoire de Raisonnement et Analyse dans les Systèmes Complexes au sein de la TRT
Les travaux dans [53] sont un rappel aux notions générales de l'optimisation multi-objectif. De
façon générale, pour ces types de problème, une solution peut être dénotée comme un vecteur de
décision xi = (x1i , x2i , . . . , xni ) dans l'espace de décision X. Pour chaque vecteur de décision, une
fonction X→Y permet de déterminer sa représentation dans l'espace de critères par un vecteur
objectif yi = f (xi ) = (f1 (x1i ), f2 (x2i ), . . . , fn (xni )). Ainsi, formellement, un vecteur objectif y1
domine y2 , i.e. y1 y2 , si aucun composant de y1 n'est inférieur au composant correspondant
dans y2 , et qu'au moins un composant est supérieur. Cette notion est nommée dominance de
Pareto. Ainsi, une solution x1 est meilleure que x2 , i.e. x1 domine x2 (x1 x2 ) si f (x1 ) domine
f (x2 ).
Le problème de base repose sur le fait qu'il peut exister plusieurs vecteurs objectif optimaux
représentant diérents compromis de qualité entre les objectifs. L'ensemble des solutions opti-
males dans l'espace de décision X∗ ⊆ X est généralement appelé l'ensemble de Pareto, et son
image dans l'espace d'objectifs est appelée la frontière de Pareto, i.e. Y ∗ = f(X) ∗ ⊆ Y.
La génération de la frontière de Pareto peut être coûteuse en temps d'exécution, raison pour la-
quelle les stratégies stochastiques, tel que les algorithmes évolutionnaires, permettent de trouver
des solutions approximées (normalement dans la frontière de Pareto) dans des délais raisonnables.
Les algorithmes génétiques font partie des techniques évolutionnaires les plus développées et
recherchées pour résoudre des problèmes d'optimisation complexes s'inspirant sur l'émulation
de l'évolution naturelle des espèces. L'idée générale repose sur la génération d'une population
cette population évolue, ce qui représente le parcours de l`espace de recherche avec le but de
trouver les solutions optimales. Ainsi, cet espace de recherche est parcouru de manière distribuée.
Comme dans tout algorithme évolutionnaire, ce parcours est contrôlé par des opérateurs évolu-
la convergence vers des points optimaux en privilégiant les meilleures solutions trouvées à chaque
de tomber sur des optima locaux. Les deux opérateurs sont nécessaires, et leur correcte intégra-
tion permet d'obtenir les points optimaux visés dans des délais raisonnables. Une intensication
trop forte réduit le temps d'exécution mais peut générer comme résultat des optima locaux, et
une trop forte exploration évite des optima locaux mais pénalise fortement le temps d'exécution.
Ainsi, un `bon' paramétrage de ces opérateurs est crucial pour l'obtention des bonnes solutions
dans des délais acceptables. Ceci fait actuellement objet de nombreux travaux de recherche.
Souvent, d'importants tests de diérentes combinaisons de paramètres sont nécessaires pour ob-
tenir une conguration adaptée à l'instance traitée. Dans les algorithmes génétiques, l'opérateur
d'intensication est lié à la notion de tness de chaque individu, i.e. son aptitude à transmettre
ses gènes aux générations suivantes du fait de la qualité de solution représentée, et l'opérateur
d`exploration vise à modier, de manière aléatoire, certaines solutions pour les déplacer dans
l`espace de recherche. La phase de sélection permet, comme dans l'évolution naturelle des es-
pèces, d'assurer que les solutions avec plus de chance de survivre soient celles de tness plus
élevé. Ainsi, à partir d'une population initiale, une fonction de tness doit être dénie telle que
les individus soient classés, et puis sélectionnés, pour construire la génération suivante. Des in-
dividus de tness élevée ont plus de chance de se reproduire. Ceci est modélisé par l'opérateur
de croisement, qui génère des individus nommés `descendants' pour la prochaine génération à
partir des individus nommés `parents'. La charge génétique des individus descendants est ainsi
formée par des gènes des deux parents. Finalement, l'opérateur de mutation permet d'appliquer
des modications aléatoires à certaines parties de la solution, en vue de trouver des solutions
Les notions d'opérateurs et de structures génétiques sont illustrées dans la Fig. 3.1. La struc-
Le `phénotype', par contre, est l'interprétation ou mapping de ces données vers l'information
d'intérêt de la problématique. Finalement, un génome est déni comme une instance spécique
du génotype.
Dans la Fig. 3.1, un codage binaire du génotype est présenté comme exemple pour illustrer le
ment considéré, dans le contexte (max,+) les valeurs des variables de décision sont : éléments
neutre et nul
1 (i.e. e=0 et ε = −∞), les gènes dans le chromosome ne pourront prendre alors
que ces valeurs. De manière générale, un individu sera caractérisé par un vecteur de variables de
Ainsi, l'opérateur de mutation, par exemple, peut modier la valeur d'un gène de e à ε ou vice
versa. L'opérateur de croisement, par contre, génère des individus comportant une combinaison
Il est nécessaire au préalable que la structure d'une solution soit encodée sous la forme d'un
chromosome, i.e. le génotype doit être déni. Les principales contraintes du problème d'optimi-
sation ont déjà été déterminées de manière concise par application de l'algèbre (max, +) ; voir
(2.29-2.32). Considérant que les activités de maintenance sont intégrées au modèle dans l'ap-
proche multi-objectif, l'équation (2.29) est alors modiée pour obtenir (3.1) et, par conséquent,
(3.2) est rajoutée au modèle pour représenter les dateurs des opérations de maintenance.
L L
xi,j = t0 ⊕ ui ⊕ i0 ,j 0 (xi0 ,j 0 ⊗ pi0 ⊗ Vi,j;i0 ,j 0 ) ⊕ k (xmk ⊗ tmk ⊗ Vi,j;k ) ⊗ Wi,j
0 0 (3.1)
∀ i, j i , j ∈ OA ∧ ∀k ∈ M
M
⊗ pi ⊗ Vk;i,j ) ∀ i, j ∈ OA ∧ ∀k ∈ M
xmk = xfk ⊕ i,j (xi,j (3.2)
La plupart des éléments dans les équations (3.1) et (3.2) ont déjà été dénis dans la section 2.2.4
xi0 ,j 0 : dateur de l'opération de transfert i0 si elle est exécutée sur l'alignement j0.
xfk : date prévue de l'activité de maintenance sur la vanne k, xée dans le programme de
1. déterminant la précédence entre les opérations en conit ou l'aectation des alignements aux opérations de
transfert, voir Section 2.2.4.
Vi,j;i0 ,j 0 : variable de décision binaire (et complémentaire à la variable Vi0 ,j 0 ;i,j qui survient lors
entre l'opération de transfert i (si exécutée sur un certain alignement j) et l'opération en conit
partage de ressources et, par conséquent, ne peuvent pas être exécutées simultanément. Vi,j;i0 ,j 0
et Vi0 ,j 0 ;i,j prennent les valeurs ε = −∞ ou e = 0, sachant que Vi,j;i0 ,j 0 6= Vi0 ,j 0 ;i,j . Pour rappel,
Vi,j;k : de manière analogue, détermine la précédence entre l'opération de transfert i (si exécutée
sur un certain alignement j ) et l'opération de maintenance sur la vanne k . De manière analogue,
Vi,j;k et Vk;i,j ∈ {ε, e}, sachant que Vi,j;k 6= Vk;i,j .
tmk et pi0 : durées d'une opération de maintenance sur la vanne k et d'une opération de transfert
0
i , respectivement.
Wi,j : variable binaire de décision déterminant l'aectation (ou pas) de l'alignement j à l'opéra-
tion de transfert i. La valeur de cette variable rend eective ou négligeable toute la contrainte
(3.1) puisque les conits modélisés pour obtenir le dateur (et par conséquent, l'ordonnancement)
ne sont eectifs que comme conséquence du choix de cet alignement. Wi,j prend la valeur de
L
Comme dans la section 2.2.4, naturellement, xi,j opt correspond à j xi,j pour tous les apparie-
la section suivante sous forme d'une approche d'algorithme génétique, en cohérence avec le
workow de la Fig. 3.2. Tout d'abord, la structure d'un individu (solution) doit être dénie
croisement) sont dénis pour la structure proposée pour chaque individu. Ensuite, une stratégie
doit être dénie pour comparer les individus vis-à-vis d'un classement qui dénira l'évolution de
la population. Cela est issu de l'évaluation des individus par rapport à des indicateurs liés aux
objectifs d'optimisation, tenant compte qu'il s'agit d'un problème d'optimisation multi-objectif.
Figure 3.2: Workow général pour la formulation du problème multi-objectif par une approche
d'algorithmes génétiques.
Dans la formulation du problème sous forme d'approche génétique, le premier aspect à dé-
nir est la structure génomique, i.e. comment représenter les solutions sous une abstraction de
Tout d'abord, diverses structures génomiques sont décrites et ensuite une structure génomique
Dans les travaux de [68], diérents types de codages génétiques sont présentés : le codage binaire
(BGA : Binary Genetic Algorithms en anglais) où les gènes prennent des valeurs de 0 ou 1 et
forment, dans un chromosome, une valeur associée à la solution (e.g. une distance ou un coût) ; le
codage réel (RGA : Real Genetic Algorithms en anglais) où la représentation de chaque gène est
en point ottant, ce qui permet d'accélérer le temps d'exécution ; et le codage structuré (SGA :
Structured Genetic Algorithms en anglais) où les chromosomes sont des structures hiérarchiques
avec codage binaire, et les gènes d'un haut niveau contrôlent les gènes d'un niveau inférieur.
Cette dernière structure génomique est d'un intérêt particulier puisque, même si elle peut être
des valeurs des variables de décision, notamment pour traiter des inter-dépendances.
Dans cette approche structurée, un changement dans un gène de haut niveau entraîne plusieurs
changements dans les gènes de niveau inférieur. Dans les algorithmes génétiques classiques, ce
comportement ne pourrait être obtenu qu'avec une séquence de nombreux changements aléa-
toires. Finalement, dans [68], les RSGA ou algorithmes génétiques avec codage réel et structuré
(en anglais : Real-Coded Structured Genetic Algorithms ) sont décrits et appliqués à la conception
des ltres numériques et des contrôleurs. Les RSGA combinent la représentation structurée et le
codage réel, pour formuler une représentation génomique dans laquelle les gènes de haut niveau,
aussi appelés gènes de contrôle modient directement un des gènes de niveau inférieur, aussi
appelés gènes de paramétrage ainsi chaque gène du chromosome prend une valeur réelle.
La Fig. 3.3 schématise les structures SGA et RSGA. Les RSGA améliorent la performance de
l'algorithme à partir de la représentation de chaque génome, tel que si dans les SGA les gènes
de plus haute hiérarchie modiaient plusieurs gènes de niveau inférieur pour coder une valeur
réelle, dans les RSGA chaque gène de contrôle modie la valeur de son gène de paramétrage
Figure 3.3: Schémas de représentation de l'information dans les algorithmes génétiques struc-
turés.
La Fig. 3.3a) présente, selon [68], une structure hiérarchique de génotype où, par exemple, le
gène a1 contrôle les valeurs des gènes a11 , a12 et a13 . Puisqu'il s'agit d'une codication binaire,
l'ensemble des gènes ne prennent que les valeurs 0 ou 1. Dans cette structure, chaque sous-
représenterait le numéro 5 en base décimale. Ainsi, le codage binaire implique l'aectation d'une
suite de valeurs aux gènes de paramétrage, en vue de l'obtention d'une valeur d'intérêt dans le
problème d'optimisation. Par contre, le codage réel considère que chaque gène caractérise déjà
la valeur d'intérêt (Fig. 3.3b)). Les RSGA réduisent le temps de calcul, ainsi que la longueur des
chaînes utilisées pour décrire chaque chromosome. En outre, un gène de paramétrage prend une
certaine valeur dépendant de la valeur de son gène de contrôle, cette valeur peut correspondre
à son activation, désactivation ou à une variation linéaire de sa valeur. Ainsi, lorsqu'un gène
de contrôle change dans une génération spécique, il peut entraîner un changement dans le
gène de paramétrage correspondant. Son activation implique qu'il conserve la même valeur pour
la génération suivante, la variation linéaire implique qu'il change de valeur par rapport à une
fonction linéaire dénie au préalable, et sa désactivation implique que sa valeur ne sera plus
prise en compte pour les générations suivantes, n'ayant alors plus d'inuence sur le processus
d'évolution.
La structure génomique vise à dénir les gènes nécessaires pour représenter un individu ou
solution du problème d'optimisation. En outre, les interactions entre ces gènes sont dénies par
L'idée fondamentale est de distinguer des variables de décision qui jouent un rôle dans l'aecta-
tion d'alignements aux opérations de transfert (interprétées comme des gènes de structure, i.e.
Wi,j dans (3.1)), et des variables de décision qui jouent un rôle dans l'ordonnancement d'opéra-
tions (interprétées comme des gènes de paramétrage, i.e. variables Vi,j;k , Vk;i,j , Vi,j;i0 ,j 0 et Vi0 ,j 0 ;i,j
dans (3.1) et (3.2)). La structure mathématique de l'équation (3.1) met en évidence que la va-
riable Wi,j valide ou non la contrainte de partage de ressources dans le problème d'optimisation
pour une paire i, j donnée. Ainsi, dans (3.1), si Wi,j = ε, alors l'ensemble de la contrainte tend
vers −∞ (i.e. xij → −∞), car l'alignement j n'est pas choisi pour l'exécution de la requête i.
Comme la contrainte (3.1) modélise les conits de partage de ressources qui surviennent lors de
la sélection de l'alignement j pour l'opération i, ces conits ne sont plus eectifs si l'alignement
n'est pas choisi (et les variables de décision qui les modélisent ne sont plus pertinentes dans le
modèle). Par contre, si l'alignement est choisi, la contrainte comportera bien les termes concer-
nant les conits de partage de ressources et les valeurs de ces variables seront considérées. Il
faut remarquer ainsi que le caractère structurel des variables de sélection d'alignements a un
impact sur les variables de décision pour l'ordonnancement. Plus spéciquement, lorsqu'un un
alignement est sélectionné, il peut entraîner des conits de partage de ressources avec d'autres
L'exemple de la Fig. 3.4 vise à illustrer la structure hiérarchique proposée pour la dénition du
génotype du problème. Dans cette gure, deux requêtes doivent être exécutées, deux alignements
sont possibles pour chacune d'entre elles et une maintenance est prévue sur l'une des ressources.
Supposant que tous les conits potentiels deviennent eectifs, i.e. les deux tankers arrivent au
début de l'horizon de temps et l'opération de maintenance sur la vanne 13 doit être eectuée à
la même date, alors les contraintes fondamentales du système sont représentées de (3.3) à (3.7).
x1,1 = u1 ⊕ (x2,3 ⊗ p2 ⊗ V1,1;2,3 ) ⊕ (xm13 ⊗ tm13 ⊗ V1,1;13 ) ⊗ W1,1 (3.3)
x1,2 = u1 ⊕ (x2,4 ⊗ p2 ⊗ V1,2;2,4 ) ⊕ (xm13 ⊗ tm13 ⊗ V1,2;13 ) ⊗ W1,2 (3.4)
x2,4 = u2 ⊕ (x1,2 ⊗ p1 ⊗ V2,4;1,2 ) ⊕ (xm13 ⊗ tm13 ⊗ V2,4;13 ) ⊗ W2,4 (3.6)
Les variables de décision dans le système d'équations (3.3-3.7), pour l'exemple de la Fig. 3.4, sont
transposées sur la structure génomique proposée dans la Fig. 3.5. La structure génomique est
hiérarchique avec une caractérisation des variables de sélection d'alignements (i.e. Wi,j ) comme
des gènes de contrôle, et des variables de décision (i.e. Vi,j;i0 i0 , Vij;k ou ses complémentaires)
Dans le cadre SGA (Fig. 3.3a)), le changement de valeur d'une variable de haut niveau peut
générer plusieurs changements de valeurs des variables de niveau inférieur (èches en noir). La
Fig. 3.5a) présente la structure hiérarchique pour l'exemple de la Fig. 3.4 décrit par les équa-
tions (3.3-3.7) ; les èches reliant les variables indiquent le sens du contrôle. Ainsi, les gènes
de plus haut niveau contrôlent certains gènes de paramétrage. Néanmoins, à diérence des ap-
proches SGA et RSGA, un contrôle est aussi établi entre certains gènes de paramétrage (èches
en rouge) et entre certains gènes de contrôle (èches en bleu) concernant les variables complé-
mentaires. Notamment, les approches consultées ne considèrent pas ce type de contrôle dans un
même niveau ; néanmoins, pour le problème adressé, cette manipulation permet d'exploiter les
Dans la Fig. 3.5, les èches bidirectionnelles indiquent l'existence d'un contrôle dans les deux
sens. La notion de base pour cette structure hiérarchique stipule que les valeurs des variables
de sélection d'alignements déterminent la pertinence ou pas des variables de décision pour les
opérations en conit. Il est aussi convenu que chaque valeur de variable de décision de conit
A et B en conit : si A est prioritaire, il est établi que B n'est pas prioritaire). Ces va-
activé, peut désactiver les autres gènes de contrôle pour la même requête, ce qui traduit le fait
que pour une requête, si un alignement est sélectionné, les autres sont rejetés.
Ainsi, dans la Fig. 3.5a), si W1,1 = e alors les conits de partage de ressources exprimés dans
pertinente dans la résolution du problème, et implique que les variables V1,1;2,3 et V1,1;13 doivent
être aectées puisque l'alignement 1 a été sélectionné. De même, si V1,1;2,3 = e (la requête 2 sur
l'alignement 3 s'exécute avant la requête 1 sur l'alignement 1), automatiquement la variable com-
plémentaire V2,3;1,1 acquiert la valeur ε (qui indique dans (3.5) que la requête 1 sur l'alignement 1
s'exécute après la requête 2 sur l'alignement 3). Par contre, si au niveau supérieur W1,1 = ε, cela
implique que la contrainte (3.3) n'est plus pertinente dans la résolution du problème car comme
l'alignement 1 n'a pas été sélectionné pour la requête 1, alors les conits potentiels sous-jacents
ne surviennent pas. Dans ce cas, toutes les variables de décision associées sont négligeables pour
le traitement du problème.
La propagation d'aectation des valeurs du niveau supérieur génétique vers le niveau inférieur
a été décrite, ainsi que la propagation dans le niveau inférieur grâce au variables de décision
complémentaires. Néanmoins, cette propagation au même niveau survient aussi pour les variables
de sélection d'alignements. Pour l'exemple présenté, avec 2 alignements possibles par requête, si
La Fig. 3.5b) représente le génome pour la structure considérée avec un contrôle génétique
1. Pour chaque opération de transfert, un des gènes de contrôle est aecté de la valeur e
représentant la sélection d'un alignement donné. Ainsi, aléatoirement pour l'opération
W2,3 = ε. Dans la Fig. 3.5b), les alignements rejetés sont illustrés par des gènes en rouge
et sont dénotés comme `désactivés'. La désactivation d'un gène de contrôle (par un autre
gène) est représentée par une èche segmentée. Le facteur aléatoire de cette étape repose
sur l'activation d'un seul gène de contrôle pour chaque requête i parmi Ji alignements
possibles.
2. Les gènes de contrôle désactivés produisent une réaction en chaîne de désactivation des
gènes de paramétrage (représentée par des lignes segmentées), et les gènes de paramétrage
désactivés ont la faculté de désactiver simultanément ses gènes complémentaires. Tous les
3. Les gènes de contrôle qui restent actifs (i.e. de valeur égale à e) habilitent ses gènes de
paramétrage à des valeurs aléatoires dans l'ensemble {e, ε}. Ces gènes actifs détermine-
[68], les gènes de paramétrage rejetés de la solution sont représentés avec une valeur égale
à ∅ pour indiquer une désactivation. Ceci indique simplement que la valeur du gène n'a
La Fig. 3.5d) présente la solution qualitative caractérisée par le chromosome. Le gènes de struc-
pour les requêtes 1 et 2, respectivement. Cette sélection d'alignements est présentée dans la Fig.
3.5d) dans l'axe des ordonnées (i.e. appariement requête-alignement). Du fait de l'activation
de gènes de structure, les gènes de paramétrage activés représentent, par rapport au génotype,
structure, les conits de partage de ressources surviennent entre chacun des alignements choisis
et l'opération de maintenance sur la vanne 13. Les valeurs des gènes de paramétrage indiquent
que la requête 1 est exécutée avant l'opération de maintenance (i.e. V1,1;13 = ε et V13;1,1 = e)
et que l'opération 2 est exécutée également avant l'opération de maintenance (i.e. V2,4;13 = ε et
V13;2,4 = e). Ainsi, aucun conit n'émerge entre les 2 alignements choisis, ce qui implique que
les opérations de transfert peuvent être exécutées simultanément. Les conits pour les opéra-
tions peuvent être déduits directement de la Fig. 3.4, ainsi que les alignements choisis sont des
alignements disjoints. Cette solution (Fig. 3.5d) montre alors un ordonnancement qualitatif où
solution du problème, même si l'ordonnancement reste qualitatif puisque les requêtes sont de
Solution au problème : une solution ou individu est encodé en termes de variables ca-
au moins une désactivation d'un gène de paramétrage, qui simultanément désactive son
pour le chromosome entier tel que éventuellement les contraintes soient satisfaites. De
qui sortent de l'espace de faisabilité, an qu'elles soient éventuellement rejetées pour
les générations suivantes ; [69] peut être consulté pour une description plus détaillée des
pourraient dénir un individu (i.e. 14 gènes aectés avec 2 valeurs possibles). Ici, du fait
sont possibles pour les gènes de contrôle, et 4 possibilités d'aectation pour les gènes de
Comme proposé dans [68], il est retenu que dans la phase initiale d'évolution, une modication
génétique de la structure des solutions (gènes de contrôle) soit appliquée. Par contre, vers les
générations nales, la modication génétique vise les paramètres, qui améliorent la qualité des
solutions correspondants aux structures déjà identiées comme étant les plus intéressantes.
l'algorithme. Sachant que, si |Ji | est le nombre d'alignements candidats pour la requête i, le
génome aura autant de gènes de contrôle pour cette requête. L'implémentation de l'opérateur
de mutation est proposée ensuite selon le comportement déclenché sur les gènes de structure et
Gènes de Structure :
Un changement de valeur d'un gène de structure pour une requête entraîne le changement opposé
sur un des gènes de contrôle pour la même requête, i.e. si l'alignement sélectionné initialement
n'est plus choisi, alors un autre alignement doit être sélectionné (ou le cas contraire). La Fig.
3.6 illustre l'opération de mutation sur les gènes de contrôle considérant le codage issu de la
Fig. 3.5. Tout d'abord, la solution courante montre une sélection des alignements 1 et 4 pour
les requêtes 1 et 2, respectivement (i.e. ces gènes de structure prennent la valeur e). Ensuite,
la mutation est appliquée, le premier gène est alors modié par sa valeur opposée (i.e. ε) et le
génome devient endommagé, signiant qu'aucun alignement n'est choisi pour la requête 1. La
réparation du génome se fait en propageant l'eet de la mutation sur le gène en question vers
ses gènes de contrôle complémentaires. Comme dans l'exemple de la Fig. 3.6, chaque requête
n'a que deux alignements possibles, la propagation se fait directement sur la seule variable
restante pour la même requête (i.e. changement ε→e dans le deuxième gène de structure), et
le génome est réparé au niveau de structure. Par contre, pour un changement initial du type
ε → e, il s'agit de changer la valeur du seul gène complémentaire aecté par e (i.e. changement
e → ε). Cette procédure rend le génome correct par la propagation des eets de mutation sur
les gènes de structure. Néanmoins, pour plus de deux alignements par requête, si le changement
initial est du type e → ε, il faut choisir aléatoirement un des gènes de contrôle restants pour la
Gènes de paramétrage :
Considérant qu'une mutation correcte (i.e. avec réparation si nécessaire) est déjà appliquée sur
les gènes de contrôle, la mutation doit être propagée vers les gènes de paramétrage. Cela implique
la désactivation des gènes de paramétrage associés aux gènes de contrôle qui ont été désactivés
(i.e. ces gènes de paramétrage ne sont plus considérés dans la solution). Dans l'exemple de
la Fig. 3.6, le premier gène de contrôle a été désactivé, indiquant que l'alignement 1 n'est plus
sélectionnée pour la requête 1. Par conséquent, ses gènes de paramétrage, qui sont les variables de
décision pour les conits entraînés par l'alignement 1, doivent être désactivés puisque ses conits
deviennent inexistants. De manière analogue, comme le gène de contrôle 2 est activé suite à la
réparation du génome, ceci signie que l'alignement 2 est alors sélectionné pour la requête 1
et les variables de décision pour les conits entraînés par l'alignement 2 doivent être aectées
aléatoirement (i.e. activation des gènes de paramétrage). Un changement de valeur dans un gène
Fig. 3.6 illustre cette propagation qui produit un nouvel individu : autre solution candidate. Un
deuxième type de mutation sur les gènes de paramétrage peut survenir. Cette mutation (qui
n'est pas issue de la propagation d'une mutation des gènes de contrôle) vise à optimiser les
paramètres pour une structure qui a déjà vécu un certain nombre de générations (ce qui indique
qu'il s'agit d'une structure optimale). Cette mutation est représentée par le même principe des
valeur, son gène complémentaire changera également de valeur, menant à une solution cohérente
physiquement.
Une population initiale avec un haut niveau de diversité, et un bon paramétrage des opérateurs
de mutation et croisement (dénition des probabilités respectives) devra évoluer de telle sorte
que les individus caractérisant des structures optimales obtiendront des valeurs de tness plus
élevées, conduisant au passage de ces gènes aux générations suivantes. La réalisation d'un bon
paramétrage n'est pas forcément évident et des essais successifs sont souvent nécessaires.
Figure 3.6: Mutation des gènes de contrôle et propagation vers les gènes de paramétrage -
exemple.
Comme pour l'opérateur de mutation, un croisement des gènes de structure entraîne des change-
ments dans les gènes de paramétrage correspondants. L'idée sous-jacente est qu'à partir de deux
chromosomes ou individus nommés parents, deux individus descendants sont générés avec une
combinaison des caractéristiques génétiques de ses parents. Deux cas peuvent survenir, soit les
parents ont une structure diérente ou identique. Dans le premier cas, le croisement génère des
trage. Dans le deuxième cas, le nouvel individu diversie la population en termes de paramétrage
tout en conservant la même structure. Considérant le facteur aléatoire associé à cet opérateur
caractéristique génétique a bien persisté lors de l'évolution et qu'elle représente une structure
optimale. Par conséquent, dans les générations suivantes le croisement génère des individus avec
structure optimale identique en variant les gènes de paramétrage pour trouver un paramétrage
optimal, ce qui se traduit par une recherche de l'ordonnancement optimal d'opérations, sachant
que la sélection d'alignements optimale a été trouvée. Les deux cas possibles de croisement sont
décrits ensuite.
1. Si les parents possèdent de gènes de contrôle diérents, les descendants héritent d'une
structure `mélangée' qui déclenche une série de changements dans les gènes de paramé-
trage. Comme cela a été indiqué pour l'opération de mutation, les gènes de structure
les gènes de paramétrage qui restent à dénir, un choix aléatoire est réalisé, toujours
la Fig. 3.7, où la structure du génotype (Fig. 3.4) est rappelée. Chaque parent caractérise
une solution qui est décrite par son chromosome, cette solution implique la sélection
est présentée à droite de la Fig. 3.7. Les descendants dérivés sont des chromosomes
issus d'une combinaison des caractéristiques structurelles des parents et les gènes de
paramétrage à activer (dû au changement des gènes de structure) sont aectés de manière
aléatoire.
des descendants de même caractéristique structurelle. Les gènes de paramétrage sont ainsi
Figure 3.7: Opération de croisement avec des parents ayant des structures diérentes appliquée
à l'exemple de la Fig. 3.4.
Dans la Fig. 3.7, à chaque chromosome correspond une solution pour l'instance considérée.
Chaque parent caractérise une solution diérente et donne lieu à 2 autres solutions (i.e. les
descendants) par l'opération de croisement. Le point de croisement est illustré par une ligne
rouge dans les gènes de structure des parents. Pour cet exemple, cette position est le seul point
cohérent possible puisque il n'y a que deux requêtes à traiter. Lorsque plus de 2 requêtes sont
à traiter, le point de croisement est établi comme un point aléatoire localisé exclusivement dans
les gènes de structure (i.e. gènes de contrôle), tel qu'il distingue les gènes associés à des requêtes
diérentes. Ceci évite des génomes endommagés dans les descendants tels que, par exemple, pour
une requête spécique, tous les gènes soient désactivés ou plusieurs gènes soient activés.
Un croisement de gènes de paramétrage n'est pas considéré car ces gènes dépendent directement
des gènes de structure. Un croisement de gènes de paramétrage résulterait, dans la plupart des
lien avec les ressources déjà aectées (par les gènes de structure). Par exemple, si les alignements
1 s'eectue sur l'alignement 2 avant que l'opération 2 ne s'eectue sur l'alignement 4. Ceci n'est
pas cohérent avec les gènes de structure. En outre, d'autres incohérences pourraient survenir
Pour l'opération de croisement dans la Fig. 3.7, les gènes de structure du premier descendent D1
combinent la première partie du parent P1 et la deuxième partie du parent P2 . Le descendant
des descendants, à partir de ces gènes de structure, certains gènes de paramétrage sont désactivés
(pour les gènes de contrôle inactifs) et les autres sont initialisés aléatoirement en cohérence avec
À ce stade, le génome est déni, chaque individu représente une solution de sélection d'aligne-
règles de manipulation des gènes ont été établies dans l'application des opérations de mutation
et de croisement. Le Tableau 3.1 synthétise le comportement proposé pour ces opérations. Un in-
dividu est ainsi complètement déni, ce qui permet la dénition des règles d'évolution de chaque
individu dans le cadre de sa population. Cette stratégie évolutionnaire est dénie dans la section
suivante.
2) le génome endommagé est réparé au niveau de séparant 2 requêtes dans les gènes
paramétrage. Les gènes à activer sont aectés par 3) Les gènes de paramétrage activés
Les algorithmes génétiques peuvent déterminer la meilleure aectation des variables de décision
dans les modèles non linéaires (max,+). Le modèle algébrique (max,+) déjà obtenu doit être
que les contraintes des dateurs dans le système correspondent à (3.1) et (3.2), et qu'elles de-
viennent linéaires lors de l'aectation de ces variables, alors chaque individu génère un système
émerge la notion d'intégration des modèles (max,+) avec l'approche d'algorithmes génétiques.
La stratégie évolutionnaire est la manière dont l'ordre partiel (i.e. yi yj ou relation de domi-
nance entre solutions diérentes) de la population peut être exploité pour trouver des solutions
meilleures à chaque génération. Cet ordre partiel peut être obtenu à l'aide de la notion de do-
minance de Pareto. Dans le contexte mono-objectif, la notion de tness est souvent équivalente
à la valeur de la fonction objectif. Dans le contexte multi-objectif, cette notion de tness d'un
individu est associée à plusieurs objectifs, ainsi qu'à la relation de qualité entre l'individu en
question et les autres individus de la population. Dans ce cadre, de nombreuses stratégies évo-
lutionnaires permettent de déterminer la tness d'un individu. Les travaux de [53] donnent une
vue générale des diverses propositions. Parmi les plus connues, les stratégies basées sur le rang,
la valeur de tness par rapport au nombre d'individus par lesquels un individu est dominé. La
de tness par rapport à la profondeur, qui indique à quelle frontière chaque individu appartient.
Le nombre de dominance détermine la tness d'un individu par rapport au nombre d'individus
qu'il domine.
lisent la notion de densité, i.e. la probabilité de sélection pour un individu diminue lors que la
densité d'individus dans son voisinage augmente. Parmi les techniques de gestion de densité se
trouvent les histogrammes, le voisin le plus proche, et les techniques de kernel ; le lecteur peut
Au même titre que la diversité et la tness, l'élitisme est un des aspects déterminants dans le
processus d'évolution. L'élitisme consiste à éviter que de bonnes solutions soient perdues lors
du processus d'évolution. Cet aspect est souvent géré à travers d'une archive des meilleures
sélectionner les individus pour les opérations génétiques) et l'élitisme, de nombreuses stratégies
évolutionnaires ont été développées et testées dans la littérature. Elles continuent à être un centre
d'intérêt dans la recherche de l'intelligence articielle. Sans être exhaustif, un rapide aperçu
est retenu : le VEGA (Vector-Evaluated Genetic Algorithm ), PAES (Pareto Archived Evolution
Strategy ), NSGA (Non Dominated Sorted Genetic Algorithm ), NPGA (Niched Pareto Genetic
Algorithm ) et le SPEA (Strength Pareto Evolutionary Algorithm ). Chacune d'entre elles gère
de manière distincte la politique de classement d'individus, ainsi que les aspects d'élitisme et
diversité. La stratégie SPEA a été sélectionnée du fait de son principe de fonctionnement assez
direct détaillé plus bas. Une recherche exhaustive sur le comportement des diérentes stratégies
évolutionnaires n'est pas le but de ce travail. Ainsi, d'autres choix pourraient être valables pour
comme le montre [57]. Il propose de considérer l'évolution de chaque individu par rapport à sa
force (` strength ' en anglais). Pour chaque individu, cet indicateur comptabilise le nombre d'in-
dividus dominés par l'individu en question. De manière générale, la force de chaque individu
permet de calculer l'indicateur dénoté en anglais comme raw tness (les détails sur sa déter-
mination sont présentés plus bas après l'algorithme). Ici, pour faire référence à cet indicateur,
le terme tness pure sera employé. La tness pure, liée à un indicateur de densité, permet de
calculer la valeur de tness de l'individu an de déterminer s'il s'agit d'un individu dominé ou
Ainsi, la valeur de tness, pour chaque individu de la population, détermine si les caractéris-
tiques génétiques de cet individu seront retenues pour les générations qui suivent. L'algorithme
SPEA2 est une version améliorée de l'algorithme SPEA. Les aspects améliorés ne sont pas
objet d'analyse ici, mais incluent principalement l'intégration d'une estimatio de densité
pour mieux guider la recherche, [57]. Le principe de base de l'approche SPEA2 est qu'une
population initiale est générée et celle-ci évolue au cours des générations suivantes. Pour
chacune de ces générations, une archive est conservée en parallèle stockant les individus les
plus forts (ou plus adaptés) trouvés lors de l'évolution, pour éviter que certaines solutions
tions. La structure générale de l'algorithme SPEA2 (proposée dans [57]) est décrite ensuite,
suivie d'une explication détaillant chacune des phases et les calculs pour les indicateurs employés.
N : taille de l'archive
1. Initialisation : Générer une population initiale P0 et créer l'archive vide (ensemble externe)
P0 = ∅. Fixer t=0 (i.e. première génération).
2. Aectation de Fitness : Calculer les valeurs de tness pour les individus dans Pt et Pt .
3. Sélection Environnementale : déterminer les individus non dominés contenus dans Pt et Pt
et les copier dans Pt+1 . Si la taille de Pt+1 dépasse N , alors réduire Pt+1 par un opérateur
de troncation. Par contre, si la taille de Pt+1 est inférieure à N, alors terminer de remplir
4. Interruption : Si t≥T ou un autre critère d'arrêt est satisfait, alors A est l'ensemble des
vecteurs de décision représentés par les individus non dominés dans Pt+1 . Arrêter.
au pas 2.
Dans la méthodologie présentée pour l'algorithme SPEA2, la phase d'initialisation est directe ;
une population et une archive vide sont créées. Dans cette population, chaque individu a le
type de structure proposée dans la Fig. 3.5b). De cette structure, les contraintes des valeurs
possibles pour les variables de décision, i.e. e ou ε, sont déjà prises en compte lorsque le génotype
approprié est déni. Ces contraintes couvrent les variables de décision de résolution de conits
pour les conits entre les opérations de maintenance et de transfert, sont dénies de manière
Conservant la notation de [68], un individu quelconque est dénoté par i. Cette notation n'intro-
duit pas d'ambiguïté avec les requêtes de transfert (aussi dénotées i dans ce document) puisqu'elle
n'est utilisée que pour dénir la méthodologie générale de l'algorithme dans cette section.
Dans l'étape 2 de l'algorithme, la valeur de tness pour chaque individu est déterminée. Pour
cela, premièrement la force de chaque individu i doit être déterminée par (3.9) où Pt représente
d'un individu est eectuée sur l`ensemble des individus de la population et de l'archive actuelle.
La tness pure d'un individu i est déterminée comme la somme des forces des individus j qui
dominent l'individu i (voir (3.10)). Il faut noter que dans ce cadre mathématique, le but est de
X
R(i) = S(j) (3.10)
j∈(Pt +Pt )
ji
Plusieurs individus peuvent avoir la même valeur de tness pure. Pour les discriminer, la no-
tion de densité est appliquée. La densité est calculée dans (3.11), où σik représente la distance
euclidienne dans l'espace d'objectifs jusqu'au voisin k pour chaque individu i. Le voisin k est
p
souvent estimé avec k= N + N, [57]. Ainsi, pour chaque individu i, la distance de chacun de
ses voisins j (dans la population, ainsi que dans l'archive) est déterminée et stockée dans une
liste. Cette liste est mise en ordre de manière croissante, et la position k de la liste est prise en
k
compte pour obtenir σi . Le dénominateur dans (3.11) est déni de façon à éviter la division par
sion, il est claire que la stratégie évolutionnaire vise alors à minimiser F (i).
Une fois les valeurs de tness aectées à tous les individus de la population et de l'archive, le
processus de sélection peut être appliqué. Notamment, la sélection environnementale est dénie
par (3.13). Elle consiste à extraire les meilleurs individus de la génération pour appliquer ul-
térieurement des opérateurs génétiques et créer une nouvelle génération, sachant que l'archive
Si le nombre d'individus non dominés (i.e. individus pour lesquels F (i) < 1) est égal à la taille
de l'archive, cette sous-procédure s'achève. Sinon, deux situations peuvent survenir : selon que la
taille de l'ensemble soit supérieure ou non à la taille de l'archive. Dans le premier cas, les meilleurs
N − |Pt+1 | individus dominés sont copiés dans l'archive. Par contre, si le nombre d'individus non
dominés dépasse la taille exigée pour l'archive, une procédure de troncature est appliquée pour
Une fois eectuée la sélection environnementale, la condition d'arrêt de l'algorithme est évaluée et
si elle est vraie, alors l'archive Pt+1 contient les meilleurs individus. Par contre, si l'exécution de
l'algorithme continue, la sélection d'accouplement est eectuée. Cette étape implique la sélection
aléatoire de deux paires d'individus pour déterminer pour chaque couple l'individu le plus fort, en
vue de faire passer ses gènes à la génération suivante. Pour ces deux individus choisis, l'opération
de croisement est eectuée avec une probabilité pc , i.e. probabilité de croisement, dénie comme
paramètre de l'algorithme. Le croisement génère 2 descendants qui remplaceront les parents dans
la prochaine génération. Ensuite, l'opérateur de mutation est appliqué, aussi avec une probabilité
de mutation pm dénie aussi en tant que paramètre de l'algorithme. Cette opération permet de
Chaque individu représente une solution caractérisée par 2 valeurs pour les fonctions objectif
du TCP et du TME. Ces valeurs sont déterminées par les dateurs du système. Ces dateurs
sont à la fois calculés en fonction d'une aectation de variables de décision par (3.1) et (3.2).
Ainsi, sachant que chaque individu représente une solution d'aectation des variables de décision
algébrique (max,+) non linéaire, générer des individus caractérisant des valeurs pour les variables
de décision et, pour chaque individu, résoudre le système d'équations (max,+) linéaire résultant
pour obtenir les dateurs. Les dateurs déterminent les valeurs des fonctions objectif, ainsi que
les valeurs de tness qui permettent d'appliquer la variation génétique, obtenir une nouvelle
population et répéter la procédure de manière itérative. Cette procédure est décrite en détail
ensuite.
algébrique en (max, +) par (3.1) et (3.2) ; voir bloc 1 : `Modèle (Max,+) Non Linéaire' sur
la Fig. 3.8. Comme indiqué, cette modélisation est concise, intuitive, et couvre des aspects de
diérentes natures tels que la gestion de partage de ressources, les dépendances d'arrivée du
Ensuite, la génération de la population initiale (bloc 2) est réalisée par aectation aléatoire des
(voir (2.30) et (3.8)), ce qui assure d'éviter de s'éloigner des solutions de l'espace de faisabilité.
Figure 3.8: Flux d'exécution de l'algorithme SPEA2 avec des opérations en algèbre (max, +).
Une fois les individus générés, comme conséquence de l'aectation des variables de décision,
un modèle (max,+) linéaire se déduit des équations non linéaires (3.1) et (3.2). Le système
d'équations obtenu est du type X = AX ⊕ B qui peut être résolu par l'opération X = A∗ B (voir
∗ def An . Ce calcul est eectué par utilisation de la boîte à outils (max,+) dans
L
[61]) où A = n∈N
Scicoslab. Le résultat est un vecteur de dateurs X (dates de démarrage des opérations) pour
chacun des individus (bloc 3). Ce vecteur permet de calculer les valeurs des fonctions objectif :
T CP et TME (bloc 4). Chacun de ces vecteurs représente une solution candidate au problème.
Une fois que chaque individu a été aecté de son vecteur de dateurs X , les relations de dominance
de Pareto peuvent être déterminées pour tous les individus de la population. Ainsi, la force de
chacun est déterminée selon (3.9), voir bloc 5. Ensuite, les valeurs de tness pure (bloc 7) et
densité (bloc 6) sont calculées selon (3.10) et (3.11), respectivement. Finalement, la valeur de
L'algorithme se poursuit en réalisant la sélection des meilleurs individus dans l'archive (bloc 9)
et si la condition d'arrêt n'est pas atteinte, la sélection d'accouplement est eectuée (bloc 10)
et les opérateurs génétiques sont appliqués (bloc 11). Une nouvelle génération est alors obtenue
pour laquelle le vecteur de dateurs pour chaque individu est nouvellement calculé.
3.5 Résultats
L'instance de la Fig. 3.9 permet d'interpréter intuitivement les meilleures solutions et de les
comparer avec les solutions apportées par l'approche proposée dans la Fig. 3.8. L'instance com-
que tous les tankers pour les requêtes arrivent dans leurs fenêtres de temps autorisées (ce qui
implique que tout retard dans le service peut entraîner une pénalité pour le terminal maritime) à
la date ui = 95 ∀i = 1, 2, 3. Cette instance vise à entraîner forcément des pénalités, étant donné
les contraintes serrées des dates limites de service rappelées dans le Tableau 3.2. L'opération de
maintenance est prévue à la date t = 100 avec une durée de 10 heures. L'algorithme SPEA2
a été implémenté directement dans Scicoslab an d'exploiter la boîte à outils (max,+) dans la
Figure 3.9: Exemple pour validation de l'approche intégrée SPEA2 + modélisation (max,+).
Table 3.2: Données d'entrée pour les opérations de transfert dans l'instance de la Fig. 3.9.
R1 30 5000 131
R2 20 4000 131
R3 20 2000 131
Les paramètres sélectionnées sont : taille de population (N ) : 30, nombre de générations (ng ) :
(pc ) : 0.6.
Les résultats obtenus sont présentés par la Fig. 3.10, où les individus sont dénis dans l'espace
de critères TME vs TCP. Il est rappelé que chaque individu est représenté par un chromosome
décrivant l'aectation des variables de décision gérant une sélection d'alignements et un vecteur
de dateurs pour les opérations de transfert et de maintenance. Ainsi, chaque individu représente
Figure 3.10: Solutions dans l'espace de critères pour l'instance de la Fig. 3.9.
Comme espéré, lors de l'évolution, les individus convergent vers les meilleures solutions possibles.
Pour les deux solutions inscrites dans la frontière de Pareto, il peut être constaté qu'un des objec-
tifs est amélioré au détriment de l'autre. En outre, aucun autre individu n'apporte d'amélioration
des deux objectifs simultanément. Ces deux individus sont dénotés comme l'ensemble d'individus
non dominés. Dans la pratique, ces individus non dominés caractérisent les solutions gurant
en Fig. 3.11. Les deux individus non dominés caractérisent la sélection des alignements P4 , P5
et P8 , et la diérence entre les deux est l'aectation des variables pour la précédence entre les
Prenant la Fig. 3.11b) pour analyse, l'aectation des alignements P4 , P5 et P8 aux requêtes R1 , R2
et R3 , respectivement, permet une exécution parallèle de R1 et R2 , puis une exécution parallèle
de R1 et R3 , et ensuite une exécution parallèle de R3 et M13 (une fois que R1 est achevée).
2. Les mêmes résultats peuvent être obtenus avec un eort de calcul moins important ; e.g. population de 10
individus et 3 générations. Néanmoins, les paramètres choisis visent à illustrer une diérence plus importante
entre les populations initiale et nale, ainsi qu'avec la frontière de Pareto pour une meilleure appréhension.
Toute autre aectation d'alignements génère des solutions moins désirables. Par exemple, la
entre les opérations de transfert (i.e. même T CP ), mais entraînerait un décalage plus important
de l'opération de maintenance puisque il faudrait attendre la n d'exécution de R3 (voir conit
La démarche présentée est ainsi capable de proposer à l'opérateur de supervision des solutions
optimales. La décision resterait basée sur les conditions d'exploitation en temps réel. Dans un
système automatisé, pour chacune des solutions présentées dans la Fig. 3.10, l'interface de su-
pervision devrait permettre à l'opérateur de cliquer sur chacune d'entre elles, générant le détail
Figure 3.11: Solutions représentées par les individus non dominés dans la Fig. 3.10.
Le problème d'optimisation multi-objectif est résolu à travers une approche basée sur des
algorithmes génétiques en combinaison avec une modélisation (max, +). Les résultats déjà
obtenus sur la modélisation algébrique (max, +), qui avaient été validés à l'aide du logiciel
d'optimisation (LINGO) dans la section 2.2.4, ont été exploités dans la technique de résolution
proposée. Il est à remarquer que les résultats sur la modélisation algébrique avaient déjà permis
de réduire les eorts de modélisation et l'intégration de nouveaux aspects, tels que la sélection
d'alignements, grâce au caractère intuitif et concis de l'algèbre. Ainsi, ces propriétés ont été
exploitées dans un contexte heuristique et ont permis de dénir une structure génomique évitant
de modéliser et de traiter des fonctions de contraintes dans l'algorithme génétique, même si des
approches déjà existantes pourraient les intégrer dans le cadre de la fonction de tness.
L'ensemble des solutions optimales peut être fourni à l'opérateur de supervision pour soutenir sa
Conclusions Partielles
Des approches classiques d'algorithmes génétiques pourraient considérer une aectation aléatoire
et indépendante des gènes qui devrait aboutir aux mêmes résultats avec un paramétrage adéquat.
Une modélisation classique pour les contraintes opérationnelles supposerait des contraintes de
partage de ressources. Ainsi, lors d'une aectation aléatoire des gènes, les individus caractérisant
des solutions infaisables seraient pénalisés dans les valeurs de tness. Pour chaque individu, les
dateurs devraient être calculés par évaluation des diérents types de contraintes.
L'avantage de l'approche proposée ici est que l'algèbre (max,+) permet de formuler intuiti-
vement, et dans une équation unique les diérents types de contraintes, de telle manière que
l'aectation des variables de décision conduit à un système d'équations (max,+) linéaire pour le-
quel les dateurs peuvent être déterminés par produit matriciel. Sachant que les conits impactent
génomique hiérarchique permet de gérer l'aectation des variables de manière plus ecace. Cette
L'intérêt dans les techniques formelles de résolution, en contraste avec les techniques approxima-
tives (telles que les algorithmes génétiques), a conduit à l'exploration des représentations basées
sur les automates tropicaux (intégration de la théorie d'automates et les algèbres tropicales). Ces
d'automates tropicaux.
Préambule
Les approches formelles pour modéliser la dynamique des systèmes à événements discrets
intuitive des conits de partage de ressources est proposée au travers d'automates locaux, et
global au plus tôt (avec un temps d'exécution minimum de toutes les opérations). Les principes
cadre théorique basé sur les dateurs est alors proposé et illustré par de nombreux exemples.
Sommaire
4.1 Automates (Min,+) et (Max,+) : Notions Théoriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.4.1 Alphabet pour une Paire d'Automates Synchronisés dans un Système à 3 Automates
(n = 3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Automates (n = 3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
83
La théorie d'automates (max,+) et (min,+) sera présentée succinctement avant son exploitation
Il est rappelé que le terme `opération' fait référence à une opération de transfert de pétrole
aux vannes dans le réseau. Aussi, la terminologie employée inclut les notions de parallélisme,
événements discrets. Néanmoins, an d'éviter des ambiguïtés, ici 2 automates sont dits en syn-
chronisation lorsqu'ils exécutent la même opération, i.e. de manière synchrone début et n. Par
la même date.
Un automate (min,+) est un automate dans lequel chaque transition a un poids associé qui peut
être interprété comme un coût. Chaque chemin dans l'automate peut être décrit avec un mot w
dont le coût est la somme, en algèbre conventionnelle, des coûts des transitions. Le coût associé
au mot w est le coût minimal parmi les coûts de tous les chemins qui peuvent être décrits avec le
même mot w dans l'automate. Un automate (min,+) peut aussi être dénoté dans la littérature
Réciproquement, un automate (max,+) a une représentation duale dont les poids des transitions
peuvent être associées à des gains. Ainsi, un chemin décrit par le mot w est le chemin de poids
maximal parmi tous les chemins décrits par le même mot w, i.e. le chemin de gain maximal.
Ces notions de maximisation et minimisation sont représentées par le semi-anneau dans lequel
l'automate est déni. Dans ce contexte, les structures des algèbres (max,+) et (min,+) inspirent
la dénition des automates (max,+) et (min,+), respectivement. Ici, le terme `automate tro-
pical' fera référence à un automate qui peut être déni dans le cadre des algèbres tropicales ;
L'algèbre (max,+) a déjà été dénie dans le chapitre 2 et l'algèbre (min,+) décrit un compor-
tement dual tel que les deux opérations mathématiques de base ⊕ et ⊗ correspondent à la
tributivité et idempotence restent valables. Les éléments nul et neutre correspondent à ε=∞
et e = 0, respectivement.
(ou ensemble d'événements), Q est l'ensemble ni d'états, t : Q×A×Q → N est la fonction
nal, respectivement. Dans ce contexte, les poids des transitions appartiennent à l'ensemble des
nombres naturels. Deux états, q et q0, sont liés par une transition étiquetée par un événement a
0
de durée t(q, a, q ). Si aucune transition ne relie ces deux états, alors t(q, a, q 0 ) = ε = ∞. Dans un
automate (min,+) (respectivement (max,+)), la durée d'un événement a peut être représentée
par une variable y(a) nommée dateur. Un dateur peut aussi modéliser la date d'achèvement d'une
séquence d'événements consécutifs, e.g. y(ab) est le dateur pour la séquence
0 ab0 . La dénition
syntaxique d'un automate (max,+) ou (min,+) est donnée par son alphabet, la fonction de
transition et l'ensemble d'états. Dans les travaux de [71], la dénition syntaxique est dénotée :
Réciproquement, un automate (max,+) est déni dans un semi-anneau avec une opération in-
trinsèque de maximisation. Dans un automate (max,+), lorsque aucune transition a ne relie deux
états q 0
et q alors t(q, a, q 0 ) = ε = −∞. Les automates (max,+) ont été largement étudiés dans
la littérature et quelques résultats sont transposables aux automates (min,+) par dualité entre
les deux techniques de modélisation. Les travaux de [40] dénissent les bases pour l'application
de ces techniques à la modélisation des systèmes à événements discrets et [42] et [43] abordent
La Fig. 4.1 présente 2 exemples d'automates tropicaux avec 1 ou plusieurs états. Les états
initiaux sont représentés avec des èches entrantes et les états naux avec un double contour. Ces
automates (max,+) ou (min,+) ne peuvent pas être diérenciés par sa représentation syntaxique
1
ni graphique, d'où le terme `tropicaux' . Pour l'automate de la Fig. 4.1a), la syntaxe est la
suivante : A = {a}, Q = {q1 }, t(q1 , a, q1 ) = 5. Cet exemple comporte un seul état (état initial
et nal identique) et une seule transition représentant l'exécution de l'événement `a'. Dans la
pratique cet événement ferait référence à l'exécution d'une tâche, opération, procédure ou autre,
d'une durée de 5 unités de temps. Ainsi, pour l'événement `a' le dateur correspond à y(a) = 5,
et le dateur de la séquence `aa', par exemple, correspondrait à y(aa) = 10, i.e. l'opération `a' est
de la Fig. 4.1b) est représenté par A = {a, b, c}, Q = {q1 , q2 , q3 }, t(q1 , a, q2 ) = 2, t(q2 , b, q2 ) = 4
et t(q2 , c, q3 ) = 5. Ainsi, les dateurs des événements sont : y(a) = 2, y(b) = 4 et y(c) = 5 et les
1. Dans la littérature le terme `automate à multiplicités' est aussi employé. Néanmoins, il fait référence à des
automates avec des transitions pondérées, une classe plus générale d'automates où les semi-anneaux de dénition
ne sont pas forcément ceux des algèbres (min,+) et (max,+).
dateurs des séquences `ab', `abc' et `abbc' seraient : y(ab) = 6, y(abc) = 11 et y(abbc) = 15. Il
est à remarquer que les automates de la Fig. 4.1 peuvent représenter soit des automates (max,+)
ou soit des automates (min,+). La dénition sémantique de ces automates détermine alors s'il
s'agit d'un automate (max,+) ou (min,+) vis-à-vis de la recherche des chemins étiquetés par un
mot. Dans le cas d'un automate (max,+) il s'agit de trouver le chemin à poids maximal parmi
les chemins décrits par le même mot, et dans le cas d'un automate (min,+) il s'agit de trouver
le chemin à poids minimal. Dans ce qui suit, seule la syntaxe des automates est étudiée. Par
Les développements dans ce chapitre ont été inspirés par les travaux de [44] et [72]. Dans [44]
un produit synchrone d'automates (max,+) est proposé pour des systèmes de 2 et 3 automates
locaux. Dans [72], sur les bases d'une modélisation avec des réseaux de Petri, le comportement
est analysé par une décomposition d'états en micro-états dénotant le passage du temps, où les
réseau.
Dans [44] un produit synchrone pour automates (max,+) permettant l'exécution simultanée
d'opérations a été proposé. Dans ce cas, il est supposé que les opérations simultanées doivent
démarrer à la même date, et que la date d'achèvement de l'ensemble d'opérations est unique et
correspond à la date d'achèvement de l'opération la plus longue. Par exemple, si les événements
a et b sont exécutées simultanément et que y(a) = 4 et y(b) = 10, alors un nouvel événement
(a, b) est généré dans l'alphabet du produit dénotant l'exécution simultanée de a et b, et sa durée
est dénie comme y(a, b) = y(a) ⊕ y(b) = 4 ⊕ 10 = 10. Ce comportement force les ressources
forcée par l'opérateur de maximisation (⊕). Par conséquent, les ressources de l'opération plus
courte ne peuvent pas être exploitées par une autre opération dès qu'elles sont libérées par la
première. Le même comportement décrit des situations avec plus de deux opérations en exécution
simultanée. Néanmoins, ceci est bien l'objectif de ce produit, i.e. la détermination des chemins
à poids maximal.
An d'illustrer le principe du produit proposé dans [44] sans rentrer dans sa formalisation (abor-
dée dans la section 4.4), la Fig. 4.2 présente le produit synchrone de 2 automates par l'approche
de [44]. Dans l'automate produit (automate c)) des événements composés dénotent l'exécution si-
multanée de 2 opérations avec la durée de l'opération la plus longue, i.e. (b, c)/10, et l'événement
commun `a' synchronise les automates. Dans la Fig. 4.3, le produit est appliqué à 3 automates
résultant (automate (d)). La composition d'événements mène toujours à une maximisation des
durées ce qui génère 2 trajectoires vers des états marqués de 25 et 17 unités de temps. La tran-
sition `1,1,1' → `2,2,2' de l'automate (d) indique que l'exécution de a et b s'achève après 15
2. puisqu'un automate (max,+) ne peut être diérencié d'un automate (min,+) à partir d'une représentation
syntaxique.
Figure 4.2: Produit synchrone 2 automates : l'automate c) c'est le produit des automates a)
et b).
Figure 4.3: Produit synchrone de 3 automates : l'automate d) c'est le produit des automates
a), b) et c). L'automate e) représente le produit souhaité pour le cas d'étude.
unités de temps, quand dans la pratique les ressources associées à l'opération a se libèrent après
2 unités de temps. Ce comportement est naturel dans un cadre de maximisation des poids des
chemins comme celui abordé par les automates (max,+). Néanmoins, pour une problématique
de fonctionnement au plus tôt i.e. élimination des périodes dites oisives des ressources, l'intérêt
se focalise sur la minimisation du temps d'exécution de toutes les opérations possibles dans le
système. Il paraît alors nécessaire de dénir un produit synchrone plus adapté en conservant une
représentation similaire à celle proposée en Fig. 4.3e). Dans cette représentation, l'opération b est
décomposée de telle manière qu'une partie est exécutée en parallèle avec l'opération a (jusqu'à
un état auxiliaire) et le reste en parallèle avec les opérations c et d (jusqu'à l'état nal), résultant
3
en une trajectoire de 15 unités de temps . Ceci illustre la formulation d'un nouveau produit an
d'optimiser l'exploitation des ressources pour une minimisation du temps d'exécution total.
L'approche décrite dans [44] est pratique et concise. Cependant, elle vise à maximiser les poids
des chemins et ne représente pas une approche susamment adéquate pour minimiser le temps
directe de la fonction de minimisation dans le cadre d'un produit dual avec des automates
(min,+) n'est pas envisageable, puisque le minimum de 2 dateurs (pour deux opérations en
exécution simultanée) ne modélise pas le temps d'achèvement de l'opération la plus longue et,
3. les autres opérations pourraient être aussi décomposées. Pourtant, le but est de représenter la durée de la
trajectoire qui serait toujours de 15 unités de temps.
par conséquent, la libération des ressources associées. En outre, la résolution des conits avec
optimisation des engagements d'opérations simultanées, doit être extrapolable pour des sous-
Cette section introduit le cadre de dénition d'un nouveau produit synchrone modélisant le
proposé que ces conits peuvent être modélisés par des automates tropicaux. Seul les aspects de
Le comportement logique fondamental modélisé par des `automates tropicaux', ou tout sim-
plement `automates' dans ce qui suit, concerne l'exclusion mutuelle entre les opérations pour
Les opérations sans conit mutuel sont modélisées comme des opérations exécutables dans des
automates appelés `locaux' diérents pouvant s'engager simultanément. Ainsi, les automates
La Fig. 4.4 montre un exemple de 4 opérations de transfert (ri ) devant être exécutées par les
alignements signalés dans le réseau (seules les vannes ouvertes sont représentées en couleur)
lorsque 2 activités de maintenance, m2 , et m6 , doivent également être lancées sur les vannes 2 et
6. Dans cette gure, et celles qui suivent, les indices de labellisation des vannes restent les mêmes
dans le réseau de pipelines et ne doivent pas être confondus avec les durées des opérations qui sont
illustrées dans les représentations par automates (Gi ), e.g. l'opération r1 nécessite l'ouverture
Dans la Fig. 4.4, les opérations m2 , r2 et m6 sont en conit, ce qui est représenté par l'automate
1) pour exécuter r2 , les vannes 7, 4, 8, 11, 12, et 13 doivent être fermées, et les vannes 2, 6, 10,
2) pour exécuter m2 , les vannes 7 et 6 doivent être fermées pour que la vanne 2 soit isolée ;
3) pour exécuter m6 , les vannes 2, 7, 4, 8, 10, 11, et 12 doivent être fermées pour isoler la vanne 6.
Localement sur G1 , une seule de ces opérations ne peut être exécutée à la fois (i.e. représentant
l'engagement des ressources pour exécuter une des opérations qui les sollicitent). Chaque tran-
sition a une étiquette avec l'événement déclencheur de l'opération et sa durée. L'état initial est
Figure 4.4: Exemple de modélisation des conits par automates tropicaux mono-état : les
opérations mutuellement exclusives sont modélisées par des transitions sortant du même état.
représenté avec une èche entrante, et l'état nal est représenté avec un double cercle ; i.e. état
La représentation par un automate mono-état (Fig. 4.4) illustre de manière concise le principe
d'exclusion mutuelle pour les opérations en conit du fait du partage de ressources. Formel-
(qui retardent le début d'exécution à l'état initial et l'achèvement d'exécution à l'état nal)
sont négligeables ici, i.e. αi = βi = e ∀i ∈ {1, 2, 3}, et seule les durées d'exécution des opé-
Le modèle est interprété comme suit : les opérations r2 , m6 , et m2 sont toutes en conit puis-
qu'elles ne peuvent pas être exécutées simultanément. Ce conit est modélisé par l'automate G1 .
Les transitions sortantes de l'état unique modélisent le fait qu'une seule de ces opérations peut
mutuelle (i.e. sont aussi en conit), et par conséquent génèrent l'automate G2 . Finalement, G3
modélise le conit entre r4 et r3 . Le modèle décrit aussi des opérations indépendantes (i.e. sans
conit) qui peuvent être exécutées simultanément (comme b et c pour la Fig. 4.2) telles que m2 ,
r1 et r3 , par exemple. Ainsi, l'intérêt d'un modèle à un seul état par automate est qu'il modélise
l'exclusion mutuelle de manière concise.
Hypothèse 4.1 . Toutes les opérations doivent être exécutées, et chaque opération qu'une seule
L'hypothèse 4.1 restreint le comportement du modèle (i.e. ensemble d'opérations à exécuter dans
un système non périodique). De manière rigoureuse, la représentation dans la Fig. 4.4 permet
que chaque opération puisse être exécutée plus d'une fois. Pour représenter de manière précise
les contraintes considérées, i.e. exécution unique, un modèle étendu est déni avec l'ensemble des
permutations permises, ce qui restreint le comportement logique pour que les cycles ne soient pas
autorisés. Cette représentation multi-état est présentée dans la Fig. 4.5 pour le même exemple.
fois, le modèle mono-état peut contenir l'explosion combinatoire. Les propos de cette recherche
se focalisent sur les relations d'exclusion mutuelle ; ainsi, le modèle mono-état donnera les mêmes
Le développement théorique qui suit caractérise à partir des dateurs une sous-classe d'automates
4. i.e. pour tous les automates locaux, à partir de l'état initial unique, un seule trajectoire sera possible telle
qu'elle conduit vers un seul état nal et toutes les opérations seront exécutées 1 fois.
Hypothèse 4.2 . n opérations en conit sont modélisées comme n événements mutuellement ex-
Dénition 4.1. ri1 dénote un micro-événement dérivé d'un événement original ri si la durée de
La dénition 4.1 vise à décomposer chaque opération originale de durée ti en plusieurs opérations
atomiques modélisant le passage du temps, chacune avec une durée d'une unité de temps, i.e.
Dénition 4.2. Une fois qu'une opération est lancée, les micro-événements subséquents pour
l'hypothèse 4.1.
La Fig. 4.6 illustre un exemple simple relatif au cas d'étude, et la Fig. 4.7 présente sa décompo-
sition en micro-événements. Sur la Fig. 4.6, les alignements pour 3 opérations de transfert sont
représentées en couleur (spéciant seulement les vannes à ouvrir). Dans cette conguration, une
opération de maintenance doit aussi être eectuée sur la vanne 2. Dans cet exemple, deux conits
part, l'opération r3 est complètement indépendante et peut être exécutée simultanément avec
ment en une séquence de tics d'horloge décrivant le temps passé dans le cadre d'un comportement
ration est égal à la durée originale ti de l'opération dans la Fig. 4.6, comme dans la dénition
4.2. La décomposition montre une certaine exibilité de l'exécution d'opérations simultanées, i.e.
une opération a peut s'exécuter en parallèle avec une opération b pour une durée déterminée,
et puis peut continuer à s'exécuter en parallèle avec une opération c sollicitant les ressources
libérées par b.
Pour l'exemple de la Fig. 4.6, r3 a une durée de 6 unités de temps (y(r3 ) = 6), ce qui est
durée diérente sera d'une importance capitale pour la proposition du nouvel alphabet.
Hypothèse 4.3 . Le nouveau produit synchrone vise à exploiter les phénomènes de parallélisme
au plus tôt ; i.e. parmi les possibilités d'exécution des opérations, seront retenues celles avec un
tion simultanée de n micro-événements dans n automates ; son dateur est d'une unité de temps.
elle est dénie par le nombre d'automates locaux (sous-systèmes) dans le modèle.
La dénition 4.6 implique que pour un système à 3 automates, par exemple, chaque macro-
événement doit avoir 3 composantes, e.g. (r14 , r54 , r84 ) représenterait l'exécution de r1 dans l'au-
permet de conserver cette notation même si aucun événement ne s'exécute sur un ou plusieurs
Dans la Fig. 4.8, les 2 trajectoires possibles pour exécuter au plus tôt les 4 opérations de l'exemple
de la Fig. 4.7 sont représentées avec une exploitation maximale du parallélisme dès l'état initial.
en parallèle dans G1 .
composé (r35 , r25 , r25 ) qui modélise l'exécution simultanée d'opérations r3 , et r2 pendant 5 unités
de temps. (r31 , m12 , r11 ) représente l'exécution de r3 lors de sa dernière unité de temps, en même
Le produit dans la Fig. 4.7 est déterministe ; i.e. l'automate possède un seul état initial et de
chaque état un même événement ne peut générer des transitions vers des états diérents.
5. positionnement sur les états des automates locaux pour dénir un comportement global.
Figure 4.8: Représentation du produit synchrone G1 ||G2 ||G3 pour l'exemple de la Fig. 4.7.
Pour des propos d'illustration, avec l'approche proposée dans [44] pour un produit d'automates
la Fig. 4.6 inclurait l' événement composé (r2 , r3 ) modélisant l'exécution simultanée de r2 et r3
avec une date d'achèvement de y(r2 ) ⊕ y(r3 ) = 5 ⊕ 6 = 6. Dans la Fig. 4.8, et selon le nouveau
produit synchrone, r2 et r3 sont exécutées simultanément et dès que les ressources associées à
r2 sont libérées (i.e. à t = 5), m2 et r1 sont exécutées à t=5 en parallèle avec la n d'exécution
de r3 .
Dénition 4.8. Le dateur d'un macro-événement composé est déni comme la somme des
j j
composants des dateurs, i.e. y(ru , rv ) = y(ruj ) ⊕ y(rvj ) = j ⊕ j = j.
Ceci est équivalent à la dénition de dateur des nouveaux événements générés pour le produit
d'automates (max,+) dans [44]. Néanmoins ici, étant donné que par dénition les composants
à ce que le dateur d'un macro-événement composé soit égal aux dateurs de ses composants ;
par exemple : y(r13 , r33 ) = y(r13 ) ⊕ y(r33 ) = 3 ⊕ 3 = 3. Ainsi, la théorie proposée est applicable
également pour les automates (min,+) et (max,+) puisqu'ils sont basés sur des algèbres avec
l'opérateur ⊕ idempotent.
An illustrer le principe de la dénition 4.9, reprenant l'exemple de la Fig. 4.7, le résultat de
la concaténation de a = (r35 , r25 , r25 ), b = (r31 , m12 , r11 ), et c = (e1 , m12 , r11 ) serait abc = (r35 r31 e1 ,
r25 m12 m12 , r25 r11 r11 ) qui est synthétisé comme : abc = (r36 e1 , r25 m22 , r25 r12 ). Évidemment, l'alphabet
Dans ce qui suit, l'alphabet de chaque automate local est décrit selon 2 types d'événements :
un automate Gi sont ceux qui ne surviennent que dans cet automate. Alors que les événements
de synchronisation sont communs à plusieurs automates locaux. Ces notions sont formalisées par
Dénition 4.10. Un dateur privé pour un automate Gi est déni comme le produit de tous les
N
dateurs concernant les événements privés dans cet automate ; i.e. yGip = a∈Aip y(a). Le dateur
privé est dénoté par yGip et Aip dénote le sous-ensemble de l'alphabet de Gi qui ne contient que
Pour le système de la Fig. 4.6 (respectivement Fig. 4.7), les dateurs privés identiés sont :
Dénition 4.11. Le dateur de synchronisation pour un automate Gi est déni comme le produit
des dateurs des événements communs de l'automate Gi avec tout autre automate.
Pour un système à 3 automates locaux, les dateurs de synchronisation possibles sont les combi-
N N N
naisons : ys(Gi ,Gj ) = a∈Ai ∩Aj y(a), ys(Gi ,Gk ) = b∈Ai ∩Ak y(b), ys(Gj ,Gk ) = c∈Aj ∩Ak y(c),
N
ys(Gi ,Gj ,Gk ) = d∈Ai ∩Aj ∩Ak y(d). En outre, s(Gu , Gv ) dénote l'ensemble des événements syn-
chronisant 2 automates : Gu et Gv , et s(Gu , Gv , Gw ) l'ensemble d'événements synchronisant 3
automates : G u , Gv , et Gw .
Pour le système représenté dans la Fig. 4.4, le seul dateur synchronisant non nul est :
ys(G1 ,G2 ) = y(r2 ) ⊗ y(m6 ) = 4 ⊗ 5 = 9, alors que pour le système de la Fig. 4.6 le dateur
Hypothèse 4.4 . Étant donné qu'à part de l'exclusion mutuelle aucune autre contrainte n'est
prise en compte pour l'ordonnancement d'opérations, il est considéré que lorsqu'un automate
comporte plusieurs événements privés, ils sont tous exécutés de manière consécutive et sans ordre
d'exécution imposé, i.e. toutes les permutations sont acceptables. Le même principe est valable
pour le cas d'un système avec plusieurs événements de synchronisation. Ceci réduit de manière
Dénition 4.12. Un dateur global pour un automate Gi est déni comme le produit de l'en-
N
semble des dateurs pour des événements appartenant à l'alphabet ; i.e. yGi = a∈Ai y(a). Le
dateur global regroupe dateurs privées et de synchronisation et formellement s'exprime par :
yGi = yGip ⊗ ys(Gi ,Gj ) ⊗ ys(Gj ,Gk ) ⊗ ys(Gi ,Gk ) ⊗ ys(Gi ,Gj ,Gk ) , pour le cas de 3 automates, par
exemple.
Pour l'exemple de la Fig. 4.4, les dateurs globaux sont : yG1 = 12, yG2 = 15 et yG3 = 15, lorsque
pour la Fig. 4.6, yG1 = 6, yG2 = 7, et yG3 = 8.
Dénition 4.13. Dans un système modélisé par n automates, chaque automate est indexé et
dénoté par Gi pour i = 1, . . . , n, en rapport aux dateurs globaux selon la règle de classement
Cette règle de classement a été appliquée à l'indexation des exemples présentés. Le but est d'en-
visager les meilleures ordonnancements qualitatifs tels que toutes les opérations soient exécutées
au plus tôt.
Dénition 4.14. A1i est le micro-alphabet d'un alphabet originalement dénoté comme Ai pour
un automate Gi . Il est formé de tous les micro-événements associés aux événements de l'alphabet
original. Par exemple, dans la Fig. 4.6 pour l'automate G2 , A2 = {r2 , m2 } et A12 = {r21 , m12 }.
Dans ce qui suit, le terme `makespan' est employé, en analogie avec les systèmes de production,
Dans cette section, l'alphabet pour le nouveau produit synchrone d'automates de 3 ou plus
Par l'approche de [44], pour le cas d'un système à 2 automates locaux, notamment G1 et
G2 de la Fig. 4.4 (et selon leur notation) l'alphabet résultant du produit G1 ||G2 serait :
A = {r2 , m6 , (m2 , r1 )}, selon (4.2). Ainsi, lorsqu'un événement commun aux deux automates
(comme r2 ou m6 ) est exécuté, il est exécuté dans les deux automates, i.e. les automates sont
synchronisés. Sinon, les événements privés sont exécutés simultanément (i.e. m2 avec r1 ) et la
date d'achèvement de cette exécution simultanée est le maximum des durées des événements
privés, dans ce cas 6 unités de temps. Dans tout scénario d'exécution, e.g. r2 m6 (m2 , r1 ) ou
(m2 , r1 )r2 m6 , la date d'achèvement de la séquence est identique, i.e. 15 unités de temps, si
chaque événement est exécuté une seule fois. Comme l'automate G2 nécessite au moins 15 unités
de temps pour exécuter toutes les opérations au moins une fois, ce résultat ne pourrait jamais
6. Les résultats pour n = 2 sont considérés triviaux et sont en fait équivalents aux travaux de [44] puisque le
parallélisme peut être exploité en générant un makespan optimal ; alors que pour n = 3 l'optimum souhaité ne
peut être atteint avec l'approche [44].
être amélioré, i.e. aucun intervalle oisif n'apparaît dans l'ordonnancement. Au delà de deux au-
tomates, des conits d'ordre supérieur sont à considérer (conits entre les diérentes paires,
Les résultats dans [44] (pour le produit d'automates (max,+)) ont inspiré l'approche présentée
ici où les dates d'achèvement de tous les événements seront minimisées. Par conséquent, [44] est
Dans [44], l'alphabet est proposé pour un produit avec n = 3 dans lequel les opérations en
parallèle possèdent la date d'achèvement de l'opération la plus longue. Cet alphabet est décrit
par (4.3). La notation est telle que Ai \(Aj ∪ Ak ) dénote les éléments de Ai sauf ceux qui sont
communs à Aj et/ou Ak . Par conséquent, Ai \(Aj ∪ Ak ) dénote les événements privés pour
l'automate Gi (i.e. événements qui ne surviennent que dans cet automate). Le produit cartésien
`×' est utilisé pour créer de nouveaux événements composés, basés sur les alphabets originaux ;
par exemple, si Ai = {a, b}, et Aj = {c}, alors Ai × Aj = {(a, c), (b, c)}.
Dans (4.3), le premier terme de l'alphabet dénote les événements communs aux 3 automates.
Le deuxième terme dénote un événement composé, formé par des événements communs aux 2
cutant en parallèle. Finalement, le dernier terme représente un événement composé formé par
3 éléments, chacun dénotant des événements (ou séquences) privés, s'exécutant dans chaque
automate simultanément. Avec la formulation (4.3), les événements communs aux 3 automates
s'exécutent en même temps car il s'agit d'événements de synchronisation et leurs dateurs sont
égaux. Les événements communs aux 2 automates sont exécutés de manière synchronisée et, en
même temps, ils peuvent s'exécuter en parallèle avec des événements (ou séquences) privés de
l'automate restant. Dans ce cas, le dateur du nouvel événement composé est le maximum des
2 dateurs (de synchronisation et privé). Le même principe est appliqué lorsque des événements
Le nouvel alphabet proposé ici, décrit par (4.4) vise à garantir un makespan minimal. Le premier
terme : (A11 ∩A12 ∩A13 ) dénote tous les micro-événements composés synchronisant les 3 automates.
A1ij,k représente tous les micro-événements composés synchronisant Gi et Gj et s'exécutant si-
multanément avec des micro-événements privés dans Gk . Finalement, A11,2,3 dénote tous les
les 3 automates. La distinction fondamentale entre l'équation (4.4) par rapport à l'équation (4.3)
est de disposer de diérents scénarios de parallélisme entre les opérations par une décomposition
en tics d'horloge dans les diérents automates. L'exposant 1 rappelle la durée d'une unité de
Le terme (A11 ∩ A12 ∩ A13 ) est déni comme l'intersection de tous les micro-alphabets. Alors que,
les termes A1ij,k et A11,2,3 sont déterminés par une procédure plus complexe impliquant l'analyse
des exécutions possibles de tous les types d'événements (i.e. de synchronisation ou privés) pour
que la meilleure conguration soit choisie, telle que le temps d'exécution soit minimisé. Les
résultats varient ainsi selon les scénarios de synchronisation retenus ; par exemple : absence de
synchronisation, synchronisation entre une paire d'automates, 2 paires, 3 paires, une tierce, et
Dans ce qui suit, le nouvel alphabet est proposé pour les diérents scénarios de synchronisation
à 3 Automates ( n = 3)
Tout d'abord, la synchronisation de la paire (G2 , G3 ) est étudiée en détail et ensuite le compor-
tement pour la synchronisation des autres paires est représenté de manière analogue. Sachant
que l'analyse reste la même pour les 3 paires possibles, la paire (G2 , G3 ) est prise aléatoirement
Selon la dénition 4.13, les indices des modèles d'automate sont choisis tels que yG3 ≥ yG2 ≥ yG1 ,
et ainsi les résultats (4.5) dénissent la relation des dateurs lorsque les automates G2 et G3 sont
synchronisés.
Cette relation entre dateurs, apporte des informations signicatives pour un ordonnancement
d'opérations optimisant le makespan dans le produit synchrone et, par conséquent, sera la base
La première inégalité de (4.5) fournit (4.6) (le dateur privé pour G3 sera égal ou supérieur au
dateur privé pour G2 ). La deuxième inégalité fournit (4.7) et indique que yG2p ⊗ ys(G2 ,G3 ) ≥
yG1p , conduisant à 2 possibilités : ys(G2 ,G3 ) ≥ yG1p ou ys(G2 ,G3 ) < yG1p . L'intérêt dans cette
relation réside sur le fait que s(G2 , G3 ) et G1p sont des ensembles d'opérations qui peuvent être
exécutés de manière simultanée ; par conséquent, ces relations de dateurs dénissent la base de
la détermination du nouvel alphabet. Finalement, de (4.5) se déduit (4.8) par transitivité (i.e. si
Il peut être aussi déduit à partir de l'équation (4.5) que tous les dateurs privés seront non
nuls (ceci est vrai pour G1 puisque sinon cet automate n'existerait pas car il ne comporte
que d'événements privés, et aussi pour G2 et G3 puisque les événements privés sont ceux qui
yG2p ⊗ ys(G2 ,G3 ) ≥ yG1p ∴ ys(G2 ,G3 ) ≥ yG1p ∨ ys(G2 ,G3 ) < yG1p (4.7)
Les résultats présentés en Fig. 4.9 reprennent (4.5) et l'hypothèse 4.3. L'ordonnancement de
la Fig. 4.9a) peut être considéré comme l'ordonnancement qualitatif optimal pour l'exécution
de toutes les opérations au plus tôt. Il est appelé qualitatif car la date d'exécution de chaque
opération n'est pas spéciée mais plutôt les dates d'exécution des blocs d'opérations (e.g. bloc
toute permutation d'opérations dans chaque bloc est possible. Cet ordonnancement est intuitif
du fait de la simplicité du scénario de synchronisation considéré. Il est construit sur les bases des
relations de dateurs, permettant d'identier les événements composés possibles survenant dans
An d'interpréter les diérents ordonnancements optimaux présentés ici, une logique d'intégra-
tion de blocs d'opérations doit être considérée, la Fig. 4.9 en présente un exemple intuitif. Dans
la gure, chaque bloc grisé indique l'intervalle des dates d'achèvement possibles pour le bloc
précédent.
Tout d'abord (Fig. 4.9a)), s(G2 , G3 ) est exécuté en parallèle avec G1p et la date d'achèvement
pour G1p est cohérente avec (4.7), indiquant que G1p peut s'achever avant, concomitamment, ou
après s(G2 , G3 ) (d'où le bloc grisé supérieur). Ensuite, (4.6) révèle que G3p s'achève concomi-
tamment ou après G2p . Finalement, (4.8) indique que la date d'achèvement des opérations dans
maux, en laissant la liberté de prendre en compte toute permutation possible d'opérations dans
déterminer les possibles micro-événements composés dans le nouveau produit synchrone pour
une exécution optimale de l'ensemble des opérations. Notamment, d'après la Fig. 4.9a), s'il est
7. Si un seul de ces automates possèdait des événements privés, l'autre automate ne comporterait aucune
information supplémentaire, et si aucun des deux n'avait d'événement privé, ils représenteraient le même automate.
Figure 4.9: Ordonnancements qualitativement optimaux pour des systèmes avec une paire
d'automates synchronisés : 3 cas possibles.
convenu dans le système que yG1p < ys(G2 ,G3 ) alors les micro-événements composés compor-
tant des éléments de s(G2 , G3 ) seront de deux types : (a1 , b1 , b1 ) et (e1 , b1 , b1 ), avec a ∈ G1p
et b ∈ s(G2 , G3 ), puisqu'une fois le bloc G1p achevé, s(G2 , G3 ) continuera son exécution. Pour
ce scénario de synchronisation, une conguration non optimale serait d'exécuter au début tous
les événements privés de tous les automates en parallèle. Le bloc privé de G3 devrait s'ache-
ver avant que s(G2 , G3 ) ne soit exécuté, introduisant alors un intervalle d'oisiveté pour G2 ,
alors que l'objectif est de libérer les ressources au plus tôt pour qu'elles puissent être exploitées
ultérieurement.
L'avantage de la conguration proposée en Fig. 4.9a) est de prioriser s(G2 , G3 ) puisqu'il ore la
possibilité d'inclure des événements privés en parallèle d'un troisième automate au plus tôt.
Dans le cas où la seule paire synchronisée est (G1 , G2 ), la relation fondamentale des dateurs
correspond à (4.9), et si par contre (G1 , G3 ) sont synchronisés, cela répond à la relation (4.10).
Sur les bases de (4.9) et (4.10), et appliquant la même analyse que pour la paire (G2 , G3 ), les
les événements dans l'alphabet du nouveau produit synchrone en termes de conditions de dateurs.
l'alphabet déni dans (4.4) où les éléments A1ij,k et A112,3 suivent les expressions (4.11-4.15).
(A1 ∩ A1 ) × (A1 \A1 ∪ A1 ) × (A1 ∩ A1 ) si y
1 3 2 1 3 1 3 s(G1 ,G3 ) 6= 0
A113,2 = (4.11)
∅ sinon
(A1 ∩ A1 ) × (A1 ∩ A1 ) × (A1 \A1 ∪ A1 ) si y
1 2 1 2 3 1 2 s(G1 ,G2 ) 6= 0
A112,3 = (4.12)
∅ sinon
(A1 \A1 ∪ A13 ) × (A12 ∩ A13 ) × (A12 ∩ A13 ) si ys(G2 ,G3 ) 6= 0 ∧ (yG1p ≥ ys(G2 ,G3 ) )
1 2
A123,1 = [(A11 \A12 ∪ A13 ) ∪ e1 ] × (A12 ∩ A13 ) × (A12 ∩ A13 ) si ys(G2 ,G3 ) 6= 0 ∧ (yG1p < ys(G2 ,G3 ) )
∅ si ys(G2 ,G3 ) = 0
(4.13)
[((A11 \A12 ∪ A13 ) ∪ e1 ) × ((A12 \A11 ∪ A13 ) ∪ e1 ) × (A13 \A11 ∪ A12 )]\Ae(1,2)
si (yG3 > yG2 ) ∧ (yG1p > ys(G2 ,G3 ) )
e1 × ((A12 \A11 ∪ A13 ) ∪ e1 ) × (A13 \A11 ∪ A12 ) si (yG3 > yG2 ) ∧ (yG1p ≤ ys(G2 ,G3 ) )
A11,2,3 = ((A11 \A12 ∪ A13 ) ∪ e1 ) × (A12 \A11 ∪ A13 ) × (A13 \A11 ∪ A12 )
si [(yG3 = yG2 ) > yG1 ] ∧ (yG1p > ys(G2 ,G3 ) )
1 1 1 1 1 1 1
e × (A2 \A1 ∪ A3 ) × (A3 \A1 ∪ A2 ) si [(yG3 = yG2 ) > yG1 ] ∧ (yG1p ≤ ys(G2 ,G3 ) )
1 1
(A1 \A2 ∪ A13 ) × (A12 \A11 ∪ A13 ) × (A13 \A11 ∪ A12 ) si yG3 = yG2 = yG1
(4.14)
[e1 × (A12 \A11 ∪ A13 ) × (A13 \A11 ∪ A12 )] ∪ [(A11 \A12 ∪ A13 ) × e1 × (A13 \A11 ∪ A12 )]
A1e(1,2) = si yG2 = yG1
1 1
[(A1 \A2 ∪ A13 ) × e1 × (A13 \A11 ∪ A12 )] si yG2 > yG1
(4.15)
répond à (4.13). Dans ce cas, alors 2 scénarios sont possibles selon la valeur du dateur privé de G1 :
soit yG1p ≥ ys(G2 ,G3 ) ou yG1p < ys(G2 ,G3 ) . Ce résultat dérive de l'analyse des dateurs (4.5-4.8) et
les impacts temporels sont identiées dans la Fig. 4.9a). Dans le premier cas (yG1p ≥ ys(G2 ,G3 ) ),
les micro-événements de s(G2 , G3 ) s'exécuteront forcément avec des événements privés de G1
(première partie de l'équation (4.13)). Dans le deuxième cas (yG1p < ys(G2 ,G3 ) et deuxième partie
de (4.13)), un micro-événement vide est ajouté au premier composant puisque G1p s'achèvera
avant la terminaison de s(G2 , G3 ). La même analyse est valable pour (4.11) et (4.12) dans les
d'une paire d'automates. Les formulations sont plus denses pour A11,2,3 puisque plusieurs possi-
bilités sont envisageables pour composer les micro-événements privés. L'objectif est toujours de
restreindre l'alphabet pour qu'aucune trajectoire n'introduise des intervalles oisifs dans l'ordon-
Suivant cette procédure, l'alphabet peut être construit pour 2 ou 3 paires d'automates synchro-
nisés. Dans ce qui suit, les formulations pour le cas le plus complexe (i.e. 3 paires d'automates
Système à 3 Automates ( n = 3)
La règle principale de classement des dateurs globaux répond à l'expression (4.16) pour le scénario
yG3p ⊗ ys(G2 ,G3 ) ⊗ ys(G1 ,G3 ) ≥ yG2p ⊗ ys(G2 ,G3 ) ⊗ ys(G1 ,G2 ) ≥ yG1p ⊗ ys(G1 ,G2 ) ⊗ ys(G1 ,G3 )
(4.16)
phabet. Dans la Fig. 4.10, les 2 ordonnancements qualitatifs optimaux sont issus de l'analyse
des scénarios possibles d'exécution des blocs d'opérations. La proposition est de débuter par
Scénario 2 : L'achèvement G1p avant s(G2 , G3 ), voir Fig. 4.10b), i.e. yG1p < ys(G2 ,G3 ) .
inégalité de (4.16) il est déduit (en algèbre conventionnelle pour faciliter la compréhension) :
yG2p + ys(G2 ,G3 ) ≥ yG1p + ys(G1 ,G3 ) . Par conséquent, si yG1p ≥ ys(G2 ,G3 ) alors yG2p ≥ ys(G1 ,G3 ) . De
la première inégalité de (4.16) il est obtenu : yG3p +ys(G1 ,G3 ) ≥ yG2p +ys(G1 ,G2 ) ; par conséquent, si
yG2p ≥ ys(G1 ,G3 ) alors yG3p ≥ ys(G1 ,G2 ) . Cela indique que l'ensemble d'événements privés Gip dans
chaque automate s'achève en même temps ou après l'ensemble d'événements de synchronisation
8. Les deux scénarios yG1p = ys(G2 ,G3 ) et yG1p > ys(G2 ,G3 ) génèrent les mêmes éléments dans l'alphabet
dans le produit lors de l'exécution de s(G2 , G3 ). Notamment, des éléments du type (a1 , b1 , b1 ) où a1 ∈ G1p , et
b1 ∈ s(G2 , G3 ).
des paires s(Gj , Gk ) ; l'intérêt est qu'il s'agit des blocs d'opérations qui peuvent être exécutés en
parallèle.
La première inégalité est équivalente à yG3p − ys(G1 ,G2 ) ≥ yG2p − ys(G1 ,G3 ) , indiquant que G3p
dépasse ys(G1 ,G2 ) dans une mesure égale ou supérieure à celle dans laquelle yG2p dépasse ys(G1 ,G3 ) .
Cela suggère intuitivement que G3p doit être exécuté au plus tôt, an de minimiser le temps
d'exécution global. Par conséquent, dans la Fig. 4.10a), il est proposé d'exécuter G3p aussi
tôt que possible (i.e. lorsque s(G2 , G3 ) s'achève) pour que le parallélisme puisse être exploité
tout d'abord avec G1p , suivi par s(G1 , G2 ), et nalement de G2p . Dans la Fig. 4.10a), certains
intervalles d'oisiveté sont inévitables telles que le bloc suivant l'exécution de s(G2 , G3 ), introduit
par l'achèvement de G1p (si achèvement après s(G2 , G3 )) qui conditionne le début d'exécution
de s(G1 , G2 ) dans les deux automates G1 et G2 . Le même principe est appliqué pour le bloc
Pour le scénario 2, comme les événements de G1 s'achèvent avant s(G2 , G3 ) (voir Fig. 4.10b)), la
séquence optimale proposée est d'exécuter immédiatement s(G1 , G2 ) (avec G3p simultanément)
et ensuite exécuter s(G1 , G3 ) une fois que G3p s'achève. G3p conditionne le début d'exécution de
s(G1 , G3 ) dans les automates G1 et G3 , ce qui peut introduire l'intervalle inévitable d'oisiveté
De manière analogue à la section précédente, le comportement des dateurs est examiné et formulé
dans les expressions (4.17-4.21). Dans (4.17), la première partie de la fonction établit que si le
scénario 1 est considéré, les seuls micro-événements générés dans A123,1 (à être substitués dans
1 1 1
(4.4)) seront de la forme (a , b , b ). Par contre, si le scénario 2 se déroule, alors les micro-
événements générés peuvent être des types (a1 , b1 , b1 ) et (e1 , b1 , b1 ), puisque (Fig. 4.10b)) G1p
s'achève avant s(G2 , G3 ), introduisant un laps de temps inévitable.
Les conditions Ci , pour i = 1, ..., 8, visent à simplier la notation dans les équations (4.18) et
(4.19), et décrivent des relations générales des dateurs (e.g. le dateur privé de Gi est inférieur au
dateur privé de Gj et en même temps les dateurs globaux sont égaux). Les conditions Ci−jk dé-
notent la valeur dans laquelle le dateur privé d'un automate dépasse le dateur de synchronisation
L'analyse de (4.17) est identique pour l'ensemble des équations (4.18-4.21) où les éléments A112,3 ,
A113,2 , et A11,2,3 sont déterminés pour être substitués dans (4.4).
(A1 \A1 ∪ A1 ) × (A1 ∩ A1 ) × (A1 ∩ A1 ) si (yG1p ≥ ys(G2 ,G3 ) )
1 2 3 2 3 2 3
A123,1 = (4.17)
[(A1 \A1 ∪ A1 ) ∪ e1 ] × (A1 ∩ A1 ) × (A1 ∩ A1 ) si (y
1 2 3 2 3 2 3 G1p < ys(G2 ,G3 ) )
(A1 ∩ A13 ) × (A12 \A11 ∪ A13 ) × (A11 ∩ A13 ) si C2 ∨ C3
1
A113,2 = (A11 ∩ A13 ) × [(A12 \A11 ∪ A13 ) ∪ e1 ] × (A11 ∩ A13 ) si C4 ∨ C5 ∨ C6 (4.19)
1
(A1 ∩ A13 ) × e1 × (A11 ∩ A13 )
si C7 ∨ C8
[(A11 \A12 ∪ A13 ) × e1 × (A13 \A11 ∪ A12 )] ∪ A13 si (yG1p > ys(G2 ,G3 ) )
e1 × (A12 \A11 ∪ A13 ) × (A13 \A11 ∪ A12 )
si (yG3p > ys(G1 ,G2 ) ) ∧ (C3−12 ≤ yG2p ) ∧ (yG1p ≤ ys(G2 ,G3 ) )
A11,2,3 = (4.20)
e1 × [(A12 \A11 ∪ A13 ) ∪ e1 ] × (A13 \A11 ∪ A12 )
si (yG3p > ys(G1 ,G2 ) ) ∧ (C3−12 > yG2p ) ∧ (yG1p ≤ ys(G2 ,G3 ) )
∅ si (yG3p ≤ ys(G1 ,G2 ) ) ∧ (yG1p ≤ ys(G2 ,G3 ) )
[e1 × (A12 \A11 ∪ A13 ) × (A13 \A11 ∪ A12 )] ∪ [e1 × (A12 \A11 ∪ A13 ) × e1 ]
si (yG2 ⊗ C1−23 > yG3 ) ∧ (yG3 > yG1 )
A113 = (4.21)
e1 × (A12 \A11 ∪ A13 ) × (A13 \A11 ∪ A12 ) si (yG2 ⊗ C1−23 ≤ yG3 ) ∧ (yG3 > yG1 )
e1 × (A1 \A1 ∪ A1 ) × e1
si (yG2 ⊗ C1−23 > yG3 ) ∧ (yG3 = yG1 )
2 1 3
Ainsi, l'ensemble des équations (4.17-4.21) dénit l'alphabet pour un système à 3 automates,
makespan.
chronisée
est modié par l'insertion des micro-événements synchronisant la tierce (G1 , G2 , G3 ). Le bloc
s(G1 , G2 , G3 ) peut être considéré dès l'instant initial ou à n'importe quel point d'exécution pour
lequel les 3 automates permettent la synchronisation. Cette inclusion des micro-événements liés
à l'exécution de s(G1 , G2 , G3 ) n'a aucun eet sur les éléments déjà déterminés pour les autres
rations sans aucune perte de généralité, sachant qu'une représentation multi-états (des permu-
tations) sous-jacente assure que chaque opération ne s'exécute qu'une seule fois.
Figure 4.11: Système à 3 automates (n = 3) présentant tous les possibles types de synchroni-
sation (représentation simpliée mono-état pour faciliter la compréhension).
- Les dateurs privés : yG1p = y(m11 ) = 4, yG2p = y(m16 ) = 9, et yG3p = y(m1 ) ⊗ y(r2 ) = 19.
Les expressions (4.17-4.21), avec les valeurs des dateurs correspondants, dénissent les éléments
ci-dessous :
A1 = {(r11 , r11 , r11 ), (m111 , m119 , m119 ), (e1 , m119 , m119 ), (m110 , m110 , m11 ), (m110 , m110 , r21 ), (m14 , e1 , m14 ),
(e1 , m116 , m11 ), (e1 , m116 , r21 ), (e1 , e1 , m11 ), (e1 , e1 , r21 )}.
tions pendant une unité de temps, e.g. (m111 , m119 , m119 ) dénote l'exécution de m11 dans G1 , et
m19 dans G2 , et G3 . En outre, A1 garantit que ces éléments génèrent au moins une trajectoire
telle que le makespan soit minimisé. Les trajectoires générées représenteraient alors des mots
Trajectoires Générées
Par concaténation des éléments dans le micro-alphabet A1 , des trajectoires (ou suites d'exécu-
tion) peuvent être obtenues. Les trajectoires T1 et T2 sont générées en respectant l'hypothèse
4.1 :
T1 : (r11 , r11 , r11 )6 (m111 , m119 , m119 )4 (e1 , m119 , m119 )4 (m110 , m110 , m11 )6 (m110 , m110 , r21 )2 (e1 , m116 , r21 )9
(e1 , e1 , r21 )2 (m14 , e1 , m14 )3 ,
T2 : (r11 , r11 , r11 )6 (m111 , m119 , m119 )4 (e1 , m119 , m119 )4 (m110 , m110 , r21 )8 (e1 , m116 , r21 )5 (e1 , m116 , m11 )4
(e1 , e1 , m11 )2 (m14 , e1 , m14 )3 .
Pour T1 , rappelant que la notation dans la dénition 4.5 indique que (a1 , b1 , c1 )j ⇔ (aj , bj , cj ),
l'opération r1 est active pendant 6 unités de temps, autorisée communément par les 3 automates,
jusqu'à son achèvement. Ensuite m11 est activée (dans G1 ) simultanément avec m19 (dans G2
et G3 ) pendant 4 unités de temps jusqu'à l'achèvement de m11 . Puis m19 se poursuit pendant
4 unités de temps encore, et ainsi de suite. Les dateurs pour T1 et T2 prennent la même valeur,
qui est le produit des dateurs des macro-événements composés. Par exemple, pour T1 :
y(T1 ) = [y(r16 ) ⊕ y(r16 ) ⊕ y(r16 )] ⊗ [y(m411 ) ⊕ y(m419 ) ⊕ y(m419 )] ⊗ . . . ⊗ [y(m34 ) ⊕ y(e3 ) ⊕ y(m34 )]
y(T1 ) = [6 ⊕ 6 ⊕ 6] ⊗ [4 ⊕ 4 ⊕ 4] ⊗ . . . ⊗ [3 ⊕ 3 ⊕ 3]
y(T1 ) = 6 ⊗ 4 ⊗ . . . ⊗ 3 = 36.
Le dateur de la trajectoire y(T1 ) représente la date d'achèvement pour toutes les opérations
dans cette séquence. En outre, dans la Fig. 4.11, l'automate du plus grand dateur est G3 avec
yG3 = 36 ; conrmant que T1 modélise l'exécution de toutes les opérations au plus tôt puisqu'il
s'agit du temps minimum pour exécuter toutes les opérations dans G3 . Remarque identique pour
T2 qui a le même dateur mais modélise une séquence d'exécution diérente.
Les trajectoires, telles que T1 et T2 , sont issues de l'alphabet proposé et modélisent des
exécutions optimales de toutes les opérations en exploitant le parallélisme entre les automates
optimisé par analyse des ordonnancements des blocs d'événements résultant d'un classement
alors un modèle décrivant, par le micro-alphabet proposé, les possibles exécutions de toutes les
L'approche proposée dans [44] relève de la détermination d'un produit synchrone pour automates
(max,+). Les bases formelles de cette approche, comme l'extension des alphabets originaux, a
inspiré les développements proposés ici. An de souligner la contribution de l'approche présentée,
d'autres trajectoires obtenues par [44] (4.3) pour le même exemple seraient :
Les trajectoires T3 et T4 sont décrites sous la notation de [44]. Les dateurs pour T3 , et T4 , sont
calculés comme proposé dans [44] (et de manière analogue au calcul ici) :
Le dateur pour T4 est identique puisque les mêmes événements composés sont considérés dans
les dates d'achèvement des opérations simultanées sont plus exibles et lorsqu'une opération
vient d'achever son exécution, une autre peut exploiter ses ressources immédiatement, réduisant
le makespan. Il est rappelé que, seule la syntaxe du modèle à base d'automates a été abordée
ici (spéciquement l'alphabet). Rien ne s'oppose à ce que cette proposition soit exploitée en
9. Ce qui est pourtant le but dans un modèle basé sur les automates (max,+).
10. en sachant qu'au niveau syntaxique les automates (min,+) et (max,+) ne peuvent pas être diérenciés.
Pour les cas de plus de 3 automates locaux modélisant l'exclusion mutuelle entre les opérations
il est possible de généraliser l'approche. Ici, seuls les aspects fondamentaux de la méthodologie
sont décrits pour des exemples avec n=4 et n=6 pour illustration.
Pour 4 automates locaux, le classement répondant à la dénition 4.13, est présenté par (4.22).
Dans le cas le plus général, où tous les types de synchronisation surviennent, les dateurs globaux
yG1 = yG1p ⊗ ys(G1 ,G2 ) ⊗ ys(G1 ,G3 ) ⊗ ys(G1 ,G4 ) ⊗ ys(G1 ,G2 ,G3 ) ⊗ ys(G1 ,G2 ,G4 ) ⊗
(4.23)
ys(G1 ,G3 ,G4 ) ⊗ ys(G1 ,G2 ,G3 ,G4 )
yG2 = yG2p ⊗ ys(G1 ,G2 ) ⊗ ys(G2 ,G3 ) ⊗ ys(G2 ,G4 ) ⊗ ys(G1 ,G2 ,G3 ) ⊗ ys(G1 ,G2 ,G4 ) ⊗
(4.24)
ys(G2 ,G3 ,G4 ) ⊗ ys(G1 ,G2 ,G3 ,G4 )
yG3 = yG3p ⊗ ys(G1 ,G3 ) ⊗ ys(G2 ,G3 ) ⊗ ys(G3 ,G4 ) ⊗ ys(G1 ,G2 ,G3 ) ⊗ ys(G2 ,G3 ,G4 ) ⊗
(4.25)
ys(G1 ,G3 ,G4 ) ⊗ ys(G1 ,G2 ,G3 ,G4 )
yG4 = yG4p ⊗ ys(G1 ,G4 ) ⊗ ys(G2 ,G4 ) ⊗ ys(G3 ,G4 ) ⊗ ys(G1 ,G2 ,G4 ) ⊗ ys(G2 ,G3 ,G4 ) ⊗
(4.26)
ys(G1 ,G3 ,G4 ) ⊗ ys(G1 ,G2 ,G3 ,G4 )
Comme indiqué précédemment (n = 3), plusieurs inégalités peuvent être obtenues an d'analyser
le comportement temporel entre les sous-systèmes. Ainsi, de (4.22) les expressions yG1 ≤ yG2 ,
yG2 ≤ yG3 , et yG3 ≤ yG4 peuvent être obtenues, et de manière transitive : yG1 ≤ yG3 , yG1 ≤ yG4 ,
et yG2 ≤ yG4 .
Pour 4 automates locaux (n = 4), il y a 6 paires possibles (6 possibilités pour le scénario d'une
rale de classement (et les inégalités associées) il est possible de dénir les expressions (4.27-4.32).
De cet ensemble d'inégalités, les relations temporelles entre des ensembles d'opérations s'exé-
cutant simultanément peuvent être déduites. La Fig. 4.12 montre l'ordonnancement qualitatif
Figure 4.12: Ordonnancement qualitatif optimal pour n = 4 et (G1 , G2 ) comme la seule paire
en synchronisation.
Cet ordonnancement reste intuitif puisqu'une seule paire d'automates en synchronisation est
considérée. Le parallélisme est exploité au plus tôt avec l'exécution du bloc en synchronisation
avec les événements privés possibles dans les automates G3 et G4 , comme rapporté dans l'hy-
pothèse 4.3. Les segments grisés dans l'ordonnancement indiquent les intervalles des possibles
dates d'achèvement des blocs précédents (en cohérence avec les expressions (4.27-4.32)).
des ensembles d'opérations (i.e. blocs) sur l'axe temporel tel que des intervalles oisifs pour les
ressources soient évités, et tel que toutes les opérations soient exécutées au plus tôt.
Pour une meilleure illustration, l'exemple de la Fig. 4.13 présente une instance du terminal
pétrolier modélisée par 4 automates locaux. Il est rappelé que la représentation mono-état vise
Dans la Fig.4.13, les 4 automates se synchronisent sur l'opération r6 . D'autre part, les paires
synchronisées sont : (G1 , G3 ), par les opérations r2 et m6 , (G2 , G4 ) par r4 , et (G3 , G4 ) par
r5 . Suivant la règle de classement de dateurs, et la logique de blocs, la Fig. 4.14 présente les
résultats naux. Naturellement, avec l'augmentation de la complexité des relations entre sous-
des dateurs selon la règle de classement, et la Fig. 4.14b) présente l'ordonnancement obtenu. Pour
cet ordonnancement, il a été supposé que ys(G1 ,G3 ) < ys(G2 ,G4 ) an d'illustrer que l'exécution
même instant. Les blocs grisés qui suivent les blocs s(G1 , G3 ) dénotent l'intervalle des dates
d'achèvement possibles.
Figure 4.13: Exemple pour 4 automates locaux (représentation simpliée à un seul état pour
facilité la compréhension).
Plusieurs scénarios de synchronisation possibles sont dénis lorsqu'un système comporte 4 auto-
mates locaux. Pour une seule paire d'automates en synchronisation 6 alternatives sont possibles,
6 6
2 = 15 possibilités pour 2 paires, et
i pour i paires ∀i ∈ {1, . . . , 6}. Aussi, d'autres scénarios
incluent : les tierces, la synchronisation de 4 automates, et des combinaisons de tous les scénarios
susmentionnés (e.g. 2 paires et une tierce). Ceci donne une idée de l'augmentation de la com-
plexité et de la raison pour laquelle une formulation générique n'a pas été eectuée pour tous
les cas possibles. Pourtant, une méthodologie basée sur un classement de dateurs a été proposée
D'autres problèmes peuvent être étudiés avec la démarche proposée. Par exemple, si un ensemble
d'automates et l'analyse par blocs permettra identier les conséquences de telles contraintes au
niveau de l'ordonnancement.
Un exemple pour n=6 est présenté dans la Fig. 4.15. Il décrit la synchronisation de 3 paires
d'automates : (G1 , G4 ), (G2 , G5 ), et (G1 , G6 ). L'ordonnancement présenté est optimal et les seg-
ments grisés indiquent les dates possibles d'achèvement des blocs d'opérations (il a été supposé
11
que ys(G2 ,G5 ) > ys(G1 ,G4 ) ). L'exécution de s(G1 , G6 ) est conditionnée par l'achèvement de G6p ,
puisqu'il est connu (par la règle de classement, i.e. yG6 ≥ yG1 ⇒ yG6p ≥ ys(G1 ,G4 ) ⊗ yG1p ) que
L'approche proposée dans ce chapitre est ainsi bien adaptée aux systèmes pour lesquels un en-
semble d'opérations doit être exécuté au plus tôt sous conit de partage de ressources. Elle
relève d'un classement d'automates en fonction de l'identication des dateurs, ce qui permet
ensuite une étude des ordonnancements qualitatifs par une vue d'intégration de blocs (d'événe-
aux techniques approximatives (tels que heuristiques), provient du fait que le comportement du
11. pour illustrer que l'exécution des blocs d'opérations pour 2 paires en synchronisation ne se terminent pas
forcément au même instant.
Ce travail présente les premiers eorts pour dénir un produit synchrone basé sur la décompo-
sition de transitions pour générer un comportement temporel global au plus tôt. Le classement
d'automates à base de dateurs permet de dériver les conditions formelles construisant les ordon-
La méthodologie pourrait être aussi exploitée pour analyser les conséquences de certaines ma-
global du système ; ou 2) l'aectation de ressources diérentes pour les opérations générant des
changements logiques au niveaux des conits et temporels dans l'ordonnancement. Des analyses
pourraient être appliquées au modèle mathématique visant à déduire les changements opération-
L'approche est à ce point plus adéquate pour des systèmes dont la modélisation doit reposer
sur des approches formelles, et implique des développements plus élaborés et denses lorsque n
augmente. Cependant, la formulation de l'alphabet reste complexe.
Conclusions Partielles
Une approche a été proposée pour la détermination d'un nouvel alphabet pour le produit syn-
chrone d'automates tropicaux sous comportement au plus tôt. L'approche est appliquée à la pro-
et de maintenance. La modélisation des conits par automates locaux est intuitive et les ordon-
nancements optimaux forcés sont obtenus par une analyse des informations temporelles des sous-
systèmes, notamment à l'aide d'un cadre mathématique basé sur des dateurs. Un micro-alphabet
pouvant décrire les ordonnancements optimaux est obtenu par une abstraction d'exécution de
L'approche présentée s'est limitée à la syntaxe du produit. Les travaux futurs envisagés à partir
de ces résultats incluent la dénition des aspects de sémantique (i.e. le langage) et la synthèse
des systèmes exécutant de nombreuses opérations avec des ressources limitées et au plus tôt
(e.g. systèmes de production, systèmes embarqués et réseaux de diérente nature tel que les
télécommunications et le transport).
Conclusions et Perspectives
Cette recherche a porté sur l'étude des approches tropicales pour des problèmes d'optimisa-
tion dans un terminal maritime pétrolier en vue d'assister les opérateurs de supervision. Les
approches proposées restent applicables aux réseaux de ux en général, voire des systèmes de
nature diérente. Une recherche sur diverses techniques alternatives de modélisation a permis
de constater : 1) une complémentarité des techniques en fonction des applications (i.e. réseaux
de Petri vs algèbre (max,+), TPN vs automates temporisés, théorie des graphes vs algèbres tro-
picales) ; 2) des avantages des approches tropicales pour le problème d'optimisation traité ; et 3)
des perspectives pour des nouvelles propositions considérant des approches alternatives. Dans le
cadre de la modélisation, les approches retenues ont été l'algèbre (max,+) et les automates tro-
picaux. D'autre part, dans le cadre de la technique de résolution, les algorithmes génétiques ont
été retenus du fait de son importance dans la communauté scientique et d'une implémentation
directe, ouvrant ainsi un spectre de possibilités pour la transposition des propositions présentées
été exploitée en vue de la synthèse du modèle en une contrainte unique. Les phénomènes de
conit de partage de ressources ont été modélisés par des variables de décision conduisant à des
modèles (max,+) non linéaires. Les avantages de manipulation des systèmes (max,+) linéaires
ont été exploitées par des propositions de priorisation d'opérations conictuelles (résultant en une
linéarisation du fait de l'aectation des variables de décision). Ces derniers résultats présentent
des approches candidates pour des applications industrielles dans lesquelles une telle priorisation
est envisageable. Dans ces cas, la détermination de l'ordonnancement consiste alors à un simple
115
Les caractéristiques du système industriel étudié ont permis d'identier des objectifs non com-
mensurables qui ont été représentés par un modèle d'optimisation multi-objectif. Une approche
a été proposée par l'intégration de modèles (max,+) non linéaires avec des algorithmes géné-
tiques. Les bases de cette approche sont une modélisation intuitive et concise des contraintes du
système, suivie de l'application d'un algorithme génétique adapté sous une structure génomique
hiérarchique permettant un contrôle entre les gènes complémentaires d'un même niveau (en vue
d'éviter un éloignement de l'espace de faisabilité). Il a été possible d'obtenir des systèmes d'équa-
tions (max,+) linéaires pour chaque individu (déterminant les dateurs des opérations) facilement
exploitables. Ainsi, les meilleures solutions représentant les compromis les plus avantageux entre
En vue d'assister les opérateurs de supervision, les résultats obtenus permettent de présenter des
solutions candidates complétant son expertise en temps réel. Sachant que dans le cas d'étude,
ainsi que dans diverses applications, les opérateurs disposent rarement d'informations sur les
1
impacts nanciers de leur décisions , les résultats fournis permettent bien d'intégrer ces in-
formations à celles gérées par les opérateurs (telles que topologie du réseau, disponibilité des
Le domaine spécique considérée relève des systèmes à événements discrets. À ce titre, des tech-
niques formelles ont également été abordées. Du fait du caractère temporel de la problématique,
les automates tropicaux ont été exploités pour une modélisation simple des conits de partage
de ressources. Sachant qu'un comportement au plus tôt supposerait une exploitation maximale
considéré. Ainsi, la contribution développée, porte sur la détermination des aspects syntaxiques
de ce produit (l'alphabet). Les formulations proposées du nouvel alphabet portent sur un cadre
théorique basé sur des dateurs. Il est ainsi possible de classer les sous-systèmes (automates lo-
caux), et de déterminer des ordonnancements au plus tôt par une analyse de décomposition des
au plus tôt des ressources. Les alphabets deviennent plus denses, en comparaison avec des pro-
duits synchrones pour des automates (max,+) modélisant un comportement au plus tard. Le
résultat global des investigations dans le cadre formel est l'alphabet pour un produit d'automates
Les travaux de recherche se sont déroulés en interaction avec les partenaires industriels
validation des propositions. Ce dynamisme a permis ainsi une modularisation maîtrisé des
avancées scientiques. Des approches mono-objectif ont été proposées par l'exploitation des
5.2 Perspectives
Dans le cadre des techniques formelles, en partant des développements proposés ici pour l'al-
phabet du nouveau produit d'automates tropicaux, les aspects sémantiques tels que le langage
devraient être abordés. Cela permettra de compter sur un modèle formel pour la détermination
du comportement global du système. Ensuite, l'exploitation des approches de commande par su-
pervision pourra être considérée en vue de restreindre le comportement du système par rapport
sources.
L'exploration des techniques alternatives de modélisation a donné des perspectives pour envisager
des propositions hybrides avec les algèbres tropicales. Dans le cadre des automates cellulaires, en
sachant qu'ils peuvent être exploités pour des problèmes d'ordonnancement, il semble prometteur
d'explorer l'intégration des algèbres tropicales dans la dénition des règles d'évolution.
Enn, vis-à-vis de l'apport proposé pour l'intégration des algorithmes génétiques avec l'algèbre
(max,+), il peut être considéré qu'une intégration analogue émerge pour tout système pouvant
décision. Ainsi, des problèmes d'optimisation exprimés sur l'algèbre (min,+) pourraient être
traités de manière équivalente à l'approche proposée ici avec les algorithmes génétiques. En outre,
des intégrations avec d'autres approches de l'intelligence articielle (e.g. essaims particulaires et
colonies de fourmis) sont à exploiter. Enn, en termes de performance, des algorithmes autres que
le SPEA peuvent être exploités dans le cadre des propositions présentées dans ces investigations.
Glossaire
Alignement : chemin reliant 2 n÷uds par des segments. Dans le cas de pipelines, un
alignement est formé par des dispositifs de contrôle de ux (vannes dans ce mémoire)
Algèbres Tropicales : ensemble des algèbres nommées ainsi à cause de son précurseur Imre
SIMON, [19]. Parmi les algèbres tropicales, les algèbres (max,+) et (min,+) peuvent être
citées.
Automate (max,+) : automate avec des transitions pondérées par des gains. Le coût
associé à un mot w dans l'automate est le coût maximal parmi les coûts de tous les
Automate (min,+) : automate avec des transitions pondérées par des coûts. Le coût
associé à un mot w dans l'automate est le coût minimal parmi les coûts de tous les
tuellement exlusives) à l'aide d'un état et `n' transitions (à la fois sortantes et entrantes
manière indistincte.
Capacité Opérative : nombre maximum d'alignements disjoints qui peuvent être habilités
utilisé pour dénoter les passages de fermeture à ouverture, ou vice versa, pour les vannes.
Dateur : variable décrivant une date fondamentale dans l'exécution d'un événement.
Dateur Global : pour un automate Gi , il est déni comme le produit (max,+) de l'en-
N
semble des dateurs pour des événements appartenant à l'alphabet ; i.e. yGi = a∈Ai y(a).
Le dateur global regroupe dateurs privées et de synchronisation et formellement s'ex-
prime par : yGi = yGip ⊗ ys(Gi ,Gj ) ⊗ ys(Gj ,Gk ) ⊗ ys(Gi ,Gk ) ⊗ ys(Gi ,Gj ,Gk ) , pour le cas de 3
Dateur Privé : pour un automate Gi , il est déni comme le produit (max,+) de tous les
N
dateurs concernant les événements privés dans cet automate ; i.e. yGip = a∈Aip y(a). Le
dateur privé est dénoté par yGip et Aip dénote le sous-ensemble de l'alphabet de Gi qui
au point puits en considérant que toutes les vannes pour le transfert sont ouvertes et
macro-événement de même durée que dans les autres, voir dénition 4.5.
vide, ou pendant n unités de temps, pour le cas du macro-événement vide, voir dénition
4.7.
Opération : terme utilisé pour faire référence aux activités de maintenance, ainsi qu'aux
opération de transfert.
Ressource : dispositif devant être aecté à une opération lors de l'exploitation du réseau.
Simultanée (Exécution) : terme utilisé pour faire référence à des opérations qui s'exé-
cutent en parallèle mais qui ne débutent ou terminent pas forcément à la même date.
qu'elles débutent et terminent en même temps. Ici, le terme est utilisé lors que le même
événement s'exécute en même temps sur un ensemble d'automates, i.e. les automates
dédiés et prédénis, des solutions pour des instances des modèles d'optimisation fournis.
Transition Atomique : fait référence à une transition à une durée d'une unité de temps.
doctorale. Lyon, France : INSA de Lyon. Laboratoire Ampère UMR CNRS 5005.
[2] J. Rojas-D'Onofrio, J. González, E. Boutleux, and E. Niel. Path search algorithm mini-
[3] J. Rojas-D'Onofrio, J. Márquez, E. Boutleux, and E. Niel. Path search algorithm for connec-
tions with pumps in crude oil pipe networks. In 18th IFAC World Congress, 2011. Milano
network in terms of operative capacity & failure risk. In 15th International Congress on
Automation, Systems and Instrumentation, 2011.
[5] R. Karuppiaha, K.C. Furmanb, and I.E. Grossmann. Global optimization for scheduling
renery crude oil operations. Computers & Chemical Engineering, 32(11) :27452766, 2008.
[6] A. Nait-Sidi-Moh, M.-A. Manier, A. El Moudni, and M. Wack. Petri net with conicts
and (max,plus) algebra for transportation systems. In 11th IFAC Symposium on Control
in Transportation Systems, volume 11, pages 548553, 2006.
[7] I. Nasri, G. Habchi, and R. Boukezzoula. An algebraic max-plus model for HVLV systems
scheduling and optimization with repetitive and exible periodic preventive maintenance :
[8] K. Balachandran, J.D. Bendtsen, R.L. Olsen, and J.M. Pedersen. Energy resource mana-
gement in smart grid. In Complexity in Engineering (COMPENG), 2012, pages 16, 2012.
Publisher : IEEE. DOI : 10.1109/CompEng.2012.6242960.
121
[10] S.-H. Ok, W.-J. Seo, J.-H. Ahn, S. Kang, and B. Moon. An ant colony optimization approach
for the preference-based shortest path search. In Communication and Networking, pages
[11] T. Erlebach. Approximation algorithms for edge-disjoint paths and unsplittable ow. In
Ecient Approximation and Online Algorithms, volume 3484, pages 97134. Springer, 2006.
DOI : 10.1007/11671541_4.
[12] S. Yuan, B. Raghavachari, and A. Patel. Finding maximum reliable path in mesh net-
[13] S. Gyapay, A. Pataricza, J. Sziray, and F. Friedler. Petri net-based optimization of produc-
[14] M.J.C. e Silva, W.J. Silva, and P.R.M. Maciel. Modelling and analysis in production system :
an approach based on petri net. In IEEE International Conference on Systems, Man and
Cybernetics, volume 5, pages 4354 4359, 2004. DOI : 10.1109/ICSMC.2004.1401216.
[15] Wang J. Modeling closed loop supply chain system based on stochastic fuzzy petri net. In
[16] O.H. Roux, D. Deleu, and P. Molinaro. Discrete time approach of time petri nets for real-
[17] M. Alsaba, J-L. Boimond, and S. Lahaye. Sur la commande des systèmes exibles de
production manufacturière par l'algèbre des dioïdes. Revue e-STA, Sciences et Technologies
de l'Automatique, 4(2) :32473259, 2007.
[20] F. Baccelli, G. Cohen, G. Jan-Olsder, and J-P. Quadrat. Synchronization and Linearity an
Algebra for Discrete Event Systems. Wiley, 2001.
[21] M. Gondran. Algèbre linéaire et cheminement dans un graphe. RAIRO - Operations Re-
search, 9 :7799, 1975.
[22] G. Cohen, S. Gaubert, and J-P. Quadrat. L'algèbre des sandwichs. Pour la Science, (328) :
5663, 2005.
[24] M. Andersen. Max-plus algebra : properties and applications, 2002. Projet de Master en
[25] A. Nowak. The tropical eigenvalue-vector problem from algebraic, graphical, and compu-
tational perspectives, 2014. Honors Theses (Paper 97). Department of Mathematics. Bates
College.
[26] L. Houssin. Cyclic jobshop problem and (max,plus) algebra. In World IFAC Congress
(IFAC 2011), pages 27172721, 2014.
[27] M. Akian, S. Gaubert, and A. Guterman. Tropical polyhedra are equivalent to mean
payo games. International Journal of Algebra and Computation, 22(1), 2012. DOI :
10.1142/S0218196711006674.
[28] B. Heidergott, G.J.and Olsder, and J.V.D. Woude. Max Plus at work. Princeton Press,
2006.
[29] L. Houssin, S. Lahaye, and J-L. Boimond. Commande en juste-à-temps sous contraintes de
[30] Z. Königsberg. Modeling, analysis and timetable design of a helicopter maintenance pro-
cess based on timed event petri nets and max-plus algebra. Neural, Parallel & Scientic
Computations, 18(1) :112, 2010.
[31] T.L. Turocy and B. Von Stengel. Game theory. Encyclopedia of Information Systems.
Elsevier, pages 403420, 2003. doi :10.1016/B0-12-227240-4/00076-9.
[32] C. Cassandras and S. Lafortune. Introduction to Discrete Event Systems. Springer, 2nd
edition, 2006.
[33] R. Alur and D. L. Dill. A theory of timed automata. Theoretical Computer Science, 126
[35] Y. Abdeddaim, A. Kerbaa, and O. Maler. Task graph scheduling using timed automata. In
Proceedings of the International Parallel and Distributed Processing Symposium, 2003. IEEE.
DOI : 10.1109/IPDPS.2003.1213431.
[36] Y. Abdeddaim and O. Maler. Job-shop scheduling using timed automata. Computer Aided
Verication. Lecture Notes in Computer Science, 2102 :478492, 2001. DOI : 10.1007/3-540-
44585-4_46.
[37] K.T. Seow, M. Gai, and T.L. Lim. A temporal logic specication interface for automata-theoretic
[38] M. Wang, Y. Qian, and X. Guang. Improved calculation method of shortest path with cellular
[39] F. Seredynski and A.Y. Zomaya. Sequential and parallel cellular automata-based scheduling
algorithms. IEEE Transactions on Parallel and Distributed Systems, 13(10) :1009 1023, 2002.
DOI : 10.1109/TPDS.2002.1041877.
[41] S. Lahaye, J. Komenda, and J. Boimond. Modélisation modulaire à l'aide d'automates (max,+).
[42] S. Lahaye, J. Komenda, and J. Boimond. Compositions of (max,+) automata. Discrete Event
Dynamic Systems, 2014. Springer. DOI : 10.1007/s10626-014-0186-6.
[43] J. Komenda, S. Lahaye, and J. Boimond. Supervisory control of (max,+) automata : A behavioral
[44] J. Komenda, S. Lahaye, and J-L. Boimond. Le produit synchrone des automates (max,+). Special
Issue of Journal Européen des Systèmes Automatisés - JESA, 43(7-9) :10331047, 2009.
for exible job shop scheduling problem. New Advanced Technologies, 2010. Available from :
[46] P. Udhayakumar and S. Kumanan. Integrated scheduling of exible manufacturing system using
[47] H. Pierreval and L. Tautou. Using evolutionary algorithms and simulation for the optimization
[48] M. Basseur, E.-G. Talbi, A. Nebro, and E. Alba. Metaheuristics for multiobjective combinatorial
optimization problems : Review and recent issues, 2006. Institut National de Recherche en
[49] K. F. Man, K. S. Tang, and S. Kwong. Genetic algorithms : Concepts and applications. IEEE
Transactions on Industrial Electronics, 43(5) :519534, 1996.
[50] M. Gen. Springer Handbook of Engineering Statistics : Genetic Algorithms and Their Applica-
tions. Springer, 2006.
[51] P. R. Srivastava and T.-h. Kim. Application of genetic algorithm in software testing. Interna-
tional journal of software engineering and its applications, 3(4) :8795, 2009.
In edited by Springer, editor, Metaheuristics for Multiobjective Optimisation, volume 535, pages
337. Springer Berlin Heidelberg, 2004.
[54] C. Coello, G. Lamont, and D. Van Veldhuizen. Evolutionary algorithms for solving multi-
objective problems. 2nd edition. In Genetic and Evolutionary Computation. Springer, 2007.
Chapter 2.
[55] A. Ghosh and S. Dehuri. Evolutionary algorithms for multi-criterion optimization : a survey.
2001. Thèse Doctorale (Chapitre 2). Université des Sciences Sociales Toulouse I.
[57] E. Zitzler, M. Laumanns, and L. Thiele. SPEA2 : Improving the Strength Pareto Evolutionary
[58] J. M. A. Pangilinan and G. K. Janssens. Evolutionary algorithms for the multiobjective shor-
test path planning problem. In International journal of computer and information science and
engineering, pages 5459, 2007.
[59] K. Quintero, E. Niel, J. Aguilar, and L. Piétrac. (max, +) optimization model for scheduling
operations in a ow network with preventive maintenance tasks. InLecture Notes in Enginee-
ring and Computer Science : Proceedings of The World Congress on Engineering and Computer
Science, WCECS 2013, volume 2, pages 10361041, 2013. 23-25 October.
[61] S. Gaubert. Methods and applications of (max,+) linear algebra. Lecture Notes in Computer
[62] K. Quintero, E. Niel, J. Aguilar, and L. Piétrac. Scheduling operations in a ow network with
exible preventive maintenance : A (max, +) approach. Engineering Letters, 22(1) :2433, 2014.
[64] W.J. Moore and A.G. Starr. An intelligent maintenance system for continuous cost-based prio-
[65] K. Quintero. Capacité de reconguration dans les réseaux de pipelines, 2010. Rapport de Stage
[66] K. Quintero, E. Niel, J. Aguilar, and Piétrac L. A cost-criticality based (max,+) optimization
model for operations scheduling. In Edited Book by Springer, editor, Transactions on Enginee-
ring Technologies. Springer, 2015.
[67] K. Quintero, E. Niel, and J. Aguilar. (max,+) model for alignment selection and schedule
[68] C.-L. Lin, C.-H. Huang, and C.-W. Tsai. Structure-specied real coded genetic algorithms with
applications. Advanced Knowledge Based Systems : Model, Applications & Research, 1 :160187,
2010.
[69] Ô. Yeniay. Penalty function methods for constrained optimization with genetic algorithms.
[70] L. Daviaud. Comportements asymptotiques des automates max-plus et min-plus, 2014. Thèse
doctorale. Université Paris Diderot (Paris 7) Sorbonne Paris Cité. Laboratoire d'Informatique
[71] T. Colcombet and L. Daviaud. Approximate comparison of distance automata. In STACS 2013
- 30th International Symposium on Theoretical Aspects of Computer Science, 2013. 574-585.
[72] M. Kammoun, Z. Achour, and N. Rezg. Air trac management using petri net synthesis tools.
In 8th International Conference of Modeling and Simulation - MOSIM'10. `Evaluation and op-
timization of innovative production systems of goods and services', 2010. Hammamet - Tunisia.