Dissertations / Theses on the topic 'Programmation mixte en nombre entiers'

Dans cette thèse, nous étudions des Hoist Scheduling Problems (HSP) qui se posent fréquemment dans des lignes automatiques de traitement de surface. Dans ces lignes, des ponts roulants sont utilisés pour transporter les pièces entre les bains. Ainsi, les ponts roulants jouent un rôle essentiel dans la performance de ces lignes ; et un ordonnancement optimal de leurs mouvements est un facteur déterminant pour garantir la qualité des produits et maximiser la productivité. Les lignes que nous étudions comportent un seul pont roulant mais peuvent être des lignes de base ou des lignes étendues (où des bains sont à fonctions et/ou capacités multiples). Nous examinons trois Hoist Scheduling Problems : l’optimisation robuste d’un HSP cyclique, l’ordonnancement dynamique d’une ligne étendue de type job shop et l’ordonnancement cyclique d’une telle ligne.Pour l’optimisation robuste d’un HSP cyclique, nous définissons la robustesse comme la marge dans le temps de déplacement du pont roulant. Nous formulons le problème en programmation linéaire en nombres mixtes à deux objectifs pour optimiser simultanément le temps de cycle et la robustesse. Nous démontrons que le temps de cycle minimal augmente avec la robustesse, et que par conséquent la frontière Pareto est constituée d’une infinité de solutions. Les valeurs minimales et maximales des deux objectifs sont établies. Les résultats expérimentaux à partir de benchmarks et d’instances générées aléatoirement montrent l’efficacité de l’approche proposée.Nous étudions ensuite un problème d’ordonnancement dynamique dans une ligne étendue de type job shop. Nous mettons en évidence une erreur de formulation dans une un modèle existant pour un problème similaire mais sans bains multi-fonctions. Cette erreur peut rendre l’ordonnancement obtenu sous-optimal voire irréalisable. Nous construisons un nouveau modèle qui corrige cette erreur. De plus il est plus compact et s’applique au cas avec des bains à la fois à capacités et à fonctions multiples. Les résultats expérimentaux menés sur des instances avec ou sans bains multi-fonctions montrent que le modèle proposé conduit toujours à une solution optimale et plus efficace que le modèle existant.Nous nous focalisons enfin sur l’ordonnancement cyclique d’une ligne étendue de type job shop avec des bains à fonctions et capacités multiples. Nous construisons un modèle mathématique en formulant les contraintes de capacité du pont roulant, les intervalles des durées opératoires, et les contraintes de capacité des bains. Nous établissons également des contraintes valides. Les expériences réalisées sur des instances générées aléatoirement montrent l’efficacité du modèle proposé
This thesis studies hoist scheduling problems (HSPs) arising in automated electroplating lines. In such lines, hoists are often used for material handing between tanks. These hoists play a crucial role in the performance of the lines and an optimal schedule of the hoist operations is a key factor in guaranteeing product quality and maximizing productivity. We focus on extended lines (i.e. with multi-function and/or multi-capacity tanks) with a single hoist. This research investigates three hoist scheduling problems: robust optimization for cyclic HSP, dynamic jobshop HSP in extended lines and cyclic jobshop HSP in extended lines.We first study the robust optimization for a cyclic HSP. The robustness of a cyclic hoist schedule is defined in terms of the free slacks in hoist traveling times. A bi-objective mixed-integer linear programming (MILP) model is developed to optimize the cycle time and the robustness simultaneously. It is proved that the optimal cycle time strictly increases with the robustness, thus there is an infinite number of Pareto optimal solutions. We established lower and upper bounds of these two objectives. Computational results on several benchmark instances and randomly generated instances indicate that the proposed approach can effectively solve the problem.We then examine a dynamic jobshop HSP with multifunction and multi-capacity tanks. We demonstrate that an existing model for a similar problem can lead to suboptimality. To deal with this issue, a new MILP model is developed to generate an optimal reschedule. It can handle the case where a multi-function tank is also multi-capacity. Computational results on instances with and without multifunction tanks indicate that the proposed model always yields optimal solutions, and is more compact and effective than the existing one.Finally, we investigate a cyclic jobshop HSP with multifunction and multi-capacity tanks. An MILP model is developed for the problem. The key issue is to formulate the time-window constraints and the tank capacity constraints. We adapt the formulation of time-window constraints for a simpler cyclic HSP to the jobshop case. The tank capacity constraints are handled by dealing with the relationships between hoist moves so that there is always an empty processing slot for new parts. Computational experiments on numerical examples and randomly generated instances indicate that the proposed model can effectively solve the problem

On se propose d'intégrer un type particulier de contrainte logique dans les problèmes de contrôle optimal à coût quadratique. Une approche numérique directe par collocation conduit à des problèmes de programmation mathématique en variables mixtes. S'intéressant d'abord au cas des systèmes à dynamique linéaire, on propose une variante de la Décomposition de Benders qui nous permet de résoudre des problèmes mixtes de taille importante (au delà de mille variables binaires). Ces résultats sont obtenus grâce aux propriétés induites par la contrainte logique. Dans le cas des problèmes mixtes issus d'une dynamique non-linéaire, la démarche proposée (Branch and Reduce) traite de façon analogue les problèmes d'optimisation globale et ceux en variables mixtes. On s'est limité à l'optimisation globale sur le problème de transfert orbital, étudiant notamment les questions de la convexification et de la réduction du domaine. Les résultats obtenus sont partiels, seuls des problèmes de petite taille ayant été traités.

Cette thèse se rapporte à la navigation et le contrôle par optimisation dans des environnements multi-obstacles. Le problème de conception est généralement énoncé dans la littérature en termes de problème d'optimisation sous contrainte sur un domaine non convexe. Ainsi, en s'appuyant sur la combinaison du contrôle prédictif de modèle et des concepts de la théorie des ensembles, on a développe des méthodes constructives basées sur l'interprétation géométrique. Dans sa première partie, la thèse se concentre sur la représentation de l'environnement multi-obstacles, basée sur une analyse approfondie des résultats récents dans le domaine. Ainsi, on a choisi d'exploiter une classe particulière d'ensembles convexes (dotés de la propriété de symétrie) afin de modéliser l'environnement, réduire la complexité et améliorer les performances. De plus, on a résolve un problème ouvert dans la navigation dans des environnements encombrés : le partitionnement de l'espace faisable en fonction de la distribution des obstacles. Le cœur de cette méthodologie est la construction d'un convex lifting qui se résume à une optimisation convexe. On a couvré à la fois les fondements mathématiques et les détails informatiques de l'implémentation. Enfin, on a illustré les concepts par des exemples géométriques et on a complété l'étude en fournissant des garanties de faisabilité globale et en améliorant le contrôle effectif au niveau stratégique
This thesis pertains to optimization-based navigation and control in multi-obstacle environments. The design problem is commonly stated in the literature in terms of a constrained optimization problem over a non-convex domain. Thus, building on the combination of Model Predictive Control and set-theoretic concepts, we develop a couple of constructive methods based on the geometrical interpretation. In its first part, the thesis focuses based on a thorough analysis of the recent results in the field on the multi-obstacle environment's representation. Hence, we opted to exploit a particular class of convex sets endowed with the symmetry property to model the environment, reduce complexity, and enhance performance. Furthermore, we solve an open problem in navigation within cluttered environments: the feasible space partitioning in accordance with the distribution of obstacles. This methodology's core is the construction of a convex lifting which boils down to convex optimization. We cover both the mathematical foundations and the computational details of the implementation. Finally, we illustrate the concepts with geometrical examples, and we complement the study by further providing global feasibility guarantees and enhancing the effective control by operating at the strategical level

Pour les opérateurs, les réseaux FTTH représentent à la fois la solution de référence pour répondre à la demande croissante de trafic fixe, et un investissement considérable dû à leur mise en place. Le but de ces travaux est d'assurer le déploiement de réseaux de qualité à moindre coût. Nous commençons à présenter les différents aspects de la planification de ces réseaux qui en font un problème complexe. La littérature concernée est abordée afin d'exhiber les nouveaux défis que nous relevons. Puis nous élaborons des stratégies permettant de trouver la meilleure solution dans différents contextes. Plusieurs politiques de maintenance ou d'utilisation du génie civil sont ainsi explorées. Les problèmes rencontrés sont analysés à la lumière de divers outils d'optimisation (programmation entière, inégalités valides, programmation dynamique, approximations, complexités, inapproximabilité...) que nous utilisons et développons selon nos besoins. Les solutions proposées ont été testées et validées sur des instances réelles, et ont pour but d'être utilisées par Orange
For operators, FTTH networks are the most widespread solution to the increasing traffic demand. Their layout requires a huge investment. The aim of this work is to ensure a cost effective deployment of quality networks. We start by presenting aspects of this network design problem which make it a complex problem. The related literature is reviewed to highlight the novel issues that we solve. Then, we elaborate strategies to find the best solution in different contexts. Several policies regarding maintenance or civil engineering use will be investigated. The problems encountered are tackled using several combinatorial optimization tools (integer programming, valid inequalities, dynamic programming, approximations, complexity theory, inapproximability…) which will be developed according to our needs. The proposed solutions were tested and validated on real-life instances, and are meant to be implemented in a network planning tool from Orange

