Le Design computationnel de protéines, en anglais « Computational Protein Design » (CPD), est un champ derecherche récent qui vise à fournir des outils de prédiction pour compléter l'ingénierie des protéines. En effet,outre la compréhension théorique des propriétés physico-chimiques fondamentales et fonctionnelles desprotéines, l’ingénierie des protéines a d’importantes applications dans un large éventail de domaines, y comprisdans la biomédecine, la biotechnologie, la nanobiotechnologie et la conception de composés respectueux del’environnement. Le CPD cherche ainsi à accélérer le design de protéines dotées des propriétés désirées enpermettant le traitement d’espaces de séquences de large taille tout en limitant les coûts financier et humain auniveau expérimental.Pour atteindre cet objectif, le CPD requière trois ingrédients conçus de manière appropriée: 1) une modélisationréaliste du système à remodeler; 2) une définition précise des fonctions objectives permettant de caractériser lafonction biochimique ou la propriété physico-chimique cible; 3) et enfin des méthodes d'optimisation efficacespour gérer de grandes tailles de combinatoire.Dans cette thèse, nous avons abordé le CPD avec une attention particulière portée sur l’optimisationcombinatoire. Dans une première série d'études, nous avons appliqué pour la première fois les méthodesd'optimisation de réseaux de fonctions de coût à la résolution de problèmes de CPD. Nous avons constaté qu’encomparaison des autres méthodes existantes, nos approches apportent une accélération du temps de calcul parplusieurs ordres de grandeur sur un large éventail de cas réels de CPD comprenant le design de la stabilité deprotéines ainsi que de complexes protéine-protéine et protéine-ligand. Un critère pour définir l'espace demutations des résidus a également été introduit afin de biaiser les séquences vers celles attendues par uneévolution naturelle en prenant en compte des propriétés structurales des acides aminés. Les méthodesdéveloppées ont été intégrées dans un logiciel dédié au CPD afin de les rendre plus facilement accessibles à lacommunauté scientifique. / Computational Protein Design (CPD) is a very young research field which aims at providing predictive tools to complementprotein engineering. Indeed, in addition to the theoretical understanding of fundamental properties and function of proteins,protein engineering has important applications in a broad range of fields, including biomedical applications, biotechnology,nanobiotechnology and the design of green reagents. CPD seeks at accelerating the design of proteins with wanted propertiesby enabling the exploration of larger sequence space while limiting the financial and human costs at experimental level.To succeed this endeavor, CPD requires three ingredients to be appropriately conceived: 1) a realistic modeling of the designsystem; 2) an accurate definition of objective functions for the target biochemical function or physico-chemical property; 3)and finally an efficient optimization framework to handle large combinatorial sizes.In this thesis, we addressed CPD problems with a special focus on combinatorial optimization. In a first series of studies, weapplied for the first time the Cost Function Network optimization framework to solve CPD problems and found that incomparison to other existing methods, it brings several orders of magnitude speedup on a wide range of real CPD instancesthat include the stability design of proteins, protein-protein and protein-ligand complexes. A tailored criterion to define themutation space of residues was also introduced in order to constrain output sequences to those expected by natural evolutionthrough the integration of some structural properties of amino acids in the protein environment. The developed methods werefinally integrated into a CPD-dedicated software in order to facilitate its accessibility to the scientific community.

