La programmation par contraintes est une approche régulièrement utilisée pour traiter des problèmes d’ordonnancement variés. Les problèmes d’ordonnancement cumulatifs représentent une classe de problèmes dans laquelle des tâches non morcelable peuvent être effectuées en parallèle. Ces problèmes apparaissent dans de nombreux contextes réels, tels que par exemple l’allocation de machines virtuelles ou l’ordonnancement de processus dans le "cloud", la gestion de personnel ou encore d’un port. De nombreux mécanismes ont été adaptés et proposés en programmation par contraintes pour résoudre les problèmes d’ordonnancement. Les différentes adaptations ont abouti à des raisonnements qui semblent à priori significativement distincts. Dans cette thèse nous avons effectué une analyse détaillée des différents raisonnements, proposant à la fois une notation unifiée purement théorique mais aussi des règles de dominance, permettant une amélioration significative du temps d’exécution d’algorithmes issus de l’état de l’art, pouvant aller jusqu’à un facteur sept. Nous proposons aussi un nouveau cadre de travail pour l’ordonnancement cumulatif robuste, permettant de trouver des solutions supportant qu’à tout moment une ou plusieurs tâches soit retardées, sans remise en cause de l’ordonnancement généré et en gardant une date de fin de projet satisfaisante. Dans ce cadre, nous proposons une adaptation d’un algorithme de l’état de l’art, Dynamic Sweep. / Constraint programming is an approach regularly used to treat a variety of scheduling problems. Cumulative scheduling problems represent a class of problems in which non-preemptive tasks can be performed in parallel. These problems appear in many contexts, such as for example the allocation of virtual machines, the ordering process in the "cloud", personnel management or a port. Many mechanisms have been adapted and offered in constraint programming to solve scheduling problems. The various adaptations have resulted in reasoning that appear a priori significantly different. In this thesis we performed a detailed analysis of the various arguments, offering both a theoretical unified caracterization but also dominance rules, allowing a significant improvement in execution time of algorithms from the state of the art, up to a factor of seven. we also propose a new framework for robust cumulative scheduling, to find solutions that support at any time one or more tasks to be delayed while keeping a satisfactory end date of the project and without calling into question the generated scheduling. In this context, we propose an adaptation of an algorithm of the state of the art, Dynamic Sweep.

La programmation par contraintes est une approche régulièrement utilisée pour résoudre des problèmes combinatoires d’origines diverses. Dans cette thèse nous nous focalisons sur les problèmes d’ordonnancement cumulatif. Un problème d’ordonnancement consiste à déterminer les dates de débuts et de fins d’un ensemble de tâches, tout en respectant certaines contraintes de capacité et de précédence. Les contraintes de capacité concernent aussi bien des contraintes cumulatives classiques où l’on restreint la somme des hauteurs des tâches intersectant un instant donné, que des contraintes cumulatives colorées où l’on restreint le nombre maximum de couleurs distinctes prises par les tâches. Un des objectifs récemment identifiés pour la programmation par contraintes est de traiter des problèmes de grandes tailles, habituellement résolus à l’aide d’algorithmes dédiés et de métaheuristiques. Par exemple, l’utilisation croissante de centres de données virtualisés laisse apparaitre des problèmes d’ordonnancement et de placement multi-dimensionnels de plusieurs milliers de tâches. Pour atteindre cet objectif, nous utilisons l’idée de balayage synchronisé considérant simultanément une conjonction de contraintes cumulative et des précédences, ce qui nous permet d’accélérer la convergence au point fixe. De plus, de ces algorithmes de filtrage nous dérivons des procédures gloutonnes qui peuvent être appelées à chaque nœud de l’arbre de recherche pour tenter de trouver plus rapidement une solution au problème. Cette approche permet de traiter des problèmes impliquant plus d’un million de tâches et 64 ressources cumulatives. Ces algorithmes ont été implémentés dans les solveurs de contraintes Choco et SICStus, et évalués sur divers problèmes déplacement et d’ordonnancement. / Constraint programming is an approach often used to solve combinatorial problems in different application areas. In this thesis we focus on the cumulative scheduling problems. A scheduling problem is to determine the starting dates of a set of tasks while respecting capacity and precedence constraints. Capacity constraints affect both conventional cumulative constraints where the sum of the heights of tasks intersecting a given time point is limited, and colored cumulative constraints where the number of distinct colors assigned to the tasks intersecting a given time point is limited. A newly identified challenge for constraint programming is to deal with large problems, usually solved by dedicated algorithms and metaheuristics. For example, the increasing use of virtualized datacenters leads to multi dimensional placement problems of thousand of jobs. Scalability is achieved by using a synchronized sweep algorithm over the different cumulative and precedence constraints that allows to speed up convergence to the fix point. In addition, from these filtering algorithms we derive greedy procedures that can be called at each node of the search tree to find a solution more quickly. This approach allows to deal with scheduling problems involving more than one million jobs and 64 cumulative resources. These algorithms have been implemented within Choco and SICStussolvers and evaluated on a variety of placement and scheduling problems.

