Solution Methods for Service Network Design with Resource Management Consideration

La gestion des ressources, équipements, équipes de travail, et autres, devrait être prise en compte lors de la conception de tout plan réalisable pour le problème de conception de réseaux de services. Cependant, les travaux de recherche portant sur la gestion des ressources et la conception de réseaux de services restent limités. La présente thèse a pour objectif de combler cette lacune en faisant l’examen de problèmes de conception de réseaux de services prenant en compte la gestion des ressources. Pour ce faire, cette thèse se décline en trois études portant sur la conception de réseaux. La première étude considère le problème de capacitated multi-commodity fixed cost network design with design-balance constraints(DBCMND). La structure multi-produits avec capacité sur les arcs du DBCMND, de même que ses contraintes design-balance, font qu’il apparaît comme sous-problème dans de nombreux problèmes reliés à la conception de réseaux de services, d’où l’intérêt d’étudier le DBCMND dans le contexte de cette thèse. Nous proposons une nouvelle approche pour résoudre ce problème combinant la recherche tabou, la recomposition de chemin, et une procédure d’intensification de la recherche dans une région particulière de l’espace de solutions. Dans un premier temps la recherche tabou identifie de bonnes solutions réalisables. Ensuite la recomposition de chemin est utilisée pour augmenter le nombre de solutions réalisables. Les solutions trouvées par ces deux méta-heuristiques permettent d’identifier un sous-ensemble d’arcs qui ont de bonnes chances d’avoir un statut ouvert ou fermé dans une solution optimale. Le statut de ces arcs est alors fixé selon la valeur qui prédomine dans les solutions trouvées préalablement. Enfin, nous utilisons la puissance d’un solveur de programmation mixte en nombres entiers pour intensifier la recherche sur le problème restreint par le statut fixé ouvert/fermé de certains arcs. Les tests montrent que cette approche est capable de trouver de bonnes solutions aux problèmes de grandes tailles dans des temps raisonnables. Cette recherche est publiée dans la revue scientifique Journal of heuristics. La deuxième étude introduit la gestion des ressources au niveau de la conception de réseaux de services en prenant en compte explicitement le nombre fini de véhicules utilisés à chaque terminal pour le transport de produits. Une approche de solution faisant appel au slope-scaling, la génération de colonnes et des heuristiques basées sur une formulation en cycles est ainsi proposée. La génération de colonnes résout une relaxation linéaire du problème de conception de réseaux, générant des colonnes qui sont ensuite utilisées par le slope-scaling. Le slope-scaling résout une approximation linéaire du problème de conception de réseaux, d’où l’utilisation d’une heuristique pour convertir les solutions obtenues par le slope-scaling en solutions réalisables pour le problème original. L’algorithme se termine avec une procédure de perturbation qui améliore les solutions réalisables. Les tests montrent que l’algorithme proposé est capable de trouver de bonnes solutions au problème de conception de réseaux de services avec un nombre fixe des ressources à chaque terminal. Les résultats de cette recherche seront publiés dans la revue scientifique Transportation Science. La troisième étude élargie nos considérations sur la gestion des ressources en prenant en compte l’achat ou la location de nouvelles ressources de même que le repositionnement de ressources existantes. Nous faisons les hypothèses suivantes: une unité de ressource est nécessaire pour faire fonctionner un service, chaque ressource doit retourner à son terminal d’origine, il existe un nombre fixe de ressources à chaque terminal, et la longueur du circuit des ressources est limitée. Nous considérons les alternatives suivantes dans la gestion des ressources: 1) repositionnement de ressources entre les terminaux pour tenir compte des changements de la demande, 2) achat et/ou location de nouvelles ressources et leur distribution à différents terminaux, 3) externalisation de certains services. Nous présentons une formulation intégrée combinant les décisions reliées à la gestion des ressources avec les décisions reliées à la conception des réseaux de services. Nous présentons également une méthode de résolution matheuristique combinant le slope-scaling et la génération de colonnes. Nous discutons des performances de cette méthode de résolution, et nous faisons une analyse de l’impact de différentes décisions de gestion des ressources dans le contexte de la conception de réseaux de services. Cette étude sera présentée au XII International Symposium On Locational Decision, en conjonction avec XXI Meeting of EURO Working Group on Locational Analysis, Naples/Capri (Italy), 2014. En résumé, trois études différentes sont considérées dans la présente thèse. La première porte sur une nouvelle méthode de solution pour le "capacitated multi-commodity fixed cost network design with design-balance constraints". Nous y proposons une matheuristique comprenant la recherche tabou, la recomposition de chemin, et l’optimisation exacte. Dans la deuxième étude, nous présentons un nouveau modèle de conception de réseaux de services prenant en compte un nombre fini de ressources à chaque terminal. Nous y proposons une matheuristique avancée basée sur la formulation en cycles comprenant le slope-scaling, la génération de colonnes, des heuristiques et l’optimisation exacte. Enfin, nous étudions l’allocation des ressources dans la conception de réseaux de services en introduisant des formulations qui modèlent le repositionnement, l’acquisition et la location de ressources, et l’externalisation de certains services. À cet égard, un cadre de solution slope-scaling développé à partir d’une formulation en cycles est proposé. Ce dernier comporte la génération de colonnes et une heuristique. Les méthodes proposées dans ces trois études ont montré leur capacité à trouver de bonnes solutions.

