×

A constraint programming-based approach to a large-scale energy management problem with varied constraints. (English) Zbl 1280.90034

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

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming

Software:

Gecode
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brandt, F. (2010). Solving a large-scale energy management problem with varied constraints. Karlsruhe Institute of Technology (KIT), Faculty of Informatics. http://digbib.ubka.uni-karlsruhe.de/volltexte/1000022490.
[2] Dentcheva, D.; Römisch, W.; Marti, K. (ed.); Kall, P. (ed.), Optimal power generation under uncertainty via stochastic programming, No. 458, 22-56 (1997), Berlin · Zbl 0907.90197 · doi:10.1007/978-3-642-45767-8_2
[3] Feltenmark, S.; Kiwiel, K. C.; Lindberg, P., Solving unit commitment problems in power production planning, 236-241 (1996), Berlin · Zbl 0924.90080
[4] Foong, W. K., Maier, H. R., & Simpson, A. R. (2008). Power plant maintenance scheduling using ant colony optimization: an improved formulation. Engineering Optimization, 40, 309-329. · doi:10.1080/03052150701775953
[5] Gardi, F.; Nouioua, K., Local search for mixed-integer nonlinear optimization: a methodology and an application, No. 6622, 167-178 (2011)
[6] GECODE—a generic constraint development environment. (2010). http://www.gecode.org.
[7] Godskesen, S., Jensen, T. S., Kjeldsen, N., & Larsen, R. (2010). Solving a real-life large-scale energy management problem. ArXiv:1012.4691. · Zbl 1280.90047
[8] Khemmoudj, M. O. I.; Porcheron, M.; Bennaceur, H., When constraint programming and local search solve the scheduling problem of electricité de France nuclear power plant outages, No. 4204, 271-283 (2006)
[9] LEMON Graph (2010). Library. http://lemon.cs.elte.hu.
[10] Lusby, R. M., Muller, L. F., & Petersen, B. (2010). A solution approach to the ROADEF/EURO 2010 challenge based on Benders’ decomposition (Tech. Rep. DTU Management 2010; 18). Technical University of Denmark, Department of Management Engineering. · Zbl 0924.90080
[11] Ngundam, J. M., Kenfack, F., & Tatietse, T. T. (2000). Optimal scheduling of large-scale hydrothermal power systems using the Lagrangian relaxation technique. International Journal of Electrical Power & Energy Systems, 22(4), 237-245. doi:10.1016/S0142-0615(99)00054-X. · doi:10.1016/S0142-0615(99)00054-X
[12] Padhy, N. (2004). Unit commitment—a bibliographical survey. IEEE Transactions on Power Systems, 19(2), 1196-1205. · doi:10.1109/TPWRS.2003.821611
[13] Pocheron, M., Gorge, A., Juan, O., Simovic, T., & Dereu, G. (2010). Challenge ROADEF/EURO 2010: a large-scale energy management problem with varied constraints. http://challenge.roadef.org/2010/.
[14] Satoh, T., & Nara, K. (1991). Maintenance scheduling by using simulated annealing method [for power plants]. IEEE Transactions on Power Systems, 6, 850-857. · doi:10.1109/59.76735
[15] Sen, S., & Kothari, D. P. (1998). Optimal thermal generating unit commitment: a review. International Journal of Electrical Power & Energy Systems, 20(7), 443-451. · doi:10.1016/S0142-0615(98)00013-1
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.