Optimisation multicritère par Pareto-optimalité de problèmes d’ordonnancement en tenant compte du coût de la production

27/09/2017
Publication e-STA e-STA 2006-1
OAI : oai:www.see.asso.fr:545:2006-1:19970
DOI :

Résumé

Optimisation multicritère par Pareto-optimalité de problèmes d’ordonnancement en tenant compte du coût de la production

Auteurs

Sur l’étude du processus d'écriture à la main. Approches classiques et non conventionnelles
Sur l’étude du processus d'écriture à la main. Approches classiques et non conventionnelles
Sur l’unicité de la réponse d’un réseau d’énergie électrique en régime de défauts
Optimisation multicritère par Pareto-optimalité de problèmes d’ordonnancement en tenant compte du coût de la production
Stabilités Comparées de Systèmes Non Linéaires et Linéarisés Basées sur une Description Redondante
Les réseaux de neurones. Application à la modélisation et à la commande des processus
Les réseaux de neurones. Classification
Les réseaux de neurones. Présentation
Stabilité et stabilisation de systèmes discrets à retard
Sur la commande par mode glissant d’un convertisseur multicellulaire série
Recherche automatique de l’architecture d’un réseau de neurones artificiels pour le credit scoring
Chiffrement Partiel des Images Basé sur la Synchronisation de Systèmes Hyperchaotiques en Temps Discret et la Transformée en Cosinus Discrète
Synthèse d’une Commande Stabilisante par Retour d’Etat de Systèmes Linéaires à Retard
Stratégies de Commande de Systèmes Manufacturiers à Contraintes de Temps Face aux Perturbations Temporelles
Etude de la Stabilité d’une Classe de Systèmes de Commande Floue de type Mamdani
Nouvelles conditions suffisantes de stabilisabilité de processus échantillonnés non linéaires
Modélisation multi-physiques d’un actionneur linéaire incrémental pour la motorisation d’une pousse-seringue
Performances comparées de méthodes de commandes par mode de glissement et par platitude d’un papillon motorisé
Etude des Incertitudes dans les Ateliers Manufacturiers à Contraintes de Temps
Modèles discrétisés du système d’écriture à la main par la transformation d’Euler et par RLS
Technique proposée pour le déchiffrage dans un système de transmission sécurisée
Stabilisation de systèmes à retard par un régulateur du premier ordre
Détermination d’attracteurs emboîtés pour les systèmes non linéaires
Modélisation par Réseaux de Petri d’une ligne de traitement de surfaces mono-robot/multi-produits
Domaine de stabilité indépendante du retard d'un système linéaire à commande retardée
Sur le credit scoring par les réseaux de neurones artificiels
Sur l'analyse et la synchronisation de systèmes chaotiques Chen
Comparaison entre les EP et les CF pour l’Optimisation des Systèmes Dynamiques Hybrides
Algorithmes génétiques sequentiels pour la résolution de problèmes d’ordonnancement en industries agroalimentaires
2011-01 04-eSTA-V26.pdf

Métriques

28
10
106.03 Ko
 application/pdf