Domain/Multi-Domain Protection and Provisioning in Optical Networks

L’évolution récente des commutateurs de sélection de longueurs d’onde (WSS -Wavelength Selective Switch) favorise le développement du multiplexeur optique d’insertionextraction reconfigurable (ROADM - Reconfigurable Optical Add/Drop Multiplexers) à plusieurs degrés sans orientation ni coloration, considéré comme un équipement fort prometteur pour les réseaux maillés du futur relativement au multiplexage en longueur d’onde (WDM -Wavelength Division Multiplexing ). Cependant, leur propriété de commutation asymétrique complique la question de l’acheminement et de l’attribution des longueur d’ondes (RWA - Routing andWavelength Assignment). Or la plupart des algorithmes de RWA existants ne tiennent pas compte de cette propriété d’asymétrie. L’interruption des services causée par des défauts d’équipements sur les chemins optiques (résultat provenant de la résolution du problème RWA) a pour conséquence la perte d’une grande quantité de données. Les recherches deviennent ainsi incontournables afin d’assurer la survie fonctionnelle des réseaux optiques, à savoir, le maintien des services, en particulier en cas de pannes d’équipement. La plupart des publications antérieures portaient particulièrement sur l’utilisation d’un système de protection permettant de garantir le reroutage du trafic en cas d’un défaut d’un lien. Cependant, la conception de la protection contre le défaut d’un lien ne s’avère pas toujours suffisante en termes de survie des réseaux WDM à partir de nombreux cas des autres types de pannes devenant courant de nos jours, tels que les bris d’équipements, les pannes de deux ou trois liens, etc. En outre, il y a des défis considérables pour protéger les grands réseaux optiques multidomaines composés de réseaux associés à un domaine simple, interconnectés par des liens interdomaines, où les détails topologiques internes d’un domaine ne sont généralement pas partagés à l’extérieur. La présente thèse a pour objectif de proposer des modèles d’optimisation de grande taille et des solutions aux problèmes mentionnés ci-dessus. Ces modèles-ci permettent de générer des solutions optimales ou quasi-optimales avec des écarts d’optimalité mathématiquement prouvée. Pour ce faire, nous avons recours à la technique de génération de colonnes afin de résoudre les problèmes inhérents à la programmation linéaire de grande envergure. Concernant la question de l’approvisionnement dans les réseaux optiques, nous proposons un nouveau modèle de programmation linéaire en nombres entiers (ILP - Integer Linear Programming) au problème RWA afin de maximiser le nombre de requêtes acceptées (GoS - Grade of Service). Le modèle résultant constitue celui de l’optimisation d’un ILP de grande taille, ce qui permet d’obtenir la solution exacte des instances RWA assez grandes, en supposant que tous les noeuds soient asymétriques et accompagnés d’une matrice de connectivité de commutation donnée. Ensuite, nous modifions le modèle et proposons une solution au problème RWA afin de trouver la meilleure matrice de commutation pour un nombre donné de ports et de connexions de commutation, tout en satisfaisant/maximisant la qualité d’écoulement du trafic GoS. Relativement à la protection des réseaux d’un domaine simple, nous proposons des solutions favorisant la protection contre les pannes multiples. En effet, nous développons la protection d’un réseau d’un domaine simple contre des pannes multiples, en utilisant les p-cycles de protection avec un chemin indépendant des pannes (FIPP - Failure Independent Path Protecting) et de la protection avec un chemin dépendant des pannes (FDPP - Failure Dependent Path-Protecting). Nous proposons ensuite une nouvelle formulation en termes de modèles de flots pour les p-cycles FDPP soumis à des pannes multiples. Le nouveau modèle soulève un problème de taille, qui a un nombre exponentiel de contraintes en raison de certaines contraintes d’élimination de sous-tour. Par conséquent, afin de résoudre efficacement ce problème, on examine : (i) une décomposition hiérarchique du problème auxiliaire dans le modèle de décomposition, (ii) des heuristiques pour gérer efficacement le grand nombre de contraintes. À propos de la protection dans les réseaux multidomaines, nous proposons des systèmes de protection contre les pannes d’un lien. Tout d’abord, un modèle d’optimisation est proposé pour un système de protection centralisée, en supposant que la gestion du réseau soit au courant de tous les détails des topologies physiques des domaines. Nous proposons ensuite un modèle distribué de l’optimisation de la protection dans les réseaux optiques multidomaines, une formulation beaucoup plus réaliste car elle est basée sur l’hypothèse d’une gestion de réseau distribué. Ensuite, nous ajoutons une bande pasiv sante partagée afin de réduire le coût de la protection. Plus précisément, la bande passante de chaque lien intra-domaine est partagée entre les p-cycles FIPP et les p-cycles dans une première étude, puis entre les chemins pour lien/chemin de protection dans une deuxième étude. Enfin, nous recommandons des stratégies parallèles aux solutions de grands réseaux optiques multidomaines. Les résultats de l’étude permettent d’élaborer une conception efficace d’un système de protection pour un très large réseau multidomaine (45 domaines), le plus large examiné dans la littérature, avec un système à la fois centralisé et distribué.

