Cette thèse, fruit d'un contrat de recherche avec Générale des Eaux,<br />porte sur le problème de tournées de service multi-périodes avec fenêtres de temps et flotte limitée. Nous proposons plusieurs méthodes de résolution approchées, ainsi qu'une méthode optimale. La méthode optimale est basée sur la génération de colonnes. Une des méthodes approchées est un algorithme mémétique basé sur une heuristique également développée dans cette thèse. Enfin, la méthode optimale est dérivée en méthode approchée par l'utilisation d'une heuristique pour la résolution du sous-problème.<br />Les algorithmes proposés permettent d'apporter des solutions efficaces à des problèmes comportant jusqu'à 300 clients, dans des temps variant de quelques secondes à quelques dizaines de minutes. Dans un second temps, nous appliquons ces méthodes à des scénarios issus de problématiques réelles, dans une logique d'aide à la décision.

Cette thèse est une illustration de problèmes de Recherche Opérationnelle abordés dans le contexte hospitalier du CHRU de Tours. La problématique considérée relève des transports et plus exactement de tournées de véhicules. Cette thèse s'articule autour de l'étude de deux principaux problèmes : le transport de flux de produits et le transport de flux de patients. Le premier problème de tournées de véhicules concerne toute la gestion des différents types de flux logistiques (logistique hôtelière, pharmacie, lingerie, plateaux repas, etc.) à livrer ou à collecter dans les services de soins de chaque hôpital du CHRU de Tours. Le deuxième problème concerne les transports de patients aussi bien urgents (SAMU) que planifiés (Centrale des ambulanciers). Pour résoudre ces problèmes, plusieurs méthodes s'inspirant des techniques de la RO sont proposées : des méthodes exactes (programmation linéaire en nombres entiers), des heuristiques (algorithme glouton, recherche tabou avec et sans mémoire adaptative, algorithme génétique, algorithme mémétique) et des moteurs de simulation à événements discrets ont été développés. Des expérimentations numériques valident l'interêt et la qualité des méthodes développées.

Nous étudions quatre problèmes d'ordonnancement sur machines parallèles. Ces quatre problèmes diffèrent par le critère que l'on cherche à minimiser : la somme des dates de fin, la somme pondérée des dates de fin, le retard total ou le retard total pondéré. Les jobs à ordonnancer sout soumis à des dates de disponibilité. Nous avons proposé pour ces quatres problèmes plusieurs règles de dominance. Une étude des bornes<br />inférieures a également été réalisée. Enfin, nous avons proposé une méthode de résolution exacte utilisant les règles de dominance ainsi que les bornes inférieures.

La conception d'architectures opérationnelles d'un système de contrôle-commande est une phase très importante lors de la conception de systèmes de production d'énergie. Cette phase consiste à projeter l'architecture fonctionnelle sur l'architecture organique tout en respectant des contraintes de capacité et de sûreté, c'est-à-dire à allouer les fonctions de commande à un ensemble de contrôleurs tout en respectant ces contraintes. Les travaux présentés dans cette thèse proposent : i)une formalisation des données et contraintes du problème d'allocation de fonctions - ii)une méthode d'allocation, par recherche d'atteignabilité, basée sur un mécanisme d'appel/réponse dans un réseau d'automates communicants à variables entières - iii)la comparaison de cette méthode à une méthode de résolution par programmation linéaire en nombres entiers. Les résultats de ces travaux ont été validés sur des exemples de taille réelle et ouvrent la voie à des couplages entre recherche d'atteignabilité et programmation linéaire en nombres entiers pour la résolution de problèmes de satisfaction de systèmes de contraintes non linéaires.

Nous nous sommes intéressés à un problème d'optimisation sur des graphes (le Vertex Cover) dans un contexte de traitement bien particulier : celui des grandes instances de données. Nous avons défini pour cela un modèle de traitement basé sur des contraintes liées principalement à la quantité de mémoire limitée, modèle qui reprenait des propriétés issues de plusieurs modèles existants dans la littérature (online, streaming...). Nous avons étudié plusieurs algorithmes adaptés à ce modèle : nous avons analysé, tout d'abord de façon théorique, la qualité de leurs solutions ainsi que leurs complexités (en pire cas et en moyenne). Nous avons ensuite mené une étude expérimentale sur de très gros graphes.