Deux problèmes robustes d'optimisation NP-difficiles sont étudiés dans cette thèse: le problème min-max regret de couverture pondérée (min-max regret WSCP) et le problème min-max regret de couverture et localisation maximale (min-max regret MCLP). Les données incertaines dans ces problèmes sont modélisées par des intervalles et seules les valeurs minimales et maximales pour chaque intervalle sont connues. Le min-max regret WSCP a été investigué notamment dans le cadre théorique, alors que le min-max regret MCLP a des applications en logistique des catastrophes étudiées dans cette thèse. Deux autres critères d'optimisation robuste ont été dérivés pour le MCLP: le max-max MCLP et le min-max MCLP. En matière de méthodes, formulations mathématiques, algorithmes exacts et heuristiques ont été développés et appliqués aux deux problèmes. Des expérimentations computationnelles ont montré que les algorithmes exacts ont permis de résoudre efficacement 14 des 75 instances générées par le min-max regret WSCP et toutes les instances réalistes pour le min-max regret MCLP. Pour les cas simulés qui n'ont pas été résolus de manière optimale dans les deux problèmes, les heuristiques développées dans cette thèse ont trouvé des solutions aussi bien ou mieux que le meilleur algorithme exact dans presque tous les cas. En ce qui concerne l'application en logistique des catastrophes, les modèles robustes ont trouvé des solutions similaires pour les scénarios réalistes des tremblements de terre qui a eu lieu à Katmandu au Népal en 2015. Cela indique que nous avons une solution robuste / Two robust optimization NP-Hard problems are studied in this thesis: the min-max regret Weighted Set Covering Problem (min-max regret WSCP) and the min-max regret Maximal Coverage Location Problem (min-max regret MCLP). The min-max regret WSCP and min-max regret MCLP are, respectively, the robust optimization counterparts of the Set Covering Problem and of the Maximal Coverage Location Problem. The uncertain data in these problems is modeled by intervals and only the minimum and maximum values for each interval are known. However, while the min-max regret WSCP is mainly studied theoretically, the min-max regret MCLP has an application in disaster logistics which is also investigated in this thesis. Two other robust optimization criteria were derived for the MCLP: the max-max MCLP and the min-max MCLP. In terms of methods, mathematical formulations, exact algorithms and heuristics were developed and applied to both problems. Computational experiments showed that the exact algorithms efficiently solved 14 out of 75 instances generated to the min-max regret WSCP and all realistic instances created to the min-max regret MCLP. For the simulated instances that was not solved to optimally in both problems, the heuristics developed in this thesis found solutions, as good as, or better than the exact algorithms in almost all instances. Concerning the application in disaster logistics, the robust models found similar solutions for realistic scenarios of the earthquakes that hit Kathmandu, Nepal in 2015. This indicates that we have got a robust solution, according to all optimization models

