Download or read book Nouvelles m thodes pour les probl mes d ordonnancement cyclique written by Touria Chafqane Ben Rahhou and published by . This book was released on 2013 with total page pages. Available in PDF, EPUB and Kindle. Book excerpt: Les travaux de recherche concernant l'ordonnancement mobilisent un nombre important de chercheurs. Cette forte émulation est principalement due au large panorama des problématiques d'ordonnancement. Parmi elles, le problème d'atelier à cheminement multiple, communément appelé " Job-Shop ", tient une place particulièrement prépondérante tant ce problème est rencontré dans le milieu industriel. De nombreux sujets de recherche, en France et à l'étranger, sont issue de cette problématique. Les problèmes de Job-Shop peuvent souvent être simplifiés en les considérant comme des problèmes cycliques. L'ordonnancement des tâches devient ainsi cyclique et son objectif est d'organiser les activités de production en répétant un cycle de base que l'on a optimisé. De nombreux paramètres entrent en jeu dans l'optimisation du cycle de base tels que la période du cycle choisie, l'ordre des opérations élémentaires pour réaliser un travail, la durée de ces opérations, le nombre de produits à réaliser par cycle, etc. Plusieurs approches ont été utilisées pour résoudre ce problème. Parmi elles, nous pouvons citer l'approche par réseaux de Petri et plus particulièrement par graphes d'événements temporisés, l'approche par les graphes, l'approche par la programmation linéaire et l'approche par la théorie des tas. L'approche par les graphes permet une représentation graphique du problème sous forme d'un graphe où les noeuds représentent les différentes opérations et où les arcs illustrent les contraintes du problème d'ordonnancement cyclique, un tel problème admet une solution réalisable si, et seulement si, le graphe associé est consistant. Cette propriété de consistance d'un problème d'ordonnancement cyclique et de son graphe permet d'élaguer l'arbre de recherche de la procédure de séparation et d'évaluation proposée pour cette approche. Concernant l'approche par la théorie des tas, le sous-problème de l'évaluation d'une solution peut être résolu aisément avec l'aide de la théorie des tas. En effet, en traduisant le problème dans une structure mathématique adaptée, l'évaluation du taux de production du cycle revient au calcul d'une valeur propre d'un produit de matrices dans lequel chacune des matrices représente une opération élémentaire. Cette propriété s'avère particulièrement intéressante dans le cas de l'évaluation successive d'un grand nombre d'ordonnancement. En outre, la théorie des tas permet une représentation très intuitive d'un ordonnancement, puisque celui-ci s'illustre comme un empilement de plusieurs briques (en fait, un " tas " de briques) dont le contour supérieur correspond aux dates de fin des dernières opérations des machines.

Download or read book M thodes d optimisation robuste pour les probl mes d ordonnancement cyclique written by Idir Hamaz and published by . This book was released on 2018 with total page 135 pages. Available in PDF, EPUB and Kindle. Book excerpt: Plusieurs problèmes d'ordonnancement cyclique ont été étudiés dans la littérature. Cependant, la plupart de ces travaux considèrent que les paramètres sont connus avec certitude et ne prennent pas en compte les différents aléas qui peuvent survenir. Par ailleurs, un ordonnancement optimal pour un problème déterministe peut très vite devenir le pire ordonnancement en présence d'incertitude. Parmi les incertitudes que nous pouvons rencontrer dans les problèmes d'ordonnancement, la variation des durées des tâches par rapport au valeurs estimées, pannes des machines, incorporation de nouvelles tâches qui ne sont pas considérées au départ, etc. Dans cette thèse, nous étudions des problèmes d'ordonnancement cyclique où les durées des tâches sont affectées par des incertitudes. Ces dernières sont décrites par un ensemble d'incertitude où les durées des tâches sont supposées appartenir à des intervalles et le nombre de déviations par rapport aux valeurs nominales est contrôlé par un paramètre appelé budget d'incertitude. Nous étudions deux problèmes en particulier. Le premier est le problème d'ordonnancement cyclique de base (BCSP). Nous formulons celui-ci comme un problème d'optimisation robuste bi-niveau et, à partir des propriétés de cette formulation, nous proposons différents algorithmes pour le résoudre. Le deuxième problème considéré est le problème du jobshop cyclique. De manière similaire au BSCP, nous proposons une formulation en termes de problème d'optimisation bi-niveau et, en exploitant les algorithmes développés pour le problème d'ordonnancement cyclique de base, nous développons un algorithme de Branch-and-Bound pour le résoudre. Afin d'évaluer l'efficacité de notre méthode nous l'avons comparé à des méthodes de décomposition qui existent dans la littérature pour ce type de problèmes. Enfin, nous avons étudié une version du problème du jobshop cyclique où les durées des tâches prennent des valeurs dans des intervalles d'une manière uniforme et dont l'objectif est de minimiser la valeur moyenne du temps de cycle. Pour résoudre ce problème nous avons adopté un algorithme de Branch-and-Bound où chaque sous-problème de l'arbre de recherche consiste à calculer le volume d'un polytope. Enfin, pour montrer l'efficacité de chacune de ses méthodes, des résultats numériques sont présentés.