Dynamic Facility Location with Modular Capacities : Models, Algorithms and Applications in Forestry

Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable.

Catholicisme et postmodernité : analyses philosophiques à partir de débats publics québécois

Avec la sécularisation, la laïcité et la diversité croissantes de la société québécoise, la place de la religion en général et du catholicisme en particulier se sont vues remises en question. Cette situation a d’ailleurs mené à la mise en place de deux commissions : l’une sur la place de la religion à l’école (1999) et l’autre sur les pratiques d’accommodements reliées aux différences culturelles (2008). Ces deux commissions auront fourni énormément d’informations sur les rapports qu’entretiennent encore les Québécois avec le catholicisme. Cette recherche a donc pour but de faire le point sur certains aspects du catholicisme au Québec à partir d’une perspective reposant principalement sur des instruments heuristiques issus des écrits signés « Jacques Derrida ». Pour ce faire, nous nous appuierons sur les travaux du Groupe de travail sur la religion à l’école, de la consultation générale sur la place de la religion à l’école et de la commission de consultation sur les pratiques d’accommodement reliées aux différences culturelles. Nous posons comme hypothèse que de manière générale, les Québécois entretiennent avec le catholicisme, des rapports « archivaux », c’est-à-dire conditionnés par des perceptions de ce dernier informées par son passé, plutôt que par son présent. De plus, ces perceptions du catholicisme, probablement développées dans le sillage de la Révolution tranquille et peut-être même un peu avant, nourriraient l’existence de « spectres » qui viendraient hanter les rapports des Québécois à tout ce qui touche le religieux et la diversité culturelle. En ce sens, il s’agit d’une dimension essentielle de ce que nous appellerions la « postmodernité » religieuse québécoise. Pour illustrer ce propos, nous mènerons une analyse de contenu documentaire. Premièrement, nous procéderons à l’analyse thématique de centaines de documents (rapports de recherche, rapports officiels, mémoires) déposés lors de ces débats. Le logiciel QDA Miner permettra d’effectuer une analyse documentaire en identifiant les passages thématiques reliés à la recherche. Nous procéderons ensuite à une analyse plus fine de ces extraits sélectionnés à partir de perspectives philosophiques provenant principalement du philosophe Jacques Derrida.