Cloud-Radio Access Network (C-RAN) est une architecture prometteuse pour faire face à l’augmentation exponentielle des demandes de trafic de données et surmonter les défis des réseaux de prochaine génération (5G). Le principe de base de CRAN consiste à diviser la station de base traditionnelle en deux entités : les unités de bande de base (BaseBand Unit, BBU) et les têtes radio distantes (Remote Radio Head, RRH) et à mettre en commun les BBUs de plusieurs stations dans des centres de données centralisés (pools de BBU). Ceci permet la réduction des coûts d’exploitation, l’amélioration de la capacité du réseau ainsi que des gains en termes d’utilisation des ressources. Pour atteindre ces objectifs, les opérateurs réseaux ont besoin d’investiguer de nouveaux algorithmes pour les problèmes d’allocation de ressources permettant ainsi de faciliter le déploiement de l’architecture C-RAN. La plupart de ces problèmes sont très complexes et donc très difficiles à résoudre. Par conséquent, nous utilisons l’optimisation combinatoire qui propose des outils puissants pour adresser ce type des problèmes.Un des principaux enjeux pour permettre le déploiement du C-RAN est de déterminer une affectation optimale des RRHs (antennes) aux centres de données centralisés (BBUs) en optimisant conjointement la latence sur le réseau de transmission fronthaul et la consommation des ressources. Nous modélisons ce problème à l’aide d’une formulation mathématique basée sur une approche de programmation linéaire en nombres entiers permettant de déterminer les stratégies optimales pour le problème d’affectation des ressources entre RRH-BBU et nous proposons également des heuristiques afin de pallier la difficulté au sens de la complexité algorithmique quand des instances larges du problème sont traitées, permettant ainsi le passage à l’échelle. Une affectation optimale des antennes aux BBUs réduit la latence de communication attendue et offre des gains en termes d’utilisation des ressources. Néanmoins, ces gains dépendent fortement de l’augmentation des niveaux d’interférence inter-cellulaire causés par la densité élevée des antennes déployées dans les réseaux C-RANs. Ainsi, nous proposons une formulation mathématique exacte basée sur les méthodes Branch-and-Cut qui consiste à consolider et ré-optimiser les rayons de couverture des antennes afin de minimiser les interférences inter-cellulaires et de garantir une couverture maximale du réseau conjointement. En plus de l’augmentation des niveaux d’interférence, la densité élevée des cellules dans le réseau CRAN augmente le nombre des fonctions BBUs ainsi que le trafic de données entre les antennes et les centres de données centralisés avec de fortes exigences en termes de latence sur le réseau fronthaul. Par conséquent, nous discutons dans la troisième partie de cette thèse comment placer d’une manière optimale les fonctions BBUs en considérant la solution split du 3GPP afin de trouver le meilleur compromis entre les avantages de la centralisation dans C-RAN et les forts besoins en latence et bande passante sur le réseau fronthaul. Nous proposons des algorithmes (exacts et heuristiques) issus de l’optimisation combinatoire afin de trouver rapidement des solutions optimales ou proches de l’optimum, même pour des instances larges du problèmes. / Cloud Radio Access Network (C-RAN) has been proposed as a promising architecture to meet the exponential growth in data traffic demands and to overcome the challenges of next generation mobile networks (5G). The main concept of C-RAN is to decouple the BaseBand Units (BBU) and the Remote Radio Heads (RRH), and place the BBUs in common edge data centers (BBU pools) for centralized processing. This gives a number of benefits in terms of cost savings, network capacity improvement and resource utilization gains. However, network operators need to investigate scalable and cost-efficient algorithms for resource allocation problems to enable and facilitate the deployment of C-RAN architecture. Most of these problems are very complex and thus very hard to solve. Hence, we use combinatorial optimization which provides powerful tools to efficiently address these problems.One of the key issues in the deployment of C-RAN is finding the optimal assignment of RRHs (or antennas) to edge data centers (BBUs) when jointly optimizing the fronthaul latency and resource consumption. We model this problem by a mathematical formulation based on an Integer Linear Programming (ILP) approach to provide the optimal strategies for the RRH-BBU assignment problem and we propose also low-complexity heuristic algorithms to rapidly reach good solutions for large problem instances. The optimal RRH-BBU assignment reduces the expected latency and offers resource utilization gains. Such gains can only be achieved when reducing the inter-cell interference caused by the dense deployment of cell sites. We propose an exact mathematical formulation based on Branch-and-Cut methods that enables to consolidate and re-optimize the antennas radii in order to jointly minimize inter-cell interference and guarantee a full network coverage in C-RAN. In addition to the increase of inter-cell interference, the high density of cells in C-RAN increases the amount of baseband processing as well as the amount of data traffic demands between antennas and centralized data centers when strong latency requirements on fronthaul network should be met. Therefore, we discuss in the third part of this thesis how to determine the optimal placement of BBU functions when considering 3GPP split option to find optimal tradeoffs between benefits of centralization in C-RAN and transport requirements. We propose exact and heuristic algorithms based on combinatorial optimization techniques to rapidly provide optimal or near-optimal solutions even for large network sizes.

Cette thèse traite de la détection et de la ré-identification de personnes dans un environnement instrumenté par un réseau de caméras à champ disjoint. Elle est à la confluence des communautés Recherche Opérationnelle et Vision car elle s'appuie sur des techniques d'optimisation combinatoire pour formaliser de nouvelles modalités de vision par ordinateur. Dans ce contexte, un détecteur visuel de personnes, basé sur la programmation linéaire en nombres entiers, est tout d'abord proposé. Son originalité est de prendre en compte le coût de traitement et non uniquement les performances de détection. Ce détecteur est évalué et comparé aux détecteurs de la littérature les plus performants. Ces expérimentations menées sur deux bases de données publiques mettent clairement en évidence l'intérêt de notre détecteur en terme de coût de traitement avec garantie de performance de détection. La seconde partie de la thèse porte sur la modalité de ré-identification de personnes. L'originalité de notre approche, dénommée D-NCR (pour Directed Network Consistent Re-identification), est de prendre explicitement en compte les temps minimum de transit des personnes dans le réseau de caméras et sa topologie pour améliorer la performance de la ré-identification. On montre que ce problème s'apparente à une recherche de chemins disjoints particuliers à profit maximum dans un graphe orienté. Un programme linéaire en nombres entiers est proposé pour sa modélisation et résolution. Les évaluations réalisées sur une base publique d'images sont prometteuses et montrent le potentiel de cette approche. / This thesis deals with people detection and re-identification in an environment instrumented by a network of disjoint-field cameras. It stands at the confluence of the Operational Research and Computer Vision communities as combinatorial optimization techniques are used to formalize new computer vision methods. In this context, a people visual detector, based on mixed-integer programming, is first propose that simultaneously take computation time and detection performances into account. This detector is evaluated and compared to the best detectors of the literature. These experiments, conducted on two public databases, clearly demonstrate the interest of our detector in terms of processing time with detection performance guarantee. The second part of the thesis deals with people re-identification. Our novel approach, called D-NCR (Directed Network Consistent Re-identification), explicitly takes minimum transit times in the camera network into account, as well as the network topology, in order to improve the re-identification performance. This problem is similar to the determination of particular maximum-profitable independent paths in an oriented graph. A mixed-integer program is proposed to model and solve this problem. The experiments made on a public dataset sound promising and tend to prove the potential of the approach.