La planification tactique consiste à élaborer des plans de production afin de répondre au mieux à la demande, à un moindre coût. Traditionnellement, cette planification est divisée en trois plans principaux : le Plan Industriel et Commercial (PIC), le Plan Directeur de Production (PDP) et le Calcul des Besoins Net (CBN). Pour élaborer ces différents plans, des modèles mathématiques dits de " lot-sizing " ont été développés. Cependant, les mécanismes de fusion/acquisition entre entreprises ont considérablement complexifié cette planification en y intégrant les aspects multi-site inhérents au concept de chaîne logistique et il n'existe pas, à notre connaissance, de modèle du domaine et de modèle mathématique de référence pour cette problématique. Dans cette thèse, nous proposons un modèle générique de connaissance pour la planification multi-site à partir duquel un modèle mathématique générique peut être obtenu. Ce dernier permet, par instanciation, de retrouver les principaux modèles de la littérature. Nous proposons également des méthodes d'optimisation efficaces pour l'élaboration des plans de production (PIC, PDP et CBN) dans un contexte mono et multi-site : - Nous nous intéressons à l'obtention du PIC et du PDP dans un contexte mono-site au travers de la résolution du Capacitated Lot Sizing Problem (CLSP) grâce à des métaheuristiques et des bornes inférieures. Par cette technique, nous améliorons des résultats de la littérature. - Nous proposons un modèle mathématique pour la planification d'une chaîne logistique de type " flowshop hybride " obtenu par instanciation du modèle mathématique générique ainsi qu'une méthode d'optimisation efficace pour déterminer les PDPs et CBNs pour cette chaîne logistique. Nous abordons ensuite les problèmes de faisabilité des plans de production ainsi déterminés au niveau opérationnel en utilisant différents couplages entre modèles mathématiques ou modèles de simulation, ce qui permet d'assurer la synchronisation verticale des plans. Enfin, dans le cadre d'un contrat industriel, nous nous intéressons à la mise en place d'une politique de gestion de stock à demande différenciée. Après avoir étudié la faisabilité d'une telle mise en oeuvre dans un contexte industriel, nous avons conçu les algorithmes et développé l'application permettant de calculer les seuils de rationnement de chaque client afin de mener un test grandeur nature de cette politique.