Quand _Refus global_ devient "Refus global" : l'histoire d'une réception partielle

Refus global, le recueil, n’est pas « Refus global », le texte rédigé par Paul-Émile Borduas et cosigné par 15 membres du groupe automatiste. Partant de cette distinction entre le recueil automatiste et son texte éponyme et du constat selon lequel la partie éclipse le tout dans le discours critique, cette thèse a pour objectif d’expliquer l’occultation du recueil dans l’histoire sociale et artistique québécoise. À partir de l’étude de la réception de 1948 à 2008, j’interroge la constitution du récit commun entourant l’œuvre, duquel le recueil est exclu. Il s’agit donc de mettre au jour les obstacles qui se sont présentés dans le parcours de réception du recueil, nuisant à la formation d’un discours unifié et cohérent à son sujet et l’empêchant de s’inscrire dans l’histoire. Dégagés de l’étude du corpus composé de 639 objets sémiotiques secondaires (OSS, selon le concept proposé par Brigitte Louichon), les obstacles à la réception du recueil relèvent à la fois de facteurs pragmatiques, telles la composition hétérogène de l’œuvre ou sa disponibilité; de facteurs institutionnels ou historiographiques, comme la disciplinarisation du champ culturel ou l’impact du récit de la Révolution tranquille sur l’histoire littéraire; et de facteurs humains, reposant sur le rôle des auteurs et de certains critiques dans l’accueil réservé à l’œuvre. Les différentes étapes de la réception sont ainsi considérées : de l’horizon d’attente (Jauss) à la réception productive (Link), en passant par la publication, les premières critiques, les rééditions, les lectures savantes, l’historicisation et l’entrée de l’œuvre dans la mémoire à titre de symbole ou d’hypotexte. Or, plutôt qu’à ce parcours de réception exemplaire, c’est son envers qui est interrogé ici, c’est-à-dire les difficultés et les déviations de la réception du recueil Refus global. Cette thèse est divisée en trois parties. La première, théorique et méthodologique, situe mon propos dans les domaines de l’histoire culturelle et des études de réception, et présente diverses considérations concernant la constitution du corpus et le traitement des données. La deuxième aborde l’horizon d’attente et la première réception, moment crucial pour la survie de l’œuvre, comme l’ont montré Hans Robert Jauss et Daniel Chartier. On y observe notamment l’effet de verrou (Cambron) qu’a le renvoi de Borduas sur la constitution du récit de réception, de même que les critères éthiques et esthétiques en fonction desquels s’est opérée la hiérarchisation des composantes du recueil. La troisième partie couvre la réception subséquente (1950-2008). À l’étude des obstacles empêchant l’intégration du recueil dans l’histoire s’ajoute alors l’étude des réceptions parallèles, parcellaires et autonomes dont a bénéficié Refus global pour survivre – ponctuellement et partiellement – en dehors du récit commun formé autour de « Refus global ». Avec les différentes catégories d’OSS (directs, indirects, hypertextuels, métacritiques et parcellaires), ces trois types de réception font partie des outils heuristiques développés dans le but d’expliquer la réception partielle dont a fait l’objet le recueil. Selon l’approche quantitative et environnementaliste de l’histoire culturelle, Refus global est envisagé comme un microcosme de la culture, dans lequel certaines œuvres sont retenues et d’autres négligées. L’analyse d’un corpus critique large et varié permet ainsi de saisir non seulement les phénomènes conduisant à la consécration du texte éponyme ou à l’oubli relatif du recueil, mais aussi les tendances critiques, les parutions marginales, les critiques isolées, etc. qui, enfouies dans les angles morts de la réception, offrent au recueil et à ses composantes des voies de contournement du discours dominant. En somme, l’étude de la réception du recueil Refus global a permis à la fois de déplacer la focalisation critique depuis « Refus global » vers Refus global, de développer des outils pour envisager la réception d’œuvres marginalisées et de mettre en évidence des critères privilégiés dans la constitution de l’histoire et de la mémoire culturelles québécoises depuis 1948.