Dans le secteur électrique et chez EDF, l'optimisation mathématique est utilisée pour modéliser et résoudre des problèmes de gestion de la production d'électricité.Citons quelques applications : la modélisation des problèmes d'équilibre des marchés, la gestion des risques d'épuisement des barrages, la programmation des arrêts de tranches nucléaires.Plus particulièrement l'hydroélectricté est une énergie renouvelable, peu chère, flexible mais limitée.Exploiter l'hydraulique constitue donc un enjeu important.Nous nous intéressons à des problèmes d'optimisation de Programmation Non Linéaire en Nombres Entiers (PNLNE) dont les variables de décision sont continues ou discrètes et dont les fonctions exprimant l'objectif et les contraintes sont linéaires ou non.Les non-linéarités et la combinatoire induite par les variables entières rendent les PNLNE difficiles à résoudre.En effet les méthodes existantes n'arrivent pas toujours à résoudre les grands PNLNE à l'optimalité avec des temps de calcul limités.En amont des performances de résolution, la faisabilité est une question préliminaire à aborder puisqu'il faut s'assurer que les PNLNE à résoudre admettent des solutions.Lorsqu'il y a des infaisabilités dans des modèles complexes, il est très utile mais très difficile de les analyser.Par ailleurs la résolution de PNLNE est plus difficile si l'on requiert une certification de la précision exacte des résultats.En effet les méthodes résolutions sont en général mises en oeuvre en arithmétique flottante, ce qui peut donner lieu à une précision approchée.Nous abordons deux problèmes d'optimisation liés à la planification de la production hydraulique, Hydro Unit-Commitment (HUC) en Anglais.Etant données des ressources d'eau finies dans les barrages l'objet du HUC est de prescrire des programmes de production les plus rentables qui soient compatibles avec les spécifications techniques des usines hydrauliques.Le volume, le débit et la puissance sont représentés par des variables continues tandis que l'activation des turbines est communément formulée avec des variables binaires.Les non-linéarités proviennent en général des fonctions qui expriment la puissance générée en fonction du volume et du débit.Nous distinguons deux problèmes : un PLNE avec des caractéristiques linéaires et discrètes et un PNL avec des caractéristiques non linéaires et continues.Dans le 2ème chapitre, nous traitons de la faisabilité d'un HUC réel en PLNE.Comparé à un HUC standard le modèle inclut deux spécifications supplémentaires : des points de fonctionnements discrets sur la courbe puissance-débit ainsi que des niveaux cibles pour le volume des réservoirs.Les complications liées aux données réelles et au calcul numérique, associées aux spécifications du modèle rendent notre problème difficile à résoudre et souvent infaisable.Nous procédons par étape pour identifier et traiter les sources d'infaisabilité, à savoir les erreurs numériques et les infaisabilités de modélisation, pour rendre le problème faisable.Des résultats numériques étayent l'efficacité de notre méthode sur un ensemble de test de 66 instances réelles qui contient de nombreuses infaisabilités.Le 3ème chapitre porte sur l'adaptation de l'algorithme Multiplicative Weights Update (MWU) à la PNLNE.Cette adaptation est fondée sur une reformulation paramétrée spécifique dénommée pointwise.Nous définissons des propriétés souhaitables pour obtenir de bonnes reformulations pointwise et nous fournissons des règles pour adapter l'algorithme étape par étape.Nous démontrons que notre matheuristique du MWU conserve une garantie d'approximation relative contrairement à la plupart des heuristiques.Le MWU est comparée à la méthode Multi-Start pour résoudre un HUC en PNL et les résultats numériques penchent en faveur du MWU
In the electricity industry, and more specifically at the French utility company EDF, mathematical optimization is used to model and solve problems related to electricity production management.To name a few applications: planning for capacity investments, managing depletion risks of hydro-reservoirs, scheduling outages and refueling for nuclear plants.More specifically, hydroelectricity is a renewable, cheap, flexible but limited source of energy.Harnessing hydroelectricity is thus critical for electricity production management.We are interested in Mixed-Integer Non-Linear Programming (MINLP) optimization problems.They are optimization problems whose decision variables can be continuous or discrete and the functions to express the objective and constraints can be linear or non-linear.The non-linearities and the combinatorial aspect induced by the integer variables make these problems particularly difficult to solve.Indeed existing methods cannot always solve large MINLP problems to the optimum within limited computational timeframes.Prior to solution performance, feasibility is preliminary challenge to tackle since we want to ensure the MINLP problems to solve admit feasible solutions.When infeasibilities occur in complex models, it is useful but not trivial to analyze their causes.Also, certifying the exactness of the results compounds the difficulty of solving MINLP problems as solution methods are generally implemented in floating-point arithmetic, which may lead to approximate precision.In this thesis, we work on two optimization problems - a Mixed-Integer Linear Program (MILP) and a Non-Linear Program (NLP) - related to Short-Term Hydropower production Scheduling (STHS).Given finite resources of water in reservoirs, the purpose of STHS is to prescribe production schedules with largest payoffs that are compatible with technical specifications of the hydroelectric plants.While water volumes, water flows, and electric powers can be represented with continuous variables, commitment statuses of turbine units usually have to be formulated with binary variables.Non-linearities commonly originate from the Input/Output functions that model generated power according to water volume and water flow.We decide to focus on two distinguished problems: a MILP with linear discrete features and a NLP with non-linear continuous features.In the second chapter, we deal with feasibility issues of a real-world MILP STHS.Compared with a standard STHS problem, the model features two additional specifications:discrete operational points of the power-flow curve and mid-horizon and final strict targets for reservoir levels.Issues affecting real-world data and numerical computing, together with specific model features, make our problem harder to solve and often infeasible.Given real-world instances, we reformulate the model to make the problem feasible.We follow a step-by-step approach to exhibit and cope with one source of infeasility at a time, namely numerical errors and model infeasibilities.Computational results show the effectiveness of the approach on an original test set of 66 real-world instances that demonstrated a high occurrence of infeasibilities.The third chapter is about the transposition of the Multiplicative Weights Update algorithm to the (nonconvex) nonlinear and mixed integer nonlinear programming setting, based on a particular parametrized reformulation of the problem - denoted pointwise.We define desirable properties for deriving pointwise reformulation and provide generic guidelines to transpose the algorithm step-by-step.Unlike most metaheuristics, we show that our MWU metaheuristic still retains a relative approximation guarantee in the NLP and MINLP settings.We benchmark it computationally to solve a hard NLP STHS.We find it compares favorably to the well-known Multi-Start method, which, on the other hand, offers no approximation guarantee

Pour les opérateurs, les réseaux FTTH représentent à la fois la solution de référence pour répondre à la demande croissante de trafic fixe, et un investissement considérable dû à leur mise en place. Le but de ces travaux est d'assurer le déploiement de réseaux de qualité à moindre coût. Nous commençons à présenter les différents aspects de la planification de ces réseaux qui en font un problème complexe. La littérature concernée est abordée afin d'exhiber les nouveaux défis que nous relevons. Puis nous élaborons des stratégies permettant de trouver la meilleure solution dans différents contextes. Plusieurs politiques de maintenance ou d'utilisation du génie civil sont ainsi explorées. Les problèmes rencontrés sont analysés à la lumière de divers outils d'optimisation (programmation entière, inégalités valides, programmation dynamique, approximations, complexités, inapproximabilité...) que nous utilisons et développons selon nos besoins. Les solutions proposées ont été testées et validées sur des instances réelles, et ont pour but d'être utilisées par Orange
For operators, FTTH networks are the most widespread solution to the increasing traffic demand. Their layout requires a huge investment. The aim of this work is to ensure a cost effective deployment of quality networks. We start by presenting aspects of this network design problem which make it a complex problem. The related literature is reviewed to highlight the novel issues that we solve. Then, we elaborate strategies to find the best solution in different contexts. Several policies regarding maintenance or civil engineering use will be investigated. The problems encountered are tackled using several combinatorial optimization tools (integer programming, valid inequalities, dynamic programming, approximations, complexity theory, inapproximability…) which will be developed according to our needs. The proposed solutions were tested and validated on real-life instances, and are meant to be implemented in a network planning tool from Orange