Download or read book Ordonnancement cyclique multi produits des lignes de traitement de surface written by Adnen El Amraoui and published by . This book was released on 2011 with total page 0 pages. Available in PDF, EPUB and Kindle. Book excerpt: Cette thèse s'intéresse au fonctionnement cyclique multi-produits des ateliers de traitement de surface, et au problème d'ordonnancement associé (HSP), caractérisé par des contraintes fortes et atypiques, dont certaines sont liées aux ressources de transport. Dans le cas de productions en grandes séries, une commande cyclique de ces systèmes est particulièrement adaptée, permettant notamment de réduire la combinatoire de résolution, et sous réserve que les ratios de produits soient connus à l'avance. Notre objectif est de trouver le meilleur ordonnancement des tâches de traitement et de transport en un temps raisonnable. Pour cela, nous proposons une première approche, basée sur un modèle linéaire et une méthode de résolution arborescente de type séparation et évaluation. Nous présentons des modélisations pour différentes extensions du problème dit de base et nous fournissons des exemples illustratifs et des résultats sur des benchmarks. Par la suite et compte tenu de l'analyse de la littérature relative aux ordonnancements cycliques mono-produit et multi-produits, nous proposons tout d'abord une heuristique dédiée au cas multi-produits étudié, et basée sur un algorithme de liste. Avec ce dernier, nous obtenons un ordonnancement cyclique dont le degré du cycle n'est pas fixé au préalable. Enfin, nous présentons une deuxième modélisation approchée sous la forme d'un algorithme génétique pour résoudre un HSP 2-cyclique. Ces différents modèles sont validés par des tests sur des benchmarks de la littérature pour lesquels nous avons obtenus des résultats prometteurs. Nous terminons par une analyse critique des avantages et inconvénients des modèles élaborés et par quelques propositions de perspectives pour ce travail.

Download or read book Programmation lin aire en nombres entiers pour l ordonnancement cyclique sous contraintes de ressources written by Maria Alejandra Ayala Perez and published by . This book was released on 2011 with total page 122 pages. Available in PDF, EPUB and Kindle. Book excerpt: Un problème d'ordonnancement cyclique consiste à ordonner dans le temps l'exécution répétitive d'un ensemble d'opérations liées par des contraintes de précédence, en utilisant un nombre limité de ressources. Ces problèmes ont des applications immédiates dans les systèmes de production ou en informatique parallèle. Particulièrement, ils permettent de modéliser l'ensemble des contraintes de précédence et de ressource à prendre en compte pour l'ordonnancement d'instructions dans les processeurs de type VLIW (Very Long Instruction Word). Dans ce cas, une opération représente une instance d'une instruction dans un programme. L'ordonnancement d'instructions de boucles internes est connu sous le nom de pipeline logiciel. Le pipeline logiciel désigne une méthode efficace pour l'optimisation de boucles qui permet la réalisation en parallèle des opérations des différentes itérations de la boucle. Dans cette thèse, nous nous intéressons principalement au problème d'ordonnancement périodique qui est un cas particulier de l'ordonnancement cyclique et qui est également la base du pipeline logiciel. Le terme ordonnancement modulo désigne un ordonnancement périodique tel que l'allocation de ressources pour une opération donnée n'est pas modifiée d'une itération sur l'autre. Pour résoudre le problème, nous nous intéressons aux formulations de programmation linéaire en nombres entiers, et notamment à la résolution du problème par des techniques de séparation, évaluation, génération de colonnes, relaxation lagrangienne et des méthodes hybrides. En particulier, nous proposons des nouvelles formulations basées sur des variables binaires représentant l'exécution d'ensembles d'instructions en parallèle. Enfin, les méthodes développées ont été validées sur des jeux d'instances industrielles pour des processeurs de type VLIW.