La programmation par contraintes est une approche régulièrement utilisée pour résoudre des problèmes combinatoires d'origines diverses. Dans cette thèse nous nous focalisons sur les problèmes d'ordonnancement cumulatif. Un problème d'ordonnancement consiste à déterminer les dates de débuts et de fins d'un ensemble de tâches, tout en respectant certaines contraintes de capacité et de précédence. Les contraintes de capacité concernent aussi bien des contraintes cumulatives classiques où l'on restreint la somme des hauteurs des tâches intersectant un instant donné, que des contraintes cumulatives colorées où l'on restreint le nombre maximum de couleurs distinctes prises par les tâches. Un des objectifs récemment identifiés pour la programmation par contraintes est de traiter des problèmes de grandes tailles, habituellement résolus à l'aide d'algorithmes dédiés et de métaheuristiques. Par exemple, l'utilisation croissante de centres de données virtualisés laisse apparaitre des problèmes d'ordonnancement et de placement multi-dimensionnels de plusieurs milliers de tâches. Pour atteindre cet objectif, nous utilisons l'idée de balayage synchronisé considérant simultanément une conjonction de contraintes cumulative et des précédences, ce qui nous permet d'accélérer la convergence au point fixe. De plus, de ces algorithmes de filtrage nous dérivons des procédures gloutonnes qui peuvent être appelées à chaque nœud de l'arbre de recherche pour tenter de trouver plus rapidement une solution au problème. Cette approche permet de traiter des problèmes impliquant plus d'un million de tâches et 64 ressources cumulatives. Ces algorithmes ont été implémentés dans les solveurs de contraintes Choco et SICStus, et évalués sur divers problèmes déplacement et d'ordonnancement.Mots-clés : Programmation par contraintes, ordonnancement, cumulatif, passage à l'échelle, point fixe, contraintes de ressources multidimensionelles, balayage synchronisé.

La programmation par contraintes est une approche régulièrement utilisée pour résoudre des problèmes combinatoires d'origines diverses. Dans cette thèse nous nous focalisons sur les problèmes d'ordonnancement cumulatif. Un problème d'ordonnancement consiste à déterminer les dates de débuts et de fins d'un ensemble de tâches, tout en respectant certaines contraintes de capacité et de précédence. Les contraintes de capacité concernent aussi bien des contraintes cumulatives classiques où l'on restreint la somme des hauteurs des tâches intersectant un instant donné, que des contraintes cumulatives colorées où l'on restreint le nombre maximum de couleurs distinctes prises par les tâches. Un des objectifs récemment identifiés pour la programmation par contraintes est de traiter des problèmes de grandes tailles, habituellement résolus à l'aide d'algorithmes dédiés et de métaheuristiques. Par exemple, l'utilisation croissante de centres de données virtualisés laisse apparaitre des problèmes d'ordonnancement et de placement multi-dimensionnels de plusieurs milliers de tâches. Pour atteindre cet objectif, nous utilisons l'idée de balayage synchronisé considérant simultanément une conjonction de contraintes cumulative et des précédences, ce qui nous permet d'accélérer la convergence au point fixe. De plus, de ces algorithmes de filtrage nous dérivons des procédures gloutonnes qui peuvent être appe- lées à chaque noeud de l'arbre de recherche pour tenter de trouver plus rapidement une solution au problème. Cette approche permet de traiter des problèmes impliquant plus d'un million de tâches et 64 resources cumulatives. Ces algorithmes ont été implémentés dans les solveurs de contraintes Choco et SICStus, et évalués sur divers problèmes de placement et d'ordonnancement.

