Efficient algorithms to solve scheduling problems with a variety of optimization criteria

La programmation par contraintes est une technique puissante pour résoudre, entre autres, des problèmes d’ordonnancement de grande envergure. L’ordonnancement vise à allouer dans le temps des tâches à des ressources. Lors de son exécution, une tâche consomme une ressource à un taux constant. Généralement, on cherche à optimiser une fonction objectif telle la durée totale d’un ordonnancement. Résoudre un problème d’ordonnancement signifie trouver quand chaque tâche doit débuter et quelle ressource doit l’exécuter. La plupart des problèmes d’ordonnancement sont NP-Difficiles. Conséquemment, il n’existe aucun algorithme connu capable de les résoudre en temps polynomial. Cependant, il existe des spécialisations aux problèmes d’ordonnancement qui ne sont pas NP-Complet. Ces problèmes peuvent être résolus en temps polynomial en utilisant des algorithmes qui leur sont propres. Notre objectif est d’explorer ces algorithmes d’ordonnancement dans plusieurs contextes variés. Les techniques de filtrage ont beaucoup évolué dans les dernières années en ordonnancement basé sur les contraintes. La proéminence des algorithmes de filtrage repose sur leur habilité à réduire l’arbre de recherche en excluant les valeurs des domaines qui ne participent pas à des solutions au problème. Nous proposons des améliorations et présentons des algorithmes de filtrage plus efficaces pour résoudre des problèmes classiques d’ordonnancement. De plus, nous présentons des adaptations de techniques de filtrage pour le cas où les tâches peuvent être retardées. Nous considérons aussi différentes propriétés de problèmes industriels et résolvons plus efficacement des problèmes où le critère d’optimisation n’est pas nécessairement le moment où la dernière tâche se termine. Par exemple, nous présentons des algorithmes à temps polynomial pour le cas où la quantité de ressources fluctue dans le temps, ou quand le coût d’exécuter une tâche au temps t dépend de t.

Les méthodes d’adaptation du Centre des droits de l’homme "Memorial" aux mesures étatiques russes- Les principes d’action d’une ONG de défense des droits de l’homme russe

En raison du virage semi-autoritaire de l’État russe au début des années 2000, l’adaptation aux mesures contraignantes de l’État, qu’elle soit consciente ou inconsciente, constitue un aspect fondamental du quotidien des ONG de défense des droits de l’homme russes. Cependant, il s’agit d’une question jusqu’ici négligée dans la littérature scientifique. Ainsi, ce mémoire a pour objet d’examiner la démarche d’adaptation d’une ONG particulièrement active sur la scène russe, le Centre des droits de l’homme Memorial, entre 1999 et 2014. La recherche révèle que cette ONG emploie deux méthodes afin de s’adapter aux mesures étatiques et que celles-ci sont, en fait, des principes d’action adoptés par l’organisation au moment de sa création. Le premier principe d’action s’appuie sur la coopération et la solidarité développées par le Centre des droits de l’homme Memorial avec d’autres ONG russes, des ONG internationales et des organisations internationales. En partenariat avec ces organisations, le Centre des droits de l’homme Memorial élabore des activités de recherche et de plaidoyer et mène des missions de surveillance des droits de l’homme. Ce principe d’action renforce considérablement la capacité d’adaptation de l’ONG et favorise l’exercice de son rôle de contrepouvoir. Le second principe d’action se fonde sur la recherche de collaboration constructive avec l’État. Lors d’interactions ponctuelles avec les autorités, l’organisation exerce un rôle d’expert en matière de droits de l’homme et tente de réduire les entraves posées à la société civile. Outre sa propriété adaptative, cette méthode d’adaptation combine deux fonctions inhérentes à la société civile, soit la représentation des intérêts des citoyens auprès des instances étatiques et l’établissement d’un partenariat avec l’État dans le but d’amener ce dernier à adopter des pratiques démocratiques. Ce mémoire montre la capacité du Centre des droits de l’homme Memorial à se mouvoir d’une méthode d’adaptation à l’autre afin de maximiser son action.