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.

De nos jours, l'évolution du commerce électronique ainsi que des niveaux de la consommation requièrent des acteurs de la chaine logistique et en particulier les transporteurs de gérer efficacement leurs opérations. Afin de rester concurrentiels et maximiser leurs profits, ils doivent optimiser leurs opérations de transport. Dans cette thèse de doctorat, nous nous focalisons sur les enchères combinatoires en tant que mécanisme de négociation pour les marchés d'approvisionnement des services de transport routier par camions permettant à un expéditeur d'externaliser ses opérations de transport et aux transporteurs d'acquérir des contrats de transport. Les mises combinatoires permettent à un transporteur participant à l'enchère d'exprimer ses intérêts pour une combinaison de contrats mis à l'enchère dans une même mise. Si la mise gagne, tous les contrats qui la forment seront alloués au transporteur au tarif exigé. Les défis majeurs pour le transporteur sont de déterminer les contrats de transport sur lesquels miser, les regrouper dans plusieurs mises combinatoires, s'il y a lieu, et décider des prix à soumettre pour chaque mise générée. Ces défis décisionnels définissent le problème de construction de mises combinatoires (BCP pour Bid Construction Problem). Chaque transporteur doit résoudre le BCP tout en respectant ses engagements préexistants et ses capacités de transport et en tenant compte des offres des compétiteurs, ce qui rend le problème difficile à résoudre. Dans la pratique, la majorité des transporteurs se basent sur leur connaissance du marché et leur historique pour fixer leurs prix des mises. Dans la littérature, la majorité des travaux sur le BCP considèrent des modèles déterministes où les paramètres sont connus et se limitent à un contexte de flotte homogène. En plus, nous notons qu'un seul travail à considérer une variante stochastique du BCP. Dans cette thèse de doctorat, nous visons à faire avancer les connaissances dans ce domaine en introduisant de nouvelles formulations et méthodes de résolution pour le BCP Le premier chapitre de cette thèse introduit une nouvelle variante du BCP avec une flotte hétérogène. En partant d'une comparaison des similitudes et des différences entre le BCP et les problèmes classiques de de tournées de véhicules, nous proposons une nouvelle formulation basée sur les arcs avec de nouvelles contraintes de bris de symétrie pour accélérer la résolution. Ensuite, nous proposons une approche heuristique et une autre exacte pour résoudre ce problème. L'heuristique développée est une recherche adaptative à grands voisinages (ALNS pour Adaptive Large Neighborhood Search) et se base sur le principe de destruction puis réparation de la solution à l'aide d'opérateurs conçus spécifiquement pour le BCP traité. La méthode exacte utilise la meilleure solution heuristique pour résoudre notre modèle mathématique avec le solveur CPLEX. Les résultats obtenus montrent la pertinence de nos méthodes en termes de qualités des solutions et des temps de calculs et ce pour des instances de grande taille. Dans le deuxième chapitre, nous nous attaquons à un cas particulier du BCP où le transporteur n'a pas d'engagements existants et vise à déterminer un ensemble de contrats mis à l'enchère profitables à miser dessus. Cette problématique correspond à un problème de tournées de véhicules avec profits (TOP pour Team Orienteering Problem). Nous proposons pour le TOP une heuristique ALNS hybride avec de nouveaux opérateurs ainsi que de nouvelles fonctionnalités tenant compte de la nature du problème. Ensuite, nous comparons les performances de notre méthode avec toutes les méthodes déjà publiées dans la littérature traitant du TOP. Les résultats montrent que notre méthode surpasse généralement toutes les approches existantes en termes de qualité des solutions et/ou temps de calculs quand elle est testée sur toutes les instances de la littérature. Notre méthode améliore la solution d'une instance de grande taille, ce qui surligne sa performance. Dans le troisième chapitre, nous nous focalisons sur l'incertitude associée aux prix de cessions des contrats mis à l'enchère et sur les offres des transporteurs concurrents. Il n'existe qu'un seul article qui traite de l'incertitude dans le BCP cependant il ne permet pas de générer des mises multiples. Ainsi, nous proposons une nouvelle formulation pour le BCP avec des prix stochastiques permettant de générer des mises combinatoires et disjointes. Nous présentons deux méthodes pour résoudre ce problème. La première méthode est hybride et à deux étapes. Dans un premier temps, elle résout un problème de sélection pour déterminer un ensemble de contrats profitables. Dans un second temps, elle résout simultanément un problème de sélection de contrats et de détermination de prix des mises (CSPP pour Contracts Selection and Pricing Problem) en ne considérant que les contrats sélectionnés dans la première étape. Notre méthode exacte résout, avec l'algorithme de branch-and-cut, le CSPP sans présélectionner des contrats. Les résultats expérimentaux et de simulations que nous rapportons soulignent la performance de nos deux méthodes et évaluent l'impact de certains paramètres sur le profit réel du transporteur. Dans le quatrième chapitre, nous nous focalisons sur l'incertitude liée au succès des mises et à la non-matérialisation des contrats. Généralement, le transporteur souhaite avoir la garantie que si certaines des mises ne sont pas gagnées ou un contrat ne se matérialise pas, il n'encourra pas de perte en servant le sous-ensemble de contrats gagnés. Dans cette recherche, nous adressons le BCP avec prix stochastiques et développons une méthode exacte qui garantit un profit non négatif pour le transporteur peu importe le résultat des enchères. Nos simulations des solutions optimales démontrent, qu'en moyenne, notre approche permet au transporteur d'augmenter son profit en plus de garantir qu'il reste non-négatif peu importe les mises gagnées ou la matérialisation des contrats suivant l'enchère. / Nowadays, the evolution of e-commerce and consumption levels require supply chain actors, in particular carriers, to efficiently manage their operations. In order to remain competitive and to maximize their profits, they must optimize their transport operations. In this doctoral thesis, we focus on Combinatorial Auctions (CA) as a negotiation mechanism for truckload (TL) transportation services procurement allowing a shipper to outsource its transportation operations and for a carrier to serve new transportation contracts. Combinatorial bids offer a carrier the possibility to express his valuation for a combination of contracts simultaneously. If the bid is successful, all the contracts forming it will be allocated to the carrier at the submitted price. The major challenges for a carrier are to select the transportation contracts to bid on, formulate combinatorial bids and associated prices. These decision-making challenges define the Bid Construction Problem (BCP). Each carrier must solve a BCP while respecting its pre-existing commitments and transportation capacity and considering unknown competitors' offers, which makes the problem difficult to solve. In practice, the majority of carriers rely on their historical data and market knowledge to set their prices. In the literature, the majority of works on the BCP propose deterministic models with known parameters and are limited to the problem with a homogeneous fleet. In addition, we found a single work addressing a stochastic BCP. In this thesis, we aim to advance knowledge in this field by introducing new formulations and solution methods for the BCP. The first chapter of this thesis introduces the BCP with a heterogeneous fleet. Starting from a comparison between the BCP and classical Vehicle Routing Problems (VRPs), we propose a new arc-based formulation with new symmetry-breaking constraints for the BCP. Next, we propose exact and heuristic approaches to solve this problem. Our Adaptive Large Neighborhood Search (ALNS) heuristic is based on a destroy-repair principle using operators designed for this problem. Our exact method starts from the heuristic solution and solves our mathematical model with CPLEX. The results we obtained revealed the relevance of our methods in terms of solutions quality and computational times for large instances with up to 500 contracts and 50 vehicles. In the second chapter, we tackle a particular case of the BCP where the carrier has no pre-existing commitments and aims to select a set of profitable auctioned contracts to bid on. This problem corresponds to a Team Orienteering Problem (TOP). We propose a hybrid ALNS heuristic for the TOP with new operators as well as new features taking into account the nature of the problem. Then, we compare the performance of our algorithm against the best solutions from the literature. The results show that our method generally outperforms all the existing ones in terms of solutions quality and/or computational times on benchmark instances. Our method improves one large instance solution, which highlights its performance. In the third chapter, we focus on the uncertainty associated with the auctioned contracts clearing prices and competing carriers offers. Only one article dealing with uncertainty in the BCP existed but it does not allow to generate multiple bids. Thus, we propose a new formulation for the BCP with stochastic prices allowing to generate non-overlapping combinatorial bids. We present two methods to solve this problem. The first one is a two-step hybrid heuristic. First, it solves a Contracts Selection Problem to determine a set of profitable contracts to bid on. Secondly, it simultaneously solves a Contracts Selection and Pricing Problem (CSPP) by considering only the set of auctioned contracts selected in the first stage. Our exact method solves a CSPP by branch-and-cut without pre-selecting contracts. The experimental and simulation results underline the performance of our two methods and evaluate the impact of certain parameters on the carrier's real profit. In the fourth chapter, we focus on the uncertainty associated with bids success and contracts non-materialization. Generally, the carrier seeks to be assured that if some of the submitted bids are not won or a contract does not materialize, it will not incur a loss by serving the remaining contracts. In this research, we address the BCP with stochastic prices and develop an exact method that ensures a non-negative profit for the carrier regardless of the auction outcomes and contracts materialization. Our simulations of the optimal solutions show that, on average, our approach increases the carrier's profit in addition to guaranteeing its non-negativity regardless of the bids won or the contracts materialization.

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.