La structuration des liquides près d'interfaces est liée aux forces d'interactions liquides/interface à des distances de quelques dimensions moléculaires. Cet effet universel joue un rôle primordial dans divers domaines tels que le transport de chaleur, le transport de particules à travers les membranes biologiques, la nanofluidique, la microbiologie et la nanorhéologie.Le but principal de cette thèse est de réaliser l'échographie par laser de liquides nanostructurés près d'une interface, afin de mieux comprendre les propriétés physiques de liquides confinés à des échelles moléculaires. La méthode utilisée est la technique d'acoustique picoseconde, qui est une technique tout optique impliquant des lasers impulsionnels pour la génération et la détection d'ultrasons picosecondes. Nous avons adapté la technique pour étudier les propriétés acoustiques longitudinales à haute fréquence des liquides ultra-minces. Les résultats de la diffusion de Brillouin dans le domaine temporel sont utilisés pour déterminer le profil de distribution de la température dans le volume de liquide étudié qui peut être extrapolé aux dimensions nanométriques. Les résultats sur le changement de la fréquence de Brillouin aussi bien que sur l’atténuation acoustique en fonction de la puissance du laser donnent un aperçu de la relation entre les propriétés thermiques et mécaniques des liquides. L'analyse de Fourier des résultats pour différentes épaisseurs de liquide donnent l'information sur la vitesse du son et de l’atténuation aux fréquences GHz. Ce nouveau schéma expérimental est une première étape vers la compréhension des liquides confinés mesuré par l'échographie d'ultrasons aux fréquences GHz. / The phenomenon of liquid structuring near interfaces is related to the liquid/interface interaction forces at distances of some molecular dimensions. Despite the fact that this universal structuring effect plays a key role in various fields such as heat transport, particle transport through biological membranes, nanofluidics, microbiology and nanorheology, the experimental investigation of liquid structuring remainschallenging.The aim of this PhD thesis is the experimental study of the structuring/ordering of liquids at nanoscale distances from their interfaces with solids. In this context, we have adapted the experimental technique of picosecond laser ultrasonics to investigate high-frequency longitudinal acoustic properties of ultrathin liquids confined between solid surfaces of different types. At first, we will present results of time-domain Brillouin scattering (TDBS) used to determine the temperature distribution profile in the investigated liquid volume which can be extrapolated to nanometer dimensions. Results for the evolution of the extracted Brillouin scattering frequencies and attenuation rates recorded at different laser powers give insight to the intrinsic relationship between thermal and mechanical properties of liquids. Second, we will describe our results for the measurements of mechanical properties of ultrathin liquids with a nanometric resolution. Fourier analysis of the recorded TDBS signals for different liquid thicknesses yield the value of the longitudinal speed of sound and attenuation at GHz frequencies. This novel TDBS experimental scheme is a first step towards the understanding of confined liquids measured by GHz ultrasonic probing.

