A branch-and-check approach for a wind turbine maintenance scheduling problem. (December 2017)

• Record Type: Journal Article
• Authors: Froger, Aurélien; Gendreau, Michel; Mendoza, Jorge E.; Pinson, Eric; Rousseau, Louis-Martin
• Is Part Of: Computers & operations research. Volume 88(2017)
• Page Start: 117
• Page End: 136
• Publication Date: 2017-12
• Subjects: Scheduling -- Maintenance -- Benders decomposition -- Branch-and-check -- Cuts; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.07.001
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We tackle an onshore wind turbine maintenance scheduling problem. We introduce two integer linear programming formulations of the problem. We propose a branch-and-check approach for the problem. We describe problem-specific cuts. The B&C approach delivers optimal or high-quality integer solutions. Abstract: 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.