Les systèmes adaptatifs basés sur les architectures FPGA (Field-Programmable Gate Arrays) peuvent bénéficier grandement de la grande flexibilité offerte par la reconfiguration partielle dynamique (DPR). Grâce au DPR, les tâches matérielles composant un système adaptatif peuvent être allouées et re-allouées à la demande ou en fonction de l'environnement dynamique. Les flots de conceptions disponibles et les outils commerciaux ont évolué pour répondre aux exigences des architectures reconfigurables qui sont toutefois limitées dans leurs fonctionnalités. Ces outils ne permettent pas un placement et une relocation efficaces de tâches matérielles de tailles variables. L'objectif principal de ces travaux de thèse consiste à proposer des nouvelles méthodologies et de nouvelles approches pour faciliter au concepteur la phase de conception d'un système adaptatif reconfigurable opérationnelle, valide, optimisé et adapté aux changements dynamiques de l'environnement. La première contribution de cette thèse porte sur la problématique de la relocation des tâches matérielles de tailles différentes. Une méthodologie de conception est proposée pour répondre à un problème majeur des mécanismes de relogement : le stockage d'une unique bitstream de configuration pour réduire les besoins de la mémoire et pour accroître la réutilisable des modules matériels générés. Une technique de partitionnement de la région reconfigurable est appliquée dans la méthodologie de relogement proposée pour augmenter l'efficacité d'utilisation des ressources matérielles dans le cas des tâches reconfigurables de tailles variables. Cette méthodologie prend en compte aussi la communication entre différentes régions reconfigurables et la région statique. Pour valider la méthode, plusieurs études de cas sont implémentées. Cette validation montre une utilisation efficace des ressources matérielles ainsi une réduction importante du temps de reconfiguration. La deuxième partie de cette thèse présente et détaille une formulation mathématique afin d'automatiser le floorplanning des zones reconfigurables dans les FPGAs. Les algorithmes de recherche présentés dans cette thèse sont basés sur la technique d'optimisation PLMNE (programmation linéaire mixte en nombres entiers). Ces algorithmes permettent de définir automatiquement l'emplacement, la taille et la forme de la zone reconfigurable dynamique. Nous nous intéressons principalement dans cette recherche à la satisfaction des contraintes de placement des zones reconfigurables et celles liées à la relocation. De plus, nous considérons l’optimisation des ressources matérielles dans le FPGA en tenant compte des tâches de tailles variables. Finalement, une évaluation de l'approche proposée est présentée
Adaptive systems based on Field-Programmable Gate Arrays (FPGA) architectures can benefit greatly from the high degree of flexibility offered by dynamic partial reconfiguration (DPR). Thanks to DPR, hardware tasks composing an adaptive system can be allocated and relocated on demand or depending on the dynamically changing environment. Existing design flows and commercial tools have evolved to meet the requirements of reconfigurables architectures, but that are limited in functionality. These tools do not allow an efficient placement and relocation of variable-sized hardware tasks. The main objective of this thesis is to propose a new methodology and a new approaches to facilitate to the designers the design phase of an adaptive and reconfigurable system and to make it operational, valid, optimized and adapted to dynamic changes in the environment. The first contribution of this thesis deals with the issues of relocation of variable-sized hardware tasks. A design methodology is proposed to address a major problem of relocation mechanisms: storing a single configuration bitstream to reduce memory requirements and increasing the reusability of generating hardware modules. A reconfigurable region partitioning technique is applied in this proposed relocation methodology to increase the efficiency of use of hardware resources in the case of reconfigurable tasks of variable sizes. This methodology also takes into account communication between different reconfigurable regions and the static region. To validate the design method, several cases studies are implemented. This validation shows an efficient use of hardware resources and a significant reduction in reconfiguration time. The second part of this thesis presents and details a mathematical formulations in order to automate the floorplanning of the reconfigurable regions in the FPGAs. The algorithms presented in this thesis are based on the optimization technique MILP (mixed integer linear programming). These algorithms allow to define automatically the location, the size and the shape of the dynamic reconfigurable region. We are mainly interested in this research to satisfy the constraints of placement of the reconfigurable zones and those related to the relocation. In addition, we consider the optimization of the hardware resources in the FPGA taking into account the tasks of variable sizes. Finally, an evaluation of the proposed approach is presented

Dans l’industrie aéronautique, les problèmes d’optimisation de structurepeuvent impliquer des changements de matériaux, de types de raidisseurs, et detailles d’éléments. Dans ce travail, il est ainsi proposé de résoudre des problèmes degrande taille (minimisation de masse) par rapport à des variables catégorielles et continues,sujets à des contraintes de stress et de déplacements. Trois algorithmes sontprésentés, discutés dans le manuscrit au regard de cas tests de plus en plus complexes.En tout premier lieu, un algorithme basé sur le "branch and bound" a été mis en place.Une formulation d’un problème dédié au calcul de minorants de la masse optimale estproposée. Bien que l’algorithme permette de trouver des solutions optimales, la tendancedu coût de calcul en fonction de l’augmentation du nombre d’éléments est exponentielle.Le second algorithme s’appuie sur une formulation bi-niveau du problème d’origine, oùle problème supérieur consiste à minimiser une approximation au premier ordre du résultatdu niveau inférieur. L’évolution du coût de calcul par rapport à l’augmentation dunombre d’éléments et de valeurs catégorielles est quasiment linéaire. Enfin, un troisièmealgorithme tire partie d’une reformulation du problème mixte catégoriel continu en unproblème bi-niveau mixte avec variables entières continûment relâchables. Les cas testsnumériques montrent la résolution d’un problème avec plus d’une centaine d’éléments.Également, le coût de calcul est quasi-indépendant du nombre de valeurs de variablescatégorielles disponibles par élément
Nowadays in the aircraft industry, structural optimization problemscan be really complex and combine changes in choices of materials, stiffeners, orsizes/types of elements. In this work, it is proposed to solve large scale structural weightminimization problems with both categorical and continuous variables, subject to stressand displacements constraints. Three algorithms have been proposed. As a first attempt,an algorithm based on the branch and bound generic framework has been implemented.A specific formulation to compute lower bounds has been proposed. According to thenumerical tests, the algorithm returned the exact optima. However, the exponentialscalability of the computational cost with respect to the number of structural elementsprevents from an industrial application. The second algorithm relies on a bi-level formulationof the mixed categorical problem. The master full categorical problem consists ofminimizing a first order like approximation of the slave problem with respect to the categoricaldesign variables. The method offers a quasi-linear scaling of the computationalcost with respect to the number of elements and categorical values. Finally, in the thirdapproach the optimization problem is formulated as a bi-level mixed integer non-linearprogram with relaxable design variables. Numerical tests include an optimization casewith more than one hundred structural elements. Also, the computational cost scalingis quasi-independent from the number of available categorical values per element

Le déséquilibre d'un sommet dans un graphe orienté est la valeur absolue de la différence entre son degré sortant et son degré entrant. Nous étudions le problème de trouver une orientation des arêtes du graphe telle que l'image du vecteur dont les composantes sont les déséquilibres des sommets par une fonction objectif f est maximisée. Le premier cas considéré est le problème de maximiser le minimum des déséquilibres sur toutes les orientations possibles. Nous caractérisons les graphes dont la valeur objective optimale est nulle. Ensuite nous donnons plusieurs résultats concernant la complexité du problème. Enfin, nous introduisons différentes formulations du problème et présentons quelques résultats numériques. Par la suite, nous montrons que le cas f=1/2 | |·| |₁ mène au célèbre problème de la coupe de cardinalité maximale. Nous introduisons de nouvelles formulations ainsi qu'un nouveau majorant qui domine celui de Goemans et Williamson. Des résultats théoriques et numériques concernant la performance des approches sont présentés. Pour finir, dans le but de renforcer certaines des formulations des problèmes étudiés, nous étudions une famille de polyèdres spécifique consistant en l'enveloppe convexe des matrices d'affectation 0/1 (où chaque colonne contient exactement une composante égale à 1) annexée avec l'indice de leur ligne non-identiquement nulle la plus basse. Nous donnons une description complète de ce polytope ainsi que certaines de ses variantes qui apparaissent naturellement dans le contexte de divers problèmes d'optimisation combinatoire. Nous montrons également que résoudre un programme linéaire sur un tel polytope peut s'effectuer en temps polynomial
The imbalance of a vertex in a directed graph is the absolute value of the difference between its outdegree and indegree. In this thesis we study the problem of orienting the edges of a graph in such a way that the image of the vector which components are the imbalances of the vertices of the graph under an objective function f is maximized. The first case considered is the problem of maximizing the minimum imbalance of all the vertices over all the possible orientations of the input graph. We first characterize graphs for which the optimal objective value is zero. Next we give several results concerning the computational complexity of the problem. Finally, we deal with several mixed integer programming formulations for this problem and present some numerical experiments. Next, we show that the case for f=1/2 | |·| |₁ leads to the famous unweighted maximum cut problem. We introduce some new formulations along with a new bound shown to be tighter than Michel Goemans & David Williamson's. Theoretical and computational results regarding bounds quality and performance are also reported. Finally, in order to strengthen some formulations of the studied problems, we study a specific class of polytopes. Consider the polytope consisting in the convex hull of the 0/1 assignment matrices where each column contains exactly one coefficient equal to 1 appended with their index of the lowest row that is not identically equal to the zero row. We give a full description of this polytope and some of its variants which naturally appear in the context of several combinatorial optimization problems. We also show that linear optimization over those polytopes can be done in polynomial time