Download or read book Une m thode d analyse d ordonnancement des syst mes flexibles de production manufacturi re utilisant le d pliage des r seaux de P tri written by Jongkun Lee and published by . This book was released on 2002 with total page 162 pages. Available in PDF, EPUB and Kindle. Book excerpt: Dans ce travail, nous avons proposé deux algorithmes qui nous ont permis de régler complètement le problème de l'évaluation et de l'optimisation des performances. Pour cela nous avons fourni une méthode hiérarchique pour diminuer le temps d'analyse et obtenir les meilleures solutions. Nous avons découpé les sous-réseaux (ils s'appellent BUC) en utilisant la matrice d'incidence, fondée sur les ressources partagées des machines, et analysé BUC par le dépliage du réseau de Petri. Cette méthode d'analyse résout le problème de l'explosion combinatoire qui est apparu lors de l'analyse du réseau de Petri. Nous avons appliqué cette méthode à l'analyse de problème d'ordonnancement cyclique en SFPM. Finalement nous pouvons dire que cette approche est facile à comprendre, elle permet de calculer facilement les solutions.

Download or read book Une approche g n tique pour la r solution d ordonnancements cycliques written by Guillaume Cavory and published by . This book was released on 2000 with total page 138 pages. Available in PDF, EPUB and Kindle. Book excerpt: Les problèmes d'ordonnancement cyclique sont très présents dans le milieu industriel. Malheureusement, ces derniers sont souvent abandonnés ou laissés de côté par les industriels à cause de leur complexité. Cette thèse propose une approche génétique de résolution du problème du Job-Shop cyclique ainsi que d'une application industrielle. Pour cela, les caractéristiques d'un ordonnancement ainsi que la définition des éléments constituants sont présentés dans un premier temps. Les algorithmes génétiques ainsi que leur fonctionnement sont détaillés dans un second temps. Le troisième point de cette thèse se focalise sur les problèmes cycliques. C'est dans cette partie que l'approche génétique est présentée. Elle consiste à coupler un algorithme génétique avec un simulateur. Ce simulateur permet d'évaluer selon un critère un problème d'ordonnancement modélisé par un graphe de précédences à contraintes linéaires. Pour cela, le graphe de précédences à contraintes linéaires est transformé en réseau de Petri. C'est ce réseau de Petri couplé à un ensemble d'heuristiques de gestion de conflits de ressource qui permettent d'évaluer le problème. Une application est présentée dans un troisième temps. Pour cette application industrielle, deux simulateurs ont été employés. Le premier est basé sur les évènements discrets et le second utilise les graphes de précédences à contraintes linéaires. Le dernier point de cette thèse porte sur une plate-forme d'évaluation et d'amélioration de performance. Cette plate-forme a été développée dans le but de répondre à des problèmes industriels et académiques de type cyclique.

