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.

Cette thèse présente une étude des systèmes dynamiques polynomiaux motivée à la fois par le grand spectre d'applications de cette classe (modèles de réactions chimiques, modèles de circuits électriques ainsi que les modèles biologiques) et par la difficulté (voire incapacité) de la résolution théorique de tels systèmes. Dans une première partie préliminaire, nous présentons les polynômes multivariés et nous introduisons les notions de forme polaire d'un polynôme (floraison) et de polynômes de Bernstein qui seront d'un grand intérêt par la suite. Dans une deuxième partie, nous considérons le problème d'optimisation polynomial dit POP. Nous décrivons dans un premier temps les principales méthodes existantes permettant de résoudre ou d'approcher la solution d'un tel problème. Puis, nous présentons deux relaxations linéaires se basant respectivement sur le principe de floraison ainsi que les polynômes de Bernstein permettant d'approcher la valeur optimale du POP. La dernière partie de la thèse sera consacrée aux applications de nos deux méthodes de relaxation dans le cadre des systèmes dynamiques polynomiaux. Une première application s'inscrit dans le cadre de l'analyse d'atteignabilité : en effet, on utilisera notre relaxation de Bernstein pour pouvoir construire un algorithme permettant d'approximer les ensembles atteignables d'un système dynamique polynomial discrétisé. Une deuxième application sera la vérification et le calcul d'invariants pour un système dynamique polynomial. Une troisième application consiste à calculer un contrôleur et un invariant pour un système dynamique polynomial soumis à des perturbations. Dans le contexte de l'invariance, on utilisera la relaxation se basant sur le principe de floraison. Enfin, une dernière application sera d'exploiter les principales propriétés de la forme polaire pour pouvoir étudier des systèmes dynamiques polynomiaux dans des rectangles.

L'optimisation multi-objectif concerne la résolution de problèmes pour lesquels plusieurs objectifs (ou critères) contradictoires sont pris en compte. Contrairement aux problèmes d'optimisation ayant un seul objectif, un problème multi-objectif ne possède pas une valeur optimale unique mais plutôt un ensemble de points appelés "ensemble non dominé". Les bornes inférieures et supérieures d'un problème multi-objectif peuvent être également décrites par des ensembles. Dans la pratique, les variables utilisées en optimisation multiobjectif représentent souvent des objets non fractionnables et on parle alors de problèmes multi-objectif en nombres entiers. Afin d'obtenir de meilleures bornes qui peuvent être utilisées dans la conception de méthodes exactes, certains problèmes sont formulés avec un nombre exponentiel de variables de décision et ces problèmes sont résolus par la méthode de génération de colonnes. Les travaux de cette thèse visent à contribuer à l'étude de l'utilisation de la génération de colonnes en programmation linéaires en nombres entiers multi-objectif. Pour cela nous étudions un problème de tournées de véhicules bi-objectif qui peut être considéré comme une généralisation de plusieurs autres problèmes de tournées de véhicules. Nous proposons des formulations mathématiques pour ce problème et des techniques pour accélérer le calcul des bornes inférieures par génération de colonnes. Les sous-problèmes qui doivent être résolus pour le calcul des bornes inférieures ont une structure similaire. Nous exploitons cette caractéristique pour traiter simultanément certains sous-problèmes plutôt qu'indépendamment.

La planification et la gestion optimale des ressources humaines jouent un rôle important dans la productivité et la compétitivité des entreprises. Dans cette thèse nous nous intéressons à la modélisation et à la résolution de différents problèmes d'optimisation soulevés par la construction de plannings pour les agents qui travaillent dans un contexte aéronautique : la création de vacations, la création de rotation, l'affectation de vacations et de rotations. Pour le problème de construction de vacations, nous proposons une approche de modélisation basée sur le concept de plage horaire et ensuite une méthode heuristique de résolution basée sur l'algorithme FFD (First Fit Decreasing) et sur la génération de colonnes. Le problème de création de rotations est résolu par une méthode de programmation linéaire en variables mixtes. Les problèmes d'affectation de vacations et de rotations sont modélisés comme des problèmes de multi-affectation généralisé. Nous proposons une décomposition temporelle et par qualification et ensuite une transformation du problème d'affectation généralisé en un problème d'affectation simple par relaxation Lagrangienne. Un algorithme ad-hoc est utilisé pour la résolution de chaque problème de base. La plupart des algorithmes élaborés ont été couplés à des bases de données réelles et commercialisés par la société IFR-France.

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 mon trent que nos formulations basées événements obtiennent les meilleurs résultats sur bon nombre de types d'instances. Dans la seconde partie (plus réduite), nous avons également proposé un branch-and-bound utilisant des coupes basées sur la frontière de Pareto, pour la résolution du problème d'ordonnancement des opérations de manutention au sein d'un entrepôt de transbordement ("crossdocking"). Les excellents résultats obtenus ont renforcé nos interrogations sur la complexité non-prouvée de ce problème, et ont permis d'établir par la suite que le problème est de complexité polynomiale.

