Résolution de problèmes d’ordonnancement multi-projet sous contraintes de ressources multi-compétences partagées

Dans cette thèse, nous considérons un ensemble de problèmes d'ordonnancement multi-projet à contraintes de ressources multi-compétences limitées. Les problèmes étudiés sont issus d'un cas industriel rencontré par une entreprise de développement de services informatiques. Dans chacun de ces problèmes, de multiples projets doivent être exécutés simultanément et achevés dans un horizon de planification fixe. Chaque projet est décomposé en un ensemble de tâches préemptives avec des dates de début au plus tôt et de fin souhaitées associées aux tâches. Chaque tâche doit être exécutée par une seule ressources possédant plusieurs compétences et un niveau d'efficacité par compétence. En outre, la durée de la tâche peut être réduite en fonction du niveau d'efficacité de la ressource affectée à cette tâche. Les ressources sont un ensemble d'employés multi-compétences de disponibilité limitée. Pour chaque employé, nous avons une disponibilité hebdomadaire connue au début de l'ordonnancement et qui n'est pas sujette au changement. De plus, un employé peut intervenir dans plusieurs projets avec un taux de participation maximum (quotité) par projet.Deux variantes de ce modèle sont abordées : une variante à un seul agent avec un seul critère à optimiser; une variante avec plusieurs agents où chacun cherche à optimiser son critère. Dans la première variante, les quotités des employés sur les projets sont fixées par le décideur. Ainsi, les disponibilités hebdomadaires des employés, sont réparties entre les différents projets au prorata de leurs quotités sur les projets. L'objectif est d'affecter les employés aux tâches des projets de manière à minimiser la somme des retards pondérés des tâches plus la somme pondérée des violations de certaines contraintes. Pour une résolution à l'optimum, nous présentons un modèle mathématique basé sur la programmation par objectif mixte en nombres entiers. Pour résoudre des instances de grandes tailles, nous proposons une heuristique gloutonne, une recherche locale et une recherche tabou. Nous comparons les performances de ces méthodes par rapport au modèle mathématique en utilisant des instances dérivées de données réelles données par l'entreprise partenaire.Dans la seconde variante, nous étendons le modèle précédent pour inclure le cas où les quotités des employés sur les projets ne sont pas fixées. Nous considérons que ces quotités doivent être déterminées par le calcul d'ordonnancement, en faisant intervenir le critère de chaque agent. Deux problèmes d'ordonnancement à deux ou trois agents ont été abordés. Le premier problème est de type optimisation sous contrainte avec deux agents en compétition. Le deuxième problème s'agit d'un problème d'ordonnancement à deux agents avec une fonction objectif globale (agent global). Il ajoute au premier problème le faite que certaines contraintes peuvent être violées lorsqu'il n'est pas possible de trouver une solution réalisable pour le premier problème ou pour diminuer le coût du retard. Ainsi, un objectif global consistant à minimiser la violation de ces contraintes est ajouté. Afin de résoudre les problèmes étudies, nous présentons deux modèles mathématiques basés sur la programmation linéaire. Ces modèles sont utilisés chacun par l'approche epsilon-contrainte pour déterminer les fronts de Pareto exacts. Cependant, cette méthode n'est efficace que pour résoudre les instances de petites tailles. Pour résoudre les instances de grandes tailles, des approches heuristiques utilisant une méthode génétique de type NSGA-II sont développées. Ces différentes approches ont été comparées en termes de qualité de solution sur des instances de taille réelle.In this thesis, we consider a set of multi-project scheduling and multi-skilled employees assignment problem with hard and soft constraints. The studied problems stem from an industrial case in an IT company. In each of those problems, multiple projects must be executed simultaneously and completed within a fixed planning horizon. Each project is broken down into a set of preemptive tasks with release and due dates associated with the tasks. We consider that every task needs exactly one skill and must be performed by one employee who has the corresponding skill with an efficiency level per skill. Thus, the processing time of the task may be reduced according to the efficiency level of the employee assigned to this task. Every employee has an availability per week (a working time) known in advance. Also, an employee may be involved in more than one project at the same time, with a maximum quota, i.e. percentage of his/her time, allotted to each project.Two variants of this model are tackled: a variant with one agent and one criterion to optimize; a variant with several agents where each agent desires to optimize his own criterion. In the first variant, the decision-maker fixes the quotas of the employees on the projects. Thus, the weekly availabilities of the employees are shared between the different projects in proportion to their quota on the projects. The objective is to assign employees to project tasks such that the total weighted tardiness of tasks and the undesirable goal deviations are minimized. For this problem, we present a mixed-integer goal programming (MIGP) formulation to produce an optimal schedule. Furthermore, a local search algorithm and a tabu search algorithm are proposed to tackle large-scale instances. We compare the performance of the heuristic algorithms against the corresponding MIGP with simulated instances derived from real-world instances got from the partner company.In the second variant, we extend the previous model to include the case where the quotas of employees on projects are not known. We consider that these quotas must be determined by the scheduling computation, taking into account the agents' critaria. Each agent manages one or several projects and competes with another agent for the use of common multi-skilled employees. We address two scheduling problems with two or three agents and multi-skill constrained-resources. In the first problem, the objective is to minimize the criterion of each compiting agent. The second problem is a two compiting agent scheduling problem with a global objective function (global agent). It also considers that some constraints can be violated when there is no feasible schedule for the first problem or to reduce the cost of delay of each agent. Thus, we further consider a global objective function that minimizes the soft constraint violations. The objectives of each agent is to minimize the total weighted tardiness of its tasks. The overall objective is to find a schedule that minimizes both agents objective functions and the global objective function. In each of these problems. For these problems, we provide two mathematical models based on mixed integer linear programming (MILP). These models are each used by the epsilon-constraint method to determine the pareto-optimal frontier. However, this method is only effective for solving small instances. To solve large instances, we provide two hybrid heuristics based on a genetic method of type NSGA-II algorithm. We compare the performance of the hybrid heuristics with simulated instances derived from real-world instances