×

A solution approach based on Benders decomposition for the preventive maintenance scheduling problem of a stochastic large-scale energy system. (English) Zbl 1280.90062

Summary: 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.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Almakhlafi, A., & Knowles, J. (2012). Benchmarks for maintenance scheduling problems in power generation. In World congress on computational intelligence, June (pp. 10-15).
[2] Benders, J. F. (1962). Partitioning procedures for solving mixed variables programming problems. Numerische Mathematik, 4, 238-252. · Zbl 0109.38302 · doi:10.1007/BF01386316
[3] Cabero, J., Ventosa, M. J., Cerisola, S., & Baíllo, Á. (2010). Modeling risk management in oligopolistic electricity markets: A Benders decomposition approach. IEEE Transactions on Power Systems, 25(1), 263-271. · Zbl 1168.90395
[4] Canto, S. P. (2008). Application of Benders decomposition to power plant preventive maintenance scheduling. European Journal of Operational Research, 184, 759-777. · Zbl 1168.90395 · doi:10.1016/j.ejor.2006.11.018
[5] Canto, S. P. (2011). Using 0/1 mixed integer linear programming to solve a reliability-centered problem of power plant preventive maintenance scheduling. Optimization Engineering, 12, 333-347. · Zbl 1284.90025 · doi:10.1007/s11081-011-9146-2
[6] Contreras, I., Cordeau, J.-F., & Laporte, G. (2010). Benders decomposition for large scale uncapacitated hub location. Technical Report CIRRELT-2010-26, Interuniversity Research Centre on Enterprise Networks, Logistics, and Transportation. · Zbl 1242.90094
[7] Dahal, K. P., & Chakpitak, N. (2007). Generator maintenance scheduling in power systems using metaheuristic-based hybrid approaches. Electric Power Systems Research, 77, 771-779. · doi:10.1016/j.epsr.2006.06.012
[8] Darlay, J., Esperet, L., Kieffer, Y., Naves, G., & Weber, V. (2010). A functional programming approach for an energy planning problem. In EURO XXIV LISBON 24th European conference on operational research (p. 280).
[9] Dopazo, J. F., & Merrill, H. M. (1975). Optimal generator maintenance scheduling using integer programming. IEEE Transactions on Power Apparatus and Systems, 94(5), 1537-1545.
[10] Doyle, E. K. (2004). On the application of stochastic models in nuclear power plant maintenance. European Journal of Operational Research, 154, 673-690. · Zbl 1053.90027 · doi:10.1016/S0377-2217(02)00805-6
[11] El-Amin, I., Duffuaa, S., & Abbas, M. (2000). A tabu search algorithm for maintenance scheduling of generating units. Electric Power Systems Research, 54, 91-99. · doi:10.1016/S0378-7796(99)00079-6
[12] El-Sharkh, M. Y., & El-Keib, A. A. (2003). An evolutionary programming-based solution methodology for power generation and transmission maintenance scheduling. Electric Power Systems Research, 65, 35-40. · doi:10.1016/S0378-7796(02)00215-8
[13] Guyon, O., Lemaire, P., Pinson, E., & Rivreau, D. (2010). Cut generation for an integrated employee timetabling and production scheduling problem. European Journal of Operational Research, 201, 557-567. · Zbl 1175.90167 · doi:10.1016/j.ejor.2009.03.013
[14] Kjeldsen, N., Godskesen, S., Larsen, R., & Jensen, T. S. (2010). Constraint programming and local search for a large-scale energy management problem with varied constraints. In EURO XXIV LISBON 24th European conference on operational research (p. 219).
[15] Kralj, B., & Rajaković, N. (1994). Multiobjective programming in power system optimization: New approach to generator maintenance scheduling. Electrical Power and Energy Systems, 16(4), 211-220.
[16] Li, Z., & Shahidehpour, M. (2005). Security-constrained unit commitment for simultaneous clearing of energy and ancillary services markets. IEEE Transactions on Power Systems, 20(2), 1079-1088. · doi:10.1109/TPWRS.2005.846063
[17] Mercier, A., Cordeau, J.-F., & Soumis, F. (2005). A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem. Computers and Operations Research, 32, 1451-1476. · Zbl 1122.90355 · doi:10.1016/j.cor.2003.11.013
[18] Mohanta, D. K., Sadhu, P. K., & Chakrabarti, R. (2007). Deterministic and stochastic approach for safety and reliability optimization of captive power plant maintenance scheduling using GA/SA-based hybrid techniques: A comparison of results. Reliability Engineering and System Safety, 92(2), 187-199.
[19] Morozowski, M., Fonseca, L., Oliveira, G., Melo, A., & Mello, J.C.O. (1995). Transmission constrained maintenance scheduling of generating units: A stochastic programming approach. IEEE Transactions on Power Systems, 10(2), 695-701. · Zbl 1053.90027
[20] Naoum-Sawaya, J., & Elhedhli, S. (2010). A nested Benders decomposition approach for telecommunication network planning. Naval Research Logistics, 57, 519-539. · Zbl 1230.90052 · doi:10.1002/nav.20419
[21] Niknam, T., Khodaei, A., & Fallahi, F. (2009). A new decomposition approach for the thermal unit commitment problem. Applied Energy, 86(9), 1667-1674. · doi:10.1016/j.apenergy.2009.01.022
[22] Porcheron, M., Gorge, A., Juan, O., Simovic, T., & Dereu, G. (2009). Challenge ROADEF/EURO 2010: A large-scale energy management problem with varied constraints. http://challenge.roadef.org/2010/files/sujetEDFv22.pdf. · Zbl 1168.90395
[23] Reihani, E., Sarikhani, A., Davodi, M., & Davodi, M. (2012). Reliability based generator maintenance scheduling using hybrid evolutionary approach. Electric Power and Energy Systems, 42(1), 434-439. · Zbl 0109.38302
[24] ROADEF Challenge. (2010). http://challenge.roadef.org/2010/.
[25] Santos, T. N., & Diniz, A. L. (2009). Feasibility and optimality cuts for the multi-stage Benders decomposition approach: Application to the network constrained hydrothermal scheduling. In Power and Energy Society general meeting, 2009. PES ’09. IEEE.
[26] Saraiva, J. T., Pereira, M. L., Mendes, V. T., & Sousa, J. C. (2011). A simulated annealing based approach to solve the generator maintenance scheduling problem. Electric Power Systems Research, 81, 1283-1291.
[27] Da Silva, E. L. (2000). Generation maintenance scheduling considering transmission constraints. Transactions on Power Systems, 15(2), 838-843.
[28] Soumis, F., Desaulniers, G., Gendreau, M., Rousseau, L.-M., Lessard, F., & Raymond, V. (2010). A mathematical-programming based solution approach for the EDF energy management problem. In EURO XXIV LISBON 24th European conference on operational research (p. 261).
[29] Steiner, R., Pirkwieser, S., & Prandtstetter, M. (2010). An ACO/VNS hybrid approach for a large-scale energy management problem. In EURO XXIV LISBON 24th European conference on operational research (p. 202).
[30] Tokola, H., Ahlroth, L., & Schumacher, A. (2010). A local search algorithm with a repair procedure for the ROADEF 2010 challenge. In EURO XXIV LISBON 24th European conference on operational research.
[31] Wolfler-Calvo, R., Létocart, L., Alfandri, L., Rozenkop, A., Chemla, D., & Turri, G. (2010). A column generation approach for scheduling nuclear power plants refueling. In EURO XXIV LISBON 24th European conference on operational research (p. 280).
[32] Wu, L., & Shahidehpour, M. (2010). Accelerating the Benders decomposition for network-constrained unit commitment problems. Energy Systems, 1, 339-376. · doi:10.1007/s12667-010-0015-4
[33] Yare, Y., & Venayagamoorthy, G. K. (2010). Optimal maintenance scheduling of generators using multiple swarms—MDPSO framework. Engineering Applications of Artificial Intelligence, 23, 895-910.
[34] Yare, Y., Venayagamoorthy, G. K., & Aliyu, U. O. (2008). Optimal generator maintenance scheduling using a modified discrete PSO. IET Proceedings on Generation, Transmission and Distribution, 2(6), 834-846.
[35] Zurn, H. H., & Quintana, V. H. (1975). Generator maintenance scheduling via successive approximations dynamic programming. IEEE Transactions on Power Apparatus and Systems, 94(2), 476-783. · doi:10.1109/T-PAS.1975.31894
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.