Download or read book Contribution l tude des ordonnancements cycliques written by Alix Munier and published by . This book was released on 1991 with total page pages. Available in PDF, EPUB and Kindle. Book excerpt: Un problème d'ordonnancement cyclique est caractérisé par un nombre fini de taches génériques de durées fixées qui doivent être exécutées une infinie de fois. Ces taches non reéntrantes sont soumises à des contraintes de précédence et de ressource qui doivent être vérifiées par toutes leurs exécutions. le critère d'optimisation généralement utilisé est la maximisation du débit. Malgré d'importantes applications industrielles ou informatiques, ce type de problème a été jusqu'ici peu abordé en tant que problème d'optimisation combinatoire. Seule la version sans contraintes de ressource de ce problème, appelée problème central répétitif a été résolue. dans cette thèse, nous étudions deux problèmes d'ordonnancement cycliques fondamentaux. Le premier consiste en un ensemble de tâches génériques qui sont exécutées sur des processeurs différenciés et qui sont soumises aux contraintes de précédence d'un problème central répétitif. Nous montrons que le problème général est NP-difficile et nous étudions la complexité de plusieurs sous-problèmes importants. De plus, nous étudions la dominance de structures périodiques simple d'ordonnancements. Le second consiste en un ensemble de tâches soumises a des contraintes de précédence linéaires. Nous montrons que l'ordonnancement au plus tôt est optimal et K-périodique. Nous donnons un algorithme pour calculer le débit optimal des tâches. Cet algorithme est basé d'une part sur une décomposition particulière du graphe des précédences et d'autre part sur l'expansion de ces composantes. Ces deux outils permettent de se ramener à l'étude d'un problème central répétitif.

Download or read book CONTRIBUTION A L ETUDE DES PROBLEMES D ORDONNANCEMENT CYCLIQUE MULTIDIMENSIONNELS written by PATRICK.. LE GOUESLIER D'ARGENCE and published by . This book was released on 1995 with total page 159 pages. Available in PDF, EPUB and Kindle. Book excerpt: LORS DE LA COMPILATION DE PROGRAMMES SEQUENTIELS SUR MACHINE PARALLELE, IL EST IMPORTANT DE DEGAGER LE MAXIMUM DE PARALLELISME. CECI PEUT ETRE FAIT EN ORDONNANCANT LES CALCULS DE FACON A OBTENIR UN ORDONNANCEMENT A LA FOIS RAPIDE ET RESPECTANT LES CONTRAINTES DE PRECEDENCE. DANS CETTE THESE, NOUS NOUS INTERESSONS AU CAS OU LE DOMAINE DE CALCUL EST UN POLYEDRE CONVEXE SEMI-INFINI OU BORNE, LORSQUE LES DEPENDANCES SONT UNIFORMES. NOUS ETUDIONS LA COMPLEXITE DE DETERMINATION DE L'ORDONNANCEMENT OPTIMAL, ET NOUS MONTRONS QUE LE PROBLEME EST NP-DIFFICILE, ET CE MEME DANS DES CAS TRES SIMPLES. PUIS NOUS ETUDIONS LES PERFORMANCES D'ORDONNANCEMENTS AFFINES ET NOUS MONTRONS QU'ILS SONT ASYMPTOTIQUEMENT OPTIMAUX. NOUS REGARDONS ENFIN DES CAS OU LE NOMBRE DE PROCESSEURS EST LIMITE. NOUS ETUDIONS LE CAS DES PROCESSEURS DIFFERENCIES, ET NOUS MONTRONS QU'IL EST POSSIBLE D'OBTENIR UN ORDONNANCEMENT DE DEBIT OPTIMAL LORSQUE LE PARALLELISME DES CALCULS N'EST PAS BORNE

Download or read book Probl mes d ordonnancement avec minimisation des encours written by Chérif Sadfi and published by . This book was released on 2002 with total page 160 pages. Available in PDF, EPUB and Kindle. Book excerpt: Dans ce travail de thèse, nous nous sommes intéressés aux problèmes d'ordonnancement avec minimisation des encours. Cet objectif se traduit par la minimisation du flot moyen (temps de séjour moyen des produits dans l'atelier). Le critère de minimisation du flot est une mesure de performance souvent rencontrée en pratique. La minimisation des encours permet de raccourcir le temps de cycle du produit et ainsi maîtriser sa date de sortie de l'atelier. Nous nous sommes intéressés particulièrement à trois types de problèmes : le problème du flow shop, le problème sur une machine avec contrainte d'indisponibilité de la machine et le problème sur une machine avec dates d'arrivées des travaux. Nous commençons notre étude par une présentation générale des problèmes d'ordonnancement, de leur complexité et un état de l'art des problèmes d'ordonnancement avec minimisation des encours. Pour le problème du flow shop, pour mieux comprendre l'influence des temps opératoires sur le résultat des méthodes de résolution, ous présentons une étude théorique du comportement de la fonction objectif et du résultat de l'ordonnancement suite à une variation des temps opératoires des travaux. Enfin, pour résoudre chacun des problèmes considérés, nous proposons différentes méthodes approximatives et exactes. Une analyse théorique et expérimentale est présentée pour chacune des méthodes proposées afin de juger sa performance.

