A solution approach based on Benders decomposition for the preventive maintenance scheduling problem of a stochastic lar
- PDF / 638,976 Bytes
- 24 Pages / 595.276 x 790.866 pts Page_size
- 39 Downloads / 180 Views
A solution approach based on Benders decomposition for the preventive maintenance scheduling problem of a stochastic large-scale energy system Richard Lusby · Laurent Flindt Muller · Bjørn Petersen
© Springer Science+Business Media New York 2013
Abstract This paper describes a Benders decompositionbased 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. R. Lusby (B)· L. F. Muller · B. Petersen Department of Management Engineering, Technical University of Denmark, Produktionstorvet, Building 426, 2800 Kongens Lyngby, Denmark e-mail: [email protected] L. F. Muller e-mail: [email protected] B. Petersen e-mail: [email protected]
1 Introduction Approximately every 2 years since 1999 the French Operations Research Society, Recherche Opérationnelle et d’Aide à la Décision (ROADEF), has organized the so-called ROADEF challenge, an international operations research contest in which participants must solve an industrial optimization problem. Given the success of previous contests, in 2010 it was jointly organized for the first time with the European Operational Research Society (EURO) and known as the ROADEF/EURO 2010 challenge. The competition was run in collaboration with Electricité de France (EDF), one of the largest utility companies in the world, and required contestants to solve a large scale energy management problem with varied constraints. EDF’s power generation facilities in France stand for a total of 98.8 GW of installed capacity, most of which is produced using thermal, and in particular nuclear, power plants. In 2008 thermal power plants accounted for 90 % of its total electricity production, 86 % of which was delivered by nuclear power plants. The ROADEF/EURO 2010 challenge focused on the nuclear power plants, since these nee
Data Loading...