Dans cette thèse, nous abordons les liens entre diverses hiérarchies de relaxations semi-algébriques pour des programmes linéaires mixtes 0-1. Parmi celles-ci, citons la hiérarchie de Sherali-Adams (S&A) et la hiérarchie Lift-and-Project (L&P). Tout d’abord, nous montrons que la hiérarchie L&P est semi-algébrique. Puis, nous introduisons une nouvelle hiérarchie de relaxations semi-algébriques, dite SRL*, intermédiaire entre les hiérarchies S&A et L&P. Nous examinons les liens entre les hiérarchies L&P et SRL*. Nous aborderons comment renforcer la description linéaire d’une relaxation L&P pour qu’elle coïncide avec celle d’une relaxation SRL*. Nous montrons aussi que toute relaxation S&A s’obtient en renforçant une relaxation SRL* par des contraintes dites « conditions de symétries ». Nous étayons notre analyse par des résultats de calculs préliminaires comparant le renforcement des relaxations L&P, S&A et SRL* de rang 2. Ensuite, nous caractérisons les programmes linéaires mixtes 0-1 pour lesquels les hiérarchies S&A et SRL* coïncident. Comme application, nous prouverons que les hiérarchies SRL* et S&A coïncident pour l'optimisation d'une fonction pseudo booléenne sur un polyèdre quelconque. Pour illustrer cette propriété nous présentons des résultats de calculs préliminaires sur des instances MINCUT avec contraintes de cardinalité. Enfin, nous présentons des expériences de calcul concernant les renforcements procurés par des relaxations L&P de rang 2 et 3 sur des instances Max-2SAT et Max-3SAT. Nous explorons également, la possibilité d’utiliser des relaxations L&P partielles.

Increasing global competition in the business world and heightened expectations of customers have forced companies to consider not only the pricing or product quality, but reliability and timeliness of the deliveries as well. In manufacturing-centric industries such as automotive and electronics, distribution and inventory costs constitute the second and third largest cost components following the production costs. Therefore, industrial and logistics companies need to continuously search for ways to lower the inventory level and distribution cost. This trend has created a closer interaction between the different stages of a supply chain, and increased the practical usefulness of the integrated models.This thesis considers two categories of integrated scheduling problems. One is Integrated Scheduling of Production-Distribution-Inventory problems (ISPDI problems) and the other is Integrated Scheduling of Production-Inventory-Distribution-Inventory problems (ISPIDI problems). Jobs are first processed on a single machine in the production stage, and then delivered to a pre-specified customer by a capacitated transporter. Each job has a distinct due date, and must be delivered to customer before this due date. Each production batch requires a setup cost and a setup time before the first job of this batch is processed. Each round trip between the factory and customer requires a delivery cost as well as a delivery time. Moreover, it is assumed that a job which is completed before its departure date or delivered to the customer before its due date will incur a corresponding inventory cost. Our objective is to minimize the total cost involving setup, inventory and delivery costs while guaranteeing a certain customer service level.For ISPDI problems, we firstly provide a mixed integer programming model for the case of multi-product, single-stage situation, and develop an improved Genetic algorithm (GA) for solving it. Then, we extend this model to a single-product, multi-stage model, and provide two methods, dominance-related greedy algorithm and GA, for solving it. For ISPIDI problems, we establish a general non-linear model for the case of single-product situation and devise a special case from the general model. Then we provide an optimality property between the production and delivery schedules for the special case. Finally, a heuristic approach is developed for solving it. For each problem under study, in order to evaluate the performance of the proposed algorithms, some interesting lower bounds on the corresponding objective functions are established according to different methods such as Lagrangian relaxation method, classical bin-packing based method. Computational results show the efficiency of the proposed models and algorithms in terms of solution quality and running time.

Les ateliers de traitement de surface automatisés, qui utilisent des robots de manutention commandés par ordinateur pour le transport de la pièce, ont été largement mis en place dans différents types d'entreprises industrielles, en raison de ses nombreux avantages par rapport à un mode de production manuel, tels que : une plus grande productivité, une meilleure qualité des produits, et l’impact sur les rythmes de travail. Notre recherche porte sur trois types de problèmes d'ordonnancement associés à ces systèmes, appelés Hoist Scheduling Problems, caractérisés par des contraintes de fenêtres de temps de traitement: (I) un problème à une seule ressource de transport où l’objectif est de minimiser le temps de cycle; (II) un problème bi-objectif avec une seule ressource de transport où il faut minimiser le temps de cycle et la consommation de ressources de traitement (et par conséquent le coût de production); et (III) un problème d'ordonnancement cyclique mono-objectif mais multi-robots.En raison de la NP-complétude des problèmes étudiés et de nombreux avantages de les outils de type quantum-inspired evolutionary algorithm (QEA), nous proposons d'abord un QEA hybride comprenant un mécanisme de décodage amélioré et une procédure réparation dédiée pour trouver le meilleur temps de cycle pour le premier problème. Après cela, afin d'améliorer à la fois la performance économique et environnementale qui constituent deux des trois piliers de la stratégie de développement durable de nos jours déployée dans de nombreuses industries, nous formulons un modèle mathématique bi-objectif pour le deuxième problème en utilisant la méthode de l'intervalle interdit. Ensuite, nous proposons un QEA bi-objectif couplé avec une procédure de recherche locale pour minimiser simultanément le temps de cycle et les coûts de production, en générant un ensemble de solutions Pareto-optimales pour ce problème. Quant au troisième problème, nous constatons que la plupart des approches utilisées dans les recherches actuelles, telles que la programmation entière mixte (MIP), peuvent conduire à l’obtention d’une solution non optimale en raison de la prise en compte courante d’une hypothèse limitant l’exploration de l’espace de recherche et relative aux mouvements en charge des robots. Par conséquent, nous proposons une approche de MIP améliorée qui peut garantir l'optimalité des solutions obtenues pour ce problème, en relaxant l'hypothèse mentionnée ci-dessus.Pour chaque problème, une étude expérimentale a été menée sur des cas industriels ainsi que sur des instances générées aléatoirement. Les résultats obtenus montrent que l’efficacité des algorithmes d'ordonnancement proposés, ce qui justifie les choix que nous avons faits
Automated treatment surface facilities, which employ computer-controlled hoists for part transportation, have been extensively established in various kinds of industrial companies, because of its numerous advantages over manual system, such as higher productivity, better product quality, and reduced labor intensity. Our research investigates three typical hoist scheduling problems with processing time windows in treatment surface facilities, which are: (I) cyclic single-hoist scheduling problem to minimize the cycle time; (II) cyclic single-hoist scheduling problem to minimize the cycle time and processing resource consumption (and consequently production cost); and (III) cyclic multi-hoist scheduling problem to minimize the cycle time.Due to the NP-completeness of the studied problems and numerous advantages of quantum-inspired evolutionary algorithm (QEA), we first propose a hybrid QEA with improved decoding mechanism and repairing procedure to find the best cycle time for the first problem. After that, to enhance with both the economic and environmental performance, which constitute two of the three pillars of the sustainable strategy nowadays deployed in many industries, we formulate a bi-objective mathematical model for the second problem by using the method of prohibited interval. Then we propose a bi-objective QEA with local search procedure to simultaneously minimize the cycle time and production cost, and we find a set of Pareto-optimal solutions for this problem. As for the third problem, we find that most existing approaches, such as mixed integer programming (MIP) approach, may identify a non-optimal solution to be an optimal one due to an assumption related to the loaded hoist moves which is made in many existing researches. Consequently, we propose an improved MIP approach for this problem by relaxing the above-mentioned assumption. Our approach can guarantee the optimality of its obtained solutions.For each problem, experimental study on industrial instances and random instances has been conducted. Computational results demonstrate that the proposed scheduling algorithms are effective and justify the choices we made

