L’optimisation de la planification de la maintenance des équipements de production d’électricité est une question importante pour éviter des temps d’arrêt inutiles et des coûts opérationnels excessifs. Dans cette thèse, nous présentons une classification multidimensionnelle des études de Recherche Opérationnelle portant sur ce sujet. Le secteur des énergies renouvelables étant en pleine expansion, nous présentons et discutons ensuite d’un problème de maintenance de parcs éoliens terrestres. Le problème est traité sur un horizon à court terme et l’objectif est de construire un planning de maintenance qui maximise le revenu lié à production d’électricité des éoliennes tout en prenant en compte des prévisions de vent et en gérant l’affectation de techniciens. Nous présentons plusieurs modélisations du problème basées sur la programmation linéaire. Nous décrivons aussi une recherche à grands voisinages basée sur la programmation par contraintes.Cette méthode heuristique donne des résultats probants.Nous résolvons ensuite le problème avec une approche exacte basée sur une décomposition du problème. Dans cette méthode, nous construisons successivement des plannings de maintenance optimisés et rejetons, à l’aide de coupes spécifiques, ceux pour lesquels la disponibilité des techniciens est insuffisante. Les résultats suggèrent que cette méthode est la mieux adaptée pour ce problème. Enfin, pour prendre en compte l’incertitude inhérente à la prévision de vitesses de vent, nous proposons une approche robuste dans laquelle nous prenons des décisions garantissant la réalisabilité du planning de maintenance et le meilleur revenu pour les pires scénarios de vent. / Efficiently scheduling maintenance operations of generating units is key to prevent unnecessary downtime and excessive operational costs. In this work, we first present a multidimensional classification of the body of work dealing with the optimization of the maintenance scheduling in the operations research literature. Motivated by the recent emergence of the renewable energy sector as an Environmental priority to produce low-carbon power electricity, we introduce and discuss a challenging Maintenance scheduling problem rising in the onshore wind industry. Addressing the problem on a short-term horizon, the objective is to find a maintenance plan that maximizes the revenue generated by the electricity production of the turbines while taking into account wind predictions, multiple task execution modes, and technician-to-task assignment constraints. We start by presenting several integer linear Programming formulations of the problem. We then describe a constraint programming-based large neighborhood search which proves to be an efficient heuristic solution method. We then design an exact branch-and-check approach based on a decomposition of the problem. In this method, we successively build maintenance plans while discarding – using problem-specific cuts – those that cannot be performed by the technicians. The results suggest that this method is the best suited to the problem. To tackle the Inherent uncertainty on the wind speed, we also propose a robust approach in which we aim to take risk-averse decisions regarding the revenue associated with the maintenance plan and its feasibility.

The aim in this thesis is to develop efficient enumeration algorithms to solve certain strongly NP-hard scheduling problems. These algorithms were developed using a combination of ideas from Integer Programming, Constraint Programming and Scheduling Theory. In order to combine different techniques in one algorithm, decomposition methods are applied. The main idea on which the first part of our results is based is to separate the optimality and feasibility components of the problem and let different methods tackle these components. Then IP is ``responsible' for optimization, whereas specific combinatorial algorithms tackle the feasibility aspect. Branch-and-cut and branch-and-price algorithms based on this idea are proposed to solve the single-machine and multi-machine variants of the scheduling problem to minimize the sum of the weights of late jobs. Experimental research shows that the algorithms proposed outperform other algorithms available in the literature. Also, it is shown that these algorithms can be used, after some modification, to solve the problem of minimizing the maximum tardiness on unrelated machines. The second part of the thesis deals with the one-machine scheduling problem to minimize the weighted total tardiness. To tackle this problem, the idea of a partition of the time horizon into intervals is used. A particularity of this approach is that we exploit the structure of the problem to partition the time horizon. This particularity allowed us to propose two new Mixed Integer Programming formulations for the problem. The first one is a compact formulation and can be used to solve the problem using a standard MIP solver. The second formulation can be used to derive lower bounds on the value of the optimal solution of the problem. These lower bounds are of a good quality, and they can be obtained relatively fast.