La recherche d'une conduite globale de la chaîne logistique cohérente avec les décisions de gestion locales à chaque partenaire nous amène à proposer trois architectures de conduite combinant, à différents degrés, approche hiérarchisée et approche distribuée. Ces architectures sont analysées dans leurs performances de manière comparative, à partir d'une planification traitant conjointement le problème de production, stockage et transport des matières dans les organisations distribuées, et s'appuyant sur un modèle analytique générique. Le problème de gestion de la capacité de production d'un partenaire participant à plusieurs chaînes logistiques fait l'objet d'une étude particulière.

Ce travail s'intéresse à la planification tactique de chaînes logistiques dans un environnement incertain et perturbé. Dans le cadre de relations "point-à point", nous proposons une approche permettant d'élaborer une planification tactique optimale et réactive d'un maillon d'une chaîne logistique en présence de paramètres incertains et de perturbations. Notre approche se fonde sur une structure à deux niveaux décisionnels. Le premier niveau effectue une planification agrégée en minimisant le coût global de production. Il établit ensuite "un plan de guidage" qui est transmis au niveau détaillé. Ce dernier effectue sa planification en suivant "au mieux" le plan de guidage et en prenant en compte les contraintes et données détaillées ignorées au niveau supérieur. Le niveau détaillé adopte un processus dynamique de planification à horizon glissant. Il réactualise ses données à chaque étape de planification afin d'assurer la réactivité du processus décisionnel. Nous caractérisons explicitement l'inertie du système décisionnel en distinguant deux phases : la phase d'anticipation et la phase de réalisation. Chaque phase est caractérisée par un délai temporel. Ainsi, nous proposons une modélisation originale du processus décisionnel de chaque décision via trois variables. Le niveau détaillé est formulé selon un programme linéaire. Au niveau agrégé, nous proposons un modèle global ayant l'originalité de prendre en compte les spécificités du processus décisionnel détaillé. Le couplage entre les deux niveaux est assuré par le plan de guidage. Selon les informations incluses dans le plan de guidage, le niveau agrégé accorde un certain degré d'autonomie au niveau détaillé, ceci conditionne la réactivité et la robustesse de la planification. Dans notre travail, nous considérons trois types de guidage : deux guidages budgétaires "globaux" et un guidage "prescriptif" par la sous-traitance agrégée. Notre approche est évaluée par simulation dans le cadre d'une demande incertaine. Pour cela, nous développons deux outils de simulation et un ensemble d'indicateurs de performances. Les expérimentations réalisées confirment la performance de notre approche par rapport à des approches classiques et mettent en évidence l'influence du type de guidage et du profil de la demande détaillée sur la réactivité et la robustesse des solutions trouvées.

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

Les réseaux maillés sans fil sont une solution efficace, de plus en plus mise en œuvre en tant qu'infrastructure, pour interconnecter les stations d'accès des réseaux radio. Ces réseaux doivent absorber une croissance très forte du trafic généré par les terminaux de nouvelle génération. Cependant, l'augmentation du prix de l'énergie, ainsi que les préoccupations écologiques et sanitaires, poussent à s'intéresser à la minimisation de la consommation énergétique de ces réseaux. Ces travaux de thèse s'inscrivent dans les problématiques d'optimisation de la capacité et de la minimisation de la consommation énergétique globale des réseaux radio maillés. Nous définissons la capacité d'un réseau comme la quantité de trafic que le réseau peut supporter par unité de temps. Ces travaux s'articulent autour de quatre axes. Tout d'abord, nous abordons le problème d'amélioration de la capacité des réseaux radio maillés de type WIFI où l'accès au médium radio se base sur le protocole d'accès CSMA/CA. Nous mettons en lumière, les facteurs déterminants qui impactent la capacité du réseau, et l'existence d'un goulot d'étranglement qui limite cette capacité du réseau. Ensuite, nous proposons une architecture de communication basée sur l'utilisation conjointe de CSMA/CA et de TDMA afin de résoudre ce problème de goulot d'étranglement. Dans la deuxième partie de cette thèse, nous nous intéressons aux réseaux maillés sans fil basés sur un partage des ressources temps-fréquence. Afin de calculer des bornes théoriques sur les performances du réseau, nous développons des modèles d'optimisation basés sur la programmation linéaire et la technique de génération de colonnes. Ces modèles d'optimisation intègrent un modèle d'interférence SINR avec contrôle de puissance continue et variation de taux de transmission. Ils permettent, en particulier, de calculer une configuration optimale du réseau qui maximise la capacité ou minimise la consommation d'énergie. Ensuite, dans le troisième axe de recherche, nous étudions en détail le compromis entre la capacité du réseau et la consommation énergétique. Nous mettons en évidence plusieurs résultats d'ingénierie nécessaires pour un fonctionnement optimal d'un réseau maillé sans fil. Enfin, nous nous focalisons sur les réseaux cellulaires hétérogènes. Nous proposons des outils d'optimisation calculant une configuration optimale des stations de base qui maximise la capacité du réseau avec une consommation efficace d'énergie. Ensuite, afin d'économiser l'énergie, nous proposons une heuristique calculant un ordonnancement des stations et leur mise en mode d'endormissement partiel selon deux stratégies différentes, nommées LAFS et MAFS.

