The EURO ROADEF 2010 Challenge aimed to schedule the maintenance and refueling operations of French nuclear power plants, ranking the approaches in competition for the quality of primal solutions. This paper justifies the high quality of the best solutions computing dual bounds with dual heuristics. A first step designs several Mixed Integer Programming (MIP) relaxations with different compromises between computation time and quality of dual bounds. To deal with smaller MIPs, we prove how reductions in the number of time steps and scenarios can guarantee dual bounds for the whole problem of the Challenge. Several sets of dual bounds are computable, improving significantly the former best dual bounds of the literature. Intermediate results allow also a better understanding of the problem and offer perspectives to improve some approaches of the Challenge.
La Programmation Lineaire en Nombres Entiers (PLNE) est couramment utilisee pour modeliser des problemes d'optimisation du monde industriel, de par la facilite a modeliser des problemes complexes d'optimisation et par l’existence d’une resolution generique par l'algorithme de Branch&Bound (B&B). La resolution B&B est souvent limitee pour des problemes de taille reelle, les methodes heuristiques sont alors utilisees pour trouver des solutions de bonne qualite sans avoir de preuve d'optimalite. Cette these etudie les limites de la resolution exacte et des heuristiques sur des problemes industriels d'EDF, en vue de leur insertion dans le processus decisionnel operationnel. L'application principale concerne la planification des arrets de maintenance et de rechargement des centrales nucleaires, sujet du Challenge ROADEF 2010. Nous avons aussi traite un probleme de production journaliere d'un parc thermique a flammes. La methodologie suivie est analogue pour les deux cas. On modelise tout d'abord le probleme avec une formulation compacte PLNE, pour en analyser les limites de la resolution frontale, avant d’envisager des methodes de decomposition. On derive ensuite les methodes exactes en matheuristiques pour resoudre des instances de taille reelle. Dans cette optique, l'hybridation de Variable Neighborhood Search (VNS) avec des voisinages definis par PLNE a donne des resultats tres probants sur les deux problemes en termes de qualites de solutions. Le fait d'avoir travaille avec des methodes exactes a permis egalement de chiffrer l'impact d'hypotheses de resolutions, de repondre a des considerations operationnelles, mais egalement d'obtenir des bornes inferieures. The reliability of the power plants and transmission lines in the electricity industry is crucial for meeting demand. Consequently, timely maintenance plays a major role reducing breakdowns and avoiding expensive production shutdowns. By now, the literature contains a sound body of work focused on improving decision making in generating units and transmission lines maintenance scheduling. The purpose of this paper is to review that literature. We update previous surveys and provide a more global view of the problem: we study both regulated and deregulated power systems and explore some important features such as network considerations, fuel management, and data uncertainty.