bitcache://4b49eb781bad44a1fae79b320e803a8a2d9e8ca3

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/545:2006-1/19970</identifier><creators><creator><creatorName>Mohamed Benrejeb</creatorName></creator><creator><creatorName>Ihsen Saad</creatorName></creator></creators><titles>
            <title>Optimisation multicritère par Pareto-optimalité de problèmes d’ordonnancement en tenant compte du coût de la production</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Wed 27 Sep 2017</date>
	    <date dateType="Updated">Wed 27 Sep 2017</date>
            <date dateType="Submitted">Mon 15 Oct 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">4b49eb781bad44a1fae79b320e803a8a2d9e8ca3</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>33907</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Optimisation multicritère par Pareto-optimalité de problèmes d’ordonnancement en tenant compte du coût de la production Ihsen SAAD, Mohamed BENREJEB Unité de Recherche LARA-Automatique Ecole Nationale d’Ingénieurs de Tunis, BP.37, le Belvédère, 1002, Tunis, Tunisie ihsen.saad@enit.rnu.tn, mohamed.benrejeb@enit.rnu.tn Résumé - Cet article traite le problème de la maximalisation de la quantité des produits réalisés dans un atelier Job-Shop flexible, tout en minimisant au mieux le Makespan, les coûts de pénalités et le coût de fabrication, en utilisant les algorithmes génétiques. L’approche adoptée consiste à générer une variété de solutions optimales diversifiées dans l’espace de recherche de solutions, et d’aider le décideur, quand il ne peut pas donner une préférence particulière à l’une des fonctions objectif. Mots clés - Ordonnancement, Job-Shop flexible, Pareto- optimalité, optimisation multicritère, algorithme génétique, Avance/Retard, coût de production. I. INTRODUCTION ’optimisation multiobjectif cherche à optimiser plusieurs composantes d’un vecteur de fonctions objectif. Contrairement au monobjectif, le problème multiobjectif n’a pas une solution unique, mais un ensemble de solutions, connu comme l’ensemble des solutions Pareto-optimales. Toute solution de cet ensemble est optimale dans le sens qu’aucune amélioration ne peut être faite sur une composante sans dégradation d’au moins une autre composante du vecteur [8]. Compte tenu qu’une solution choisie par un décideur peut ne pas être acceptable par un autre, il s’avère utile de prévoir plusieurs alternatives au choix d’une solution Pareto optimale [11]. Dans cet article, sont traités les problèmes d’ordonnancement dans les ateliers de production de type Job-Shop flexible où l’objectif principal est de produire le maximum de produits avec un temps d’exécution et un coût minimal. L’objectif est donc de rechercher un ordonnancement réalisable minimisant le Makespan, la charge critique, la charge totale, la pénalité Avance/Retard et le coût de fabrication, en appliquant des méthodes de transformation des problèmes multiobjectif en problèmes monobjectif [1]. Cet article est organisé comme suit. Le problème Job-Shop flexible est formulée dans la section 2 et l’approche de résolution proposée à ce problème décrite dans le section 3. L’efficacité de cette approche est testée pour deux benchmarks dans la section 4. II. FORMULATION DU PROBLEME JOB-SHOP FLEXIBLE Le problème d’ordonnancement Job-Shop flexible présente la difficulté de l’affectation des tâches de chaque produit à une machine, et celle relative à l’ordonnancement de l’ensemble des tâches dans un ordre minimisant un certain critère. Le but de l’étude envisagée est de rechercher un ordonnancement réalisable qui minimise le Makespan, la charge critique, la charge totale, la pénalité Avance/Retard ainsi que le coût de fabrication. Les données du problème considéré sont les suivants : • Il y a N produits indépendants, soit Jj , 1 2j N= , ,..., ; • Chaque produit jJ nécessite un ensemble d’opérations à réaliser selon un ordre bien défini, spécifique à la gamme de fabrication jG ; • Chaque gamme de fabrication jG nécessite une série de jn opérations i jO, , 1 ji n= ,..., ; • La réalisation de chaque opération i jO, nécessite la sélection d’une ressource ou d’une machine kM parmi M machines, 1k M= ,..., . • Chaque machine ne peut réaliser qu’une seule opération à la fois; • La préemption n’est pas autorisée. Notations : jr : date de début au plus tôt du produit jJ jd : date de fin au plus tard à laquelle on désire avoir terminé l’exécution du produit jJ L jtf : date de fin d’exécution du produit jJ i j kp , , : durée d’exécution de l’opération i jO, sur la machine kM i jα , : durée minimale de i jO, , i jα , = 1 min ( )i j k k M d , , ≤ ≤ , kw : charge de la machine kM j kω , : coefficient d’utilisation de la machine kM pour la production du produit jJ , {0 1}j kω , = , kjw : charge de la machine kM pour le produit jJ jMp : matière première du produit jJ kCm : coût unitaire sur la machine kM jCf : coût de fabrication du produit jJ A. Formulations des critères et du coût total de production Les critères considérés sont en nombre de cinq, dont les trois premiers constituent des critères classiques utilisés pour l’optimisation des problèmes d’ordonnancement de type Job-Shop flexible [4][9], et les deux derniers sont deux critères économiques récemment élaborés [6]. Les objectifs considérés sont relatifs à la minimisation: • du Makespan 1C : 1 max 1 max j j N C C tf⎛ ⎞ ⎜ ⎟ ⎝ ⎠≤ ≤ = = (1) • de la charge critique 2C : ( )2 1 max k k M C w ≤ ≤ = (2) • de la charge totale des machines 3C : 3 1 M k k C w = = ∑ (3) • de la pénalité d’avance et de retard 4C : 4 1 1 ( ) N N j j j j j j j C A h E b T = = = = +∑ ∑ (4) avec pour l’avance : max(0 )j j jE d tf= , − (5) et pour le retard : max(0 )j j jT tf d= , − (6) jh et jb étant les coûts de pénalisation du produit jJ respectivement pour l’avance et le retard, et jA la pénalité pour le produit jJ , • du coût de fabrication des produits 5C : ( ) 5 1 1 1 j j N j j k k kj j N k M C Cf Mp Cm wω ≤ ≤ , ≤ ≤ ≤ ≤ = ⎛ ⎞ = +⎜ ⎟ ⎝ ⎠ ∑ ∑ ∑ (7) Le coût de la production d’un produit jJ étant jCp : j j jCp A Cf= + (8) le coût total de production pC est donc : 4 5pC C C= + (9) B. Formulations des bornes inférieures B.1. Bornes du Makespan En supposant qu’il n’y pas d’intervalle d’attente entre deux opérations successives, considérons la minoration suivante : 1 1 jn j i j j i r tf j Nα , = + ≤ , ∀ = ,...,∑ (10) Par application du la fonction “ max ” sur l’inégalité (10), il vient : 1 1 1 max max( ) jn j i j j j N j N i r tfα , ≤ ≤ ≤ ≤ = ⎧ ⎫⎪ ⎪ + ≤⎨ ⎬ ⎪ ⎪⎩ ⎭ ∑ (11) ou encore : max 1 1 max jn j i j j N i r Cα , ≤ ≤ = ⎧ ⎫⎪ ⎪ + ≤⎨ ⎬ ⎪ ⎪⎩ ⎭ ∑ (12) Le premier membre de cette inégalité constitue une borne inférieure du Makespan des produits : 1 1 1 max jn b j i j j N i C r α , ≤ ≤ = ⎧ ⎫⎪ ⎪ = +⎨ ⎬ ⎪ ⎪⎩ ⎭ ∑ (13) Si le cardinal de l’ensemble des N produits est supérieur au nombre de machines, ou dans le cas de relaxation de certaines contraintes (préemption des tâches, contrainte disjonctive sur les ressources,...), il n’y a pas de solution atteignant la borne inférieure [2]. La méthode de calcul d’une borne inférieure possible 2bC , à appliquer dans ce cas, est la suivante : 2 1 1 1 1 jnM N b k ij k j i C r M α ⎛ ⎞ ⎜ ⎟′ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟= = =⎝ ⎠ = +∑ ∑∑ (14) où kr ′ est la date de disponibilité au plus tôt de la machine k . Les bornes 1bC et 2bC ainsi définies permettent de prévoir des limites pour les valeurs du Makespan : { }1 1 2 maxmaxb b bC C C C= , ≤ (15) B.2. Borne inférieure de la charge critique des machines La borne inférieure de la charge critique des machines, notée 2 b C , s’exprime par [3]: 1 1 2 jnN i j j ib C E M α ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ,⎜ ⎟ ⎜ ⎟= =⎝ ⎠ ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ∑ ∑ (16) où E(.) est la partie entière. B.3. Borne inférieure de la charge totale des machines La borne inférieure de la charge totale des machines, notée 3 b C , s’exprime par [5]: 3 1 1 jnN b i j j i C α ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ,⎜ ⎟ ⎜ ⎟= =⎝ ⎠ = ∑ ∑ (17) B.4. Borne inférieure de la pénalité d’Avance et du Retard En supposant que les produits finissent juste à temps (pas de stocks et pas de pénalités), la valeur du critère 4C est positive : 4 0C ≥ (18) La borne inférieure relative à la pénalité d’avance et du retard est donc zéro [6]. B.5. Borne inférieure du coût de fabrication des produits En considérant que les produits finissent juste à temps (pas de stocks et pas de pénalités), l’inégalité suivante est toujours vraie pour chaque opération i jO, : min ( )k i j k k i j k k Cm p Cm p, , , ,≥ (19) La quantité suivante 5 b C constitue dans ce cas une borne inférieure du coût de fabrication des produits [6] : 5 1 1 1 min ( ) jnN N b j i j k k k j j i C Mp p Cm, , = = = = + .∑ ∑∑ (20) III. APPROCHE D’EVALUATION MULTICRITERE D’une manière générale, les critères considérés présentent des relations non linéaires et complexes entre elles et n’ont pas forcement la même importance du point de vue de décideur. Ainsi, beaucoup de considérations peuvent être retenues pour tenir compte de toutes ces difficultés. Pour ce faire, une méthode d’évaluation floue est proposée. Cette dernière est basée sur les étapes qui suivent : • Pour chaque fonction objectif, une borne inférieure est calculée, telle que : ( ) 1b i i cC x C x S i n≥ ∀ ∈ , ≤ ≤ (21) où S est l’espace des solutions réalisables et cn nombre de fonctions objectif. • Les valeurs des fonctions objectif, dans la plupart des cas, peuvent appartenir à différents intervalles de magnitude variable. En particulier, soit H une heuristique choisie et h iC la valeur maximale de la solution donnée par l’heuristique considérée selon la iéme fonction objectif. La fuzzification est appliquée en utilisant les fonctions d’appartenance décrites sur la figure 1. Un vecteur ( )C x est associé à chaque solution réalisable x , 1( ) c b b nC x C C⎡ ⎤⎡ ⎤∈ ,+∞ ×...× ,+∞⎣ ⎦ ⎣ ⎦ , avec 1( ) ( ( ) ( ))c T nC x C x C x= ,..., . Pour chaque vecteur ( )C x , une fuzzification de ses composantes ( )iC x , proposée selon leurs positions dans les intervalles b h i iC C⎡ ⎤ ⎢ ⎥ ⎣ ⎦ , , est considérée en deux sous-ensembles flous i B et i M , figure 1. On a : C C (x) ( ( )) si ( ) h B b hi i i i i i ih b i i C x C x C C C C ε µ ε ε − + ⎡ ⎤= , ∈ , +⎣ ⎦− + ( ( )) 0 sinonB i iC xµ = , (22) ( ( ))B i iC xµ étant la mesure floue de ( )iC x dans le sous- ensemble i B . 1 µ C + εC B M ii i i b h Ci i Fig 1. Application floue dans la résolution du problème d’échelle Ensuite, la qualité de chaque solution x est caractérisée par le vecteur ( )BC x (23) dont toutes les composantes sont homogènes puisqu’elles appartiennent toutes au même intervalle [0 1], et sont toutes sans dimension : 1( ) ( ) ( ( )) 1 2 c T B n B i i i c C x a a a C x i nµ = ,..., = , ∀ = , ,..., (23) • Pour l’évaluation multicritère, la fonction objectif ( )gC x est réduite à la minimisation de la somme pondérée des critères relative à l’utilisation de l’opérateur d’agrégation OWA [10] : 1 ( ) cn g i i i C x w a = = ∑ (24) Pour aider le décideur quand il ne peut pas clairement donner une préférence particulière à des fonctions objectif, un ensemble de solutions Pareto-optimales est construit sans accorder de privilège à une direction particulière de recherche. Cette approche est basée sur un algorithme dans lequel, la fonction objectif ( )gC . , définie dans la relation (24), est utilisée pour l’évaluation des solutions. Les pondérations iw (1 )ci n≤ ≤ sont calculées en utilisant une règle floue. L’idée est de mesurer la qualité moyenne des solutions selon chaque critère à chaque itération et de calculer les différents poids suivant le degré de cette qualité. Le but est d’étudier les gains et les améliorations possibles des solutions en accordant la priorité à l’optimisation des fonctions objectif dont la moyenne des valeurs est loin de la borne inférieure, cette approche est appelée approche agrégative avec direction de recherche dynamique. Soit k iC la moyenne des solutions de la ieme i fonction objectif trouvée à la ieme k itération : ( ) ( ) k k ix Pk i k C x C card P ∈ = ∑ (25) kP étant la population des solutions à cette itération. b i 1 iC µ C +i ε k Ci b Proche Loin i ' k 0 Fig 2. Fonction d’appartenance des différentes valeurs des critères Pour chaque vecteur ( )C x , une fuzziffication est appliquée sur ces composantes ( )iC x selon leurs positions dans les intervalles 0b iiC C ε′⎡ ⎤, +⎣ ⎦ où ε′ est une petite valeur positive introduite pour éviter le problème de la division par zéro ( 0 1 b iCε′ = . , si 0 b i iCC = ; 0ε′ = sinon ). L’évaluation de la qualité des solutions se fait en utilisant les fonctions d’appartenance définies dans la figure 2, relatives aux deux sous ensembles flous, Proche et Loin de la borne inférieure. Les fonctions d’appartenance peuvent ainsi être formulées comme suit [3] : ( ) 0 0 si k b k kL bi i i i iik ib i i CC CC C C CC µ ε ε − ′⎡ ⎤= , ∈ , +⎣ ⎦′− + (26) ( ) 1 sinonkL iik Cµ = , Le calcul des différentes pondérations 1k iw + est effectué en utilisant les deux règles floues suivantes : • Si ( k iC est Proche de b iC ) alors ( 1k iw + diminue ) • Si ( k iC est Loin de b iC ) alors ( 1k iw + augmente ) qui conduisent à l’expression de k iw suivante : ( ) ( )1 tq 1 et 2c kL ik ik i cn kL jk j j C w i k i n k Q C µ µ = = , ∀ ∀ ≤ ≤ ≤ ≤ ∑ (27) 1 iw correspond à la première itération définie par : 1 1 tq 1i c c w i i n n = , ∀ ≤ ≤ (28) Q le nombre total d’itérations et L l’indice relatif au sous-ensemble flou Loin. Les différents vecteurs de pondération 1 2 ( )Q W W W, ,..., sont calculés progressivement de la ieme k génération kP à la génération 1kP + , selon la distance entre les bornes inférieures et la moyenne des individus de la ieme k génération, représentée par une cercle noir fermé dans la figure 3. Le but est d’améliorer des solutions en accordant la priorité à l’optimisation des fonctions objectif dont la moyenne des valeurs est loin de la borne inférieure. Il s’en suit qu’en utilisant une règle floue, il est envisageable de contrôler la direction de recherche afin de construire un ensemble final avec des solutions s’approchant le plus possible des valeurs optimales, figure 3. C b 1 2C b C1 2C solutions pour différentes populations bornes inférieures optimum pour la population P1 P P k Q W W 1 k+1 Pk Fig 3. Direction de recherche Cette méthode, généralement utilisée quand le décideur ne peut pas donner une préférence particulière à une fonction objectif, permet aussi de générer des poids des critères différents d’une itération à une autre de manière dynamique en fonction de la moyenne des solutions. IV. SIMULATION Deux benchmarks de type Job-Shop flexible N M× , traitant N produits sur M machines [9], sont traités ici pour montrer la validité de la mise en œuvre de la méthode d’optimisation multicritère par Pareto-optimalité. Les coûts de pénalité et le coût de la matière sont, dans les deux cas, les suivants (en unité monétaire) : 2 0 5 2 1 2 3 1 2 j j j k Mp h et b j N Cm k M = , = , = , = , ,..., = , = , ,..., A. Benchmark 1 L’application consiste à réaliser 15 produits sur 10 machines, le nombre des opérations étant constant pour tous les produits et les durées opératoires données par le tableau 1, et les critères à optimiser en nombre 5 étant formulés dans les relations (1-4) et (7). L’application de l’approche d’optimisation proposée a donné l’ordonnancement présenté dans la table 2, pour lequel les valeurs des critères sont indiquées dans la table 5. B. Benchmark 2 Dans cette application, 8 produits sont à réaliser sur 8 machines, le nombre des opérations variant ici selon le produit pour les durées opératoires du tableau 3, et les critères à optimiser en nombre 5 étant formulés dans les relations (1-4) et (7). L’approche proposée a donné, dans ce cas, les deux ordonnancements différents, de la table 4, relatifs à des critères de valeurs identiques, table 5. Tab 1. Durées opératoires relatives au benchmark 15 10× M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 O1,1 1 4 6 9 3 5 2 8 9 4 O2,1 1 1 3 4 8 10 4 11 4 3 O3,1 2 5 1 5 6 9 5 10 3 2 J1 O4,1 10 4 5 9 8 4 15 8 4 4 O1,2 4 8 7 1 9 6 1 10 7 1 O2,2 6 11 2 7 5 3 5 14 9 2 O3,2 8 5 8 9 4 3 5 3 8 1 J2 O4,2 9 3 6 1 2 6 4 1 7 2 O1,3 7 1 8 5 4 9 1 2 3 4 O2,3 5 10 6 4 9 5 1 7 1 6 O3,3 4 2 3 8 7 4 6 9 8 4 J3 O4,3 7 3 12 1 6 5 8 3 5 2 O1,4 6 2 5 4 1 2 3 6 5 4 O2,4 8 5 7 4 1 2 36 5 8 5 O3,4 9 6 2 4 5 1 3 6 5 2 J4 O4,4 11 4 5 6 2 7 5 4 2 1 O1,5 6 2 5 4 1 2 3 6 5 4 O2,5 5 4 6 3 5 2 28 7 4 5 O3,5 6 2 4 3 6 5 2 4 7 9 J5 O4,5 6 5 4 2 3 2 5 4 7 5 O1,6 4 1 3 2 6 9 8 5 4 2 J6 O2,6 1 3 6 5 4 7 5 4 6 5 O1,7 1 4 2 5 3 6 9 8 5 4 J7 O2,7 2 1 4 5 2 3 5 4 2 5 O1,8 2 3 6 2 5 4 1 5 8 7 O2,8 4 5 6 2 3 5 4 1 2 5 O3,8 3 5 4 2 5 49 8 5 4 5 J8 O4,8 1 2 36 5 2 3 6 4 11 2 O1,9 6 3 2 22 44 11 10 23 5 1 O2,9 2 3 2 12 15 10 12 14 18 16 O3,9 20 17 12 5 9 6 4 7 5 6 J9 O4,9 9 8 7 4 5 8 7 4 56 2 O1,10 5 8 7 4 56 3 2 5 4 1 O2,10 2 5 6 9 8 5 4 2 5 4 O3,10 6 3 2 5 4 7 4 5 2 1 J10 O4,10 3 2 5 6 5 8 7 4 5 2 O1,11 1 2 3 6 5 2 1 4 2 1 O2,11 2 3 6 3 2 1 4 10 12 1 O3,11 3 6 2 5 8 4 6 3 2 5 J11 O4,11 4 1 45 6 2 4 1 25 2 4 O1,12 9 8 5 6 3 6 5 2 4 2 O2,12 5 8 9 5 4 75 63 6 5 21 O3,12 12 5 4 6 3 2 5 4 2 5 J12 O4,12 8 7 9 5 6 3 2 5 8 4 O1,13 4 2 5 6 8 5 6 4 6 2 O2,13 3 5 4 7 5 8 6 6 3 2 O3,13 5 4 5 8 5 4 6 5 4 2 J13 O4,13 3 2 5 6 5 4 8 5 6 4 O1,14 2 3 5 4 6 5 4 85 4 5 O2,14 6 2 4 5 8 6 5 4 2 6 O3,14 3 25 4 8 5 6 3 2 5 4 J14 O4,14 8 5 6 4 2 3 6 8 5 4 O1,15 2 5 6 8 5 6 3 2 5 4 O2,15 5 6 2 5 4 2 5 3 2 5 O3,15 4 5 2 3 5 2 8 4 7 5 J15 O4,15 6 2 11 14 2 3 6 5 4 8 Tab. 2. Solution relative au benchmark 15 10× O1 O2 O3 O4 J1 1;5;6 1;16;17 3;18;19 6;19;23 J2 4;3;4 3;4;6 10;15;16 4;18;19 J3 2;6;7 7;15;16 2;16;18 4;19;20 J4 5;0;1 5;10;11 6;16;17 10;21;22 J5 5;9;10 6;10;12 2;18;20 4;20;22 J6 2;7;8 1;17;18 J7 1;6;7 1;18;20 J8 7;2;3 8;15;16 4;16;18 1;20;21 J9 10;8;9 3;9;11 7;16;20 8;20;24 J10 10;9;10 8;16;18 10;18;19 10;22;24 J11 7;14;15 6;15;16 9;16;18 7;20;21 J12 8;13;15 5;15;19 9;19;21 7;21;23 J13 2;11;13 10;13;15 10;19;21 2;21;23 J14 1;12;14 9;14;16 8;18;20 5;20;22 J15 1;14;16 3;16;18 3;19;21 5;22;24 Tab. 3. Durées opératoires relatives au benchmark 8 8× M1 M2 M3 M4 M5 M6 M7 M8 O1,1 5 3 5 3 3 20 10 9 O2,1 10 20 5 8 3 9 9 6J1 O3,1 20 10 20 5 6 2 4 5 O1,2 5 7 3 9 8 20 9 20 O2,2 20 8 5 2 6 7 10 9 O3,2 20 10 20 5 6 4 1 7 J2 O4,2 10 8 9 6 4 7 20 20 O1,3 10 20 20 7 6 5 2 4 O2,3 20 10 6 4 8 9 10 20J3 O3,3 1 4 5 6 20 10 20 7 O1,4 3 1 6 5 9 7 8 4 O2,4 12 11 7 8 10 5 6 9J4 O3,4 4 6 2 10 3 9 5 7 O1,5 3 6 7 8 9 20 10 20 O2,5 10 20 7 4 9 8 6 20 O3,5 20 9 8 7 4 2 7 20 J5 O4,5 11 9 20 6 7 5 3 6 O1,6 6 7 1 4 6 9 20 10 O2,6 11 20 9 9 9 7 6 4J6 O2,6 10 5 9 10 11 20 10 20 O1,7 5 4 2 6 7 20 10 20 O2,7 20 9 20 9 11 9 10 5J7 O2,7 20 8 9 3 8 6 20 10 O1,8 2 8 5 9 20 4 20 10 O2,8 7 4 7 8 9 20 10 20 O3,8 9 9 20 8 5 6 7 1 J8 O4,8 9 20 3 7 1 5 8 20 Les différentes valeurs des critères données par la méthode d’optimisation multicritère par Pareto-optimlité montrent son efficacité, table 5. Les valeurs des critères pour la frontière sont assez proches de celles des bornes inférieures. En effet, une telle approche permet de générer des solutions Pareto-optimales de bonne qualité. Les différents résultats obtenus par l’utilisation de la méthode d’optimisation multicritère par Pareto-optimlité sont présentés et comparés avec d’autres méthodes dans la table 6 : la colonne notée ’AL’ est relative à l’approche par localisation [4] et la colonne suivante ’PSO+SA’ est relative à l’optimisation par recuit simulé [9]. Les différents résultats montrent que les solutions obtenues sont généralement acceptables et satisfaisantes, malgré que cinq critères sont employés au lieu de trois critères dans [4] et [9]. Les valeurs des fonctions objectifs montrent l’efficacité de l’approche proposée, la table 5. Tab. 4. Solutions relatives au benchmark 8 8× O1 O2 O3 O4 J1 4;0;3 5;3;6 6;6;8 J2 3;0;3 4;3;5 7;9;10 5;10;14 J3 7;0;2 4;5;9 1;9;10 J4 2;0;1 6;1;6 1;10;14 J5 1;0;3 7;3;9 6;9;11 7;11;14 J6 3;3;4 8;4;8 2;9;14 J7 3;4;6 8;8;13 4;13;16 J8 1;3;5 2;5;9 8;13;14 5;14;15 O1 O2 O3 O4 J1 5;0;3 5;3;6 6;6;8 J2 3;0;3 4;3;5 7;9;10 5;10;14 J3 7;0;2 4;5;9 1;9;10 J4 2;0;1 6;1;6 1;10;14 J5 1;0;3 7;3;9 6;9;11 7;11;14 J6 3;3;4 8;4;8 2;9;14 J7 3;4;6 8;8;13 4;13;16 J8 1;3;5 2;5;9 8;13;14 5;14;15 Tab. 5. Résumé des résultats obtenus pour les deux benchmarks étudiés N M× 1 b C 1C 2 b C 2C 3 b C 3C 4 b C 4C 5 b C 5C gC 15 10× 23 24 10 11 91 94 0 17 287 312 0.933 8 8× 12 16 10 12 73 77 0 11.5 229 247 0.591 Tab. 6. Comparaison des résultats obtenus pour les deux benchmarks étudiés AL PSO+SA Méthode proposée N M× 1C 2C 3C 1C 2C 3C 1C 2C 3C 8 8× 16 13 75 16 13 73 16 12 77 15 10× 23 11 95 24 11 94 V. CONCLUSION L’optimisation multicritère par Pareto-optimlité s’effectue en deux parties: une partie d’évaluation et une partie de résolution. La première, vise à élaborer un moyen de mesure de la qualité des solutions et à intégrer par utilisation de la description floue des préférences subjectives dans un cadre coopératif. Elle peut conduire à des solutions dominantes, au sens Pareto, en exploitant un ensemble de bornes inférieures proposé. Dans la seconde partie, représentant le noyau de l’approche pour l’optimisation multicritère des ateliers flexibles de type Job-Shop, il s’est avéré possible d’intégrer au mieux les difficultés du problème et de tenir compte des préférences du décideur qui ne sont pas forcément homogènes. Elle permet aussi de générer des solutions admissibles tout en étudiant les relations de dominances possibles entre les solutions candidates et de déterminer une ou un ensemble de solutions dominantes selon les critères considérés ou selon une agrégation de tels critères. Références [1] Y. Collette et P. Siarry, Optimisation multiobjectif, Editions Eyrolles, Paris, 2002. [2] D. Berkoune, K. Mesghouni, et B. Rabenasolo, Approche d’évaluation pour des problèmes d’ordonnancement multicritère : Méthode d’agrégation avec direction de recherche dynamique, Méthodologies et Heuristiques pour l’Optimisation des Sys. Industriels, MHOSI’2005, 2005, Hammamet. [3] I. Kacem, Ordonnancement multicritère des job-shops flexibles : formulation, bornes inférieures et approche évolutionniste coopérative, Thèse de Doctorat, Université des Sciences et Technologiques de Lille, Lille, 2003. [4] I. Kacem, S. Hammadi and P. Borne. Pareto-optimality approach for flexible job-shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic. Math. and Computers in Sim., 60, pp. 245-276, 2002. [5] I. Kacem, S. Hammadi et P. Borne, Approach by localization and genetic manipulations algorithms for flexible Job-Shop probllems, Proceeding of International IEEE Conference on Systems, Man, and Cybernetics, Tucson Arizona, pp. 2599-2604, 2001. [6] I. Saad, S. Hammadi, M. Benrejeb et P. Borne, Choquet Integral for Criteria Aggregation in the Flexible Job-Shop Scheduling Problems, Sélectionné pour être publié dans IMACS International Journal, Mathematics and Computers in Simulation (MATCOM), 2006. [7] G. Syswerda, Schedule Optimization Using Genetic Algorithm, in Handbook of Genetic Algorithm, Van Nostrand Reinhold, New York, 1990. [8] E.G. Talbi, Métaheuristiques pour l’optimisation combinatoire multiobjectif, Tutorial, Journées Evolutionnaires Trimestrielles, Paris, 1999. [9] W. Xia et Z. Wu, An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 48, Issue 2, March 2005, pp. 409-425. [10] R.R. Yager, On weighted median aggregation operators in multicriteria decision making. IEEE Trans. on Systems, Man and Cybernetics, 18, pp. 183-190, 1988. [11] E. Zitzler et L. Thiele, Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. IEEE Transactions on Evolutionary Computation, 3, 4, pp. 257-271, November 1999.