Alors que les préoccupations concernant le réchauffement climatique deviennent de plus en plus sérieuses, l'une de ses premières causes: la consommation d'électricité, continue à croître. Une des manières d'endiguer le phénomène pourrait être de mieux équilibrer la consommation et la production, afin d'allumer moins de gros groupes de production, et de permettre l'intégration de plus de sources renouvelables. Le nouveau paradigme du marché de l'électricité incite les consommateurs à réduire leur pic de consommation, et à différer leur consommation quand la demande est moindre, à l'aide d'incitations tarifaires. De nouveaux algorithmes d'optimisation, et de nouvelles méthodologies sont donc nécessaires pour optimiser la puissance d'électrique utilisée par les consommateurs. Schneider Electric propose, à travers le projet européen Arrowhead, d'étudier trois cas applicatifs : un ascenseur avec plusieurs sources énergétiques, une usine manufacturière et un réseau d'eau potable. Pour chacune de ces trois applications, une méthodologie pour optimiser les pics de puissance consommée (parfois à l'aide d'une fonction de coût de l'électricité) est donnée, ainsi que des algorithmes d'optimisation. Dans le cas de l'ascenseur multi-sources, deux contrôleurs couplés sont proposés : l'un au niveau stratégique résolvant un problème linéaire, et l'autre à base de règles au niveau tactique. Dans le cas de l'usine, la méthodologie que nous avons utilisée pour faire des mesures, construire des modèles énergétiques, et finalement optimiser est expliquée. De plus, trois formulations linéaires, ainsi qu'une procédure de recherche locale, et une formulation naïve de programmation par contraintes sont données afin de résoudre le problème d'ordonnancement NP-difficile. Dans le cas du réseau d'eau, une formulation à contraintes quadratiques est utilisée pour comparer des plans de pompage optimisés avec la tactique utilisée habituellement dans le réseau. Les méthodes proposées entraînent des gains sur la facture énergétique de 1.5% à 114%, dépendamment du contexte. De plus, elles permettent aux consommateurs de participer au nouveau marché de l'énergie. Finalement, les connaissances retirées de l'étude de ces trois pilotes sont résumées, et des lignes directrices sont données pour l'optimisation de la facture énergétique d'un système quelconque consommant de l'énergie. / While concerns about global warming have never been so important, one of its first causes: global electricity consumption, is still growing. One way to stem the phenomenon could be to better balance demand and production, in order to switch on less big production groups and to allow the integration of more renewable production sources. The new paradigm of electricity market incites customers to reduce their electricity consumption peak and to shift their consumption when the demand is lower, by introducing economical incentives. Thus, new optimization algorithms and methodologies are needed at the customers side to optimize power usage over time. Schneider Electric proposes, through the Arrowhead European project, to study three application use-cases: an elevator with multiple electricity sources, a manufac- turing plant, and a drinking water network. For each of these use-cases, a methodology to optimize power consumption peaks (sometimes through an electricity cost function) is given, as well as optimization algorithms. For the multisource elevator case, two coupled controllers are proposed: one at the strategic level solving a linear problem, the other one rule-based at the tactical level. For the manufacturing plant, the methodology we used to monitor, build energy models, and finally optimize is explained. Furthermore, three linear formulations are given, as well as a simple local search procedure and a naive constraint satisfaction formulation to handle the NP-hard scheduling problem. For the water network use-case, a quadratically constrained formulation is used to compare optimized pumping plans with the Business As Usual tactic. The methods proposed bring between 1.5% to 114% savings on the energy bill, depending on the context. Moreover, they allow electricity consumers to participate in the demand-response market. Finally, the knowledge extracted from our three use-cases is summarized, and guide- lines are given to optimize the electricity bill of any electricity consumer system.