Download or read book Contribution a l etude des problemes d ordonnancement cyclique multidimensionnels written by Patrick Le Goueslier D'argence and published by . This book was released on 1995 with total page 0 pages. Available in PDF, EPUB and Kindle. Book excerpt:

Download or read book Les probl mes d ordonnancement written by Bernard Roy and published by . This book was released on 1964 with total page 174 pages. Available in PDF, EPUB and Kindle. Book excerpt:

Download or read book Des priorit s fixes aux priorit s dynamiques en ordonnancement temps r el written by Bernard Chauvière and published by . This book was released on 2007 with total page 190 pages. Available in PDF, EPUB and Kindle. Book excerpt: Nos recherches portent sur l’étude des systèmes temps-réel composés de tâches périodiques et ordonnancés en environnement multiprocesseur. Nos travaux s’organisent autour de deux thèmes de recherche~: la production de solutions d’ordonnancement et l’analyse quantitative de l’ordonnançabilité. Pour mener à bien ces recherches, nous avons été amenés à étudier certaines propriétés théoriques comme la cyclicité des séquences d’exécution. Sous certaines hypothèses, englobant par exemple RM, DM et EDF, nous montrons que les séquences d’exécution multiprocesseur sont cycliques, et nous proposons un intervalle de faisabilité. Nous apportons deux contributions au problème de l’ordonnancement. D’une part, nous proposons une méthode pour déterminer toutes les configurations de priorités fixes permettant d’ordonnancer un système de tâches. Nous étendons cette approche aux configurations de priorités fixes par instance et proposons l’étude d’une nouvelle classe de politiques d’ordonnancement. D’autre part, nous appliquons les méthodes d'approximation (méthode taboue, algorithmes génétiques, etc) au problème de l'ordonnancement des systèmes de tâches liées par des contraintes de précédence, afin d'obtenir des séquences d'exécution optimisant certains critères comme la durée totale d'exécution par exemple. Lorsque aucune politique connue n’est utilisable, le concepteur est généralement amené à modifier la conception du système. Peu de travaux permettent de le guider. Nous proposons une méthode basée sur les chaînes de Markov qui renseigne sur le comportement d’un système de tâches en fonction du support matériel utilisé. Les informations apportées permettent de comprendre les problèmes qui sont à la source des difficultés et donc d’aider à modifier la conception. Elles renseignent aussi sur la qualité de service offerte par le système.

