×

A branch-and-check approach for a wind turbine maintenance scheduling problem. (English) Zbl 1391.90643

Summary: In this paper, we deal with a maintenance scheduling problem arising in the onshore wind power industry. We consider a short-term horizon and a multi-skilled workforce. The goal is to schedule maintenance operations to maximize electricity production while taking into account forecast wind-speed values, multiple task execution modes, and daily restrictions on the routes of the technicians. We first introduce two integer linear programming formulations of the problem. Then, building on one of our models, we propose a branch-and-check (B&C) approach that uses both generic Benders cuts and cuts specially crafted for our problem. We report experiments on a 160-instance testbed. For 80% of the instances, our exact approach finds an optimal solution in a reasonable computational time. The remaining instances reach the three-hour time limit, and our B&C gives solutions with average gaps of 1.7% with respect to the upper bounds. The results suggest that our method significantly outperforms commercial solvers running our integer linear programming models.

MSC:

90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90B35 Deterministic scheduling theory in operations research
90B25 Reliability, availability, maintenance, inspection in operations research
90C11 Mixed integer programming
90C10 Integer programming

Software:

Algorithm 457
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Adulyasak, Y.; Cordeau, J.-F.; Jans, R., Benders decomposition for production routing under demand uncertainty, Oper. Res., 63, 4, 851-867, (2015) · Zbl 1329.90018
[2] Baptiste, P.; Le Pape, C.; Nuijten, W., Satisfiability tests and time-bound adjustments for cumulative scheduling problems, Ann. Oper. Res., 92, 305-333, (1999) · Zbl 0958.90037
[3] Beck, J., Checking-up on branch-and-check, Princip. Pract. Constraint Progr. CP 2010 SE - 10, 6308, 84-98, (2010)
[4] Biro, M.; Hujter, M.; Tuza, Z., Precoloring extension. I. interval graphs, Discrete Math., 100, 1, 267-279, (1992) · Zbl 0766.05026
[5] Botton, Q.; Fortz, B.; Gouveia, L.; Poss, M., Benders decomposition for the hop-constrained survivable network design problem, INFORMS J. Comput., 25, 1, 13-26, (2013)
[6] Bron, C.; Kerbosch, J., Algorithm 457: finding all cliques of an undirected graph, Commun. ACM, 16, 9, 575-577, (1973) · Zbl 0261.68018
[7] Codato, G.; Fischetti, M., Combinatorial benders’ cuts for mixed-integer linear programming, Oper. Res., 54, 4, 756-766, (2006) · Zbl 1167.90601
[8] De Camargo, R.; De Miranda, G.; Ferreira, R., A hybrid outer-approximation/benders decomposition algorithm for the single allocation hub location problem under congestion, Oper. Res. Lett., 39, 5, 329-337, (2011) · Zbl 1235.90078
[9] Ding, F.; Tian, Z.; Jin, T., Maintenance modeling and optimization for wind turbine systems: a review, 2013 International Conference on Quality, Reliability, Risk, Maintenance, and Safety Engineering (QR2MSE), 569-575, (2013)
[10] Froger, A.; Gendreau, M.; Mendoza, J.; Pinson, E.; Rousseau, L.-M., Maintenance scheduling in the electricity industry: a literature review, Eur. J. Oper. Res., 251, 3, 695-706, (2016) · Zbl 1346.90271
[11] Froger, A.; Gendreau, M.; Mendoza, J.; Pinson, E.; Rousseau, L.-M., Solving a wind turbine maintenance scheduling problem, J. Schedul, (2017)
[12] Gendron, B.; Scutellà, M.; Garroppo, R.; Nencioni, G.; Tavanti, L., A branch-and-benders-cut method for nonlinear power design in Green wireless local area networks, Technical Report CIRRELT-2014-42, (2014), CIRRELT
[13] Hooker, J. N.; Ottosson, G., Logic-based benders decomposition, Math. Program., 96, 1, 33-60, (2003) · Zbl 1023.90082
[14] Irawan, C.; Ouelhadj, D.; Jones, D.; Stålhane, M.; Sperstad, I., Optimisation of maintenance routing and scheduling for offshore wind farms, Eur. J. Oper. Res., 256, 1, 76-89, (2017) · Zbl 1394.90278
[15] Jensen, T.; Toft, B., Graph coloring problems, 39, (2011), John Wiley & Sons
[16] Kovács, A.; Erdõs, G.; Viharos, Z.; Monostori, L., A system for the detailed scheduling of wind farm maintenance, CIRP Ann. - Manuf. Technol., 60, 1, 497-501, (2011)
[17] Laporte, G.; Louveaux, F. V., The integer l-shaped method for stochastic integer programs with complete recourse, Oper. Res. Lett., 13, 3, 133-142, (1993) · Zbl 0793.90043
[18] Naoum-Sawaya, J.; Elhedhli, S., An interior-point benders based branch-and-cut algorithm for mixed integer programs, Ann. Oper. Res., 210, 1, 33-55, (2010) · Zbl 1284.90042
[19] Östergård, P., A new algorithm for the maximum-weight clique problem, Nordic J. Comput., 8, 4, 424-436, (2001) · Zbl 1003.68117
[20] Östergård, P., A fast algorithm for the maximum clique problem, Discrete Appl. Math., 120, 1, 197-207, (2002) · Zbl 1019.05054
[21] Sadykov, R., A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates, Eur. J. Oper. Res., 189, 3, 1284-1304, (2008) · Zbl 1144.90010
[22] Thorsteinsson, E., Branch-and-check: a hybrid framework integrating mixed integer programming and constraint logic programming, (Walsh, T., Principles and Practice of Constraint Programming CP 2001, Lecture Notes in Computer Science, 2239, (2001), Springer Berlin Heidelberg), 16-30 · Zbl 1067.68677
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.