<p>De nos jours, il est peu de processus ou de tâches qui ne requièrent pas l'optimisation d'une quantité :diminuer le temps de livraison, diminuer l'espace utilisé, réduire les efforts de développement, C'est donc sans surprise que la recherche en optimisation soit l'un des domaines les plus actifs des sciences des technologies de l'information. En optimisation combinatoire, les métaheuristiques sont à compter parmi le fleuron des techniques algorithmiques. Mais ce succès est encore au prix d'une quantité significative de temps de conception et développement. Ne serait-il pas possible d'aller encore plus loin ?D'automatiser la préparation des métaheuristiques ?En particulier dans des conditions telles le manque de temps, l'ignorance de techniques spécialisées ou encore la mauvaise compréhension du problème traité ?C'est ce à quoi nous répondons dans la présente thèse au moyen d'une approche de méta-modélisation de la recherche :l'heuristique de la Gestalt.</p><p><p><p>Considérant la représentation du problème comme un levier que l'on peut activer sous le processus de recherche mené par une métaheuristique, la thèse suggère la construction d'une abstraction de cette représentation capable d'assister la métaheuristique à trouver de bonnes solutions en contraignant sa recherche. Cette approche, inspirée de la psychologie de la Gestalt, nous l'appelons l'heuristique de la Gestalt. Son fonctionnement repose principalement sur l'agrégation des variables de la représentation. Cette agrégation donne lieu à une abstraction structurelle, mais également fonctionnelle en ce sens que les opérateurs de la métaheuristique doivent désormais respecter l'intégrité des agrégats définis.</p><p><p><p>Après avoir établi le contexte de la dissertation, nous discutons de la transposition de la psychologie de la Gestalt dans le cadre de l'optimisation combinatoire et des métaheuristiques. S'ensuit la formalisation de l'heuristique de la Gestalt et la description de sa réalisation. Finalement, une série d'études expérimentales sont menées pour éprouver le concept avancé et valider l'implémentation basée sur les algorithmes évolutionnistes que nous proposons. En conclusion, nous affirmons que l'implémentation de l'heuristique de la Gestalt basée, entre autres, sur un algorithme génétique de groupement est capable d'assister positivement des algorithmes génétiques lorsque les instances de problèmes traitées possèdent une structure riche et complexe, que leur taille est importante, que l'on est tôt dans le processus d'optimisation et que l'algorithme génétique n'est pas paramétré spécifiquement.</p> / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished