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.
A problem similar to the one studied here has been considered in @cite_6 by in 1997. They consider roughly the same scheduling problem as is handled here and formulate a mixed integer programming model. In their model there is no decision variable concerning refueling amounts; this decision is instead handled as a predefined fixed amount. There is also no uncertainty of future demand or prices, and the demand is given per week, in contrast to the competition where the electricity demand is given per time step, i.e., their discretization is more coarse-grained.
@cite_6
2109425988 1984494184 2080382509 2055066666
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... Abstract The problem addressed here is scheduling the shutdown for refueling and maintenance of nuclear power plants. The models have up to four reactors requiring of the order of five shutdowns each over a five-year time horizon. The resulting mixed-integer program is large and complex with interesting structure. We show good results using a mixed-integer optimizer taking advantage of a strong linear programming formulation. The New York Power Authority (NYPA) wanted to develop a 10-year schedule for refueling its Indian Point 3 Nuclear Power Plant (IP3) that balanced fish protection, which occurs when IP3 is shut down for refueling, and the costs of buying and loading fuel. We developed a decision analysis model to compare alternative strategies for refueling. It explicitly considered key uncertainties associated with future operation: how well IP3 operates, how long it takes to refuel, and when New York State is likely to deregulate the electric utility industry. The NYPA decision makers used the model to reinforce their choice of a refueling strategy. They were not surprised that more fish protection occurred with strategies that restricted the starting date for refueling to the third week in May, rather than allowing the starting date to float throughout the period from May through August. However, the decision makers were surprised that the more restrictive strategies also resulted in lower costs. This paper describes a Benders decomposition-based framework for solving the large scale energy management problem that was posed for the ROADEF 2010 challenge. The problem was taken from the power industry and entailed scheduling the outage dates for a set of nuclear power plants, which need to be regularly taken down for refueling and maintenance, in such a way that the expected cost of meeting the power demand in a number of potential scenarios is minimized. We show that the problem structure naturally lends itself to Benders decomposition; however, not all constraints can be included in the mixed integer programming model. We present a two phase approach that first uses Benders decomposition to solve the linear programming relaxation of a relaxed version of the problem. In the second phase, integer solutions are enumerated and a procedure is applied to make them satisfy constraints not included in the relaxed problem. To cope with the size of the formulations arising in our approach we describe efficient preprocessing techniques to reduce the problem size and show how aggregation can be applied to each of the subproblems. Computational results on the test instances show that the procedure competes well on small instances of the problem, but runs into difficulty on larger ones. Unlike heuristic approaches, however, this methodology can be used to provide lower bounds on solution quality.