Download or read book Minimisation des perturbations et parall lisation pour la planification et l ordonnancement written by Thierry Moisan and published by . This book was released on 2016 with total page 157 pages. Available in PDF, EPUB and Kindle. Book excerpt: Nous étudions dans cette thèse deux approches réduisant le temps de traitement nécessaire pour résoudre des problèmes de planification et d'ordonnancement dans un contexte de programmation par contraintes. Nous avons expérimenté avec plusieurs milliers de processeurs afin de résoudre le problème de planification et d'ordonnancement des opérations de rabotage du bois d'oeuvre. Ces problèmes sont d'une grande importance pour les entreprises, car ils permettent de mieux gérer leur production et d'économiser des coûts reliés à leurs opérations. La première approche consiste à effectuer une parallélisation de l'algorithme de résolution du problème. Nous proposons une nouvelle technique de parallélisation (nommée PDS) des stratégies de recherche atteignant quatre buts : le respect de l'ordre de visite des noeuds de l'arbre de recherche tel que défini par l'algorithme séquentiel, l'équilibre de la charge de travail entre les processeurs, la robustesse aux défaillances matérielles et l'absence de communications entre les processeurs durant le traitement. Nous appliquons cette technique pour paralléliser la stratégie de recherche Limited Discrepancy-based Search (LDS) pour ainsi obtenir Parallel Limited Discrepancy-Based Search (PLDS). Par la suite, nous démontrons qu'il est possible de généraliser cette technique en l'appliquant à deux autres stratégies de recherche : Depth-Bounded discrepancy Search (DDS) et Depth-First Search (DFS). Nous obtenons, respectivement, les stratégies Parallel Discrepancy-based Search (PDDS) et Parallel Depth-First Search (PDFS). Les algorithmes parallèles ainsi obtenus créent un partage intrinsèque de la charge de travail : la différence de charge de travail entre les processeurs est bornée lorsqu'une branche de l'arbre de recherche est coupée. En utilisant des jeux de données de partenaires industriels, nous avons pu améliorer les meilleures solutions connues. Avec la deuxième approche, nous avons élaboré une méthode pour minimiser les changements effectués à un plan de production existant lorsque de nouvelles informations, telles que des commandes additionnelles, sont prises en compte. Replanifier entièrement les activités de production peut mener à l'obtention d'un plan de production très différent qui mène à des coûts additionnels et des pertes de temps pour les entreprises. Nous étudions les perturbations causéees par la replanification à l'aide de trois métriques de distances entre deux plans de production : la distance de Hamming, la distance d'édition et la distance de Damerau-Levenshtein. Nous proposons trois modèles mathématiques permettant de minimiser ces perturbations en incluant chacune de ces métriques comme fonction objectif au moment de la replanification. Nous appliquons cette approche au problème de planification et ordonnancement des opérations de finition du bois d'oeuvre et nous démontrons que cette approche est plus rapide qu'une replanification à l'aide du modèle d'origine.

Download or read book Techniques d ordonnancement d atelier et de fourn es bas es sur la programmation par contraintes written by Arnaud Malapert and published by . This book was released on 2011 with total page 350 pages. Available in PDF, EPUB and Kindle. Book excerpt: Résoudre un problème d’ordonnancement consiste à organiser un ensemble de tâches, c’est-à-dire déterminer leurs dates de début et de fin et leur attribuer des ressources en respectant certaines contraintes. Dans cette thèse, nous proposons de nouvelles approches exactes basées sur la programmation par contraintes pour deux classes de problèmes d’ordonnancement P-difficiles validées expérimentalement par l’implémentation d’un ensemble de nouvelles fonctionnalités dans le solveur de contraintes choco. Dans un problème d’atelier, n lots sont constitués chacun de m tâches à exécuter sur m machines distinctes. Chaque machine ne peut exécuter qu’une tâche à la fois. La nature des contraintes liant les tâches d’un même lot peut varier (séquencement global ou par lot, pas de séquencement). Le critère d’optimalité étudié est la minimisation du délai total. Nous proposons d’abord une étude et une classification des différents modèles et algorithmes de résolution. Ensuite, nous introduisons une nouvelle approche flexible pour ces problèmes classiques. Une machine à traitement par fournées peut traiter plusieurs tâches en une seule opération, une fournée. Les dates de début et de fin des tâches d’une même fournée sont identiques. Le problème étudié consiste à minimiser le retard algébrique maximal de n tâches de différentes tailles sur une machine de capacité b. Conjointement, la somme des tailles des tâches d’une fournée ne doit pas excéder la capacité b. Nous proposons, dans ce contexte, un modèle basé sur une décomposition du problème. Nous définissons ensuite une nouvelle contrainte pour l’optimisation basée sur une relaxation du problème qui améliore sa résolution.