Cette thèse s'inscrit dans le domaine de l'optimisation combinatoire. Elle utilise l'approche polyèdrale pour résoudre des problèmes combinatoires qui se posent dans le contexte des réseaux de télécommunications. Nous introduisons et étudions le problème de synthèse de réseaux à composantes connexes unicycliques. Après avoir rappelé que le problème est facile à résoudre en absence d'autres contraintes, nous étudions de nouvelles variantes en intégrant de nouvelles contraintes techniques. Nous commençons par une contrainte portant sur la taille des cycles. Nous souhaitons interdire tous les cycles contenant au plus $p$ sommets. Le problème est alors NP-Difficile. Des inégalités valides sont alors proposées pour ce problème. On montre sous des conditions bien précises que ces inégalités peuvent être des facettes. Plusieurs algorithmes polynomiaux ont été proposés pour la séparation des inégalités valides. Ces algorithme sont mis en oeuvre et des résultats numériques sont donnés. Nous nous focalisons par la suite sur un nouveau problème dit de Steiner consistant à partitionner un réseau en composantes unicycliques tout en imposant que certains sommets soient sur les cycles. On montre alors que ce problème est facile au sens de la complexité algorithmique en proposant un algorithme polynomial et une formulation étendue du problème. On présente également une description partielle de l'enveloppe convexe des vecteurs d'incidence de ces réseaux. La séparation des inégalités est également étudiée. Nous proposons notamment une généralisation de l'algorithme de Padberg-Rao pour séparer les inégalités Blossom. D'autres contraintes techniques sont prises en compte : contraintes de degrés, contrainte sur le nombre de composantes connexes, appartenance de certains sommets à une même composante connexe et enfin la séparation de certains sommets qui doivent être sur des composantes différentes. Enfin, nous faisons une étude spectrale de deux classes spécifiques de graphes unicycliques. / In this thesis, we use the polyhedral approach to solve combinatorial problems in telecommunications context. First, we introduce the problem of network design with unicyclic connected components. We recall that without other constraints, our problem is easy to solve, and we propose a study with new technical constraints. We start our study by adding constraints on the size of cycles. We aim to obtain unicyclic components such that the size of each cycle is not lower than a certain p. This problem is NP-Hard. We describe some valid inequalities for the design of unicyclic graphs with girth constraints. The faces induced by these valid inequalities are also studied. Some of them can be separated in polynomial time. A cutting plane algorithm based on these inequalities is implemented to solve the problem. Furthermore, we focus on a Steiner type problem, which consists in partitioning the graph to unicyclic components, such that some given vertices belong to a cycle. We prove then that our problem is easy to solve, and we propose an exact extended formulation and a partial description of the convex hull of the incidence vectors of our Steiner network problem. Polynomial time separation algorithms are described. One of them is a generalization of the Padberg&Rao algorithm to separate blossom inequalities. Other technical constraints are proposed such as degree constraints, a bound of the number of unicyclic components, constraints related to whether some given pairs of vertices belong to the same component or to different components. Finally, we study the spectra of two specified classes of unicyclic graphs.

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. / Several studies on cyclic scheduling problems have been presented in the literature. However, most of them consider that the problem parameters are deterministic and do not consider possible uncertainties on these parameters. However, the best solution for a deterministic problem can quickly become the worst one in the presence of uncertainties, involving bad schedules or infeasibilities. Many sources of uncertainty can be encountered in scheduling problems, for example, activity durations can decrease or increase, machines can break down, new activities can be incorporated, etc. In this PhD thesis, we focus on scheduling problems that are cyclic and where activity durations are affected by uncertainties. More precisely, we consider an uncertainty set where each task duration belongs to an interval, and the number of parameters that can deviate from their nominal values is bounded by a parameter called budget of uncertainty. This parameter allows us to control the degree of conservatism of the resulting schedule. In particular, we study two cyclic scheduling problems. The first one is the basic cyclic scheduling problem (BCSP). We formulate the problem as a two-stage robust optimization problem and, using the properties of this formulation, we propose three algorithms to solve it. The second considered problem is the cyclic jobshop problem (CJSP). As for the BCSP, we formulate the problem as two-stage robust optimization problem and by exploiting the algorithms proposed for the robust BCSP we propose a Branch-and-Bound algorithm to solve it. In order to evaluate the efficiency of our method, we compared it with classical decomposition methods for two-stage robust optimization problems that exist in the literature. We also studied a version of the CJSP where each task duration takes uniformly values within an interval and where the objective is to minimize the mean value of the cycle time. In order to solve the problem, we adapted the Branch-and-Bound algorithm where in each node of the search tree, the problem to be solved is the computation of a volume of a polytope. Numerical experiments assess the efficiency of the proposed methods.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