Quand la politique et la génétique se rencontrent : comment le public interprète-t-il la recherche?

L’objectif général de cette thèse de doctorat est de mieux comprendre comment le public interprète les nouvelles scientifiques portant sur la génétique humaine, plus précisément les nouvelles portant sur la génétique des comportements et celles portant sur la génétique des groupes raciaux. L’ouvrage prend la forme d’une thèse par article. Le Chapitre 1 introduit le lecteur aux buts et aux pratiques de la vulgarisation scientifique, présente un sommaire de la recherche sur les effets des médias, résume les principaux travaux produits par le champ de la génopolitique, et définit la structure des croyances du public à l’égard de l’influence de la génétique sur les traits humains. Le Chapitre 2 présente les fondements de la méthode expérimentale, il en explique les atouts et il offre des exemples de différents types de devis expérimentaux utilisés en science politique. Toutes les recherches produites dans cette thèse reposent au moins en partie sur cette méthode. Le Chapitre 3 présente les résultats d’une expérience de sondage qui vise à mesurer l’effet de la lecture d’une nouvelle à propos de la recherche en génétique des comportements sur des participants. L’étude démontre que le public interprète la nouvelle avec maladresse et tend à généraliser l’influence de la génétique à d’autres traits humains qui n’y sont pas mentionnés. J’avance l’hypothèse qu’un raccourci psychologique amplement documenté puisse expliquer cette réaction : l’heuristique de l’ancrage et de l’ajustement. Le Chapitre 4 présente lui aussi les résultats d’une expérience de sondage. L’étude consiste à manipuler certaines informations du contenu d’une nouvelle sur la génopolitique de manière à vérifier si certains éléments sont particulièrement susceptibles de mener à la généralisation hâtive mise en évidence dans le Chapitre 3. Les analyses suggèrent que cette généralisation est amplifiée lorsque la nouvelle présente de hauts niveaux d’héritabilité tirés d’études de jumeaux, ainsi que lorsqu’elle présente des travaux de génétique des populations visant à étudier l’origine des différences géographiques. Ce chapitre présente des recommandations à l’égard des journalistes scientifiques. Le Chapitre 5 s’intéresse à un aspect différent de la génétique humaine : celui de la génétique des races. L’objectif de cette recherche est de comprendre comment le public réagit aux travaux qui invalident l’idée selon laquelle les humains sont divisés en différentes races génétiquement distinctes. Les analyses de données transversales ainsi que les résultats d’une expérience de sondage convergent et indiquent que les conservateurs et les libéraux réagissent de manière diamétralement opposée à cette information. D’un côté, les libéraux acceptent le constat scientifique et réduisent leur impression que la génétique explique en partie les inégalités sociales; de l’autre, les conservateurs rejettent l’argument avec une intensité si forte que le rôle qu’ils attribuent aux différences génétiques s’en voit bonifié. Ces résultats sont interprétés à partir de la théorie du raisonnement motivé. Enfin, le Chapitre 6 résume les principaux constats, met en évidence les contributions que ma thèse apporte à la science politique et à la communication scientifique, et présente quelques pistes pour la recherche future.

Étude de la médiane de permutations sous la distance de Kendall-Tau

