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.

Un système de systèmes est un système dont les composants sont eux-mêmes des systèmes indépendants, tous communiquant pour atteindre un objectif commun. Lorsque ces systèmes sont mobiles, il peut être difficile d'établir des connexions de bout-en-bout. L'architecture mise en place dans de telles situations est appelée réseau tolérant aux délais. Les données sont transmises d'un système à l'autre – selon les opportunités de communication, appelées contacts, qui apparaissent lorsque deux systèmes sont proches – et disséminées dans l'ensemble du réseau avec l'espoir que chaque message atteigne sa destination. Si une donnée est trop volumineuse, elle est découpée. Chaque fragment est alors transmis séparément.Nous supposons ici que la séquence des contacts est connue. On s'intéresse donc à des applications où la mobilité des systèmes est prédictible (les réseaux de satellites par exemple). Nous cherchons à exploiter cette connaissance pour acheminer efficacement des informations depuis leurs sources jusqu'à leurs destinataires. Nous devons répondre à la question : « Quels éléments de données doivent être transférés lors de chaque contact pour minimiser le temps de dissémination » ?Nous formalisons tout d'abord ce problème, appelé problème de dissémination, et montrons qu'il est NP-difficile au sens fort. Nous proposons ensuite des algorithmes pour le résoudre. Ces derniers reposent sur des règles de dominance, des procédures de prétraitement, la programmation linéaire en nombres entiers, et la programmation par contraintes. Une partie est dédiée à la recherche de solutions robustes. Enfin, nous rapportons des résultats numériques montrant l'efficacité de nos algorithmes. / Systems of systems are supersystems comprising elements which are themselves independent operational systems, all interacting to achieve a common goal. When the subsystems are mobile, these may suffer from a lack of continuous end-to-end connectivity. To address the technical issues in such networks, the common approach is termed delay-tolerant networking. Routing relies on a store-forward mechanism. Data are sent from one system to another – depending on the communication opportunities, termed contacts, that arise when two systems are close – and stored throughout the network in hope that all messages will reach their destination. If data are too large, these must be split. Each fragment is then transmitted separately.In this work, we assume that the sequence of contacts is known. Thus, we focus on applications where it is possible to make realistic predictions about system mobility (e.g. satellite networks). We study the problem of making the best use of knowledge about possibilities for communication when data need to be routed from a set of systems to another within a given time horizon. The fundamental question is: "Which elements of the information should be transferred during each contact so that the dissemination length is minimized"?We first formalize the so-called dissemination problem, and prove this is strongly NP-Hard. We then propose algorithms to solve it. These relies on different dominance rules, preprocessing procedures, integer-linear programming, and constraint programming. A chapter is dedicated to the search for robust solutions. Finally experimental results are reported to show the efficiency of our algorithms in practice.

Dans le cadre de cette thèse, nous traitons le problème de flow-shop à deux machines avec temps de transport où l’objectif consiste à minimiser le temps de complétion maximal. Dans un premier temps, nous nous sommes intéressés à la modélisation de ce problème. Nous avons proposé plusieurs programmes linéaires en nombres entiers. En particulier, nous avons introduit une formulation linéaire basée sur une généralisation non triviale du modèle d’affectation pour le cas où les durées des opérations sur une même machine sont identiques. Dans un deuxième temps, nous avons élargi la portée de ces formulations mathématiques pour développer plusieurs bornes inférieures et un algorithme exact basé sur la méthode de coupe et branchement (Branch-and-Cut). En effet, un ensemble d’inégalités valides a été considéré afin d’améliorer la relaxation linéaire de ces programmes et d’accélérer leur convergence. Ces inégalités sont basées sur la proposition de nouvelles règles de dominance et l’identification de sous-instances faciles à résoudre. L’identification de ces sous-instances revient à déterminer les cliques maximales dans un graphe d’intervalles. En plus des inégalités valides, la méthode exacte proposée inclut la considération d’une méthode heuristique et d’une procédure visant à élaguer les nœuds. Enfin, nous avons proposé un algorithme par séparation et évaluation (Branch-and-Bound) pour lequel, nous avons introduit des règles de dominance et une méthode heuristique basée sur la recherche locale. Nos expérimentations montrent l’efficacité de nos approches qui dominent celles de la littérature. Ces expérimentations ont été conduites sur plusieurs classes d’instances qui incluent celles de la littérature, ainsi que des nouvelles classes d’instances où les algorithmes de la littérature se sont montrés peu efficaces. / In this thesis, we study the two-machine flow-shop problem with time delays in order to minimize the makespan. First, we propose a set of Mixed Integer Programming (MIP) formulations for the problem. In particular, we introduce a new compact mathematical formulation for the case where operations are identical per machine. The proposed mathematical formulations are then used to develop lower bounds and a branch-and-cut method. A set of valid inequalities is proposed in order to improve the linear relaxation of the MIPs. These inequalities are based on proposing new dominance rules and computing optimal solutions of polynomial-time-solvable sub-instances. These sub-instances are extracted by computing all maximal cliques on a particular Interval graph. In addition to the valid inequalities, the branch-and-cut method includes the consideration of a heuristic method and a node pruning procedure. Finally, we propose a branch-and-bound method. For which, we introduce a local search-based heuristic and dominance rules. Experiments were conducted on a variety of classes of instances including both literature and new proposed ones. These experiments show the efficiency of our approaches that outperform the leading methods published in the research literature.