L’optimisation combinatoire concerne la résolution de problèmes pour lesquels les variables prennent des valeurs discrètes et sur lesquelles s’appliquent des contraintes. L’ensemble des variables et des contraintes définissent un modèle représentant le problème. Un très grand nombre de problèmes industriels peuvent être représentés sous cette forme. Un logiciel qui prend un modèle en entrée et produit une solution est appelé solveur. La programmation par contraintes (PPC) est l’une des techniques algorithmiques pouvant être utilisée par ces solveurs. Dans ce mémoire, nous développons un nouveau solveur. L’objectif premier est de compter sur un solveur facilement modifiable dans le but d’y ajouter de nouvelles approches de résolution développées par les chercheurs. De plus, dans le but de démontrer l’utilité du solveur, nous développons une approche exploitant ce solveur dans le but de générer des patrons de chargement alternatifs pour un séchoir à bois utilisé par l’industrie des produits forestiers. Finalement, nous présentons dans ce mémoire une nouvelle technique pour résoudre avec plus d’efficience certains problèmes de PPC. Les algorithmes de filtrage associés aux contraintes sont typiquement déclenchés en fonction d’événements qui se produisent lors de la résolution du problème. Nous proposons un nouvel événement qui permet d’effectuer du filtrage tardif des variables. Nous montrons que, pour un problème classique d’optimisation combinatoire (Balanced Incomplete Block Design), il donne une meilleure performance tout en maintenant le même niveau de filtrage par rapport à l’utilisation des événements classiques. / Combinatorial optimization concerns the solving of problems for which the variables take discrete values and on which constraints apply. The set of variables and constraints form the model of the problem. A lot of industrial problems can be represented in this form. A solver is a software that takes as input a model and produces a solution. Constraint programming (CP) is one of the algorithmic techniques that can be used within a solver. In this master’s thesis, we develop a new solver. The primary objective is to rely on an easily modifiable solver in order to add new resolution approaches developed by researchers. Moreover, in order to demonstrate the utility of the solver, we develop an approach using that solver in order to generate alternative loading patterns for a kiln in the forest industry. Finally, in this master’s thesis, we present a new technique for solving some CP problems. The filtering algorithms are triggered according to events that occur when solving the problem. We propose a new event that allows to perform a lazy filtering of the variables. We demonstrate, on a classical combinatorial optimization problem (Balanced Incomplete Block Design), that it gives a better performance while maintaining the same level of filtering when compared with classical events.