Dans cette thèse nous développons des structures de supervision permettant de définir des consignes optimales pour des actionneurs thermiques, ainsi que des stratégies de commande appropriées pour le pilotage d'une pompe à chaleur (PAC). Pour répondre à ces objectifs, plusieurs étapes ont été réalisées :- Modélisation orientée commande d'une PAC réversible, des thermistances, et de l'environnement permettant de les lier à l'intérieur de l'habitacle. Des modèles physiques ont été définis et intégrés dans une plateforme du type Model-in-the-Loop pour permettre a posteriori la validation des stratégies de commande et d'optimisation. - Commande d'une PAC. La linéarisation du modèle de PAC autour de certains points de fonctionnement a permis le développement de la commande de l'actionneur principal. La structure de commande proposée permet de prendre en compte, en boucle fermée, des contraintes d'état et d'entrée du système. Les performances de cette structure ont été analysées en considérant successivement des régulateurs principaux de type PI et Hinf. Enfin, des algorithmes réalisant le pilotage d'un actionneur secondaire du système ont été également proposés. - Optimisation des actionneurs thermiques. L'utilisation combinée de thermistances et de la PAC présente des avantages en termes de réduction de la consommation énergétique et/ou du maintien de la puissance thermique demandée dans des conditions aux limites de fonctionnement. Le problème d'optimisation a été résolu en deux temps : des solutions hors-ligne ont été obtenues par résolution d'un problème mixte en nombre entier avec modèle prédictif, puis utilisées pour déduire des stratégies embarquables sur le véhicule.

Afin de répondre à la problématique de la régulation multi-objectif et multi-mode des carrefours à feux, nous proposons trois modèles de programmation linéaire mixte en nombres entiers constituant les moteurs d'un système de régulation pleinement adaptatif, ainsi que deux procédures interactives d'optimisation multi-objectif permettant d'adapter itérativement une "politique de régulation" à la situation de trafic. Les critères pris en compte, tous à minimiser, sont le temps d'attente et le nombre d'arrêts des véhicules particuliers, et un critère dédié aux transports en commun permettant de fixer un temps d'attente souhaité pour chaque bus. Des expérimentations ont montré qu'un des trois modèles, dit hybride, se démarque positivement des deux autres. Ce modèle a alors été mis en œuvre avec une des deux procédures interactives, permettant de contrôler un trafic simulé sur une période d'une heure dans différents scénarios types, et comparé à un système de régulation semi-adaptatif.

Le problème d’approvisionnement conjoint (JDP) proposé est un problème de planification des tournées de livraisons sur un horizon de temps décomposé en périodes élémentaires, l’horizon de temps étant la période commune de livraison de tous les produits,. La donnée de ces paramètres permet d’obtenir une formulation linéaire du problème, avec des variables de décision binaires. Le modèle intègre aussi des contraintes de satisfaction de la demande à partir des stocks et des quantités livrées, des contraintes sur les capacités de stockage et de transport.Afin de résoudre aussi le problème de choix des tournées de livraison, il est nécessaire d'introduire dans le modèle des contraintes et des variables liées aux sites visités au cours de chaque tour. Il est proposé de résoudre le problème en deux étapes. La première étape est le calcul hors ligne du coût minimal de la tournée associé à chaque sous-ensemble de sites. On peut observer que pour tout sous-ensemble donné de sites, le cycle hamiltonien optimal reliant ces sites à l'entrepôt peut être calculé à l'avance par un algorithme du problème du voyageur de commerce (TSP). Le but ici n'est pas d'analyser pleinement le TSP, mais plutôt d'intégrer sa solution dans la formulation de JRP. .Dans la deuxième étape, des variables binaires sont associées à chaque tour et à chaque période pour déterminer le sous-ensemble de sites choisi à chaque période et son coût fixe associé
The proposed joint delivery problem (JDP) is a delivery tour planning problem on a time horizon decomposed into elementary periods or rounds, the time horizon being the common delivery period for all products. The data of these parameters provides a linear formulation of the problem, with binary decision variables. The model also incorporates the constraints of meeting demand from stock and the quantities supplied, storage and transport capacity constraints.In order to also solve the problem of choice of delivery rounds, it is necessary to introduce in the model several constraints and variables related to the sites visited during each round. It is proposed to solve the problem in two steps. The first step is the calculation of the minimum off-line cost of the tour associated with each subset of sites. One can observe that for any given subset of sites, the optimal Hamiltonian cycle linking those sites to the warehouse can be calculated in advance by a traveling salesman problem algorithm (TSP). The goal here is not to fully analyze the TSP, but rather to integrate its solution in the formulation of the JRP. In the second stage, binary variables are associated with each subset and each period to determine the selected subset of sites in each period and its associated fixed cost

Le déséquilibre d'un sommet dans un graphe orienté est la valeur absolue de la différence entre son degré sortant et son degré entrant. Nous étudions le problème de trouver une orientation des arêtes du graphe telle que l'image du vecteur dont les composantes sont les déséquilibres des sommets par une fonction objectif f est maximisée. Le premier cas considéré est le problème de maximiser le minimum des déséquilibres sur toutes les orientations possibles. Nous caractérisons les graphes dont la valeur objective optimale est nulle. Ensuite nous donnons plusieurs résultats concernant la complexité du problème. Enfin, nous introduisons différentes formulations du problème et présentons quelques résultats numériques. Par la suite, nous montrons que le cas f=1/2 | |·| |₁ mène au célèbre problème de la coupe de cardinalité maximale. Nous introduisons de nouvelles formulations ainsi qu'un nouveau majorant qui domine celui de Goemans et Williamson. Des résultats théoriques et numériques concernant la performance des approches sont présentés. Pour finir, dans le but de renforcer certaines des formulations des problèmes étudiés, nous étudions une famille de polyèdres spécifique consistant en l'enveloppe convexe des matrices d'affectation 0/1 (où chaque colonne contient exactement une composante égale à 1) annexée avec l'indice de leur ligne non-identiquement nulle la plus basse. Nous donnons une description complète de ce polytope ainsi que certaines de ses variantes qui apparaissent naturellement dans le contexte de divers problèmes d'optimisation combinatoire. Nous montrons également que résoudre un programme linéaire sur un tel polytope peut s'effectuer en temps polynomial
The imbalance of a vertex in a directed graph is the absolute value of the difference between its outdegree and indegree. In this thesis we study the problem of orienting the edges of a graph in such a way that the image of the vector which components are the imbalances of the vertices of the graph under an objective function f is maximized. The first case considered is the problem of maximizing the minimum imbalance of all the vertices over all the possible orientations of the input graph. We first characterize graphs for which the optimal objective value is zero. Next we give several results concerning the computational complexity of the problem. Finally, we deal with several mixed integer programming formulations for this problem and present some numerical experiments. Next, we show that the case for f=1/2 | |·| |₁ leads to the famous unweighted maximum cut problem. We introduce some new formulations along with a new bound shown to be tighter than Michel Goemans & David Williamson's. Theoretical and computational results regarding bounds quality and performance are also reported. Finally, in order to strengthen some formulations of the studied problems, we study a specific class of polytopes. Consider the polytope consisting in the convex hull of the 0/1 assignment matrices where each column contains exactly one coefficient equal to 1 appended with their index of the lowest row that is not identically equal to the zero row. We give a full description of this polytope and some of its variants which naturally appear in the context of several combinatorial optimization problems. We also show that linear optimization over those polytopes can be done in polynomial time

