Algorithmes génétiques sequentiels pour la résolution de problèmes d’ordonnancement en industries agroalimentaires

01/01/2011
Publication e-STA e-STA 2011-1
OAI : oai:www.see.asso.fr:545:2011-1:13449
DOI :

Résumé

Algorithmes génétiques sequentiels pour la résolution de problèmes d’ordonnancement en industries agroalimentaires

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

773
8
197.68 Ko
 application/pdf
bitcache://7d11945665ad3edb488d89912a34eccafc1b70bd

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:2011-1/13449</identifier><creators><creator><creatorName>Mohamed Benrejeb</creatorName></creator><creator><creatorName>Pierre Borne</creatorName></creator><creator><creatorName>Asma Karray</creatorName></creator></creators><titles>
            <title>Algorithmes génétiques sequentiels pour la résolution de problèmes d’ordonnancement en industries agroalimentaires</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2011</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sat 1 Jan 2011</date>
	    <date dateType="Updated">Mon 25 Jul 2016</date>
            <date dateType="Submitted">Wed 19 Sep 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">7d11945665ad3edb488d89912a34eccafc1b70bd</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>22480</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Algorithmes Génétiques Sequentiel pour la résolution de problèmes d’ordonnancement en industries agroalimentaires Asma Karray1,2 , Mohamed Benrejeb1 , Pierre Borne2 1 LARA Automatique: Ecole Nationale d’Ingénieurs de Tunis, BP 48, Le Belvédère 1002 Tunis, Tunisie 2 LAGIS: Ecole Centrale de Lille, Cité scientifique, BP 48, 59650 Villeneuve d’Ascq Cedex, France karray.asma@gmail.com, Mohamed.benrejeb@enit.rnu.tn, pierre.borne@ec-lille.fr Résumé—Dans cet article, un problème d’ordonnancement multi-objectif d’un atelier de production agroalimentaire à une machine est présenté. Les différentes caractéristiques et opérations le concernant sont introduites puis sa formulation et sa résolution par une nouvelle approche basée sur les algorithmes génétiques est proposée. L’idée de base de cette approche est d’utiliser les algorithmes génétiques de façon séquentielle. Les résultats d’une étude comparative avec des approches existantes dans la littérature montrent l’efficacité de notre proposition. Cette comparaison se base sur la qualité du résultat mais aussi sur le temps d’exécution. Mots clés-component; algorithmes génétiques ; séquentielle; ordonnancement; agroalimentaire; multi-objectifs ; une machine. I. INTRODUCTION L’ordonnancement est une branche de la recherche opérationnelle et de la gestion de la production qui vise à améliorer l’efficacité d’une entreprise en termes de coûts de production et de délais de livraison. Les problèmes d’ordonnancement sont présents dans tous les secteurs d’activités de l’économie, depuis l’industrie manufacturière [1] jusqu’à l’informatique [2]. Les différents problèmes que l'on rencontre en ordonnancement dépendent principalement des machines et de l'enchaînement des opérations. Parmi ces problèmes, on distingue les problèmes d’ordonnancement à une machine. Ces problèmes, utilisés comme modèle pour les autres catégories de problèmes, se sont avérés efficace en pratique [3]. Malgré leur apparente simplicité, les problèmes à une machine sont NP-difficiles au sens fort [4] [5] [6]. Plusieurs méthodes d’optimisation dont les méthodes exactes et les méthodes approchées peuvent être utilisées pour résoudre les problèmes d’ordonnancement. Les méthodes exactes telles que la programmation linéaire, la programmation dynamique et la méthode Branch & Bound se sont avérées peu efficaces pour la résolution des problèmes de grandes tailles, alors que les méthodes approchées ont conduit à des solutions proches de l’optimum. Parmi ces méthodes, les métaheuristiques ont prouvé leur efficacité pour la résolution de problèmes d’ordonnancement à une machine. Parmi ces métaheuristiques ont cite le recuit simulé [7], la recherche tabou [8], les algorithmes génétiques [9] [10], les colonies de fourmis [11] et les essaims particulaires [12]. L’approche proposée dans cet article est basée sur les algorithmes génétiques, initialement développés par Holland [13], qui constituent des algorithmes d’exploration fondés sur les mécanismes de la sélection naturelle et de la génétique. Ils se sont distingués par une grande efficacité face aux problèmes d’ordonnancement tel que le flow shop [14], le job shop [15] and l’open shop [16]. Aussi les algorithmes génétiques ont montré leur efficacité pour résoudre les problèmes à une machine [17], [18]. Dans cet article, un problème d’ordonnancement multi- objectif à une machine est considéré, l’approche relative à la résolution étant basée sur les algorithmes génétiques. Après la présentation en section 2, des différentes notations et des hypothèses du problème considéré. Les algorithmes génétiques ainsi que l’approche développée, sont introduits dans la section 3. Et leurs mises en œuvre dans la section 4. La comparaison des efficacités de la méthode développée avec celles des méthodes classiques pour deux benchmarks, effectuée dans la section 5. Notations ijO : jème opération du produit i ijt : date effective de début de fabrication de l’opération ijO ijr : date de début au plus tôt de l’opération ijO ijγ : date de fin effective de l’opération ijO ijd : date échue de l’opération ijO ijp : durée opératoire de l’opération ijO iP : produit fini de l’opération ijO ijkc : kème composant de l’ensemble des composants de l’opération ijO ijkυ : date de validité limite du composant ijkc iPC : date de fin de fabrication du produit iP ren ijkP : prix de revient du composant ijkc maxC : date de fin de l’ordonnancement i liv Pd : date de livraison du produit iP iPDv : durée de vie du produit iP iPDr : durée de retour du produit iP e-STA copyright 2011 by see Volume 8, N°1, pp 15-22 i ven PP : prix de vente unitaire du produit iP i stk PC : coût du stockage, par unité de temps, d’une unité du produit iP II. POSITION DU PROBLEME En industries agroalimentaires, les produits manipulés sont en général de durées de vie et de dates de mise en fabrication assez courtes. Ainsi, dans un atelier agroalimentaire, une opération est caractérisée aussi bien par sa date de début au plus tôt et sa date de fin au plus tard mais aussi par les dates de validités limites des composants nécessaires pour accomplir cette opération [19]. En plus du critère de la minimisation de la durée maximale d’exécution de l’ordonnancement, les autres critères choisis sont relatifs à l’industrie agro-alimentaire : • le coût des produits périmés, engendré par la péremption de certains composants primaires nécessaires pour la fabrication du produit fini; • le coût du discount distribution représentant la perte sur le prix de vente du produit fini, proportionnel à la durée du stockage du produit fini avant sa livraison. L’objectif est alors de sélectionner parmi l’ensemble des ordonnancements réalisables celui qui présente le meilleur compromis entre les différents critères en réduisant et en filtrant l’espace de recherche initial. La décision d’ordonnancer a pour objectif de minimiser les coûts engendrés par la péremption de certains composants, le coût du discount de distribution ainsi que la durée totale de fabrication du produit fini. Les fonctions objectifs C1, C2 et C3, considérées dans cet article, sont : • la minimisation de la durée maximale d’exécution de la dernière opération, 1 max ( )max 1 C C CPi i n = = ≤ ≤ (1) • le coût des produits périmés, ( ) max(0, ) 2 tij ijkrevC Pijk tij ijki j k ν ν  −  =∑∑∑  −   (2) • le coût du discount de distribution, 3 max 0, venP Pliv stkiC d C CPiP PDv Dri iP Pi i i     = − × +∑    −      (3) L’objectif de cet article est de construire un ordonnancement qui satisfait ces critères tout en respectant les contraintes du problème : • la contrainte de gamme qui représente l’ordre de passage de l’opération dans la gamme, • la contrainte de disponibilité de l’opération à ordonnancer selon sa date de début au plus tôt. III. ALGORITHMES GENETIQUES SEQUENTIEL (AGS) PROPOSE L’approche de résolution, présentée dans cet article, est basée sur le principe des algorithmes génétiques, largement utilisés ces dernières années pour la résolution de problème d’ordonnancement à une machine [20], [21], [22]. Les algorithmes génétiques utilisent à la fois les principes de la survie des structures les mieux adaptées, et les échanges d’informations aléatoires, parfois guidées, pour former un algorithme d’exploration qui possède certaines des caractéristiques de l’exploration humaine [23]. Après l’introduction de cette métaheuristique, est développée l’algorithme proposé nommé Algorithme Génétique Séquentiel AGS. A. Généralités sur les algorithmes génétiques Les algorithmes génétiques sont des techniques de recherche basées sur la théorie de l’évolution naturelle des espèces énoncée par Darwin. Ils se sont avérés très efficaces dans la résolution des problèmes complexes dans des différentes disciplines [24]. Ces algorithmes manipulent un ensemble de points dans l'espace de recherche, appelés population d'individus. Chaque individu ou chromosome représente une solution possible du problème donnée. Il est constitué d’éléments, appelés gènes, dont les valeurs sont appelées allèles. Les algorithmes génétiques font évoluer cette population d'individus par générations successives, en utilisant des opérateurs inspirés de la théorie de l'évolution qui sont la sélection, le croisement et la mutation. Le déroulement des algorithmes génétiques standards, figure1, peut être résumé comme suit : • génération de la population initiale, • sélection, • reproduction (croisement et mutation), • remplacement par la nouvelle population, B. Méthode proposée Notre approche proposée AGS, repose sur l’idée d’utiliser les algorithmes génétiques d’une façon séquentielle. En effet, au lieu d’utiliser un seul algorithme pour répondre aux trois critères C1, C2 et C3, trois algorithmes génétiques sont utilisés pour résoudre successivement ces trois critères. Le résultat trouvé par le premier algorithme est injecté dans le deuxième et ainsi de suite jusqu’à obtention d’un résultat qui satisfait les trois critères. Le codage choisi pour l’approche AGS est le codage CLOA et les opérateurs génétiques pris en considération sont l’opérateur de sélection par la roulette, l’opérateur de croisement bi-points et l’opérateur de mutation bi-points. e-STA copyright 2011 by see Volume 8, N°1, pp 15-22 Algorithme : Algorithmes génétiques Début Calculer fitness. Tant que « critère d’arrêt non satisfait » Faire Sélectionner individus Faire croisement des individus Faire mutation des individus Remplacer individus Calculer fitness Fin tant que Fin Figure 1. Etapes de mise en oeuvre des algorithmes génétiques La résolution par stratégie séquentielle se fait en trois étapes. • Etape 1: Application des algorithmes génétiques pour la résolution du critère C1. Dans cette étape, la population initiale est générée aléatoirement. Les opérateurs de sélection, de croisement et de mutation constituent le processus de reproduction pour créer de nouvelles populations qui est répété jusqu’à obtention d’une population PF1 qui s’approche au mieux de la solution optimale. • Etape 2 : La population PF1 obtenus précédemment est choisie comme population initiale de notre algorithme pour répondre au critère C2. A partir de cette population, des nouvelles populations sur lesquelles on applique les opérateurs de croisement, de mutation et de sélection sont générées de façon itérative. Au final, une nouvelle population PF2 proche de la solution optimale est obtenue. • Etape 3 : Cette étape est semblable à l’étape 2. En effet, la population PF2, obtenue précédemment, est choisie comme population initiale de notre algorithme pour répondre au critère C3. Elle servira de base pour les générations ultérieures qui sont obtenues à partir du processus de reproduction. Ce processus est répété jusqu’à l’obtention d’une population PF3 qui s’approche au mieux de la solution optimale. A la fin de cet algorithme, nous obtenons une population satisfaisant les trois critères C1, C2 et C3. Cette méthode de résolution que nous qualifions de séquentielle ou de série est schématisée dans la figure 2. IV. MISE EN ŒUVRE DE L’ALGORITHME PROPOSEE La mise en œuvre de l’algorithme génétique séquentiel proposé passe par plusieurs phases dont celle relative au codage, celle relative à la génération de la population initiale et ceux relatifs aux opérateurs génétiques. A. codage proposé Le codage CLOA proposé dans la figure 3, défini l’ordre, la date de début au plus tôt, la durée et la date de fin effective des opérations. Ce codage est inspiré du codage CLO (Codage Liste des Opérations) [25] et du codage CPM (Codage Parallèle Machines) [26] ; il consiste à proposer des listes ordonnées d’une gamme de produits en ligne de fabrication. Codage proposé. Début Génération aléatoire de la population initiale Evaluation des individus selon le critère C1 Test d’arrêt ? Population finale PF1 Croisement et Mutation Séléction Nouvelle génération Population initiale = PF1 Evaluation des individus selon le critère C2 Test d’arrêt ? Population finale PF2 Population initiale = PF2 Evaluation des individus selon le critère C3 Test d’arrêt ? Population finale PF3 Croisement et Mutation Séléction Nouvelle génération Croisement et Mutation Séléction Nouvelle génération Stop oui non oui non non oui Figure 2. Organigramme de l’algorithme AGS proposé La date de fin effective de l’opération ijo est obtenue par la relation (4) : max( , )ij ij ik ijr pγ γ= + (4) où ijγ représente la date de fin de l’opération iko qui précède l’opération ijo . B. Génération de la population initiale La population initiale est un ensemble d’individus qui servira de base pour les générations antérieurs. Ainsi, cet ensemble d’individus doit être assez diversifié. Pour avoir un ensemble d’individus assez diversifié, la génération de la population initiale dans notre application se fait en générant des individus aléatoirement. La figure 4 présente l’algorithme de génération de la population initiale. e-STA copyright 2011 by see Volume 8, N°1, pp 15-22 , , , 1 1 1 1 o r p i i i i γ , , , 2 2 2 2 o r p i i i i γ , , ,o r p ij ij ij ij γ Algorithme : Génération Aléatoire de la population aléatoire Variable locale n : taille de la population Début Pour i=1 jusqu’à n Faire Générer un individu valide aléatoirement Fin Pour Fin Figure 3. Codage proposé Figure 4. Algorithme de génération de la population initiale C. Opérateurs génétiques proposés Les opérateurs génétiques permettent la diversification la population au cours des générations et d’explorer l’espace d’état, représenté par l’espace des solutions. Ces différents opérateurs proposés pour la résolution du problème traité, sont présentés dans ce qui suit. 1) Opérateurs de séléction: La méthode de sélection élaborée est basée sur le principe de la roulette. Cette méthode exploite la métaphore d’une roulette de casino pour laquelle chaque individu de la population occupe une section de la roue proportionnelle à sa valeur d’évaluation. Ainsi, la position d’arrêt de la bille indique l’individu sélectionné. Dans cette méthode, les individus non dominés sont gardés afin de permettre l’obtention de différentes solutions optimales possibles qui constitueront un support de décision et garantiront aussi la diversité de l’évolution des individus. 2) Opérateurs de croisement : Dans cet article, nous avons choisi d’adapter le croisement bi-points. L’opération de croisement à deux points, illustrée par la figure 5, se déroule comme suit : L’opérateur, choisit deux individus parents et deux points de croisement choisis aléatoirement k1 et k2, ensuite, les opérations du parent1, qui précèdent le premier point de croisement et qui suivent le second point de croisement, sont copiées dans l’enfant 1 et les opérations du parent 2, qui précèdent le premier point de croisement et qui suivent le second point de croisement, sont copiées dans l’enfant 2. Finalement et à la même position, les opérations non existantes du parent 2 sont copiées dans l’enfant 1 et les opérations non existantes du parent 1 sont copiées dans l’enfant 2. 3) Opérateur de mutation : Cet opérateur choisit aléatoirement deux positions d’un même individu (parent), à chaque position correspond une opération ijo et une opération iko (ij et ik indices de l’opération). Ensuite, il y a permutation entre l’opération ijO et l’opération ijo pour générer un autre individu (enfant), figure 6. Figure 5. Exemple d’un croisement bi-points Figure 6. Exemple d’une mutation V. RESULTATS OBTENUS Après le choix du séquencement des critères, est présentée une comparaison des résultats obtenus par l’algorithme AGS proposée avec ceux obtenus par les méthodes classiques pour la résolution de problèmes multi-objectifs : l’approche Pareto- optimalité et la pondération des fonctions objectives. A. Exemples d’atelier à une machine Deux exemples, traitant de problèmes en industries agroalimentaires sont considérés. Ils consistent à ordonnancer respectivement 10 et 30 produits dans des ateliers à une machine pour montrer l’efficacité de l’approche développée AGS pour la résolution de deux problèmes de tailles et de complexités différentes dont les données sont consignées dans les annexes 1et 2. Ces données sont relatives aux date de début au plus tôt des opérations ( ijr ), durée opératoire des opérations ( ijp ), date de validité limite des composants ( ijkυ ), prix de revient des composants ( rev ijkP ), date de livraison du produit fini ( i liv Pd ), durée de vie du produit fini ( iPDv ), durée de retour du produit fini ( iPDr ), prix de vente unitaire du produit ( i ven PP ) et coût du e-STA copyright 2011 by see Volume 8, N°1, pp 15-22 stockage, par unité de temps, d’une unité du produit fini ( i stk PC ). Prenant en compte les données présentées, la durée minimale d’exécution de la dernière opération, le coût des produits périmés et le coût du discount de distribution sont calculés à partir des relations (1), (2) et (3). B. Analyse des résultats Après le choix des paramètres de l’approche AGS et le choix du séquencement des critères, est présentée une comparaison des résultats obtenus par l’algorithme AGS proposée avec ceux obtenus par les méthodes classiques. 1) Paramètre de l’approche AGS proposée Le tableau 1 indique les valeurs des paramètres utilisés par l’approche AGS, afin de générer les solutions. Ces paramètres sont la taille de la population, le nombre d’itérations, les probabilités de croisement et de mutation. TABLE I. VALEURS DES PARAMETRES RELATIF A L’ALGORITHME AGS Benchmark 1 Benchmark 2 Taille de la population 10 30 Nombre d’itérations 300 600 Probabilité de croisement 0.7 0.7 Probabilité de mutation 0.01 0.01 2) Choix du séquencement des critères L’algorithme AGS proposé, utilisant le codage CLOA est appliqué en vue d’obtenir le meilleur ordre de passage des opérations minimisant les critères C1, C2 et C3. Ainsi, pour un certains nombre de générations, l’application des opérateurs de croisement et de mutation génère de nouveaux individus dont les nouveaux coûts sont calculés d’une manière itérative jusqu’à l’obtention du meilleur individu de coût le plus bas. L’approche proposée étant basée sur l’utilisation des algorithmes génétiques d’une façon séquentielle, trois algorithmes génétiques sont utilisés chacun resolvant le problème relatif à un critère. Le résultat trouvé par le premier algorithme est traité par le deuxième et ainsi de suite jusqu’à obtention du résultat final minimisant les trois critères. Cette approche est appliquée d’abord pour les critères C1, C2 et C3 pris dans cet ordre. Par la suite, une permutation sur les critères est ensuite effectuée pour étudier l’influence de l’ordre sur la qualité du résultat final. Pour les six algorithmes ainsi distingués : AGS123, AGS132, AGS213, AGS231, AGS321 et AGS312. Le tableau 2 résume les résultats obtenus relatifs aux benchmark 1 et 2 par application de l’algorithme AGS proposé. Le choix du premier critère a donc une influence significative sur le résultat final obtenu par l’algorithme proposée AGS. En effet, la valeur minimale de chaque critère est obtenue lorsque l’algorithme proposé commence par la mise en œuvre de ce critère. Par exemple, la valeur minimale du critère C1 est 22 pour le benchmark 1 et 67 pour le second benchmark, ces valeurs sont obtenues par les algorithmes AGS123 et AGS132. De même pour le critère C2 et C3, la valeur minimale de chaque critère est obtenue respectivement par les algorithmes AGS213, AGS231 et les algorithmes AGS321 et AGS312. Nous envisageons maintenant de comparer les résultats obtenus par AGS avec ceux relatifs au problème d’optimisation considéré multi-objectifs ramené à un problème mono-objectif. Pour cela considérons la fonction F, somme pondérées aux poids respectifs 1α , 2α et 3α des trois fonctions objectifs C1, C2 et C3 : 1 1 2 2 3 3C C CF α α α+ += (5) avec : 0iα ≻ , 1,2,3i= et 1 2 3 1α α α+ + = . Les coefficients iα peuvent, par un choix adéquat de leurs valeurs, privilégier un critère par rapport à un autre. Nous avons imposé ces valeurs 0.4 pour C1, 0.1 pour C2 et 0.5 pour C3. Le coût du discount de distribution est ainsi privilégié par rapport à celui du makespan et par rapport à celui des produits périmés. Sur le tableau 3 qui donne la valeur de la fonction F, on note que l’algorithme AGS321 présente la plus basse valeur de la fonction F pour le premier benchmark alors que l’algorithme AGS 312 présente la plus basse valeur de la fonction F pour le benchmark 2. 3) Etude comparative des performances de l’algorithme AGS proposée : L’efficacité de l’approche AGS développée, est ici comparée avec celles relatives à l’approche Pareto-optimalité (APO) et l’approche basée sur la pondération des fonctions (APF) est effectué tout en se basant sur la valeur du minimum trouvé et le temps de compilation. Dans la mise en œuvre des deux approches APO et APF sont utilisées les mêmes valeurs des paramètres retenus pour le cas de l’algorithme AGS proposée du tableau 1. Les résultats obtenus par application des différentes méthodes utilisées pour les deux benchmarks sont consignés dans le tableau 4. Le meilleur résultat au benchmark 1 a été donc obtenu par application de la méthode développée AGS, la valeur de la fonction F trouvée étant inférieure à celles obtenues par APO et par APF. Ce résultat reste valable même lorsqu’on augmente le nombre d’opérations ce qui est le cas du benchmark 2. Du point de vue vitesse de compilation, l’approche AGS est plus rapide que les deux méthodes précédentes. En effet, la différence de vitesses, pour le benchmark 1, entre l’approche AGS et l’APO est approximativement de 4 seconde environ et entre l’approche AGS et l’APF est approximativement de 2 seconde. La différence de vitesses, pour le second benchmark, entre l’approche AGS et l’APO est approximativement de 22.5 seconde environ et entre l’approche AGS et l’APF est approximativement de 26.3 seconde. L’approche AGS développé permet donc de trouver de meilleurs résultats que ceux relatifs aux méthodes APO et APF et des temps de compilation plus rapide. e-STA copyright 2011 by see Volume 8, N°1, pp 15-22 TABLE II. RESULTATS DE SIMULATION DU SGA_1 Benchmark 1 Benchmark 2 AGS 123 AGS 132 AGS 213 AGS 231 AGS 321 AGS 312 AGS 123 AGS 132 AGS 213 AGS 231 AGS 321 AGS 312 C1 22 22 24 23 25 26 67 67 68 68 68 68 C2 8 8 8 8 13 14 59 59 59 58 62 64 C3 31 27 36 35 18 18 76 77 70 68 58 56 TABLE III. RESULTATS DE LA FONCTION OBJECTIVE F POUR CHAQUE ALGORITHMES Benchmark 1 Benchmark 2 AGS 123 AGS 132 AGS 213 AGS 231 AGS 321 AGS 312 AGS 123 AGS 132 AGS 213 AGS 231 AGS 321 AGS 312 F 25.1 23.1 28.4 27.5 20.3 20.8 70.7 71.2 68.1 67.1 62.4 61.6 TABLE IV. RESULTATS DE LA FONCTION OBJECTIVE F POUR CHAQUE ALGORITHMES Benchmark 1 Benchmark 2 Méthode d’optimisation APO APF AGS APO APF AGS F 25.5 24 20.3 82.4 85 61.6 CPU (s) 9.2526 8.6694 6.5011 68,3566 72,1139 45,8669 VI. CONCLUSION La nouvelle approche multi-objectif proposée exploitant les algorithmes génétiques pour l'ordonnancement d’un problème en industries agro-alimentaires à une machine, fondée sur l’idée d’utiliser le séquencement des objectifs, permet de fournir, en des temps acceptables, un ensemble de solutions optimales. Comparée aux méthodes APO et APF de point de vue qualité des résultats et temps de calcul, elle s’est révélée la plus efficace pour les deux benchmarks étudiés de différentes complexités. REFERENCES [1] M. Pinedo, Scheduling theory, algotithms, and Systems. Prentice- Hall, Inc., New Jersey, 1995. [2] J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt, J. Weglarz, Scheduling computer and manufacturing process. Springer, Berlin, 1996. [3] K. C. Ying, S. W. Lin, C. Y. Huang, Sequencing single-machine tardiness problems with sequence dependent setup times using an iterated greedy heuristic. Expert Systems with Applications, Vol. 36: 7087–7092, 2009. [4] J.K. Lenstra, A.H.G. Rinnooy Kan, P. Bruker, Complexity of machine scheduling problems. Annals of Discrete Mathematics, Vol. 1: 343-362, 1977. [5] M. Garey, D. Johnson, Computer and Intractability: a Guide to the Theory of NP- Completeness. Freeman W-H, San Francisco, 1979. [6] J. Carlier, Scheduling jobs with release dates and tails on identical machines to minimize the makespan. European Journal of Operational Research, Vol. 29: 298-306, 1987. [7] F. Jin, S. Song, C. Wu, A simulated annealing algorithm for single machine scheduling problems with family setups. Computers & Operations Research, Vol. 36: 2133- 2138, 2009. [8] F. F. Choobineh, E. Mohebbi and H. Khoo, A multiobjective tabu search for a single-machine scheduling problem with sequence- dependent setup times. European Journal of Operational Research, Vol. 175: 318–337, 2006. e-STA copyright 2011 by see Volume 8, N°1, pp 15-22 [9] F. Tangour, S. Hammadi, P. Borne et M. Benrejeb, Ordonnancement dynamique dans un atelier de production agroalimentaire. Séminaire d’Automatique- Industrie, SAI’06, Matmata, 2006. [10] Fuh-Der Chou, An experienced learning genetic algorithm to solve the single machine total weighted tardiness scheduling problem. Expert Systems with Applications, Vol. 36: 3857–3865, 2009. [11] M. Hassine, N. Liouane, K. Ben Othman, Elaboration d’une métaheuristique d’aide à l’ordonnancement. La cinquième Conférence Internationale d’Electrotechnique et d’Automatique, JTEA, 02-04 Mai 2008, Hammamet. [12] D. Anghinolfi, M. Paolucci, A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times. European Journal of Operational Research, Vol. 193: 73–85, 2009. [13] J.H. Holland, Adaptation in natural and artificial systems. Ann Arbor, MI: University of Michigan Press; 1975. [14] O. Etiler, B. Toklu, M. Atak, J. Wilson, A genetic algorithm for flow shop scheduling problems. Journal of the Operations Research Society Vol. 55:830–5, 2004. [15] J. F. Gonçalves, J. J. D. M. Mendes, M. G. C Resende, A hybrid genetic algorithm for the job shop scheduling problem. European Journal of Operational Research, Vol. 167: 77–95, 2005. [16] C. F. Liaw, A hybrid genetic algorithm for the open shop scheduling problem. European Journal of Operational Research, Vol.124:28–42, 2000. [17] P. C. Chang, S.S. Chen, C. Y. Fan, Mining gene structures to inject artificial chromosomes for genetic algorithm in single machine scheduling problems. Applied Soft Computing 8, 767–777, 2008. [18] F. D. Chou, An experienced learning genetic algorithm to solve the single machine total weighted tardiness scheduling problem. Expert Systems with Applications 36, 3857–3865, 2009. [19] E. Gargouri, S. Hammadi, P. Borne, A study of scheduling problem in agro-food manufacturing systems. Mathematics and Computers in Simulation, Vol. 60: 277–291, 2002. [20] A. Madureira, C. Ramos, S. D. C. Sliva, A GA based scheduling system for dynamic single machine problem. In Proceeding of the 4th IEEE international symbosium on assembly and task planning soft research park, pp. 28–129. Japan, 2001. [21] M. Koksalan, A. B. Keha, Using genetic algorithms for single machine bicriteria scheduling problems. European Journal of Operational Research 145, 543–556, 2003. [22] P. C. Chang, J.C. Hsieh, C.H. Liu, A case-injected genetic algorithm for single machine scheduling problems with release time. Int. J. Prod. Econ. 103 (2), 551–564, 2006. [23] D.E. Goldberg, Genetic algorithms in search, optimization, and machine learning, Advison-Wesley, 1989. [24] Pei-Chann Chang, Shih-Shin Chen, Chin-Yuan Fan, Mining gene structures to inject artificial chromosomes for genetic algorithm in single machine scheduling problems. Applied Soft Computing 8, 767–777, 2008. [25] I. Kacem, S. Hammadi and P. Borne, Flexible job-shop scheduling problems: formulation, lower-bounds, encodings, and controlled evolutionary approach. Computational Intelligence in Control, Idea Group Publishing, 2003. [26] K. Mesghouni, S. Hammadi and P. Borne, On modeling genetic algorithm for fexible job-shop scheduling problem. Studies in Informatics and Control Journal, Vol.7: 37-47, 1998. ANNEXE 1 : DONNEES RELATIVES AU BENCHMARK 1 1r j 1p j 1 1jν 1 2jν 1 3jν 1 1 revP j 1 2 revP j 1 3 revP j 1 livdP DvPi DrPi venPPi stkCPi 11 O 0 1 13 15 - 2 1 - 14 35 10 6 3 12 O 1 2 14 14 12 3 2 4 8 35 10 6 3 13 O 2 4 13 5 13 4 2 3 8 35 10 6 3 14 O 3 2 13 14 12 3 4 2 12 33 9 8 4 15 O 4 1 12 13 11 2 3 2 20 33 9 8 4 16 O 1 2 7 15 14 1 2 1 12 33 9 8 4 17 O 3 1 7 15 14 1 2 3 12 33 9 8 4 18 O 2 3 13 16 12 2 1 2 14 31 11 5 2 19 O 1 2 9 15 14 2 4 3 8 31 11 5 2 110 O 3 4 9 15 14 2 1 3 18 31 11 5 2 e-STA copyright 2011 by see Volume8, N°1, pp 15-22 ANNEXE 2 : DONNEES RELATIVES AU BENCHMARK 2 1r j 1p j 1 1jν 1 2jν 1 3jν 1 1 revP j 1 2 revP j 1 3 revP j 1 livdP DvPi DrPi venPPi stkCPi 11 O 0 1 13 15 - 2 1 - 24 65 40 6 3 12 O 1 2 14 14 12 3 2 4 18 65 40 6 3 13 O 2 4 13 5 13 4 2 3 18 65 40 6 3 14 O 3 2 13 14 12 3 4 2 22 63 39 8 4 15 O 4 1 12 13 11 2 3 2 30 63 39 8 4 16 O 1 2 7 15 14 1 2 1 22 63 39 8 4 17 O 3 1 7 15 14 1 2 3 22 63 39 8 4 18 O 2 3 13 16 12 2 1 2 24 61 41 5 2 19 O 1 2 9 15 14 2 4 3 18 61 41 5 2 110 O 3 4 9 15 14 2 1 3 28 61 41 5 2 111 O 0 1 13 15 - 2 1 - 24 65 40 6 3 112 O 1 2 14 14 12 3 2 4 18 65 40 6 3 113 O 2 4 13 5 13 4 2 3 18 65 40 6 3 114 O 3 2 13 14 12 3 4 2 22 63 39 8 4 115 O 4 1 12 13 11 2 3 2 30 63 39 8 4 116 O 1 2 7 15 14 1 2 1 22 63 39 8 4 117 O 3 1 7 15 14 1 2 3 22 63 39 8 4 118 O 2 3 13 16 12 2 1 2 24 61 41 5 2 119 O 1 2 9 15 14 2 4 3 18 61 41 5 2 120 O 3 4 9 15 14 2 1 3 28 61 41 5 2 121 O 0 1 13 15 - 2 1 - 24 65 40 6 3 122 O 1 2 14 14 12 3 2 4 18 65 40 6 3 123 O 2 4 13 5 13 4 2 3 18 65 40 6 3 124 O 3 2 13 14 12 3 4 2 22 63 39 8 4 125O 4 1 12 13 11 2 3 2 30 63 39 8 4 126 O 1 2 7 15 14 1 2 1 22 63 39 8 4 127 O 3 1 7 15 14 1 2 3 22 63 39 8 4 128 O 2 3 13 16 12 2 1 2 24 61 41 5 2 129 O 1 2 9 15 14 2 4 3 18 61 41 5 2 130 O 3 4 9 15 14 2 1 3 28 61 41 5 2 e-STA copyright 2011 by see Volume 8, N°1, pp 15-22