La programmation par contraintes est une technique accélérant la recherche de solutions pour des problèmes d’optimisation combinatoire. Ce mémoire porte sur l’application de cette technique en ordonnancement. Le but est d’intégrer une fonction de coût convexe à la contrainte Disjunctive qui régit l’ordre d’exécution d’un ensemble de tâches ne pouvant pas se chevaucher dans le temps. Dans ce contexte, le coût est perçu comme un retard déterminé par une échéance préférable indiquée pour chaque tâche. La contribution se traduit en l’introduction de la contrainte DisjunctiveTardiness qui tisse de nouveaux liens entre l’ordre d’exécution des tâches et la somme des retards engendrés. La cohérence de la contrainte est assurée par un algorithme de filtrage. L’algorithme raisonne à partir de la construction d’un réseau de flot pondéré basé sur la fenêtre d’exécution des tâches et leur échéance préférable. Il est implémenté dans un solveur et comparé à une alternative compétitive. Tel qu’observé, le nouvel algorithme amène un filtrage tangible, mais sa complexité trop élevée empêche d’aboutir à un nouvel état de l’art en pratique. En revanche, plusieurs pistes de solution pour réduire le temps d’exécution sont proposées. / Constraint programming is a technology originating from artificial intelligence that explores a search space to solve combinatorial problems. It uses filtering algorithms to filter the search space and speedup the search of a solution. This master thesis covers an application of this method in scheduling. The goal is to integrate a convex cost function to the Disjunctive constraint that governs the execution order of tasks unable to overlap each other on a time line. In this context, the cost is treated as a delay (tardiness) computed from a due date specified for each task. The contribution translates in a new constraint named DisjunctiveTardiness that brings a stronger relation between the order in a schedule and the sum of tardinesses. Consistency of the constraint is achieved by a filtering algorithm. The algorithm builds a weighted network flow from the allowed time window of the tasks and their due date. The solution is implemented in a solver. The experimental results show that the new algorithm applies stronger filtering, but its time complexity is too high to recommend it in practice. To conclude, several potential upgrades are proposed to reduce the execution time.

Dans ce travail, nous considérons un système multi-états série-parallèle dont les composantes sont sujettes à des réparations minimales et à des actions de maintenance préventive imparfaite. Le système peut avoir différents niveaux de performance, allant d'un fonctionnement parfait à une défaillance complète. Les composantes peuvent être en opération ou hors d'usage. La fiabilité d'un système multi-états est définie par sa probabilité de satisfaction d'une demande donnée. La fiabilité de chaque composante est caractérisée par sa fonction de hasard. Chaque action de maintenance préventive conduit à une réduction de l'âge effectif de l'équipement. Elle est caractérisée par son coefficient de réduction d'âge et par son coût. L'objectif consiste à planifier des actions de maintenance préventive pendant la durée de vie du système multi- états, de façon à minimiser le coût total moyen de maintenance, sous une contrainte de fiabilité. Il s'agit d'un problème d'optimisation combinatoire qui a été auparavant formulé et résolu par les algorithmes génétiques dans [47]. Dans ce travail, ce problème est résolu en utilisant une méthode heuristique basée sur le méta-heuristique des colonies de fourmis. Inspirée par les études sur le comportement des fournis réelles, cette méthode possède plusieurs caractéristiques intéressantes et constitue une approche intéressante pour résoudre les problèmes d'optimisation de la fiabilité. Une technique à base de la fonction de génération universelle est implémentée pour évaluer la fiabilité du système multi-états. En combinant la technique de la fonction de génération universelle et l'optimisation par colonies de fourmis, l'algorithme proposé permet d'obtenir efficacement une séquence quasi-optimale des actions de maintenance. L'approche développée et testée dans ce travail constitue une alternative intéressante pour la résolution du problème d'optimisation de la maintenance préventive imparfaite pour les systèmes multi-états. Des exemples numériques de la détermination de plans quasi-optimaux de maintenance préventive sont également présentés. / In this work, we consider a series-parallel multi-state System composed of elements subjected to minimal repair and imperfect preventive maintenance actions. The System has a range of performance levels from perfect functioning to complete failure. Components may experience two possible states: good and failed. Multi-state System reliability is defined as the System ability to satisfy given demand. The reliability of each element is characterized by its hazard function. Each preventive maintenance action may affect the effective age of equipment, and is characterized by its age reduction coefficient and cost. The objective is to determine a minimal average cost plan of preventive maintenance actions during multi-state System lifetime, under the constraint of providing a required level of System reliability. This is a combinatorial optimization problem which has been previously formulated and solved by genetic algorithms in [47]. In this work, this problem is solved by using a heuristic based on ant colony meta-heuristic. Inspired by studies on the behaviour of real ants, this method has many interesting characteristics and approaches for solving reliability optimization problems. A universal generating function technique is implemented to evaluate System reliability. By combining the use of the universal generating function technique and ant colony optimization, the proposed algorithm obtains efficiently quasi-optimal sequence of maintenance actions. The approach developed and tested in this work constitutes an interesting alternative approach to solve the imperfect preventive maintenance problem for multi-state Systems. Numerical examples of the determination of quasi-optimal preventive maintenance plans are also presented.