Lors de l'engagement d'un projet, un chef de projet doit structurer le projet de conception. Il s'agit de définir une architecture préliminaire du produit, de structurer le processus de conception et de regrouper les acteurs du projet en équipes interdépendantes (le regroupement est appelé "architecture des acteurs"). Ces trois activités sont fortement inter-reliées et critiques lors de la phase de conception préliminaire, car les décisions prises auront un impact fort sur les performances de l'ensemble du projet. Cependant, peu de méthodes formelles ont été proposées pour les considérer conjointement. Par ailleurs, lors de l'affectation des tâches du processus aux acteurs, le chef de projet doit s'assurer que les acteurs sont compétents pour réaliser une tâche. Il doit aussi prendre en compte des besoins de futurs projets qui pourraient nécessiter des apprentissages dans les projets en cours. Dans la réalité, la complexité de l'organisation d'un projet empêche d'avoir une vision globale des conséquences des choix d'affectation, qui plus est, sur plusieurs périodes et sur plusieurs projets. Peu de travaux se sont intéressés à ce type de problème. Or aujourd'hui, les tâches et les compétences nécessaires dans les projets de conception évoluent rapidement en lien avec la forte évolution des technologies et des besoins du marché. Le développement des compétences des ressources humaines devient une des priorités de l'entreprise qui ne les considère plus comme des ressources statiques (comme des machines) mais comme des ressources dynamiques auxquelles il faut attacher des objectifs de développement. Dans ce mémoire, nous proposons une méthode d'aide à la constitution d'équipes permettant de coupler la structuration du projet et le pilotage des compétences. Ce travail consiste alors à optimiser l'affectation des tâches aux acteurs et le regroupement des acteurs en équipes, en tenant compte à la fois des contraintes liés à l'architecture du produit et des objectifs de développement de compétences, sur de multiples projets et de multiples périodes. Ce problème étant complexe, ce mémoire de thèse présente des contributions à des sousproblèmes (affectation mon-période, affectation multi-périodes avec prise en compte du développement des compétences, architecture des acteurs avec prise en compte de l'architecture du produit), avant de proposer une formulation du problème global et une méthode de résolution en deux phases intégrant un algorithme de recuit simulé.

Dans cette thèse, nous étudions des algorithmes pour le monitoring des traces d’activité à grande échelle. Le monitoring est une aptitude clé dans plusieurs domaines, permettant d’extraire de la valeur des données ou d’améliorer les performances d’un système. Nous explorons d’abord le monitoring de données temporelles. Nous présentons un nouveau type de jointure sur des intervalles, qui inclut des fonctions de score caractérisant le degré de satisfaction de prédicats temporels. Nous étudions ces jointures dans le contexte du batch processing (traitement par lots). Nous formalisons la Ranked Temporal Join (RTJ), une jointure qui combine des collections d’intervalles et retourne les k meilleurs résultats. Nous montrons comment exploiter les propriétés des prédicats temporels et de la sémantique de score associée afin de concevoir TKIJ , une méthode d’évaluation de requête distribuée basée sur Map-Reduce. Nos expériences sur des données synthétiques et réelles montrent que TKIJ est plus performant que les techniques de l’état de l’art et démontre de bonnes performances sur des requêtes RTJ n-aires sur des données temporelles. Nous proposons également une étude préliminaire afin d’étendre nos travaux sur TKIJ au domaine du stream processing (traitement de flots). Nous explorons ensuite le monitoring dans le crowdsourcing (production participative). Nous soutenons la nécessité d’intégrer la motivation des travailleurs dans le processus d’affectation des tâches. Nous proposons d’étudier une approche adaptative, qui évalue la motivation des travailleurs lors de l’exécution des tâches et l’exploite afin d’améliorer l’affectation de tâches qui est réalisée de manière itérative. Nous explorons une première variante nommée Individual Task Assignment (Ita), dans laquelle les tâches sont affectées individuellement, un travailleur à la fois. Nous modélisons Ita et montrons que ce problème est NP-Difficile. Nous proposons trois méthodes d’affectation de tâches qui poursuivent différents objectifs. Nos expériences en ligne étudient l’impact de chaque méthode sur la performance globale dans l’exécution de tâches. Nous observons que différentes stratégies sont dominantes sur les différentes dimensions de performance. En particulier, la méthode affectant des tâches aléatoires et correspondant aux intérêts d’un travailleur donne le meilleur flux d’exécution de tâches. La méthode affectant des tâches correspondant au compromis d’un travailleur entre diversité et niveau de rémunération des tâches donne le meilleur niveau de qualité. Nos expériences confirment l’utilité d’une affectation de tâches adaptative et tenant compte de la motivation. Nous étudions une deuxième variante nommée Holistic Task Assignment (Hta), où les tâches sont affectées à tous les travailleurs disponibles, de manière holistique. Nous modélisons Hta et montrons que ce problème est NP-Difficile et MaxSNP-Difficile. Nous développons des algorithmes d’approximation pour Hta. Nous menons des expériences sur des données synthétiques pour évaluer l’efficacité de nos algorithmes. Nous conduisons également des expériences en ligne et comparons notre approche avec d’autres stratégies non adaptatives. Nous observons que notre approche présente le meilleur compromis sur les différentes dimensions de performance. / In this thesis, we study scalable algorithms for monitoring activity traces. In several domains, monitoring is a key ability to extract value from data and improve a system. This thesis aims to design algorithms for monitoring two kinds of activity traces. First, we investigate temporal data monitoring. We introduce a new kind of interval join, that features scoring functions reflecting the degree of satisfaction of temporal predicates. We study these joins in the context of batch processing: we formalize Ranked Temporal Join (RTJ), that combine collections of intervals and return the k best results. We show how to exploit the nature of temporal predicates and the properties of their associated scored semantics to design TKIJ , an efficient query evaluation approach on a distributed Map-Reduce architecture. Our extensive experiments on synthetic and real datasets show that TKIJ outperforms state-of-the-art competitors and provides very good performance for n-ary RTJ queries on temporal data. We also propose a preliminary study to extend our work on TKIJ to stream processing. Second, we investigate monitoring in crowdsourcing. We advocate the need to incorporate motivation in task assignment. We propose to study an adaptive approach, that captures workers’ motivation during task completion and use it to revise task assignment accordingly across iterations. We study two variants of motivation-aware task assignment: Individual Task Assignment (Ita) and Holistic Task Assignment (Hta). First, we investigate Ita, where we assign tasks to workers individually, one worker at a time. We model Ita and show it is NP-Hard. We design three task assignment strategies that exploit various objectives. Our live experiments study the impact of each strategy on overall performance. We find that different strategies prevail for different performance dimensions. In particular, the strategy that assigns random and relevant tasks offers the best task throughput and the strategy that assigns tasks that best match a worker’s compromise between task diversity and task payment has the best outcome quality. Our experiments confirm the need for adaptive motivation-aware task assignment. Then, we study Hta, where we assign tasks to all available workers, holistically. We model Hta and show it is both NP-Hard and MaxSNP-Hard. We develop efficient approximation algorithms with provable guarantees. We conduct offline experiments to verify the efficiency of our algorithms. We also conduct online experiments with real workers and compare our approach with various non-adaptive assignment strategies. We find that our approach offers the best compromise between performance dimensions thereby assessing the need for adaptability.

Bien que la gestion des ressources humaines soit une problématique bien étudiée, elle reste d’actualité encore aujourd’hui, notamment en raison de la grande diversité des contextes applicatifs. De plus, les outils d’aide à la décision adressant ces problèmes peuvent encore être améliorés. Dans cette thèse, nous nous intéressons au contexte particulier où les activités des employés correspondent à des tâches fixées dans le temps, requérant des compétences précises et ne pouvant être préemptées. Nous étudions tout d’abord un problème issu de l’industrie pharmaceutique où il s’agit non seulement de trouver une affectation équitable des tâches, mais également de construire les horaires de travail du personnel de manière à respecter les contraintes légales et organisationnelles. Pour résoudre ce problème, nous proposons et comparons deux méthodes exactes, l’une fondée sur un modèle PLNE, l’autre sur un modèle PPC, ainsi que deux méta-heuristiques, l’une reposant sur une décomposition du problème, l’autre reposant sur une recherche par voisinages larges. Nous discutons ensuite de l’intégration de la meilleure de ces méthodes au sein d’un outil d’aide à la décision. Nous nous intéressons ensuite à un problème d’affectation de tâches fixées visant à minimiser le nombre d’employés requis. Pour résoudre ce problème, nous proposons une approche PPC tirant parti de la structure du problème. Nous montrons que cette approche permet d’obtenir rapidement de bonnes bornes, permettant ainsi de prouver l’optimalité sur les instances de la littérature dans un temps raisonnable. / Although workforce scheduling has been studied for decades, it remains highly relevant. In particular, applications and contexts are numerous, and they are always changing. Moreover, decision-support tools dedicated to workforce scheduling could still be improved. In this thesis, we focus on the particular context where workers are assigned to fixed tasks which cannot be preempted and require specific skills. First, we study a problem arising in a company specialized in drug evaluation where fixed tasks have to be assigned in a fair way to qualified employees so that the resulting individual shifts and plannings respect legal and organizational constraints. To handle this problem, we design and compare two exact methods, one based on a MIP model, the other on a CP approach, but also two meta-heuristics, one based on a decomposition strategy, and the other on a large neighborhood search. The best method is integrated within a decision support system. Second, we study a fixed tasks assignment problem, where the objective is to minimize the number of resources required to perform all the tasks. To tackle this problem, we suggest a constraint based approach which takes advantage of the structure of the problem. This approach enables to compute good bounds quickly, and thus, it proves optimality over state-of-the-art instances within a reasonable time limit.