La distance de Kendall-τ compte le nombre de paires en désaccord entre deux permuta- tions. La distance d’une permutation à un ensemble est simplement la somme des dis- tances entre cette permutation et les permutations de l’ensemble. À partir d’un ensemble donné de permutations, notre but est de trouver la permutation, appelée médiane, qui minimise cette distance à l’ensemble. Le problème de la médiane de permutations sous la distance de Kendall-τ, trouve son application en bio-informatique, en science politique, en télécommunication et en optimisation. Ce problème d’apparence simple est prouvé difficile à résoudre. Dans ce mémoire, nous présentons plusieurs approches pour résoudre le problème, pour trouver une bonne solution approximative, pour le séparer en classes caractéristiques, pour mieux com- prendre sa compléxité, pour réduire l’espace de recheche et pour accélérer les calculs. Nous présentons aussi, vers la fin du mémoire, une généralisation de ce problème et nous l’étudions avec ces mêmes approches. La majorité du travail de ce mémoire se situe dans les trois articles qui le composent et est complémenté par deux chapitres servant à les lier.

Étude de la médiane de permutations sous la distance de Kendall-Tau

La distance de Kendall-τ compte le nombre de paires en désaccord entre deux permuta- tions. La distance d’une permutation à un ensemble est simplement la somme des dis- tances entre cette permutation et les permutations de l’ensemble. À partir d’un ensemble donné de permutations, notre but est de trouver la permutation, appelée médiane, qui minimise cette distance à l’ensemble. Le problème de la médiane de permutations sous la distance de Kendall-τ, trouve son application en bio-informatique, en science politique, en télécommunication et en optimisation. Ce problème d’apparence simple est prouvé difficile à résoudre. Dans ce mémoire, nous présentons plusieurs approches pour résoudre le problème, pour trouver une bonne solution approximative, pour le séparer en classes caractéristiques, pour mieux com- prendre sa compléxité, pour réduire l’espace de recheche et pour accélérer les calculs. Nous présentons aussi, vers la fin du mémoire, une généralisation de ce problème et nous l’étudions avec ces mêmes approches. La majorité du travail de ce mémoire se situe dans les trois articles qui le composent et est complémenté par deux chapitres servant à les lier.

Ordonnancement des opérations dans une unité d’extrusion

Les travaux de ce mémoire traitent du problème d’ordonnancement et d’optimisation de la production dans un environnement de plusieurs machines en présence de contraintes sur les ressources matérielles dans une usine d’extrusion plastique. La minimisation de la somme pondérée des retards est le critère économique autour duquel s’articule cette étude car il représente un critère très important pour le respect des délais. Dans ce mémoire, nous proposons une approche exacte via une formulation mathématique capable des donner des solutions optimales et une approche heuristique qui repose sur deux méthodes de construction de solution sérielle et parallèle et un ensemble de méthodes de recherche dans le voisinage (recuit-simulé, recherche avec tabous, GRASP et algorithme génétique) avec cinq variantes de voisinages. Pour être en totale conformité avec la réalité de l’industrie du plastique, nous avons pris en considération certaines caractéristiques très fréquentes telles que les temps de changement d’outils sur les machines lorsqu’un ordre de fabrication succède à un autre sur une machine donnée. La disponibilité des extrudeuses et des matrices d’extrusion représente le goulot d’étranglement dans ce problème d’ordonnancement. Des séries d’expérimentations basées sur des problèmes tests ont été effectuées pour évaluer la qualité de la solution obtenue avec les différents algorithmes proposés. L’analyse des résultats a démontré que les méthodes de construction de solution ne sont pas suffisantes pour assurer de bons résultats et que les méthodes de recherche dans le voisinage donnent des solutions de très bonne qualité. Le choix du voisinage est important pour raffiner la qualité de la solution obtenue. Mots-clés : ordonnancement, optimisation, extrusion, formulation mathématique, heuristique, recuit-simulé, recherche avec tabous, GRASP, algorithme génétique