Les travaux de cette thèse concernent la conception et l'optimisation de lignes de transfert reconfigurables. L'objectif principal est de concevoir une ligne d'usinage à moindre coût tout en respectant les contraintes techniques, technologiques et économiques du problème. Le problème d'optimisation correspondant est un problème d'équilibrage de lignes d'usinage sujet à des contraintes spécifiques. Il consiste à affecter les opérations aux stations de travail en minimisant les coûts d'installation. En plus des contraintes habituelles de ce type de problème, à savoir, les contraintes de précédence, d'inclusion et d'exclusion, nous avons dû considérer des contraintes d'accessibilité. De plus, la spécificité principale des lignes reconfigurables par rapport aux lignes de transfert dédiées, vient de la réalisation en série des opérations. Celle-ci rend souvent nécessaire la mise en place de stations équipées de plusieurs centres d'usinage travaillant en parallèle pour obtenir les volumes de production souhaités. Enfin, l'utilisation d'une tête d'usinage mono-broche induit la prise en compte de temps inter-opératoire de déplacements et de changement d'outils qui dépendent de la séquence d'opérations. Dans un premier temps, nous avons proposé une modélisation mathématique du problème à l'aide d'un programme linéaire en nombres mixtes. Nous avons aussi développé des méthodes de calcul de bornes inférieures ainsi qu'une procédure de prétraitement. Cependant, les contraintes additionnelles rendent la résolution du problème d'équilibrage plus difficile que dans le cas des lignes dédiées, et l'approche proposée ne permet généralement pas de résoudre des instances de taille industrielle. Pour répondre à ce besoin, nous avons donc développé plusieurs méthodes de résolution approchées du problème en nous inspirant de métaheuristiques efficaces sur des problèmes d'optimisation combinatoire.

Le problème de commande motrice de systèmes exécutant des activités multi-objectifs et fortement contraintes est à résoudre pour permettre l’émergence de comportements performants et robustes ; l’élaboration de stratégies complexes de coordination motrice est critique pour en assurer les performances, faisabilité et sécurité.Bien que les approches de commande prédictive multi-objectifs permettent la définition de stratégies complexes et sous contraintes coordonnant l’activité motrice du système, leur coût de calcul est un inconvénient critique à leur application.Le travail présenté dans ce manuscrit vise à considérer des techniques de commande prédictive multi-objectifs pour des applications pratiques à la robotique humanoïde.Une architecture de commande est alors proposée sous la forme d’un contrôleur multi-objectif à deux niveaux, exploitant les avantages respectifs des formulations prédictive et instantanée.La contribution de ce travail prend la forme de la validation des avantages d’une telle approche dans son développement pour des défis pratiques, en simulation et implémentation temps-réel, sur les robots iCub et TORO ainsi que sur des modèles d’humain.Le coût de calcul du niveau prédictif est contenu par l’introduction de problèmes réduits, permettant la formulation avantageuse de problèmes de commande au travers de programmes en nombres entiers mixtes et de distributions séquentielles et parallèles.Malgré les approximations sur la dynamique du système au niveau prédictif, des comportements complexes émergent, exploitant des stratégies de coordination entre objectifs et contraintes conflictuels pour augmenter les performances et robustesse face à des perturbations
Rising to the challenge of motor control for systems involved in multi-objective and highly-constrained activities is a requirement to enable the emergence of efficient and robust behaviors; the elaboration of complex motor coordination strategies is critical in ensuring performance, feasibility and safety.Although multi-objective predictive approaches enable the definition of complex and constrained strategies coordinating the motor activity of the system, their computational cost is a critical drawback from practical applications.The work presented in this dissertation aims at considering multi-objective predictive control for feasible and practical applications to humanoid robotics.A control architecture is proposed to this purpose as a multi-objective, two-layered controller exploiting the respective advantages of predictive and instantaneous formulations.The contribution of this work takes the form of the validation of the benefits from such an approach in its development for practical challenges and applications, in simulation and real-time implementation, on the iCub and TORO robots and virtual human models.Computational demand of the predictive level is contained with the introduction of reduced multi-objective predictive problems, enabling computationally-favorable formulations of the control problem using mixed-integer programming and sequential and parallel distributions.Despite the resulting approximations on the dynamics of the system at the predictive level, complex behaviors are emerging, exploiting elaborate coordination strategies between conflicting objectives and constraints to increase performance and robustness against disturbances

Dans plusieurs pays européens, la capacité de l’infrastructure est complètement exploitée aux heures de pointe et aux points critiques : une grande quantité de trains traversent ces points critiques dans un laps de temps très réduit. Dans cette situation le retard d’un train provoqué par un conflit de circulation peut se propager dans tout le réseau. Le problème de la gestion opérationnelle du trafic ferroviaire consiste à trouver les modifications des itinéraires et des ordonnancements des trains qui minimisent la propagation des retards. Dans cette thèse, nous proposons une approche de décomposition de Benders pour la formulation linéaire en nombres entiers à variables mixtes utilisée dans l’algorithme RECIFE-MILP. Après avoir constaté que l’approche de décomposition standard de Benders ne permet pas de trouver rapidement une solution de bonne qualité pour certaines instances du problème, nous étudions trois approches alternatives afin d’améliorer la performance de notre algorithme. Nous proposons d’abord une approche que nous appelons la reformulation réduite de Benders. Ensuite, nous introduisons des inégalités dans la formulation du problème maître de Benders. Finalement, nous scindons le processus de résolution en trois étapes au lieu de deux comme dans la décomposition standard de Benders. L'analyse expérimentale montre que la combinaison de la première et dernière approche surpasse l’algorithme original RECIFE-MILP dans la résolution de grandes instances sous certaines conditions
In railway systems, during congested traffic situations, the infrastructure capacity is completely exploited for trains circulation. In these situations, when traffic is perturbed some trains must be stopped or slowed down for ensuring safety, and delays occur. The real-time Railway Traffic Management Problem (rtRTMP) is the problem of modifying trains route and schedule to limit delay propagation. In this thesis, we propose a Benders decomposition of a MILP-based algorithm for this problem, named RECIFE-MILP. After observing that the standard Benders decomposition (BD) does not allow the effective solution of rtRTMP instances, we study three possible approaches to improve the performance. Specifically, we first propose a modification of the problem reformulation which is typical of BD, obtaining what we call reduced BD. Then, we introduce some inequalities to the Benders master problem. Finally, we split the solution process in three steps rather than two as in the standard BD. As we show in a thorough experimental analysis, the combination of the first and last approaches outperforms the original RECIFE-MILP algorithm when tackling large instances with some specific features

Dans ce travail de thèse, nous avons étudié deux types de problèmes d'ordonnancement. La majeure partie concerne le problème d'ordonnancement de projet à moyens limités (RCPSP). Le problème d'ordonnancement des opérations de manutention dans un entrepôt de transbordement ("crossdocking") est également traité avec une moindre importance. Dans une première partie (la plus étendue), nous abordons le RCPSP. À partir de modélisations utilisant la programmation linéaire en nombres entiers, nous avons proposé deux nouvelles formulations de ce problème, utilisant des variables indicées par des événements. Dans l'une d'entre elles, on utilise une variable binaire pour marquer le début de l'exécution de chaque activité et une autre variable pour marquer sa fin. Dans la seconde proposition, une seule variable est utilisée. Elle identifie les événements après lesquels l'activité reste en cours ou débute son exécution. De façon générale, comparées à d'autres modèles de la littérature sur divers types d'instances, nos propositions affichent des résultats plus intéressants sur les instances contenant des activités aux durées disparates et associées à de longs horizons d'ordonnancement. En particulier, sur ces mêmes types d'instances mais hautement cumulatives (caractéristiques de base du RCPSP), elles sont également les plus performantes. Nous avons également abordé la résolution d'une extension du RCPSP consistant à prendre en compte des ressources particulières, qui peuvent être consommées en début d'exécution de chaque activité, mais aussi produites à leur fin : il s'agit du RCPSP avec consommation et production de ressources. Afin d'effectuer une comparaison expérimentale entre différents modèles, nous avons proposé une adaptation de nos formulations basées événements, des formulations à temps discret de Pritsker et de Christofides, et de la formulation à temps continu basée sur les flots (proposé par Artigues sur la base des travaux de Balas). Globalement, les résultats montrent que nos formulations basées événements obtiennent les meilleurs résultats sur bon nombre de types d'instances. .
In this thesis, we studied two types of scheduling problems. The major part concerns the Resource-Constrained Project Scheduling Problem (RCPSP). The scheduling problem of handling operations in a warehouse of Crossdocking is also dealt. First, from models using mixed integer linear programming, we proposed two new formulations of this problem, using variables indexed by events. In one of them, we use a binary variable to mark the beginning of the performing of each activity and another variable to mark its end. In the second proposal, a single variable is used. It identifies events in which the activity starts or continues its performing. Overall, compared to other models in the literature on various types of instances, our proposals show more interesting results on the instances with long scheduling horizons containing activities with disparate durations. In particular, on the highly cumulative instances (basic characteristics of RCPSP) of these types of instances, they are the most efficient. We also treat the resolution of the extension of the RCPSP which consists in taking into account specific resources that can be consumed during the performing of each activity, but also produced in another quantity at the end of performing of each activity: it is the RCPSP with consumption and production of resources. To make a comparison between different experimental models, we proposed an adaptation of our event-based formulations, the discrete-time formulations of Pritsker and Christofides, and the flow-based continuous-time formulation (proposed by Artigues on basis of the work of Balas). Overall, the results show that our event-based formulations are most successful on many types of instances. Second, in one less extensive part, we proposed a branch-and-bound using some cuts based on the Pareto frontier for the resolution of the scheduling problem of handling operations in a warehouse of Crossdocking. The excellent results obtained, which had strengthened our questions about the non-proved complexity of this problem, have contributed to establish later that this problem is of polynomial complexity