Trata a presente tese da sustentação da indispensabilidade de utilização, em um sistema tributário, para almejar ser justo, da tributação indireta. E não basta a utilização dela como elemento complementar do sistema. É necessário que sua participação seja equilibrada em relação à utilização da tributação direta, igualmente indispensável à justeza do sistema. Assim, entre a tributação direta e a indireta, não se deve cogitar de qual das duas é mais justa, sim que uma e outra contribuem igualmente para que o sistema como um todo, possa ser o mais justo possível. A exposição se inicia com um escorço histórico em que se procura analisar e situar o funcionamento dos sistemas tributários na evolução e conformação das diversas sociedades que antecedem à nossa, com uma natural ênfase à civilização ocidental como a entendemos, isto é, centrada em uma corrente econômica, cultural e técnica, de linha mediterrânea e européia. Neste escorço, superada a exposição referente às origens mais remotas, foram feitos alguns destaques temáticos, o primeiro e mais importante destacando a atuação de Colbert no reinado de Luiz XIV, na França, pela sua contribuição crítica ao sistema tributário então vigente naquele país, e a reforma que implementou com a introdução de impostos indiretos e redução de impostos diretos, no sentido de institucionalizar e fortalecer o reino. Outros destaques foram feitos, merecendo especial citação Ricardo, Enno Becker e Keynes, o primeiro pela sua exposição crítica dos impostos vigentes na Inglaterra em seu tempo, o segundo pela sua notável participação na elaboração da Constituição de Weimar e o terceiro pela sua atuação nos Estados Unidos após a crise de 1929 e sua participação na conferência de Bretton Woods. Findo o escorço histórico, segue-se uma exposição de natureza pessoal, historiando a forma como a presente tese se conformou, sob o título de \"Reintrodução\". A partir da conceituação de \"justiça fiscal\", a tese propriamente dita se delineia, passando-se de uma análise crítica relacionada ao objetivo maior, a justiça, para a análise do papel dos impostos indiretos e diretos e da contribuição de melhoria. Em sua parte final cuida-se do ajustamento sistêmico do problema, inspirando, além do desejável ajuste científico e cibernético, uma profunda reforma tributária, que poderia destinar-se ao Brasil, ou a qualquer outro país, em qualquer estágio de desenvolvimento que se encontre. O modelo é inspirado na reforma que, produzida inicialmente na França com a introdução da T.V.A. (\"Taxe a la Valeur Ajoutée\"), depois estendida à comunidade econômica européia, praticamente institucionalizou naqueles quadrantes um tipo de imposto único indireto, altamente simplificador desse sistema impositivo. Propõe-se desta forma, a introdução também de um imposto único similar, direto, que aliado à uma nova contribuição de melhoria, melhor instituída, e da terceirização sistêmica das taxas, dariam estrutura final a todo o conjunto tributário nacional, tendo por objetivo maior o estado de direito democrático moderno. Esta, assim, seria a \"grande síntese\" tributária passível de ser alcançada, em qualquer sistema moderno. / Cette thèse concerne le maintien du caractère indispensable de Ia tributation indirecte dans un système tributaire qui vise à Ia justice. Cependant, il ne suffit pas I\'emploie de Ia tributation indirecte en tant qu\'élement complémentaire du système. Il faut que sa participation soit equilibrée par rapport à I\'emploie de Ia tributation directe, également indispensable à Ia justesse du système. Ainsi, entre les impôts directs et les indirects, Ia cogitation est que tous les deux contribuent également pour que le système soit juste et non qu\'an entre le deux est plus juste. L\'exposition part d\'un raccourci historique dont le but est d\'analyser et placer le fonctionnement des systèmes tributaire dan I\'évolution et Ia conformation de plusieurs societés ultérieures, comprennant surtout Ia civilisation occidentale en tant que nous I\'envisageons. Ça veut dire, dont I\'axe consiste dans une chaine économique, culturelle et technique d\'origine meditarrenée et européenne. Dans ce raccourci, apres avoir surmonté I\'exposition concernant les origines les plus lointaines, on a choisi quelques groupes thématiques, dont le premier et le plus important concerne I\'action de Colbert dans le royaume de Louis XIV, en France, en raison de sa contribution critique au système tributaire lors y en vigueur, ainsi que Ia reforme qu\'il a implanté, dont I\'innovation consistait dans I\'introduction des impôts indirects et dans Ia reduction des impôts directs, de façon à institucionaliser et rendre plus puissant le royaume. Ensuite, on passe à d\'autres souslignements, et on doit mentionner de façon spéciale ceux-Ià concernant Ricardo, Enno Becker et Keynes. Le premier en raison de son exposition critique des impôts, lors en vigueur dans l\'Angleterre. Le second en fonction de sa remarquable participation dans I\'élaboration de Ia Constitution de Weimar. Et le troisième en raison de son sction aux États Unis aprés Ia débâcle de 1929, ainsi que sa participation dans Ia réunion de Bretton Woods. Apres ce raccourci historique, on passe à une exposition d\'ordre personnel, en racontant en detail le développement de cette thèse, sous le titre \"Reintroduction\". À partir de Ia conceptualisation de \"justice fiscale\", Ia thèse, en son essence, se delinée, et on passe à une analyse critique par rapport à son but majeur - Ia justice -, par I\'analyse de Ia fonction des impôts indirects et directs et Ia contribution d\'amélioration. La dernière section est consacrée à I\'ajustement systémique du problème, qu\'inspire, au-delà d\'un souhaitable couplage scientifique et cybernétique, une reforme tributaire profonde, capable d\'être employée soit au Brésil soit à un autre pays quelconque, independamment du degrée de développement qu\'il a atteint. Le modele s\'inspire à Ia reforme qui a commencé en France, avec I\'introduction par Maurice Lauré de Ia T.V.A. (Taxe à Ia Valeur Ajoutée) et, qu\'ensuite, étendue à Ia Communauté Européenne, a contribué pour I\'institutionnalisation, dans Ia pratique, d\'un genre d\'impôt unique indirect, de façon à simplifier remarquablement de système de ces impôts. On propose, donc, I\'introduction d\'un impôt unique similaire, direct, que s\'alliant à une nouvelle contribution d\'amélioration, meilleurment instituée, et de Ia concession systématique des services, serait capable de donner une structure finale à tout I\'ensemble tributaire national, en une grande synthèse, ayant pour but majeur I\'état de droit démocratique moderne.