Download or read book Commande cyclique des syst mes flexibles de production manufacturi re l aide des r seaux de p tri written by Ouajdi Korbaa and published by . This book was released on 2013 with total page 0 pages. Available in PDF, EPUB and Kindle. Book excerpt: Nous nous interessons, dans ce memoire, au probleme de commande des s.f.p.m. La complexite de ce probleme est en general trop importante pour envisager la recherche de la meilleure solution avec la prise en compte de tous les criteres (min. Temps total de production, min. En-cours). La commande cyclique se presente comme une solution interessante qui permet de reduire considerablement la complexite. Les travaux de ohl 95a et cam 97 ont permet la mise en place d'une approche structuree, utilisant les reseaux de petri comme outil de modelisation et d'analyse de performances, prenant en compte progressivement les differents indeterminismes du systeme de production afin de conserver le plus longtemps l'optimalite de la recherche. L'utilisation d'heuristiques, pour finir la resolution, est imposee par le caractere np-difficile du probleme d'ordonnancement cyclique. Nous proposons ici une etude approfondie et une extension de cette methode a plusieurs niveaux. Nous etudions tout d'abord la combinatoire des differentes phases precedant l'ordonnancement. Cette etude est indispensable dans l'optique d'une informatisation de l'approche. Dans le second chapitre, nous presentons un algorithme d'ordonnancement cyclique ainsi que une extension a la prise en compte des operations de transfert. Afin de determiner une commande entiere du systeme, nous etudions les regimes transitoires, de lancement et d'arret de la production, sous differents aspects (bornes, durees optimales, continuite des fonctions, existence d'un regime permanent). Le resultat final est une commande previsionnelle entiere du systeme depuis le lancement de la production jusqu'a son arret.

Download or read book M thodes heuristiques pour un probl me d ordonnancement avec contraintes sur les ressources written by Véronique Bouffard and published by . This book was released on 2003 with total page 156 pages. Available in PDF, EPUB and Kindle. Book excerpt:

Download or read book Application des algorithmes volutionnistes dans les probl mes d optimisation en ordonnancement de la production written by Khaled Mesghouni and published by . This book was released on 1999 with total page 125 pages. Available in PDF, EPUB and Kindle. Book excerpt: Le problème d'ordonnancement des ateliers constitue sûrement pour les entreprises une des difficultés importantes de leur système de gestion et de conduite. En effet, c'est à ce niveau que doivent être prises en compte les caractéristiques réelles multiples et complexes des ateliers. Nous nous intéresserons dans ce travail aux problèmes d'ordonnancement de type job-shop flexible, ce sont des problèmes extrêmement difficiles à résoudre, ils appartiennent à la classe dite NP difficile, ils demandent un espace de recherche combinatoire et un traitement particulièrement complexe. Les méthodes exactes demandent un temps d'exécution considérable et/ou des formulations mathématiques complexes, particulièrement quand la taille du problème est importante. Toutefois, il existe des méthodes dites stochastiques telles que les algorithmes évolutionnistes qui donnent des résultats très proches de l'optimum. Nous proposons deux approches évolutionnistes originales pour résoudre les problèmes du type job-shop flexible. Ces derniers sont sujets à des contraintes diverses qu'il faut absolument respecter pour aboutir à une solution réalisable. La première approche est basée sur le premier codage dit codage parallèle des machines, le chromosome ainsi représente donne une information visible de la charge des machines et de la répartition des opérations sur ces dernières ce qui permet une utilisation efficace du parc de machines. L'utilisation des algorithmes à stratégie d'évolution passe par la mise au point d'une population de démarrage dite population initiale. Vu que cette population conditionne la convergence de notre algorithme, nous avons utilisé un processus hybride utilisant les différentes méthodes classiques pour générer une bonne première population. Dans la deuxième approche, nous proposons un deuxième codage qui intègre la majorité des contraintes du problème d'ordonnancement dans la conception même du chromosome, ceci nous permet de construire des opérateurs de croisement et du mutation sans avoir à intégrer des processus de corrections qui alourdiraient le temps de calcul. Les résultats des simulations que nous avons effectuées montrent bien la validité de nos approches, ainsi que leurs capacités à donner un ensemble de solutions réalisables et proches de l'optimum en un temps très court.