L'Ingénierie des Systèmes (IS) est une approche pluridisciplinaire et collaborative pour mener à bâtir et structurer la conception puis la réalisation et le développement de systèmes complexes. L’IS repose à la fois sur une approche processus et sur la mise en oeuvre de modèles de systèmes s'appuyant de fait dans un contexte basé ou dirigé par des modèles. On parle alors d’Ingénierie Système Basée sur des Modèles (ISBM ou Model based Systems Engineering MBSE). L’ISBM introduit des concepts, méthodes et techniques pour construire et gérer des modèles. Elle a pour objectif l’atteinte et l’amélioration de leur qualité afin de procurer aux parties prenantes un degré de confiance jugé suffisant pour aider la prise des décisions de conception, d'amélioration et de réalisation. Ces décisions conditionnent le fonctionnement, la sûreté, la sécurité, les coûts, et plus généralement tout un ensemble de propriétés attendues à la fois du modèle comme du système modélisé, tout au long de la phase aval de l’ingénierie et de développement, jusqu’à la réalisation et au déploiement du système. La qualité des modèles est obtenue au travers des processus de Vérification et Validation (V&V). Les objectifs sont alors d’assurer que les modèles soient cohérents, bien formés, bien construits et représentés correctement. En effet, aux yeux des parties prenantes, les modèles doivent être fiables, fidèles et pertinents au regard des besoins des concepteurs, représentant aussi précisément que possible le point de vue du système en cours de conception. Des langages de modélisation dit « métier » (Domain Specific Modelling Languages ou DSML) sont spécifiquement créés pour pouvoir fournir des représentations i.e. des modèles dans les différents points de vue sur le système. Un DSML est basé sur une syntaxe et sur une sémantique. La sémantique de ces langages est en général fournie par des approches externes (vérificateurs de modèles). Ces dernières sont, à notre sens, une limitation clé pour le déploiement des stratégies de V&V dans le contexte de l’ISBM. En réponse à cette limitation, la contribution conceptuelle de cette thèse est présentée sous la forme d’un nouveau langage de métamodélisation, nommé xviCore (noyau exécutable, vérifiable et interopérable). xviCore fournit les concepts et les principes pour définir puis vérifier et valdier la syntaxe et la sémantique en phase de construction de tels DSML en combinant trois métalangages : un métalangage orienté objet pour la conception de la partie syntaxique, un métalangage pour la conception du comportement et un métalangage pour la conception de propriétés formelles. La contribution méthodologique de ces travaux permet ensuite le déploiement d’une stratégie de V&V «directe» en lieu et place des traditionnelles approches externes. Elle est basée sur la simulation et la preuve formelle de propriétés. Le mécanisme de simulation permet d’observer le comportement des modèles de systèmes au travers de leur exécution, tandis que le mécanisme de preuve permet de spécifier et ensuite de vérifier des propriétés formelles. La contribution technique se compose d’un ensemble des plugins Eclipse qui implémentent le métalangage xviCore, le mécanisme de simulation et le mécanisme de la preuve formelle. / Systems Engineering (SE) is an interdisciplinary and collaborative approach for successful design and management of large scale complex systems. Among other principles, SE promotes and mandates a model-based (or model-driven) approach for all stages of system design processes, denoted Model-Based Systems Engineering (MBSE). This implies concepts, techniques and tools for creating and managing various systems models for the purpose of stakeholders, and for reaching and improving the quality of models helping then stakeholders during decision-making processes, to make decisions faster and efficiently with enough confidence. Indeed, these decisions impact all along the downstream phases of system engineering and development until the realization and deployment of the real system, its functioning, safety, security, induced costs and so on. In this work, a particular attention is given to model verification and validation (V&V). The goals are to assure prior to decision-making processes, first, that models are coherent, well-formed and correctly build and represented, and second, that they are trustworthy and relevant, representing as accurately as possible the viewpoints of a system under design as expected by stakeholders.Such models provide stakeholders with confidence and trust, aiding them in making, but also in arguing decisions. Models are created by using modeling languages that are specifically tailored for a given viewpoint of a system, denoted Domain Specific Modeling Languages (DSMLs).The basic principles on which a DSML is based are its syntax and its semantics, but current DSMLs have been more studied from the syntactical point than from the semantical one that is often neglected or, when needed, provided by means of translating the DSML into third party formalisms. This is the key limitation preventing the deployment of a successful V&V strategy in MBSE context. To overcome this shortcoming, this thesis proposes first a conceptual contribution consisting of a new metamodeling language, called eXecutable, Verifiable and Interoperable Core (xviCore), allowing stakeholders to build DSMLs (called xviDSMLs), that along with their syntax also integrates semantics. Our solution combines, three meta-languages, an object-oriented metamodeling language for the specification of the syntactical part with a formal behavioral modeling language and a property modeling language for the semantical part. The methodological contribution of this work allows the deployment of successful V&V strategies allowing for direct (without transformation) model verification by simulation and properties proof. We propose a mechanism to simulate the expected behavior of a SoI through model execution based on the blackboard-based communication model, and a mechanism for specification and verification of formal properties. The technical contribution consists of an Eclipse-EMF deployable plug-in that implements the metamodeling language xviCore and the mechanisms for simulation and formal property verification.

La programmation orientée langage (Language-Oriented Programming – LOP) préconise l’utilisation de langages de modélisation dédiés exécutables (eXecutable Domain-Specific Modeling Languages – xDSMLs) pour la conception, le développement, la vérification et la validation de systèmes hautement concurrents. De tels systèmes placent l’expression de la concurrence dans les langages informatiques au coeur du processus d’ingénierie logicielle, par exemple à l’aide de formalismes dédiés appelés modèles de concurrence (Models of Concurrency – MoCs). Ceux-ci permettent une analyse poussée du comportement des systèmes durant les phases de vérification et de validation, mais demeurent complexes à comprendre, utiliser, et maîtriser. Dans cette thèse, nous développons et étendons une approche qui vise à faire collaborer l’approche LOP et les MoCs à travers le développement de xDSMLs dans lesquels la concurrence est spécifiée de façon explicite (Concurrency-aware xDSMLs). Dans de tels langages, on spécifie l’utilisation systématique d’un MoC au niveau de la sémantique d’exécution du langage, facilitant l’expérience pour l’utilisateur final qui n’a alors pas besoin d’appréhender et de maîtriser l’utilisation du MoC choisi.Un tel langage peut être raffiné lors de la phase de déploiement, pour s’adapter à la plateforme utilisée, et les systèmes décrits peuvent être analysés sur la base du MoC utilisé. / Language-Oriented Programming (LOP) advocates designing eXecutable Domain-Specific Modeling Languages (xDSMLs) to facilitate the design, development, verification and validation of modern softwareintensive and highly-concurrent systems. These systems place their needs of rich concurrency constructs at the heart of modern software engineering processes. To ease theirdevelopment, theoretical computer science has studied the use of dedicated paradigms for the specification of concurrent systems, called Models of Concurrency (MoCs). They enable the use of concurrencyaware analyses such as detecting deadlocks or starvation situations, but are complex to understand and master. In this thesis, we develop and extend an approach that aims at reconciling LOP and MoCs by designing so-called Concurrencyaware xDSMLs. In these languages, the systematic use of a MoC is specified at the language level, removing from the end-user the burden of understanding or using MoCs. It also allows the refinement of the language for specific execution platforms, and enables the use of concurrency-aware analyses on the systems.