Le cross-docking est une stratégie utilisée pour optimiser les opérations à l’intérieur de l’entrepôtdans le cadre de l’optimisation de la chaine logistique . Comme pour les entrepôts traditionnels,les produits sont collectés depuis plusieurs origines de production tels que les fournisseurs,les usines, les fabricants, etc., par des camions, puis ils sont acheminés vers des plateformes appeléescross-docks. Arrivés au cross-dock, les produits sont d’abord déchargés sur des quais d’entréedu cross-dock. Ils sont ensuite triés selon leurs destinations et sont immédiatement transférés,à l’aide des matériels de manutention, vers des quais de sortie correspondants pour, quelquesfois être consolidés avec d’autres produits allant à la même destination et sont rechargés dansdes camions sortants. Contrairement aux entrepôts traditionnels où la durée de stockage desproduits est indéfinie, pour le cross-dock, ils sont déchargés et rechargés le même jour sans attendredans la zone de stockage temporaire, ou peuvent attendre moins d’un jour. Dans cettethèse, nous étudions le problème d’optimisation NP-difficile apparaissant dans le cross-dock appelé“Cross-dock Door Assignment Problem (CDAP)”. Le CDAP consiste à affecter des camionsentrants et sortants, respectivement aux quais d’entrée et de sortie du cross-dock. Le but estde minimiser le coût total de transport à l’intérieur du cross-dock. La formulation quadratiquestandard du CDAP inclut le problème d’affectation généralisée comme sous-problème. Dans cettethèse, nous effectuons une revue de littérature étendue du cross-docking. Nous nous concentronsensuite sur la modélisation mathématique du CDAP via une formulation quadratique standard,ainsi que sur la linéarisation standard de ce modèle. À partir de cette étude approfondie, nousproposons plusieurs nouveaux modèles linéaires non standard pour formuler le CDAP. Nous comparonsensuite ces modèles entre eux et ensuite avec les modèles récents de la littérature afinde déterminer le meilleur modèle linéaire. Nous proposons ensuite une Relaxation Lagrangiennepour produire de meilleures nouvelles bornes inférieures à la valeur de la solution optimale. LaRelaxation Lagrangienne est appliquée au modèle qui produit de meilleures bornes inférieuresde la relaxation continue. Le dual lagrangien est résolu par l’algorithme du sous-gradient. Lesexpérimentations montrent que les instances de grande taille ne peuvent pas être résolues parune méthode exacte en temps et ressources mémoires raisonnables. Nous proposons et implémentonsdonc deux heuristiques basées sur la recherche taboue probabiliste pour pouvoir traiterefficacement les instances de grande taille du CDAP. Pour évaluer l’efficacité de ces deux heuristiques,nous comparons leurs performances, d’abord entre elles, ensuite avec celles d’heuristiquesrécentes de la littérature. Les résultats obtenus montrent l’efficacité de nos méthodes sur des jeuxde données de la littérature
Cross-docking is a strategy originally introduced to optimize operations inside a warehouseas part of the optimization of the Supply Chain. Like traditional warehouses, productsare collected from numerous freight yards such that suppliers, factories, manufactures,etc., usingtrucks, and are moved towards processing centers named cross-docks. At cross-dock yard, productsfirst get unloaded on inbound dock doors. Afterwards, they are sorted according to theirdestinations and are immediately transferred, using handling devices, to appropriate outbounddock doors to be sometimes consolidated with other products of the same destination and arereloaded into shipping trucks. Unlike traditional warehouse where storage period of productsis indefinite, for cross-dock, goods are unloaded and reloaded the same day without waiting intemporary storage area or can wait less than one day. In this PhD thesis, we study an NP-hardoptimization problem raised by cross-dock referred to “Cross-dock Door Assignment Problem(CDAP)”. The CDAP consists in assignment of incoming and outgoing trucks to inbound andoutbound dock doors of cross-dock, respectively. The goal is to minimize the total transportationcost inside the cross-dock. The standard quadratic formulation of the CDAP includes theGeneralized Assignment Problem as subproblem. In this dissertation, we perform an extensivecross-docking literature review. Then, we carry out a broad analysis of the standard quadraticformulation as well as the standard linearization of the CDAP. From this in-deph study, wepropose several new non standard Mixed Integer Linear Programming models for the CDAP. Todetect the best linear model among those we propose and those existing, we compare the performanceof these models on instances proposed in the literature. We next propose a LagrangianRelaxation approach to produce the best new lower bounds to optimal solution value. This LagrangianRelaxation is applied to the model that produces the best LP relaxation bounds. TheLagrangian dual is solved using a subgradient algorithm. According to the experiments it seemsthat large-scale instances cannot be solved with an exact method in reasonable running times andmemory requirements. Thus, we propose and implement two heuristics based on “ProbabilisticTabu Search” to operate efficiently with larger instances of the CDAP. To assess the effectivenessof these proposed heuristics, we compare their performance, first between them and thenwith recent heuristics in the literature. The results demonstrate the efficiency of the proposedapproaches on data sets from the literature

De nos jours, la demande en trafic mobile a considérablement augmenté. Face à cette croissance, plusieurs propositions font l'objet d'étude pour remédier à un tel défi. L’architecture des réseaux d’accès de type Cloud (C-RAN) est l’une des propositions pour faire face à cette demande croissante, et constitue une solution candidate potentielle pour les réseaux futurs 5G. L'architecture C-RAN dissocie deux éléments principaux de la station de base: La BBU ou ``Baseband Unit", qui constitue une unité intelligente pour le traitement des données en bande de base, et le RRH ou ``Remote Radio Head", constituant en une antenne passive pour fournir l'accès aux utilisateurs (UEs). Grâce à l’architecture C-RAN, les BBUs sont centralement regroupées, alors que les RRHs sont distribués sur plusieurs sites. Plusieurs avantages sont ainsi dérivés, tels que le gain en multiplexage statistique, l’efficacité d’utilisation des ressources, et l’économie de puissance. Contrairement à l’architecture conventionnelle où chaque RRH est exclusivement associé à une BBU, dans l’architecture C-RAN, plusieurs RRHs sont regroupés en une seule BBU lorsque les conditions de charge sont faibles. Ceci présente plusieurs avantages, tel que l’amélioration en efficacité énergétique et la minimisation en consommation de puissance. Dans cette thèse, nous adressons le problème d’optimisation des associations BBU-RRH. Nous nous intéressons à l’optimisation des regroupements des RRHs aux BBUs en tenant compte de critères multiples. Plusieurs contraintes sont ainsi envisagées, tel que la réduction de la consommation d'énergie sous garantie de Qualité de Service (QoS) minimale. En outre, la prise en compte du changement du niveau d’interférence en activant/désactivant les BBUs est primordiale pour l’amélioration de l’efficacité spectrale. En plus, décider dynamiquement de la réassociation des RRHs aux BBUs sous des conditions de charges variables représente un défi, vu que les UEs connectés aux RRHs changeant leurs associations font face à des ``handovers" (HOs)
The demand on mobile traffic has been largely increasing nowadays. Facing such growth, several propositions are being studied to cope with this challenge. Cloud-Radio Access Networks Architecture (C-RAN) is one of the proposed solutions to address the increased demand, and is a potential candidate for future 5G networks. The C-RAN architecture dissociates two main elements composing the base station: The Baseband Unit (BBU), consisting in an intelligent element to perform baseband tasks functionalities, and the Remote Radio Head (RRH), that consists in a passive antenna element to provide access for serviced User Equipments (UEs). In C-RAN architecture, the BBUs migrate to a Cloud data center, while RRHs remain distributed across multiple sites. Several advantages are derived, such as statistical multiplexing gain, efficiency in resource utilization and power saving. Contrarily to conventional architecture, where each RRH is associated to one BBU, in C-RAN architecture, multiple RRHs can be embraced by one single BBU when network load conditions are low, bringing along several benefits, such as enhanced energy efficiency, and power consumption minimization. In this thesis, the BBU-RRH association optimization problem is addressed. Our aim is to optimize the BBU-RRH association schemes, taking into consideration several criteria. The problem presents many constraints: For example, achieving minimized power consumption while guaranteeing a minimum level of Quality of Service (QoS) is a challenging task. Further, taking into account the interference level variation while turning ON/OFF BBUs is paramount to achieve enhanced spectral efficiency. Moreover, deciding how to re-associate RRHs to BBUs under dynamic load conditions is also a challenge, since connected UEs face handovers (HOs) when RRHs change their associations

