This paper introduces a three-phase heuristic approach for a large-scale energy management and maintenance scheduling problem. The problem is concerned with scheduling maintenance and refueling for nuclear power plants up to five years into the future, while handling a number of scenarios for future demand and prices. The goal is to minimize the expected total production costs. The first phase of the heuristic solves a simplified constraint programming model of the problem, the second performs a local search, and the third handles overproduction in a greedy fashion. This work was initiated in the context of the ROADEF EURO Challenge 2010, a competition organized jointly by the French Operational Research and Decision Support Society, the European Operational Research Society, and the European utility company Electricite de France. In the concluding phase of the competition our team ranked second in the junior category and sixth overall. After correcting an implementation bug in the program that was submitted for evaluation, our heuristic solves all ten real-life instances, and the solutions obtained are all within 2.45 of the currently best known solutions. The results given here would have ranked first in the original competition.
Setting production levels for power plants is treated in the literature under the term economic dispatch' --- i.e., the problem of dispatching units to producing power in an economic way to minimize production costs. While many different settings are considered, see for example @cite_5 by Chowdhury and Rahman, there are new features in the production planning for nuclear power plants. The new features concern special bounds on production levels when the fuel level is low, which leads to nonlinear constraints. When a type 2 plant's fuel level drops below a given treshold, a decreasing power production level is imposed. Without this constraint the production planning could be solved with linear programming.
@cite_5
2059695025 166079659 2109425988 2178167101
This paper presents a heuristic method based on column generation for the EDF (Electricite De France) long-term electricity production planning problem proposed as subject of the ROADEF EURO 2010 Challenge. This is to our knowledge the first-ranked method among those methods based on mathematical programming, and was ranked fourth overall. The problem consists in determining a production plan over the whole time horizon for each thermal power plant of the French electricity company, and for nuclear plants, a schedule of plant outages which are necessary for refueling and maintenance operations. The average cost of the overall outage and production planning, computed over a set of demand scenarios, is to be minimized. The method proceeds in two stages. In the first stage, dates for outages are fixed once for all for each nuclear plant. Data are aggregated with a single average scenario and reduced time steps, and a set-partitioning reformulation of this aggregated problem is solved for fixing outage dates with a heuristic based on column generation. The pricing problem associated with each nuclear plant is a shortest path problem in an appropriately constructed graph. In the second stage, the reload level is determined at each date of an outage, considering now all scenarios. Finally, the production quantities between two outages are optimized for each plant and each scenario by solving independent linear programming problems. This paper addresses a large-scale power plant maintenance scheduling and production planning problem, which has been proposed by the ROADEF EURO Challenge 2010. We develop two lower bounds for the problem: a greedy heuristic and a flow network for which a minimum cost flow problem has to be solved. Furthermore, we present a solution approach that combines a constraint programming formulation of the problem with several heuristics. The problem is decomposed into an outage scheduling and a production planning phase. The first phase is solved by a constraint program, which additionally ensures the feasibility of the remaining problem. In the second phase we utilize a greedy heuristic--developed from our greedy lower bound--to assign production levels and refueling amounts for a given outage schedule. All proposed strategies are shown to be competitive in an experimental evaluation. Two major decisions are made when scheduling the operations of a fossil-fuel power-generating system over a short time horizon. The “unit commitment” decision indicates what generating units are to be in use at each point in time. The “economic dispatch” decision is the allocation of system demand among the generating units in operation at any point in time. Both these decisions must be considered to achieve a least-cost schedule over the short time horizon. In this paper we present a mixed integer programming model for the short time horizon power-scheduling problem. The objective of the model is to minimize the sum of the unit commitment and economic dispatch costs subject to demand, reserve, and generator capacity and generator schedule constraints. A branch-and-bound algorithm is proposed using a Lagrangian method to decompose the problem into single generator problems. A sub gradient method is used to select the Lagrange multipliers that maximize the lower bound produced by the relaxation. We present... The demand for electrical energy is globally growing very quickly. For this reason, the optimization of power plant productions and power plant maintenance scheduling have become important research topics. A Large Scale Energy Management (LSEM) problem is studied in this paper. Two types of power plants are considered: power plants of type 1 can be refueled while still operating. Power plants of type 2 need to be shut down from time to time, for refueling and ordinary maintenance (these are typically nuclear plants). Considering these two types of power plants, LSEM is the problem of optimizing production plans and scheduling of maintenances of type 2 plants, with the objective of keeping the production cost as low as possible, while fulfilling the customers demand. Uncertainty about the customers demand is taken into account in the model considered. In this article, a matheuristic optimization approach based on problem decomposition is proposed. The approach involves mixed integer linear programming and simulated annealing optimization methods. Computational results on some realistic instances are presented.