En réponse aux contraintes économiques, au problème du vieillissement de la population et aussi à la volonté des patients de se faire soigner dans le milieu familial, l’Hospitalisation À Domicile (HAD) prend de plus en plus d’ampleur. Dans ce travail de recherche, nous nous intéressons aux établissements d’hospitalisation à domicile, parmi les différentes problématiques qui existent dans ce domaine, nous étudions le problème de routage et de planification des personnels.Nous développons tout d’abord un modèle de programmation linéaire en nombres entiers qui permet de formuler clairement les contraintes du problème.Nous présentons par la suite, une matheuristique permettant de résoudre le problème défini sur une journée de planification. Nous développons également une variante de notre matheuristique sur un horizon de 14 jours. Cette dernière prend en considération plusieurs contraintes en plus de celles considérées pour la planification sur une journée. Enfin, nous introduisons un problème de réoptimisation de routage et de la planification des personnels pour l’hospitalisation à domicile et présentons quelques approches de résolutions. Ces différentes méthodes combinent des heuristiques, la programmation dynamique et la programmation mathématique. / Home health care (HHC), i.e., visiting and nursing patients athome, is a growing sector in the medical care system. There fore, the optimal scheduling of the health care staffs arises. The objective of this problem consists in constructing routes and rosters for the staffs while optimizing costs. We propose an integer linear programming formulation (ILP) that clearly formulate the constraints of the problem. We present a matheuristic to solve the daily routing and rostering problem. We also develop a variant of our matheuristic defined for a period of 14 days. It takes into account several constraints in addition to those considered in the daily planning. Finally, we introduce the problem of reoptimizing the routing and rostering staffs and we give some ideas to solve this problem. These methods combine heuristic algorithms, dynamic programming and mathematical programming.

L’alignement stratégique du système d’information est une problématique récurrente en entreprise, de nombreux projets opérations à dimension système d’information ne permettant pas d’obtenir les gains attendus par les Directions Générales. Face à ces nombreux constats d’échecs, plusieurs variables explicatives peuvent être invoquées. Cette recherche vise à en tester une, celle du mépris des faisabilités opérationnelles. Le terme de mépris a été choisi à dessein afin d’insister sur la dimension « incarnée » de la manoeuvre d’alignement, et notamment des « conditions que l’on puisse faire » qui sont exprimées par les différentes parties prenantes. Fondée sur une double définition du mépris interrogeant le thème de la « prise » comme de la « mé-prise », les résultats obtenus dans le cadre de cette recherche exploratoire font du mépris des faisabilités opérationnelles un objet en sciences de gestion et montrent que le mépris des faisabilités opérationnelles peut être l’une des variables explicatives du désalignement stratégique. / Information system alignment is a vital subject in companies as many IT projects fail to achieve the benefits expected by top management. To explain this statement, many variables can be put forward. We decided to focus our study on one of those potential explanatory reasons which is “contempt for operational feasibilities”. The “contempt” expression has been precisely chosen to underline the embodied dimension of strategic alignment, and, in particular, “the underpinning conditions under which one can realize” as expressed by project stakeholders. Based on a twofold definition of contempt questioning the action of “taking” and “mis-taking” operational feasibilities, the results collected during this exploratory research highlight the relevance of placing this subject in the field of management and show how contempt for operational feasibilities can have proven effects on information system misalignment.