La planification sanitaire régionale consiste à répartir dans l'espace régional les ressources sanitaires rares (équipement lourd, personnel, ...) entre différentes structures sanitaires existantes ou non, afin d'"optimiser" la réponse aux besoins en soins de la population régionale. Cette répartition s'effectue dans un contexte décisionnel multidimensionnel, dont les dimensions médicale, économique et celles relatives à l'aménagement du territoire. Depuis une quarantaine d'années, la recherche de méthodes rationnelles applicables à la planification sanitaire a permis l'investigation de nombreuses voies de modélisation, et la proposition de méthodes variées. Malgré leur multitude, aucune d'entre elles n'a acquis de légitimité auprès des planificateurs. Trois motifs expliquent ce phénomène: le caractère restrictif de la définition donnée au système de santé, la complexité des techniques mathématiques utilisée, souvent obscures pour les non initiés, et le rôle passif réservé au planificateur. Le travail présenté dans ce mémoire propose la formalisation d'un outil interactif d'aide à la planification sanitaire. Cette formalisation s'appuie sur une approche globale du système de santé, à partir de laquelle nous avons établit une définition de la planification sanitaire. A l'issue de cette formalisation, nous proposons un outil HERO qui lie un Système d'Information Géographique (SIG) avec un outil de résolution multiobjectif. Via le SIG, l'outil informe le planificateur sur l'état de santé de la population ainsi que sur les mécanismes de production et de consommation de soins. L'outil de résolution multiobjectif assiste ce dernier dans l'élaboration d'un plan en lui fournissant un moyen d'évaluation de la pertinence de ses choix dans la répartition spatiale des ressources. Le fonctionnement de HERO est illustré sur un exemple utilisant des données du Bas-Rhin (France).

Mes travaux de recherche portent sur la théorie de la démonstration, le lambda-calcul et l'informatique théorique, dans la ligne de la correspondance de Curry-Howard entre les preuves et les programmes.

Dans ma thèse de doctorat, j'ai étudié les opérateurs de mise en mémoire pour les types de données. Ces notions, qui sont introduites par Krivine, permettent de programmer en appel par valeur tout en utilisant la stratégie de la réduction de tête pour exécuter les $\lambda$-termes. Pour cette étude, j'ai introduit avec David une extension du $\lambda$-calcul avec substitutions explicites appelée $\lambda$-calcul dirigé. Nous en avons déduit une nouvelle caractérisation des termes de mise en mémoire et obtenu des nombreux résultats très fins à leur sujet. En ce qui concerne le typage des opérateurs de mise en mémoire, Krivine a trouvé une formule du second ordre, utilisant la non-non traduction de Gödel de la logique classique dans la logique intuitionniste, qui caractérise ces opérateurs. Je me suis attaché à diverses généralisations du résultat de Krivine pour les types à quantificateur positif dans des extensions de la logique des prédicats du second ordre.

J'ai poursuivi, après ma thèse, une activité de recherche sur l'extension de la correspondance de Curry-Howard à la logique classique, au moyen des instructions de contrôle. J'ai étudié des problèmes liés aux types de données dans deux de ces systèmes : le $\lambda \mu$-calcul de Parigot et le $\lambda C$-calcul de Krivine. J'ai donné des algorithmes très simples permettant de calculer la valeur d'un entier classique dans ces deux systèmes. J'ai également caractérisé les termes dont le type est l'une des règles de l'absurde. J'ai étendu le système de Parigot pour en obtenir une version non déterministe mais où les entiers se réduisent toujours en entiers de Church. Curieusement, ce système permet de programmer la fonction ``ou parallèle''.

Je me suis intéressé aux systèmes numériques qui servent à représenter les entiers naturels au sein du $\lambda$-calcul. J'ai montré que pour un tel système, la possession d'un successeur, d'un prédécesseur et d'un test à zéro sont des propriétés indépendantes, puis qu'un système ayant ces trois fonctions possède toujours un opérateur de mise en mémoire. Dans un cadre typé, j'ai apporté une réponse négative à une conjecture de Tronci qui énonçait une réciproque du résultat précédent.

La notion de mise en mémoire ne s'applique qu'à des types de données. Une définition syntaxique a été donné par Böhm et Berarducci, et Krivine a proposé une définition sémantique de ces types. J'ai obtenu avec Farkh des résultats reliant la syntaxe et la sémantique des types de données. Nous avons proposé également des définitions des types entrée et des types sortie pour lesquelles nous avons montré diverses propriétés syntaxiques et sémantiques.

J'ai réussi à combiner la logique intuitionniste et la logique classique en une logique mixte. Dans cette logique, on distingue deux genres de variables du second ordre, suivant que l'on peut, ou non, leur appliquer le raisonnement par l'absurde. Ce cadre m'a permi de donner le type le plus général pour les opérateurs de mise en mémoire. Vu le rôle important que cette logique semble devoir jouer dans la théorie de ces opérateurs, j'en ai mené avec A. Nour une étude théorique approfondie. Le système de logique mixte propositionnelle auquelle nous avons abouti évoque les sytèmes $LC$ de Girard et $LK^{tq}$ de Danos, Joinet et Schellinx.

Je me suis intéressé avec David à l'équivalence induite par l'égalité entre les arbres de Böhm infiniment $\eta$-expansés. Avec Raffalli, je me suis également intéressé à la sémantique de la logique du second ordre.

Le problème d'allocation de postes d'amarrage (PAPA) est l'un des principaux problèmes de décision aux terminaux portuaires qui a été largement étudié. Dans des recherches antérieures, le PAPA a été reformulé comme étant un problème de partitionnement généralisé (PPG) et résolu en utilisant un solveur standard. Les affectations (colonnes) ont été générées a priori de manière statique et fournies comme entrée au modèle %d'optimisation. Cette méthode est capable de fournir une solution optimale au problème pour des instances de tailles moyennes. Cependant, son inconvénient principal est l'explosion du nombre d'affectations avec l'augmentation de la taille du problème, qui fait en sorte que le solveur d'optimisation se trouve à court de mémoire. Dans ce mémoire, nous nous intéressons aux limites de la reformulation PPG. Nous présentons un cadre de génération de colonnes où les affectations sont générées de manière dynamique pour résoudre les grandes instances du PAPA. Nous proposons un algorithme de génération de colonnes qui peut être facilement adapté pour résoudre toutes les variantes du PAPA en se basant sur différents attributs spatiaux et temporels. Nous avons testé notre méthode sur un modèle d'allocation dans lequel les postes d'amarrage sont considérés discrets, l'arrivée des navires est dynamique et finalement les temps de manutention dépendent des postes d'amarrage où les bateaux vont être amarrés. Les résultats expérimentaux des tests sur un ensemble d'instances artificielles indiquent que la méthode proposée permet de fournir une solution optimale ou proche de l'optimalité même pour des problème de très grandes tailles en seulement quelques minutes.
The berth allocation problem (BAP) is one of the key decision problems at port terminals and it has been widely studied. In previous research, the BAP has been formulated as a generalized set partitioning problem (GSPP) and solved using standard solver. The assignments (columns) were generated a priori in a static manner and provided as an input to the optimization model. The GSPP approach is able to solve to optimality relatively large size problems. However, a main drawback of this approach is the explosion in the number of feasible assignments of vessels with increase in problem size which leads in turn to the optimization solver to run out of memory. In this research, we address the limitation of the GSPP approach and present a column generation framework where assignments are generated dynamically to solve large problem instances of the berth allocation problem at port terminals. We propose a column generation based algorithm to address the problem that can be easily adapted to solve any variant of the BAP based on different spatial and temporal attributes. We test and validate the proposed approach on a discrete berth allocation model with dynamic vessel arrivals and berth dependent handling times. Computational experiments on a set of artificial instances indicate that the proposed methodology can solve even very large problem sizes to optimality or near optimality in computational time of only a few minutes.