Aurélien Froger

Michel Gendreau

Jorge E Mendoza

Eric Pinson

Louis-Martin Rousseau

A branch-and-check approach for a wind turbine maintenance scheduling problem

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.

Introduction

The energy sector is being challenged to produce low-carbon electricity, and so the share of renewables has significantly increased in recent years. Boosted by the need to mitigate climate change and adaptation support (e.g., tax incentives, the Paris climate change agreement) as well as the constantly decreasing cost of turbines, wind energy is currently the world's fastest-growing source of electricity (63 GW of new capacity in 2015). It accounts for around 3.3% of world electricity production 1 .

Although the availability factor of wind turbines exceeds 95% 2 , their capacity factor 3 is usually around 30-40% as a result of the variability of wind and of design decisions (for a fixed wind speed, the larger the blades the more electricity the turbine can produce). The impact of operational decisions is also non-negligible. As the wind industry grows, the reliability and profitability of wind farms naturally becomes one of the priorities of the sector. In this context, the efficient scheduling of wind turbine maintenance operations is essential to prevent unnecessary downtime and excessive operational costs.

Maintenance planning and scheduling has been widely studied in the electricity industry, particularly for thermal power plants; see Froger et al. (2016) for a comprehensive review. Many of the existing methods are not applicable to the wind power industry, where the impact of shutting down equipment depends on an uncontrollable factor: the weather. Studies of maintenance optimization in the wind energy sector primarily focus on reliability-centered maintenance (RCM). RCM is a methodology incorporating reactive, preventive, and condition-based maintenance decisions. These decisions, essentially taken under financial considerations, are mostly based on monitoring and on the use of failure prediction models. Studies usually focus on a single turbine or a single wind farm and explore why failures happen, what should be done when they occur, and how they can be predicted or prevented. See [START_REF] Ding | Maintenance modeling and optimization for wind turbine systems: A review[END_REF] for a survey. The results of these studies can help to define the preventive maintenance operations that need to be performed in the short term. However, they may provide only rough estimates of turbine downtime and lost production. Indeed, it is difficult to produce a maintenance plan in which all the maintenance operations are scheduled during periods where the wind speed is below 3.5 m.s ¡1 , which is too low to produce electricity. This is because human resources is a major bottleneck.

To the best of our knowledge, only a few studies have addressed turbine maintenance scheduling considering fine-grained resource management. [START_REF] Kovács | A system for the detailed scheduling of wind farm maintenance[END_REF] scheduled maintenance for onshore wind turbines over a one-day horizon. They aimed to minimize lost production due to maintenance and failures. They solved an integer linear programming (ILP) formulation of the problem with a commercial solver. For offshore wind farms, [START_REF] Irawan | Optimisation of maintenance routing and scheduling for offshore wind farms[END_REF] solved a maintenance routing and scheduling problem minimizing labor, travel, and penalty costs. They proposed a method based on Dantzig-Wolfe decomposition in which the feasible routes for each vessel are generated a priori.

We consider the wind turbine maintenance scheduling problem, focusing on onshore wind farms, introduced by [START_REF] Froger | Solving a wind turbine maintenance scheduling problem[END_REF]. The problem is to provide a maintenance plan over a short-term horizon that maximizes wind electricity production while taking into account fine-grained resource management involving task assignments to a multi-skilled workforce. [START_REF] Froger | Solving a wind turbine maintenance scheduling problem[END_REF] introduced several models based on ILP and constraint programming (CP). They found that the computational time grows prohibitively with problem size, and they therefore proposed a CP-based large neighborhood search (CPLNS) approach.

The primary contribution of this paper is an efficient exact approach for the wind turbine maintenance scheduling problem. We decompose the problem into a task scheduling subproblem and a technician-to-task assignment (TTA) subproblem, and we solve it using a branch-and-check (B&C) approach. While solving the task scheduling subproblem, we discard, via cuts throughout the branch-and-bound tree, maintenance plans that cannot be performed by the technicians. In addition to the generic Benders cuts, we introduce problem-specific cuts and demonstrate they are key to speeding up the convergence of the approach.

The remainder of this paper is organized as follows. In Section 1 we describe the problem. In Section 2 we introduce new ILP formulations, and in Section 3 we present a B&C approach as an exact solution method.

In Section 4 we discuss experiments with the 160-instance testbed proposed by [START_REF] Froger | Solving a wind turbine maintenance scheduling problem[END_REF]. Finally, in Section 5, we present our conclusions and discuss future research.

Problem statement

The goal is to schedule a set I of maintenance tasks over a discrete and finite planning horizon T while maximizing the revenue from the electricity production of a set W of wind turbines. The turbines are spread across a set of locations L (consisting of wind farms and possibly home depots). Let l w L be the location of turbine w W and l i the location where task i I is performed.

The time horizon is a totally ordered set partitioned into |T | periods of identical length. T spans several days from a set D. Let T d be the time periods of day d D. Moreover, since the execution of a task can impact production during non-working hours, we introduce a special time period (a rest period ) between two consecutive days to represent a night or weekend. The maintenance tasks are non-preemptive, but they are interrupted during the rest periods if they cover different days (e.g., a technician can start a task at the end of one day and complete it at the beginning of the next).

Although we do not include rest periods in T , in the objective function we consider the loss of production generated by tasks covering these periods. In more detail, we use two parameters to define the impact of the tasks on the availability of the turbines. Binary parameter b wi is 1 if and only if task i I shuts down turbine w W when technicians are working on the task. Binary parameter r b wi is 1 if and only if task i shuts down turbine w during the rest periods it covers. Parameters b wi and r b wi are 0 if turbine w is not located where the task i is performed (i.e., if l i $ l w ). A maintenance task can shut down more than one turbine, but this is rare in practice.

We have a finite set R of maintenance technicians. Each technician has one or more skills from a set S, and we introduce a binary vector λ r over S such that λ rs 1 if and only if technician r has skill s S. We assume that a technician cannot perform more than one task during a given period. Each task i I requires technicians with a specific skill s i S. For convenience, we define R i to be the set of technicians that can perform task i (i.e., R i tr R | λ rsi 1u).

To avoid expensive travel time, technicians must spend each day on tasks at compatible locations. Compatible locations are those that can be reached from each other in travel times that are negligible with respect to the duration of a time period. Let t max be the maximum travel time between two locations that we can consider to be "negligible." The top of Figure 1 shows the locations that are compatible with l 1 (i.e., l 2 and l 3 ).

To model these daily location-based incompatibilities (DLBIs), we introduce the binary parameter σ ll I taking the value 1 if and only if locations l and l I are compatible (naturally σ ll I σ l I l ). The bottom of Figure 1 shows the four sets of compatible locations in our example. During a single day, a technician can execute tasks at l 1 and l 2 or l 3 but not both. The maintenance tasks usually take hours (or days), and therefore the technicians travel between only a few locations during a single day.

Each technician r R has an individual availability schedule expressed by a binary vector π r , with π t r 1 if and only if r is available during period t T . The availability schedule takes into account training days, vacations, and assignments to tasks that are not part of the optimization 4 . When technician r is not available 4 tasks that have been already started before the beginning of the planning horizon or that are performed along with external companies during period t, his or her location is fixed to l t r L. For vacations and training days, this parameter is set to a dummy location l ¦ such that dl L, σ l ¦ l 1. We assume that all the technicians work the same shift, which is common practice in this industry.

Each task i I has a set M i of execution modes. For each mode m M i , there is an associated task duration d im and a number q im of required technicians. It is forbidden to switch modes after starting a task.

Moreover, the technician assigned to a task must complete it, even if the task covers one or more rest periods.

The tasks must be executed during specific periods. These take into account the availability of spare parts and the external restrictions imposed by the operator. For safety, no task can be executed when the forecast wind speed is too strong. To model these restrictions, we introduce the binary parameter γ t i that is 1 if and only if task i I can be performed during period t T . We also impose nonoverlapping constraints on each subset of tasks that belongs to the set ov pIq.

The objective is to determine a schedule that maximizes the revenue generated by electricity production while satisfying the constraints described above. Let g t w be the revenue generated by turbine w if it can produce electricity during period t T . Similarly, let r g d w be the revenue generated by turbine w if it can produce electricity during the rest period following day d D. These revenues are estimated based on forecast wind speed.

It is possible to postpone some tasks into the next planning horizon. When task i is postponed, there is penalty of o i ¥ 0. The value of the penalty includes an estimate of the loss of revenue induced by the postponement and the future planning of the task and may include outsourcing costs (the decision-maker will decide if the task should be outsourced rather than postponed). It also depends on the priority of the task (the higher the priority, the higher the penalty). The priority is based on reliability considerations (the longer a delay, the higher the probability of failure) and contract commitments. If the penalty is sufficiently high, a task will be postponed only if there is no available technician. In short, the objective function corresponds to the difference between the revenue and the penalties. We summarize the notation used in A.

We now analyze the complexity of this wind turbine maintenance scheduling problem (WTMSP). Let us first define the decision problem WTMSP dec associated with WTMSP. In this problem, a parameter G R is given as a lower bound on the value of the objective function. WTMSP dec involves determining if there exists a task schedule such that the objective value is greater than or equal to G. By polynomially reducing the cumulative scheduling problem5 , which is known to be NP-complete in the strong sense [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF], to WTMSP dec , we easily prove that WTMSP is strongly NP-hard. In some special cases, WTMSP is trivial.

For instance, if the penalties are all 0, it is optimal to delay all the tasks. A similar observation is that each task with a penalty of 0 can be set to delayed a priori, without affecting the value of the optimal solution.

Integer linear programming formulations

In this section, we propose an ILP model that will serve as a baseline for the exact approach. This formulation is broadly inspired by the model introduced by [START_REF] Froger | Solving a wind turbine maintenance scheduling problem[END_REF]. We then propose an alternative formulation of the problem that provides a better basis for comparison.

Baseline formulation

The baseline formulation relies on the a priori generation for each task of all possible combinations of start period and execution mode. Such a combination is called a plan6 ; see Since the number of periods is limited and there are only a few execution modes, the total number of plans is reasonable. Let P be the set of plans, i p the task involved in plan p P, and P i the set of all plans involving task i (i.e., P i tp P|i p iu). For each task i, we also create a plan p 0 i P i representing the postponement of the task. For a plan p, the execution periods of i p are expressed by a binary vector a p over T such that a t p 1 if and only if i p is executed during period t T . Let S p and C p be the start and finish periods of plan p (i.e., S p min tT a t p t and C p max tT a t p t). Similarly, we introduce a binary vector r a p over D such that r a d p 1 if and only if i p covers the rest period following day d D. Let D p be the set of days covered by plan p. For convenience and with a slight abuse of notation, we introduce the parameters s p , l p , b wp , and r b wp equal to s ip , l ip , b wip , and r b wip . Moreover, we denote by R p the set of technicians that can be assigned to plan p. Specifically, R p contains the technicians r R ip such that for every period t we have π t r ¥ a t p and for every day d D p and every period t T d , we have π t r 1 or both π t r 0 and σ lpl t r 1. Let q p be the number of technicians required for plan p. The fundamental difference between our model and that of [START_REF] Froger | Solving a wind turbine maintenance scheduling problem[END_REF] is that our model does not assign technicians to plans. Clearly, it does not matter which specific technicians we assign to plans with the same start and finish periods, the same location, and the same skill.

pPi x p 1 di I, (2)
iB pPi

a t p x p ¤ 1 dB ov pIq , dt T , (3)
f t w pPi b wp a t p x p ¤ 1 dw W, di I, dt T , (4)
r f d w pPi r b wp r a d p x p ¤ 1 dw W, di I, dd D, (5) iI|si
S pPi a t p q p x p ¤ |R t S | dt T , d S S, (6)
ŗ R h y rh p P h q p x p dh H, (7)
ḩH l a t h y rh ¤ π t r v t rl dr R, dl L, dt T , (8)
ļL v t rl 1 dr R, dt T , (9)
v t rl t r 1 dr R, dt T s.t.π t r 0, (10)
v t rl ļI L|σ ll I0 v t I rl I ¤ 1 dr R, dd D, dpt, t I q T d ¢ T d , t $ t I , dl L, (11)
x p t0, 1u dp P, (12)

f t w t0, 1u dw W, dt T , (13)
r

f d w t0, 1u dw W, dd D, (14)
y rh t0, 1u dh H, dr R h , (15)
v t rl t0, 1u dr R, dl L, dt T (16)
The objective in (1) is the difference between the revenue generated by the turbines and the postponement penalties. Constraints (2) ensure that at least one plan involving each task is selected (i.e., each task is either executed or postponed). Constraints (3) are the nonoverlapping constraints. Constraints (4) and ( 5) compute the impact of the tasks on the availability of the turbines during the periods of T and the rest periods. Constraints (7) ensure that the technician requirements are fulfilled: the number of technicians assigned to every pattern h must be equal to the number of technicians required by the selected plans associated with h. Constraints (8) couple the locations of the technicians to the tasks they perform. Constraints (9) prevent technicians from performing multiple tasks during the same period. When technicians are not available, constraints (10) ensure compliance with their known locations. Constraints (11) define the DLBIs. Finally, constraints (12)-( 16) are the binary restrictions.

Sometimes commercial solvers can more easily solve models with redundant constraints (because of their different structure). With this in mind, we include the cumulative scheduling constraints (6) in rP 1 s although they can be deduced from constraints ( 7) and (8). To build these constraints, we introduce for each period t T the bipartite graph G t ppS, R t q , U t q in which, with a slight abuse of notation, vertices from S represent skills, vertices from R t indicate the technicians available during period t (i.e., R t tr R|π t r 1u), and edges from U t are defined as follows: ds S, dr R t ps, rq U t if and only if λ rs 1. Via a generalization of the König-Hall theorem, constraints (6) then correspond to a necessary and sufficient condition for the existence of a maximum cardinality b-matching (MCbM) from S to R t . Here the function b is defined by bpsq °iI|sis °pPi a t p q p x p for every vertex s in S, and by bprq 1 for every vertex r in R t . To express these constraints, let R t S tr R|hs S, λ rs 1 π t r 1qu be the set of technicians available during period t with at least one skill in subset S S. The number of these constraints is exponential: 2 |S| ¡ 1 ¨¢ |T |). In our experiments, however, the number tends to be small; we therefore add them all to our model.

Alternative formulation

A potential improvement to the model concerns the space-time tracking of the technicians. Observing that the number of constraints ( 11) is usually large, we develop an alternative technician management strategy. This strategy is based on the daily assignment of each technician to a set of compatible locations. To compute these sets, we compute all the maximal cliques (cliques that cannot be enlarged) in a graph where each vertex represents a location, and there is an edge between two vertices if the underlying locations l and l I can be visited during the same day by the same technician (i.e., σ ll I 1). Figure 2 illustrates the construction of the graph and highlights the maximal cliques. We use the algorithm of [START_REF] Bron | Algorithm 457: Finding all cliques of an undirected graph[END_REF] to find these cliques.

Figure 2: Construction of the graph used to compute the maximal cliques on an example.

Let K be the set of all maximal cliques in the graph. We define K d r to be the set of cliques to which technician r can be assigned during day d, i.e., tk K | dt T d , π t r 1 pπ t r 0 l t r kqu. We then introduce binary variable u d rk that is 1 if and only if during day d D technician r R can perform tasks only at locations included in clique k K d r . Let d t be the day to which period t belongs. We can track the location of the technicians with the following constraints: The model resulting from replacing constraints (8), ( 9), ( 10), (11), and ( 16) by ( 17), ( 18), ( 19), and (20) in the baseline formulation rP 1 s is called rP 2 s.

ķ K d r u d rk 1 dr R, dd D, (17) ḩH|rR h a t h y rh ¤ π t r dr R, dt T , (18
3 Exact solution approach

Problem decomposition

The exact approach presented in this section takes advantage of the intrinsic decomposition of the problem into a task scheduling subproblem and a TTA subproblem. The scheduling problem selects a plan for each task to maximize the difference between the revenue from the electricity production and the postponement penalties. In this problem, technician considerations are partially eliminated. Given a fixed selection of plans, the TTA subproblem determines if the technician requests can be satisfied while imposing the DLBIs and the individual resource availabilities. We aim to coordinate these two problems. Note that an optimal solution to the scheduling problem leading to a feasible TTA is optimal for the overall problem.

We first introduce the scheduling problem. An initial formulation rShP 1 s is:

rShP 1 s max wW £ ţT g t w f t w ḑD r g d w r f d w ¡ pP o p x p (21)
subject to:

(2), ( 3), ( 4), ( 5), ( 6), ( 12), ( 13), ( 14)

The cumulative scheduling constraints (6) in rShP 1 s help to speed up the convergence of a coordination procedure between the two problems. Solving the task scheduling problem without any information on the availability of the technicians would result in a selection of plans that would be unlikely to lead to a feasible TTA.

We now assume that we have a solution to rShP 1 s, which is a fixed selection px p q pP of plans (hereafter referred to simply as x). An ILP formulation rSP 2 pxqs of the TTA subproblem is:

rSP 2 pxqs min ḩH θ h (22) subject to: ŗ R h y rh θ h p P h q p xp dh H, (23) ḩH
s.t. rR h y rh ¤ 1 dr R, dH C max pGq , (24)
θ h ¥ 0 dh H, (25)
y rh t0, 1u dh H, dr R h (26)
We introduce slack variables pθ h q hH for the technician requirement constraints (23). The unavailability periods of each technician are respected by the definition of the set R h . The clique constraints (24) ensure that the TTAs comply with the DLBIs. Specifically, set C max pGq contains all the maximal cliques in graph G where each vertex represents a pattern in H, and there is an edge between two vertices if the underlying patterns h and h I cannot be visited by the same technician. This edge exists if the following clause holds:

pS h I ¤ C h S h ¤ C h Iq phd D, T d tS h , S h 1, ..., C h u $ r T d tS h I, S h I 1, ..., C h Iu $ rq σ l h l h I 0 ¨(27)
One can visualize G as an extended version of an interval graph. To define the TTA subproblem for a given solution x (and therefore to compute all the maximal cliques), we need only to consider the patterns of Hpxq th H | °pP h q p xp ¡ 0u. This significantly reduces the number of variables in rSP 2 pxqs and the number of clique constraints (24) since we consider a subgraph of G.

The TTA subproblem is NP-complete; this follows from its equivalence to a L-coloring problem. Nonetheless, under certain assumptions, it is solvable in polynomial time. We omit the details here; see B for a discussion of the complexity of the TTA subproblem.

We observe that rSP 2 pxqs always has a feasible solution because of the slack variables pθ h q hH . However, the TTA subproblem is feasible only if the value of the optimal solution is zero.

When the value of the optimal solution to rSP 2 pxqs is strictly positive (i.e., the TTA subproblem is infeasible), one can use a combinatorial Benders (CB) cut [START_REF] Codato | Combinatorial Benders' cuts for mixed-integer linear programming[END_REF] to discard the current solution x in rShP 1 s. This cut is similar to those defined for logic-based Benders decomposition [START_REF] Hooker | Logic-based Benders decomposition[END_REF] and have some similarities with the integer optimality cuts for the integer L-shaped method [START_REF] Laporte | The integer L-shaped method for stochastic integer programs with complete recourse[END_REF]. It is also known as a no-good cut. Observing that a solution always contains |I| nonzero variables x p since exactly one plan must be selected per task, and using the binary variables px p q pP , we can define a CB cut as follows (with Ppxq tp P|x p 1u):

pPpxq x p ¤ |I| ¡ 1 (28)
Clearly, this cover inequality requires at least one of the variables in x to change its value.

Since the feasible region of our problem is bounded, the number of integer points satisfying all the constraints of rShP 1 s is finite, and thus the same holds for the number of CB cuts. Let F be the set of all solutions x to rShP 1 s that lead to an infeasible TTA subproblem. The overall maintenance scheduling problem can therefore be reformulated as the following master problem rPs:

rPs max wW £ ţT g t w f t w ḑD r g d w r f d w ¡ pP o p x p
subject to:

(2), ( 3), ( 4), ( 5), ( 6), ( 12), ( 13), ( 14)

pPpxq x p ¤ |I| ¡ 1 dx F (28)
We denote by rRMPs a restricted master problem (RMP) of problem rPs that contains at most a small subset of constraints (28). To efficiently solve the problem while exploiting this Benders-like decomposition, we adopt a B&C approach. The B&C framework was introduced by [START_REF] Thorsteinsson | Branch-and-check: A hybrid framework integrating mixed integer programming and constraint logic programming[END_REF]; it is primarily designed for LP and CP hybridization. Cuts are generated on the fly during the solution of the initial RMP. At each integer node of the branch-and-bound tree, the corresponding solution is sent to the TTA subproblem. Benders and/or problem-specific cuts are generated to discard solutions leading to an infeasible TTA. [START_REF] Thorsteinsson | Branch-and-check: A hybrid framework integrating mixed integer programming and constraint logic programming[END_REF] applied B&C to a planning and scheduling problem, while [START_REF] Sadykov | A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates[END_REF] used it for a complex scheduling problem on a single machine. See [START_REF] Beck | Checking-up on branch-and-check[END_REF] for a survey. This approach is also referred to as a

Benders-based branch-and-cut algorithm (Naoum-Sawaya and Elhedhli, 2010) and as a branch-and-Benders-cut method [START_REF] Gendron | A branch-and-Benders-cut method for nonlinear power design in green wireless local area networks[END_REF]. It has been used to solve several types of problems: hub location [START_REF] De Camargo | A hybrid outer-approximation/Benders decomposition algorithm for the single allocation hub location problem under congestion[END_REF], production routing under demand uncertainty [START_REF] Adulyasak | Benders decomposition for production routing under demand uncertainty[END_REF], location-design [START_REF] Gendron | A branch-and-Benders-cut method for nonlinear power design in green wireless local area networks[END_REF], facility location and network design (Naoum-Sawaya and Elhedhli, 2010), and hop-constrained survivable network design [START_REF] Botton | Benders decomposition for the hop-constrained survivable network design problem[END_REF]. [START_REF] Botton | Benders decomposition for the hop-constrained survivable network design problem[END_REF] reported a significant improvement using this approach instead of the classical implementation of Benders decomposition, while [START_REF] Gendron | A branch-and-Benders-cut method for nonlinear power design in green wireless local area networks[END_REF] outlined the benefits in terms of solution quality, scalability, and robustness.

The efficiency of B&C is primarily based on the constraints we generate to cut off infeasible solutions to rRMPs. In the following subsection, we describe our cut generation procedure.

Cut generation procedure

For every solution x to rRMPs, we must check the feasibility of the TTA subproblem. We can solve rSP 2 pxqs to optimality using a commercial solver, but this approach has two major drawbacks. First, since rSP 2 pxqs is a pure ILP model, solving it may be too time-consuming. Second, if the optimal value of rSP 2 pxqs is strictly positive, the resulting CB cut (28) may be too weak because it discards only the current solution. To overcome these drawbacks and to build stronger cuts, we propose three cut generation strategies based on different approximations to the TTA subproblem.

Benders feasibility cuts

Let rSP LR 2 pxqs be the linear relaxation of rSP 2 pxqs. Constraints (26) of rSP 2 pxqs are replaced in rSP LR 2 pxqs by the following constraints:

y rh ¤ 1 dh H, dr R h , (29)
y rh ¥ 0 dh H, dr R h (30)
We can generate cuts based on the solution to the linear relaxation rSP LR 2 pxqs of rSP 2 pxqs. Since a solution x to rRMPs is feasible for the whole problem only if the optimum of rSP LR 2 pxqs is zero, x is feasible for the whole problem only if the optimum of the dual rDSP LR 2 pxqs of rSP LR 2 pxqs is less than or equal to zero (by the duality theorem). Let us associate the dual variables ι h , H r , and ϕ rh with constraints ( 23), ( 24), and (29), respectively. The objective function of rDSP LR 2 pxqs, denoted Θ xpι, , ϕq, is:

Θ xpι, , ϕq ḩH £ p P h q p xp ι h ŗ R h ϕ rh ŗR ḨCpHq s.t. r hH R h H r (31)
Let D be the polyhedron defined by the constraints of the dual problem rDSP LR 2 pxqs. Since rSP LR 2 pxqs always has a feasible solution, rDSP LR 2 pxqs is bounded and achieves its optimum at an extreme point of D. Let η 1 , η 2 , ..., η n (with η k pι k , k , ϕ k q) be the finite set of extreme points of D. By the weak duality theorem, the following inequalities must hold to ensure the existence of a zero-valued solution to rSP LR 2 pxqs:

Θ x pι k , k , ϕ k q ¤ 0 dk t1, ..., nu (32)
Constraints ( 32) are the classical Benders feasibility (BF) cuts. Because the constraint matrix of rSP LR 2 pxqs

is not totally unimodular, relaxing the integrality constraints ( 26) may lead to a fractional solution. A cut generation algorithm responsible for identifying violated constraints (32) will therefore not, in general, find a feasible solution to rPs. Nevertheless, identifying violated BF cuts may help us to generate fewer CB cuts. The advantages are: i) BF cuts can be computed by solving a continuous linear model, and ii) they may discard more solutions than just the current solution to rRMPs. One drawback of BF cuts is that they are generic and therefore likely to be weak.

Problem specific-cuts

For the efficient coordination of the task scheduling and the TTA subproblem, we must find reduced subsets of plans causing the infeasibility of the latter. In the following subsections, we describe two problem-specific procedures to find these reduced subsets, and we show how we build stronger problem-specific cuts.

First, we introduce the following TTA requirements:

[C1] Each task must be performed by technicians with the appropriate skill.

[C2] A technician cannot perform more than one task during a given period.

[C3] The technician assignments must not violate the DLBIs.

[C4] Each technician has an availability schedule that must be respected.

[C5] The technician assigned to a task must complete it, even if it covers some rest periods.

Obviously, the TTA subproblem is feasible if and only if

[C1], [C2], [C3], [C4]
, and [C5] are satisfied.

Second, to simplify the discussion, we introduce the concept of jobs. A job refers to either a pattern or a technician unavailability period. More precisely, a job j is defined by pl j , S j , C j , s j , R j , q j q, where l j is the location where j is executed, S j its start period, C j its finish period, S j a set of skills such that the technician performing j must have at least one of these skills, R j the set of technicians who can perform j, and q j the number of technicians required for job j. For every unavailability period of technician r R occurring at period t (t T such that π t r 1), we build an artificial job defined by pl t r , t, t, S r , tru, 1q where S r ts S|λ rs 1u

is the set of skills of technician r. If a technician is unavailable during contiguous periods and if he or she is assigned each time to the same location (with regard to l t r ), we associate only one job with these unavailability periods7 . Let J R be the set of jobs associated with the technician unavailability periods. We also associate with each solution x to rRMPs a set J pxq of jobs. We build this set in two steps. First, we add to J pxq all the jobs of J R . Then, for every pattern h H such that q h pxq ¡ 0 (with q h pxq °pP h q p xp ), we create a job defined by pl h , S h , C h , ts h u, R h , q h pxqq. Let J H pxq be the set of jobs associated with patterns. We also define the parameter h j to be the pattern associated with job j J H pxq.

Maximum cardinality b-matching cuts

In this section, we extend the idea used to generate constraints (6) by partially taking into account [C3] and [C5] while fully taking into account [C1], [C2], and [C4]. More precisely, when building the potential assignments of technicians to tasks, we jointly consider the unavailability periods of the technicians and the restriction of not switching technicians during the execution of a task. We then show that the TTA subproblem can be approximated by a series of MCbM problems (as many as the length of the time horizon).

First, for a fixed period t T and a given solution x to rRMPs, we introduce an undirected graph q G t pxq composed of:

• A set of vertices q V t where q

V t q V t J q V t R :
q V t J : for each job j J pxq such that S j ¤ t ¤ C j , we add a vertex in q V t J . Parameter j ν denotes the job associated with ν q V t J . Conversely, ν j denotes the vertex associated with job j.

-q V t R : a vertex of q V t
R represents a technician r R during period t. Let r v be the technician associated with ν q

V t R . • A set of edges q U t such that dν 1 q V t J , dν 2 q V t R : pν 1 , ν 2 q q U t ô r ν2 R jν 1 .
We formally describe in Proposition 3.1 and Corollary 3.1 the link between the TTA subproblem and a series of MCbM problems defined in the above graphs.

Proposition 3.1. Let x be a solution to rRMPs and assume that [C3] and [C5] are not taken into account. The TTA subproblem for x is equivalent to a series of |T | MCbM problems in q G t pxq where for each period t T function b is defined by b ν q jν for ν q V t J and by b ν 1 for ν q

V t R .
Proof. Since [C3] and [C5] are not taken into account, the TTA subproblem can be independently solved for each period of the planning horizon.

Assuming that during each period t we can find a MCbM in each of the graphs G t pxq with a cardinality equal to °jPJ p xq 1 rS j ,C j s ptqqj, we can immediately build a solution to the TTA subproblem from the selected edges by making the underlying assignments.

Assume now that we have a feasible solution to the TTA subproblem. For each period t, we can build a b-matching in q G t pxq from the working schedule of each technician during this specific period. If technician r R is assigned to pattern h H during period t, we select the edge pν1, ν2q U where jν 1 j h (j h denoting the job associated with pattern h) and rν 2 r. This construction ensures the building of a b-matching. Moreover, since all the requirements are fulfilled, this b-matching has maximum cardinality.

Corollary 3.1. If we assume that [C3] and [C5] are not taken into account, the TTA subproblem is feasible for a solution x to rRMPs if and only if the MCbM in q G t pxq for each period t T contains °jJ pxq 1 rSj,Cjs ptqq j edges of q U t .

Proof. This is a direct consequence of Proposition 3.1.

Given a fixed period t, finding the MCbM in q G t pxq from q V t J to q V t R is equivalent to solving a maximum flow problem in a slightly modified version of this graph. We use this equivalence to derive new cuts. Let p G t pxq be this new directed graph and p V t and p U t the new sets of vertices and arcs. We build p G t pxq as follows:

1. We define p V t q V t tω t , ω t u where ω t and ω t represent the source and sink vertices. 2. For every directed arc pν 1 , ν 2 q p U t , let γ max ν1ν2 be its maximal capacity and f ν1ν2 the flow on the arc. We formally define p U t as follows:

• dν 1 q V t J , dν 2 q V t R : pν 1 , ν 2 q p U t ô r ν2 R jν 1 and γ max ν1ν2 V • dν q V t J : pω t , νq p U t and γ max ω t ν q jν • dν q V t R : pν, ω t q p
U t and γ max νω t 1 Let f ¦ pt, xq be the value of the maximum flow in p G t pxq. If f ¦ pt, xq °ν q V t J q jν then the jobs of J pxq covering t cannot be fully scheduled during this period. We therefore have to discard the solution x. We first compute the minimum flow cut in p G t pxq (see Figure 3). This cut can be described by two disjoint sets p V t p q and p V t p¡q where the source ω t and sink ω t belong to p V t p q and p V t p¡q, respectively. For cut modeling purposes, we also introduce the sets q V t J p¡q q Applying the max-flow/min-cut theorem to p

V t J p V t p¡q, q V t J p q q V t J p V t p q, q V t R p¡q q V t R p V t p¡q, and q V t R p q q V t R p V t p q.
G t pxq, we have f ¦ pt, xq ν q V t J p¡q γ max ω t v v q V t R p q γ max vω t (33)
If we replace the capacity of each arc by its value, we obtain

f ¦ pt, xq ν q V t J p¡q q jν | q V t R p q| (34)
The valid minimum flow cut (that invalidates x) is

ν q V t J p¡q q jν | q V t R p q| ¥ ν q V t J q jν (35)
which we can reformulate as follows:

ν q V t J p q q jν ¤ | q V t R p q| (36)
Inequality (36) leads to the following valid constraint (hereafter referred to as a MCbM cut) that eliminates

x from the feasible region of rRMPs:

jJ H pxq s.t. νj q V t J p q pP h j q p x p ¤ | q V t R p q| ¡ jJ R s.t. νj q V t J p q q j ( 37
)
It is possible to strengthen the MCbM cut by considering its composition. First, | q V t R p q| $ |R| because at least one of constraints (6) would be unsatisfied otherwise. This also implies that | q V t R p¡q| $ 0. By definition of the max-flow/min-cut, the technicians associated with q V t R p¡q are either not connected to any other vertices or they are assigned to j J pxq such that ν j q V t J p¡q, but they cannot be assigned to any j such that ν j q V t J p q.

Either these technicians do not have the required skills for those jobs or they have at least one unavailability period that prevents the assignment. We deduce that inequality (36) is also valid for every potential job that covers period t and cannot be performed by any of the technicians associated with a vertex of q V t R p¡q. The MCbM cut (37) can therefore be rewritten as ḩH

Ψph, t, q V t R p¡qq p P h q p x p ¤ | q V t R p q| ¡ jJ R s.t. νj q V t J p q q j ( 38
)
where Ψph, t, q V t R p¡qq is 1 if and only if pattern h covers period t and none of the technicians associated with q V t R p¡q can be assigned to h.

We must solve the MCbM problem only for every period t where at least one technician cannot be assigned to a job because of an unavailability period occurring at a period other than t. Otherwise, constraints (6) are necessary and sufficient conditions for the existence of b-matchings with the desired cardinality.

Maximum-weight clique cuts

Another strategy to discard a solution x to rRMPs that leads to an infeasible TTA relies on showing that it is impossible to assign the technicians to the tasks without violating the DLBIs. Since the DLBIs are defined by day, this search decomposes into |D| independent searches in which for each d D we consider only the jobs of J pxq that cover d. During the search, it is also necessary to take into account the skills required to perform the different jobs. For a fixed subset S S, we consider only the jobs j J pxq such that S j S $ r and the technicians with at least one skill in this subset. This procedure increases the likelihood of finding violated DLBIs if the current solution to the RMP does not lead to a feasible TTA subproblem. This is particularly true when the ratio between the requirements and the number of available technicians varies widely across skills.

To look for violated DLBIs, we solve for each day d and each subset S S a maximum-weight clique

(MWC) problem in an undirected graph r G d S pxq. The graph r G d
S pxq is composed of:

• A set of vertices r V d
S such that each vertex maps a job j of set J pxq that i) covers day d (i.e., T d tS j , ..., C j u $ r) and ii) requires at least one of the skills in S (i.e., S j S $ r). Let j ν be the job associated with ν r

V d S .
We associate with every vertex ν a weight equal to the number of technicians q jν required to perform job j ν .

• A set of edges r U d S where for ν 1 , ν 2 r

V d S : pν 1 , ν 2 q r U d S ô ν 1 $ ν 2 ¡ S jν 2 ¤ C jν 1 S jν 1 ¤ C jν 2 ¨ σ lj ν 1 lj ν 2 0 ©
There is an edge between ν 1 and ν 2 in r G d

S pxq if and only if a technician cannot be assigned to both jobs

νC d S pxq q jν ¤ |R S | (39)
The valid constraint (hereafter referred to as a MWC cut) that discards a solution x to rRMPs is therefore

jJ H pxq s.t. νj C d S pxq pP h j q p x p ¤ |R S | ¡ jJ R s.t. νj C d S pxq q j ( 40
)
This cut simply states that the number of technicians required by the jobs associated with the vertices of the clique must be less than the number of technicians with at least one skill in S. We have derived this cut not only for the MWC but also for all the cliques that have a weight greater than |R S |.

It is possible to tighten the MWC cut ( 40) by adding additional patterns on its left side. We proceed as follows. First, we consider the subgraph G sub pxq of G (G is used to derive the clique inequalities in rSP 2 pxqs) that includes a vertex for pattern h H if i) h HzHpxq (i.e., q h pxq 0), ii) h covers day d, iii) s h S, and iv) if a technician is assigned to h, he or she cannot be assigned to any job involved in C d

jJ H pxq s.t. νj C d S pxq pP h j q p x p ḩHrC d S pxqs p P h q p x p ¤ |R S | ¡ jJ R s.t. νj C d S pxq q j (41)
For efficiency, we reduce the size of G sub pxq since it suffices to consider one vertex for all the patterns with the same location and coverage of the same portion of the day. This remark also applies to r G d S pxq.

Last but not least, to avoid overloading our algorithm, we solve the MWC problem only if i) the sum of the weights of the vertices is greater than the number of available technicians, and ii) during a particular day there are at least two jobs that do not overlap and are executed at incompatible locations. Otherwise, constraints (6) ensure for each day and each subset of skills the nonexistence of a clique with a weight strictly greater than the number of available technicians. We use the algorithms introduced by Östergård (2001) and Östergård (2002) to solve the maximum clique and MWC problems.

Since the approximations to the TTA subproblem described in Sections 3.2.2 and 3.2.3 can be decomposed into a series of small problems, we can potentially identify multiple subsets of plans that cause the infeasibility of the TTA subproblem. This usually leads to the generation of multiple cuts, which is known to significantly improve the efficiency of a cut generation process. We can also consider solving the small problems in parallel.

For clarity, we provide three examples in C to illustrate how we build up the different cuts. For the approximations described in Sections 3.2.2 and 3.2.3, the first two examples show that neither the MCbM nor MWC cuts strictly dominate the other. The third example illustrates a case where the two approximations do not find any cuts although the TTA subproblem is infeasible.

General structure of algorithm

We now provide a full description of our two-stage B&C approach. Figure 4 outlines the general structure.

The two stages are as follows:

Figure 4: Flow chart of our B&C approach.

N.B.: The steps with dashed outlines are performed by an ILP solver.

• Stage 1 (solve a linear relaxation of rPs):

In the first stage we generate potentially useful MCbM and MWC cuts while working with a much easier problem. We consider rShP LR 1 s, the linear relaxation of rShP 1 s ("Initialization 1"). We solve the problem to optimality with an LP solver ("Solve rShP LR 1 s"). We then solve the approximations to the TTA subproblem described in Section 3.2.2 (the MCbM becomes a fractional MCbM) and in Section 3.2.3 (at this stage, we derive a cut only for the MWC) for the continuous solution x of rShP LR 1 s ("Solve MWC and MCbM problems"). If we generate cuts, we add them to rShP LR 1 s ("Add cuts to rShP LR s") and reoptimize the resulting problem. Otherwise, we terminate this first stage ("Cuts? No").

To avoid wasting time generating cuts that may not be useful, we perform at most 100 iterations ("Stop 1"). Note that this stage could have been performed at the root-node of the search tree defined for the second stage. However, our aim is to take advantage of the preprocessing techniques embedded in commercial ILP solvers.

• Stage 2 (Solve the master problem rPs):

In the second stage, we solve the problem by a branch-and-check method implemented on top of a commercial solver. We initialize rRMPs with all the cuts that have been generated during the first stage ("Initialization 2") and we solve it by a branch-and-bound algorithm. For every integer solution x to rRMPs obtained in the branch-and-bound tree ("Solution? integer"), we determine if x is feasible for the TTA subproblem. We start by solving the MCbM and MWC problems ("Solve MWC and MCbM problems").

If this produces at least one cut, we discard the current solution x by adding the generated cut(s) to rRMPs ("Add cuts to rRMPs"). Otherwise, we solve the LP formulation rSP LR 2 pxqs ("Solve rSP LR 2 pxqs").

If we identify a violated BF cut of type ( 32), we add it to rRMPs ("Add cuts to rRMPs"). Otherwise, we cannot determine the feasibility of the TTA subproblem before solving the ILP formulation rSP 2 pxqs ("Solve rSP 2 pxqs"). If its optimal value is strictly positive, we generate a CB cut of type ( 28) and add it to rRMPs ("Add cuts to rRMPs"). Otherwise, we conclude that px, ȳq (with ȳ the solution of rSP 2 pxqs) is a new feasible solution ("New best solution"). Note that the branch-and-bound scheme ensures that px, ȳq is strictly better than the best previous solution. We can therefore update the best solution so far, px ¦ , y ¦ q, to px, ȳq. We terminate this phase ("Stop 2") with the optimal solution to rPs or a feasible solution if the time limit has been reached (if no solution is found within the time limit, one can always consider the feasible solution in which all the tasks are postponed).

From an implementation point of view, we start this stage by simply forwarding an ILP formulation of the RMP to the solver. The cut generation procedure is implemented inside a callback routine that is invoked by the solver at every node of the branch-and-bound tree. The cuts computed during this stage are provided to the solver as lazy constraints. After adding them at a particular node, the solver checks the feasibility of the integer solutions in terms of these constraints. If the candidate solution at an integer node is not feasible, the solver discards it and adds the violated lazy constraints to the active nodes of the branch-and-bound tree.

4 Computational experiments

Instances

We report results for the 160-instance testbed proposed by [START_REF] Froger | Solving a wind turbine maintenance scheduling problem[END_REF]. These instances were randomly generated based on insight into wind prediction and maintenance operations obtained from industrial partners.

Froger et al. ( 2017) considered time horizons of different lengths (5 and 10 days with 2 or 4 periods per day), different numbers of tasks (20,40,80), and different numbers of skills (1 or 3). For each combination of parameters, they generated two categories of instances: five "type A" instances with a tight technician-to-work ratio (i.e., the technicians can perform most but not necessarily all of the tasks during the planning horizon), and five "type B" instances with a regular technician-to-work ratio (i.e., the technicians can perform all the tasks). The resulting 32 families of instances are as representative as possible of the situations that may occur.

The cost of postponement is set in such a way that postponing a task is nonprofitable. We refer to each instance family via "a b c d e" where a, b, c, d, and e refer to the number of periods in the planning horizon, the number of periods within a day, the number of skills, the number of tasks, and the technician-to-work ratio, respectively. For a discussion of the instance generation process see [START_REF] Froger | Solving a wind turbine maintenance scheduling problem[END_REF].

Results

We implemented our algorithms using Java 8 (JVM 1.8.0.25). We use Gurobi 6.5.1 to solve the LP and ILP models. We ran our experiments on a Linux 64 bit-machine, with an Intel(R) Xeon(R) X5675 (3.07 Ghz) and 12 GB of RAM. We set a 3-hour time limit (the CPU times are reported in seconds and rounded to the nearest integer). We implemented the cut generation procedure of our B&C approach using the callback provided by Gurobi 8 . To assess our results, we compute the gap with respect to the optimal solution when it is known, or to the best upper bound found by the solver over all the tests reported, i.e., gap pz U B ¡zq{|z|, where z is the objective of the computed solution and z U B is the objective of the optimal solution or the best upper bound found by any of our methods.

We tested four exact approaches. We present the results for the direct solution of the two ILP formulations of the problem (rP 1 s and rP 2 s). To quantify the impact of the problem-specific cuts of Section 3.2, we present the results of the B&C approach presented in Section 3.3 without (B&C) and with (B&C) the MCbM and MWC cuts. These approaches differ only in how we discard an infeasible solution x to rRMPs. In Table 1, we report the average, over all the instances belonging to the same family or sharing a common characteristic, of the gap (Gap), the solution time (Time), and the percentage of tasks scheduled in the best solution (%S). We also report the number of optimal solutions found within the time limit (#Opt). We use bold font to indicate the best approach for the given family. See D for the detailed results for each instance. For a meaningful comparison, the average solution time takes into account only those instances for which an optimal solution is found within the time limit. Similarly, the average gap and the percentage of tasks scheduled (i.e., not postponed) takes into account only the instances that are not optimally solved. Since postponement is heavily penalized, a large gap often indicates a low percentage of scheduled tasks. This allows a better understanding of the results. On average 99% of the tasks are scheduled in the optimal or best-known solutions.

We observe that rP 2 s seems to outperform rP 1 s. However, it is difficult to compare these formulations:

the best model in terms of gap and solution time if the problem is not optimally solved can vary within a family, even if rP 2 s usually gives a tighter LP bound (see in Appendix D). We also observe that the average gap is considerable for most of the families (the solver fails to schedule a large proportion of the tasks), and the computational time is significant. This is because the formulations involve many binary variables and constraints. We conclude that directly solving the ILP formulations with a commercial solver is not the best approach.

The performance of the B&C approach is strongly correlated with the cuts generated from the approximations to the TTA subproblem. The problem-specific cuts allow us to find the optimal solution for 63 additional instances. On the remaining instances, they significantly reduce the gap from around 4.0%. This highlights the strength of the problem-specific cuts.

The B&C approach outperforms by far the direct solution of the ILP formulations for every family. It solves to optimality 80% of the instances and reduces the computational time (by around 3 min on average).

Moreover, the overall average gap when optimality is not reached is relatively small (1.7%).

Our results suggest that the number of skills does not have a significant impact on the difficulty of the instances (although instances with three skills appear to be easier to solve). This may be because there are fewer symmetries among technicians and a smaller number of feasible configurations for the task scheduling.

On the other hand, the number of tasks seems to have an impact when the technician-to-work ratio is tight.

8 A callback is a user function that is called periodically by Gurobi to allow the user to query or modify the state of the optimization (Gurobi Optimizer Reference Manual: http://www.gurobi.com/documentation/6.5/refman.pdf) This can be explained by the greater difficulty of finding a maintenance plan when there are more tasks. For the instances with a regular technician-to-work ratio, although the number of plans is larger when there are more tasks, the number of patterns does not grow proportionally, which results in a moderately more complicated TTA subproblem. Moreover, our exact approaches are more appropriate for two periods per day rather than four, because the computational time is lower and the number of optimal solutions is larger. A plausible explanation is that the DLBIs are tighter on instances with more periods per day. More periods provide a wider choice of task start times and therefore more opportunities to move technicians between locations. There is also a larger number of plans and patterns; this may contribute to the level of difficulty. In conclusion, according to our experiments, the difficulty of an instance increases with the number of periods per day and the tightness of the technician-to-work ratio. On average, 90% of the cuts are problem-specific and 10% are generic Benders cuts. These results indicate that the approximations are not always able to identify the infeasibility of the TTA subproblem. However, when |S| 1, solving the MCbM and MWC problems almost always identifies the infeasibility. We generate more cuts for instances with three skills, four periods per day, and a tight technician-to-work ratio. This is because of the larger number of patterns in the first two cases and because there is less flexibility in the scheduling of the tasks in the third case. We never generate CB cuts. The optimal solution to rSP LR 2 pxqs is usually the constraint matrix is not totally unimodular9 . We generate only a few MCbM cuts and many MWC cuts. This is because the RMP has no information about the DLBIs at the beginning of the optimization. It is thus more likely that these constraints are not satisfied by the RMP solutions. Furthermore, all the components of the B&C approach have a favorable trade-off between efficiency and computational time. Since the relaxation of the problem considered in the first stage contains only continuous variables and at most a few cuts, this stage requires on average just 1% of the time, and the limit on the number of iterations is never reached in our experiments. The results also show that solving the RMP via the B&C approach is the most time-consuming part of the second stage, requiring on average 99% of the time.

This compares with the negligible time to solve, given a solution x to rRMPs, rSP LR 2 pxqs and rSP 2 pxqs with the commercial solver, or the approximations to the TTA subproblem.

Conclusions and future research

We have proposed a B&C approach for a challenging maintenance scheduling problem arising in the onshore wind industry. This exact method decomposes the problem into a task scheduling problem and a TTA sub-problem. For each selection of plans, we determine the existence of an assignment of the technicians to the scheduled tasks that adheres to the technician availability and the daily travel limitations. Since the ILP formulation of the TTA subproblem does not have the integrality property, we use CB cuts to cut off infeasible maintenance plans in the RMP, while trying to identify violated classical Benders cuts beforehand. However, the key components of the algorithm are the approximations of the TTA subproblem as a series of MCbM and MWC problems. Our results show that the resulting problem-specific cuts are effective in speeding up the convergence of the B&C approach. The B&C method finds optimal solutions in reasonable computational times and provides high-quality integer solutions when optimality is not reached. It significantly outperforms the direct solution of the ILP models.

In future work, we will explore speeding up the solution of the problem (especially when integer solutions are scarce) by checking the approximations of the TTA subproblem at non-integer nodes. This may produce cuts that eliminate continuous infeasible solutions. However, adding too many such cuts to the RMP may decrease the efficiency of the approach since it is likely to increase the time needed to solve the LP relaxation at each node. In preliminary experiments, we tested two strategies for generating MWC and MCbM cuts at non-integer nodes. First, we considered all the plans p P such that x p ¡ 0 and arbitrarily added the cuts where the value of the slack variable was greater than or equal to 0.5. We also stopped the search for a cut at a node as soon as the first cut was found. Second, we considered all the plans p P such that x p 1. We did not observe a significant improvement with either of these strategies. However, we could investigate more advanced strategies for generating cuts at non-integer nodes. Another possibility to speed up the solution of the problem would be to solve the LP relaxation of the RMP at each node using column generation. It would then be necessary to express the cuts (generated when the TTA subproblem is infeasible) with alternative variables to simplify the solution of the pricing problem. Last but not least, we have considered the deterministic version of the problem, but there is an inherent uncertainty in wind-speed forecasts. Future research will focus on solving the resulting stochastic optimization problem using stochastic programming and/or robust optimization techniques.

A Notation

B.1 Equivalence to the L-coloring problem

To determine the complexity of the TTA subproblem, we prove its equivalence to the L-coloring problem. First, we associate a color color r with every technician r R. For a given solution x to rRMPs, we introduce the undirected graph : Gpxq composed of:

• A set of vertices : V -For each job j J pxq, we add q j vertices in :

V. Parameter j ν denotes the job associated with ν :

V and :

V j the set of vertices associated with job j. Let L ν be the set of colors associated with vertex ν: L ν tcolor r u rRj .

• A set of edges :

U defined such that dν 1 ν 2 :

V:

pν 1 , ν 2 q : U ô ν 1 $ ν 2 ¡ S jν 2 ¤ C jν 1 S jν 1 ¤ C jν 2 ¨ σ lj ν 1 lj ν 2 0 ©
(There is an edge between ν 1 and ν 2 in : Gpxq if and only if a technician cannot be assigned to both jobs j ν1 and j ν2 with regard to [C2] and [C3].)

We prove in Proposition B.1 the equivalence between the TTA subproblem and the L-coloring problem in : Gpxq.

Proposition B.1. Let x be a solution to rRMPs. The TTA subproblem for x is equivalent to the L-coloring problem in :

Gpxq.

Proof. Assume that we have a feasible solution to the TTA subproblem. This solution directly yields the list R ass j of technicians assigned to every job j J pxq (in that solution). We can then build a solution to the L-coloring problem by iterating through the vertices of :

Gpxq. Specifically, for each vertex ν :

V, we pick a technician r R ass jν (and remove it from this set) and color ν with color r . By construction of the graph, for a job j the set R ass j becomes empty only when every vertex of :

V j is colored. The graph is L-colorable since each ν :

V acquires an admissible color in L ν .

Alternatively, assume that we have a solution c to the L-coloring problem in : Gpxq. This solution directly yields the list R ass j of technicians assigned to every job j J pxq. Specifically, for each vertex ν :

V, we add to R ass j the technician r R such that color r cpνq. We then induce the underlying assignment of the technicians to the plans selected in the solution to the RMP. By construction of : Gpxq, the assignments satisfy the DLBIs and match the technician availability periods. This produces a feasible solution to the TTA subproblem.

Since the graph coloring problem is a special case of the L-coloring problem, the strong NP-completeness of the former [START_REF] Jensen | Graph Coloring Problems[END_REF] implies the strong NP-completeness of the latter. Therefore, the TTA subproblem is NP-complete in the strong sense. Note that in the case of interval graphs, the L-coloring problem remains NP-complete [START_REF] Biro | Precoloring extension. I. Interval graphs[END_REF] although the graph coloring problem becomes polynomial.

C Examples C.1 Example 1

Our first example illustrates how we build the different cuts. We consider a fixed time horizon with 8 periods of identical length (T t1, 2, ..., 8u) partitioned into two days: T 1 t1, 2, 3, 4u and T 2 t5, 6, 7, 8u. We have three locations: L tl 1 , l 2 , l 3 u. Locations l 2 and l 3 cannot both be visited on the same day (i.e., σ l2l3 0). We do not define any other DLBIs. There are 4 tasks (I tA, B, C, Du), 3 technicians (R tr 1 , r 2 , r 3 u), and 3 skills (S ts 1 , s 2 , s 3 u). The characteristics of the tasks and technicians are defined in Tables 3a and3b. For simplicity, we introduce only the parameters that are useful for the illustration of the cut generation process.

Table 4 shows a solution to rRMPs in which no cuts have been added. The table gives the start and finish periods of each task as well as the number of technicians required. We refer to this solution as x. Note that x satisfies constraints (6) of the RMP 10 .

Table 3: Data of Example 1. tr 2 , r 3 u Let u r1 be the job associated with the unavailability period of technician r 1 . Observing that u r1 and p B both cover day 2 and are defined at the incompatible locations l 2 and l 3 , we deduce that technician r 1 cannot be assigned to plan p B (although he or she has the required skill). In x the selected plans are associated with different patterns, and therefore we simply introduce one job for each plan. Job j A refers to plan p A , job j B refers to plan p B , and so on. First, we consider the generation of MCbM cuts. Figure 5 shows q G t pxq for each period of the planning horizon.

I l i s i A l 1 s 1 B l 2 s 1 C l 1 s 2 D l 3 s 3 (
For period t 7, the maximum flow in p G 7 pxq is 2, and this is the maximum cardinality of a b-matching in G 7 pxq. Since q j B q j C 3, x is an infeasible solution to the overall problem. We then compute the minimum cut in p G 7 pxq (see Figure 6).

From the general expression (37), we build the MCbM cut (42):

2x p B 1x p C ¤ 2 (42)
Second, we consider the generation of MWC cuts. Figure 7 depicts r G d S pxq for both days and every subset S S of skills. It shows that the MWC has a weight strictly greater than the number of available technicians in four cases. From the general expression (40), we build the MWC cuts ( 43) and (44):

1x p A 2x p B 1x p C ¤ 3 (43)
10 For instance, at period 7 we have seven cumulative constraints. Plugging in the values of the variables, we obtain 2 ¤ 3, 1 ¤ 1, 0 ¤ 2, 3 ¤ 3, 2 ¤ 3, 1 ¤ 2, 3 ¤ 3 when S is respectively equal to ts 1 u,ts 2 u,ts 3 u,ts 1 , s 2 u,ts 1 , s 3 u,ts 2 , s 3 u,ts 1 , s 2 , s 3 u. ts1,s2u pxq. Third, we solve rSP LR 2 pxqs with a commercial solver. Since its optimal value is strictly greater than zero (equal to 2), we identify the violated BF cut (45) using dual values obtained from the solver:

2x p B x p C 2x p D ¤ 3 (45)
Fourth, we directly solve the ILP formulation rSP 2 pxqs. As for the linear relaxation, the optimal value is 2.

We then generate the CB cut

x p A x p B x p C x p D ¤ 3 (46)
Table 5 gives the infeasible selection of plans discarded by the MCbM, MWC, BF, and CB cuts. We denote a selection of plans using a four dimensional vector where the first, second, third and fourth coordinates refer to the plan selected for task A, task B, task C and task D, respectively. An ellipsis indicates that infeasibility holds for any plan selected at the corresponding coordinate. For the cut (42), we can build a stronger MCbM cut of type (38) as described in Section 3.2.2. We add to the left-hand side of the cut (42) all the patterns covering period 7 to which technician r 1 cannot be assigned (this is the only technician associated with a vertex of set q V t R p¡q).

For the MWC cuts ( 43) and ( 44), we can build stronger MWC cuts of type (41) as described in Section 3.2.3. To strengthen MWC cut (43), we consider the subgraph G sub pxq of G that includes the vertices linked to i) patterns at location l 1 covering periods 3 and 4, ii) patterns at location l 2 covering period 4, and iii) patterns at location l 3 covering at least period 2, 3, or 4. A technician cannot be assigned to any of the previous patterns if he or she is assigned to pattern p A , p B , or p D . We then solve a maximum clique problem in this subgraph, and we add to the left-hand side of the MWC cut (43) all the plans associated with the patterns involved in the maximum clique. We proceed in a similar way for cut (44) by considering the subgraph G sub pxq of G that includes the vertices linked to i) patterns at location l 1 covering periods 7 and 8, ii) patterns at location l 2 covering at least period 7 or 8, and iii) patterns at location l 3 covering at least period 8. A technician cannot be assigned to any of the previous patterns if he or she is assigned to pattern p B or p D or to the job u r1 . Again, we solve a maximum clique problem in this subgraph, and we add to the left-hand side of the MWC cut (44) all the plans associated with the patterns involved in the maximum clique. In this example, when building the subgraph, we do not pay attention to the skill associated with the patterns because the MWC cuts ( 43) and ( 44) have been computed with S S. Otherwise, only the patterns with their skill in S can be added to the left-hand side of the cuts (since the right-hand side of the cuts is based on the total number of technicians with at least one skill of S).

For Example 1, the approximation of Section 3.2.3 dominates that of Section 3.2.2 (i.e., the MWC cuts are stronger than the MCbM cuts).

C.2 Example 2

Our second example illustrates a case where the approximation of Section 3.2.2 dominates that of Section 3.2.3 (i.e., the MCbM cuts are stronger than the MWC cuts). We consider a fixed time horizon with 4 periods (T t1, 2, 3, 4u) partitioned into two days: T 1 t1, 2u and T 2 t3, 4u. We have 1 location (L tlu), 2 tasks (I tE, F u), 1 skill (S tsu), and 2 technicians (R tr 4 , r 5 u). Technician r 2 is unavailable during periods 1 and 3. The characteristics of the tasks and technicians are summarized in Tables 6a and6b. Let u r5 be the jobs associated with the unavailability periods of technician r 5 . First, we consider the generation of MCbM cuts. Figure 8 shows q G t pxq for each period of the horizon. Since technician r 2 is unavailable for task B, the maximum cardinality of a b-matching at period 2 is 1, whereas the tasks scheduled during this period require two technicians. The following MCbM cut is produced:

x p E x p F ¤ 1 (47)
Second, we consider the generation of MWC cuts. Solving the MWC problems does not produce a MWC cut. Therefore, for Example 2, the approximation of Section 3.2.2 dominates that of Section 3.2.3.

C.3 Example 3

In our third example, the problem-specific approximations do not find a cut although the TTA subproblem is infeasible. We consider a fixed time horizon with 8 periods (T t1, ..., 8u) partitioned into two days: T 1 t1, 2, 3, 4u and T 2 t5, 6, 7, 8u. We have 1 location (L tlu), 4 tasks (I tG, H, I, Ju), 3 skills (S ts 6 , s 7 , s 8 u), and 2 technicians (R tr 6 , r 7 u). The characteristics of the tasks and technicians are summarized in Tables 8a and8b. First, we consider the generation of MCbM cuts. Figure 10 shows q G t pxq for each period of the horizon. We However, it is easy to see that the TTA subproblem is infeasible. First, technician r 7 must perform tasks I and J. Second, tasks G and H cannot be performed by the same technician since they overlap. The same holds for tasks G and J and for tasks H and I. The TTA subproblem is therefore infeasible since technician r 7 cannot perform either tasks G, I, and J, or tasks H, I and J. The solution of rSP LR 2 pxqs gives an optimal value strictly greater than zero (equal to 1). We then identify the violated BF cut (48) (which has here the same expression as a CB cut):

x p G x p H x p I x p J ¤ 3 (48)
In this example no MCbM or MWC cuts are identified although the TTA subproblem is infeasible. We write "a b c d e f" where "a b c d e" indicates the family and "f" the instance number. The column "Obj" gives the objective of the best solution computed by any of our methods; "Time" gives the computational time (in seconds); "Relax" gives the value of the linear relaxations of rP 1 s and rP 2 s; "UB" gives the upper bound used to compute the gap. For reference, the column "CPLNS" reports the best solution found by [START_REF] Froger | Solving a wind turbine maintenance scheduling problem[END_REF] with a CPLNS approach.

D Detailed experimental results

  (a) Compatible locations with l1 (b) Sets of compatible locations

Figure 1 :

 1 Figure 1: Illustration of daily location-based incompatibilities.

Figure 3 :

 3 Figure 3: Minimum cut in graph p G t pxq.

j

  ν1 and j ν2 with regard to [C2] and [C3]. Proposition 3.2 formally describes the link between the solution of the TTA subproblem and the solution of MWC problems. Proposition 3.2. The TTA subproblem is feasible for a solution x to rRMPs if for each subset S S of skills and each day d D the maximum weight of a clique in r G d S pxq is less than or equal to |R S |. Proof. For a fixed day d and a fixed subset of skills S, suppose for the sake of contradiction that the maximum weight of a clique in r G d S pxq is strictly greater than |R S |. By construction of r G d S pxq, a technician cannot perform more than one job among the jobs whose vertices belong to that clique. Since we need more technicians than are available, the TTA subproblem is infeasible. Let us now assume a fixed day d D and a fixed subset of skills S. Let C d S pxq be the set of vertices that belong to the MWC of r G d S pxq. If the total weight of the vertices in r G d S pxq is strictly greater than |R S |, the constraint that eliminates x is:

S

  pxq with regard to [C2] and [C3]. We then solve a maximum clique problem in G sub pxq. Let H C d S pxq $ be the set of patterns associated with the vertices that are part of the maximum clique of G sub pxq. Since a technician cannot be assigned to more than one of the jobs in C d S pxq or one of the patterns of H

  associated with pattern h H J H pxq set of jobs associated with patterns involved in selection of plans x J R set of jobs associated with technician unavailability periods J pxq set of jobs associated with selection of plans x (J pxq J H pxq J R ) dt day associated with time period t T lw, li location of turbine w W and location where task i I must be performed l t r location of technician r R when he or she is not available during period t σ ll I binary parameter equal to 1 if and only if locations l and l 1 are compatible ovpIq family of sets of tasks that cannot overlap si skill required for task i I oi penalty if task i I is postponed bwi binary parameter equal to 1 if and only if execution of task i I shuts down turbine w W when technicians are working on i r bwi binary parameter equal to 1 if and only if execution of task i I shuts down turbine w W during the rest periods it covers g t w profit if turbine w W can produce electricity during period t T r g d w profit if turbine w W can produce electricity during rest period following day d D λrs binary parameter equal to 1 if and only

  N.B.: Bold font indicates a solution to the MCbM problem. A dashed outline indicates that no b-matching with the desired cardinality can be found.

Figure 5 :

 5 Figure 5: Graphs q G t pxq for Example 1 and different values of t T .

Figure 6 :

 6 Figure 6: Minimum cut in p G 7 pxq for Example 1.

  N.B.: Bold font indicates a solution to the MWC problem. A dashed outline indicates that the weight of this clique is strictly greater than the maximum allowed.

Figure

  Figure 7: r G d S pxq for Example 1.

  2x p B 1x p C ¤ 2 (44) The cut (43) is built from the clique computed in either r G 1 ts1,s2,s3u pxq or r G 1 ts1,s3u pxq, and the cut (44) is built from the clique computed in either r G 2 ts1,s2,s3u pxq or r G 2

N

  .B.: Bold font indicates a solution to the MCbM problem. A dashed outline indicates that no b-matching with the desired cardinality can be found.

Figure 8 :

 8 Figure 8: Graphs q G t pxq for Example 2 and different values of t T .

  Figure 9 depicts r G d S pxq for both days. N.B.: Bold font indicates a solution to the MWC problem.

Figure 9

 9 Figure 9: r G d S pxq for Example 2.

N

  .B.: Bold font indicates a solution to the MCbM problem.

Figure 10 :

 10 Figure 10: Graphs q G t pxq for Example 3 and different values of t T .

N

  .B.: Bold font indicates a solution to the MWC problem.

Figure 11

 11 Figure 11: r G d S pxq for Example 3.

  are used to represent the start and finish periods of the pattern). Let P h be the set of plans sharing the same parameters as pattern h. For each pattern h H and each technician r R h , we introduce the binary variable y rh that is 1 if and only if technician r is assigned to pattern h. Assigning technicians to patterns reduces the number of assignment variables. Lastly, we define the binary variable v t rl that is 1 if and only if technician r is at location l during period t.

	The following ILP gives the baseline formulation, rP 1 s:
	rP 1 s max	wW	£	ţT	g t w f t w	ḑD	r g d w	r f d w	¡	pP	o p x p	(1)
	subject to:

These parameters define what we call a pattern. Let H be the set of all patterns. For convenience, for pattern h H, we introduce s h , l h , and R h that respectively define its required skill, its location, and the set of technicians that can be assigned. Conversely, let H l th H | l h lu be the set of patterns associated with location l L. The active periods for pattern h are represented by a binary vector a h over T such that a t h 1 if and only if h is active during period t T (S h and C h

Table 1 :

 1 Detailed computational results for the exact approaches.

	Family		rP1s Gap %S #Opt Time	B&C Gap %S #Opt Time Gap %S #Opt Time Gap %S #Opt Time B&C rP2s
	10 2 1 20 A		-	-	5/5	598	-	-	5/5	152	-	-5/5	2,272	-	-	5/5	5
	10 2 1 20 B		-	-	5/5	12	-	-	5/5	37	-	-5/5	2	-	-	5/5	1
	10 2 1 40 A 0.01% 100%	2/5 1,813 0.01% 100%	1/5	7 0.70% 100% 2/5	3,379	-	-	5/5	7
	10 2 1 40 B		-	-	5/5	205	-	-	5/5	121	-	-5/5	8	-	-	5/5	1
	10 2 3 20 A		-	-	5/5 2,635	-	-	5/5 1,574 1.0% 97% 2/5	2,871	-	-	5/5	162
	10 2 3 20 B		-	-	5/5	31	-	-	5/5	18	-	-5/5	94	-	-	5/5	2
	10 2 3 40 A		-	-	5/5 3,220	-	-	5/5 3,996 2.2% 98% 2/5	4,040	-	-	5/5	17
	10 2 3 40 B		-	-	5/5	180	-	-	5/5	295	-	-5/5	18	-	-	5/5	1
	20 2 1 40 A		2.4% 98%	2/5 8,074	1.4% 98%	2/5 2,858 6.4% 96% 1/5	7,301	-	-	5/5	230
	20 2 1 40 B 0.01% 100%	4/5	232	-	-	5/5 2,078	-	-5/5	695	-	-	5/5	4
	20 2 1 80 A	436%	0%	0/5	-	334% 20%	0/5	-8.2% 96% 0/5	-0.02% 100%	4/5	300
	20 2 1 80 B	318% 50%	3/5 1,485	229% 49%	3/5 3,823 0.13% 100% 4/5	580	-	-	5/5	5
	20 2 3 40 A 1.25% 99%	1/5	322	1.2% 99%	3/5 5,534 4.6% 95% 1/5	1,136 2.1% 98%	4/5	40
	20 2 3 40 B		-	-	5/5	376	-	-	5/5	155	-	-5/5	525	-	-	5/5	3
	20 2 3 80 A	257% 20%	0/5	-	156% 39%	0/5	-3.3% 98% 0/5	-	-	-	5/5	51
	20 2 3 80 B		-	-	5/5 3,415	196% 50%	3/5 2,456 0.02% 100% 4/5	163	-	-	5/5	5
	20 4 1 20 A		1.8% 96%	0/5	-	1.3% 97%	0/5	-2.1% 95% 0/5	-2.2% 95%	3/5 1,715
	20 4 1 20 B		-	-	5/5	204	-	-	5/5	405	-	-5/5	131	-	-	5/5	2
	20 4 1 40 A	264%	0%	0/5	-	61% 75%	0/5	-8.6% 93% 0/5	-1.2% 98%	2/5 1,586
	20 4 1 40 B	174% 49%	1/5 5,208	107% 74%	1/5 1,968 0.3% 100% 4/5	630	-	-	5/5	6
	20 4 3 20 A		1.2% 98%	0/5	-	2.4% 95%	4/5 5,005 3.1% 95% 0/5	-2.0% 95%	4/5	237
	20 4 3 20 B 0.01% 100%	4/5	52	-	-	5/5	113 3.1% 95% 4/5	134	-	-	5/5	9
	20 4 3 40 A	373% 20%	0/5	-	5.3% 95%	0/5	-6.7% 94% 0/5	-0.85% 98%	1/5 8,888
	20 4 3 40 B		1.5% 99%	2/5 6,112 0.03% 100%	3/5 2,108 0.29% 100% 1/5	1,608	-	-	5/5	11
	40 4 1 40 A	352%	0%	0/5	-	106% 76%	0/5	-15.7% 89% 0/5	-2.1% 98%	0/5	-
	40 4 1 40 B 1,594% 40%	0/5	-	3.0% 98%	0/5	-0.7% 100% 0/5	-	-	-	5/5	31
	40 4 1 80 A 4,948%	0%	0/5	-4,948%	0%	0/5	-16.1% 90% 0/5	-1.5% 99%	0/5	-
	40 4 1 80 B	331%	0%	0/5	-	331%	0%	0/5	-1.8% 99% 0/5	-	-	-	5/5	89
	40 4 3 40 A 1,087% 20%	0/5	-	4.6% 96%	0/5	-14.6% 90% 0/5	-1.5% 99%	0/5	-
	40 4 3 40 B	477% 20%	0/5	-0.84% 99%	2/5 2,118 0.3% 100% 0/5	-	-	-	5/5	36
	40 4 3 80 A 2,813%	0%	0/5	-2,727% 18%	0/5	-14.3% 90% 0/5	-2.3% 98%	0/5	-
	40 4 3 80 B 3,899%	0%	0/5	-3,899%	0%	0/5	-0.96% 100% 0/5	-	-	-	5/5	86
	Characteristics	rP1s Gap %S #Opt Time	B&C Gap %S #Opt Time Gap %S #Opt Time Gap %S rP2s	B&C #Opt Time
	|S| |T | |D|	1 3 2 4		854% 35% 32/80 1,108 1,036% 39% 37/80 1,677 179% 56% 57/80 1,383 1,197% 30% 12/80 1,555 1,014% 61% 20/80 1,757 6.5% 95% 14/80 621% 61% 34/80 1,035 6.7% 95% 36/80 982% 61% 43/80 1,896 4.9% 96% 29/80 144% 60% 57/80 1,461 3.9% 97% 51/80	957 1.6% 98% 722 1.7% 98% 982 1.0% 99% 380 1.7% 98%		64/80 64/80 78/80 50/80	179 186 49 390
	Type	A B		878% 38% 20/80 2,618 1,059% 35% 49/80 921	759% 65% 25/80 2,838 7.8% 94% 13/80 3,106 1.7% 98% 802% 53% 52/80 913 0.8% 100% 52/80 288 --		48/80 80/80	456 18
	All			940% 37% 69/160 1,413	773% 61% 77/160 1,538 5.7% 96% 65/160	852 1.7% 98% 128/160	182

Table 2

 2 gives the average number of cuts generated during the execution of the B&C approach for each group of tests. The overall average (#Cuts) is decomposed into CB, BF, MCbM, and MWC cuts. Detailed results for each family of instances are available in D.

Table 2 :

 2 Average number of cuts generated in B&C approach.

	Characteristic	#Cuts	CB	BF	Other cuts MCbM MWC
	|S| |T | |D|	1 3 2 4	102 224 56 270	0 0 0 0	0.3 28 9 19	3 10 3 10	98 186 44 241
	Type	A B	262 63	0 0	24 4	10 4	229 56
	All		163	0	14	7	142

  if technician r R has skill s S binary parameter equal to 1 if and only if task ip is executed during period t T Sp,Cp start and finish period of plan p P Rp, bwp, r bwp, op) = (si p , li p , Ri p , bwi p , r bwi p , oi p )

	π t r	binary parameter equal to 1 if and only if technician r R is available during period t T
	ip	task involved in plan p P
	a t p
	qp	number of required technicians if plan p P is selected
	hj	pattern associated with job j
	qj	number of technicians required by job j
	lj	location of job j
	Sj, Cj start and finish period of job j
	Sj	set of skills such that a technician requires at least one of these skills for job j
	Rj	set of technicians that can be assigned to job j
	(sp, lp,

(S h ,C h ,a t h ,s h ,l h ,H l ,R h ) = (Sp,

Cp,a t p ,sp,lp,H l ip ,Rp) with p P h B Complement: TTA subproblem and complexity

Table 4 :

 4 Solution to restricted master problem for Example 1.

	I	Selected plan p	Sp	Cp	qp	Rp
	A B C	p A p B p C	2 4 7	5 7 8	1 2 1	tr 1 , r 2 , r 3 u tr 2 , r 3 u tr 2 u
	D	p D	1	3	2

Table 5 :

 5 Infeasible selections of plans discarded A , p B , p C , p D q pp A , p B , p C , ...q pp A , p B , ..., p D q p..., p B , p C , p D q p..., p B , p C , ...q p..., p B , ..., p D q

	Selections of plans	CB BF MCbM MWC

pp

Table 6 :

 6 Data of Example 2.

Table 7 :

 7 Table7shows a solution to rRMPs in which no cuts have been added. The table gives the start and finish periods of each task as well as the number of technicians required. Note that x satisfies constraints (6) of the RMP. Solution to restricted master problem for Example 2.

	I	Selected plan p	Sp	Cp	qp	Rp
	E F	p E p F	1 2	2 4	1 1	tr 4 u tr 4 u

Table 8 :

 8 Data of Example 3.Table9shows a solution rRMPs in which no cuts have been added. The table gives the start and finish periods of each task as well as the number of technicians required. Again, it is easy to verify that x satisfies constraints (6) of the RMP.

	(a) Characteristics of tasks.
	I	l i	s i		(b) Characteristics of technicians.
	G H I	l l l	s 6 s 6 s 7	R r 6 r 7	ts S | λrs 1u unavailability periods -ts 6 u ts 6 , s 7 , s 8 u
	J	l	s 8

-

Table 9 :

 9 Solution to restricted master problem for Example 3.

	I	Selected plan p	Sp	Cp	qp	Rp
	G H I J	p G p H p I p J	2 4 7 1	5 7 8 3	1 1 1 1	tr 6 , r 7 u tr 6 , r 7 u tr 7 u tr 7 u

Table 10 :

 10 Average number of cuts generated in B&C approach.

					Other cuts
	Family	All	CB	BF	MCbM	MWC
	10 2 1 20 A	21	0	0	2	19
	10 2 1 20 B	10	0	0	1	9
	10 2 1 40 A	36	0	0	0.8	35
	10 2 1 40 B	12	0	0	0.6	12
	10 2 3 20 A	153	0	94	9	50
	10 2 3 20 B	28	0	7	6	15
	10 2 3 40 A	66	0	16	9	41
	10 2 3 40 B	17	0	0.2	2	15
	20 2 1 40 A	67	0	0	1	66
	20 2 1 40 B	28	0	0	1	27
	20 2 1 80 A	105	0	0	3	101
	20 2 1 80 B	18	0	0	1	17
	20 2 3 40 A	144	0	17	7	120
	20 2 3 40 B	40	0	5	2	32
	20 2 3 80 A	118	0	6	5	107
	20 2 3 80 B	31	0	0.6	0.8	30
	20 4 1 20 A	94	0	0	5	90
	20 4 1 20 B	26	0	0	3	23
	20 4 1 40 A	202	0	5	12	185
	20 4 1 40 B	57	0	0	3	54
	20 4 3 20 A	314	0	34	16	263
	20 4 3 20 B	84	0	21	13	50
	20 4 3 40 A	392	0	38	26	329
	20 4 3 40 B	96	0	20	10	66
	40 4 1 40 A	229	0	0	3	226
	40 4 1 40 B	91	0	0	2	88
	40 4 1 80 A	480	0	0	5	476
	40 4 1 80 B	151	0	0	4	146
	40 4 3 40 A	672	0	65	19	588
	40 4 3 40 B	144	0	9	6	129
	40 4 3 80 A	1,106	0	102	33	971
	40 4 3 80 B	184	0	5	5	174

Table 11 :

 11 Detailed results for each instance

	Instance	Time	rP1s Obj	Relax	Time	rP2s Obj	Relax	Time	B&C	Obj	CPLNS	UB
	10 2 1 20 A 1	86	47923.7	48132.64	110	47923.7	48144.54	1	47923.7	47923.7	47923.7
	10 2 1 20 A 2	2475	43231.5	44326.76	430	43231.5	44343.24	13	43231.5	42474.1	43231.5
	10 2 1 20 A 3	67	58597.6	62152.91	92	58597.6	62183.79	1	58597.6	57673.5	58597.6
	10 2 1 20 A 4	8	63014.9	63179.87	7	63014.9	63167.33	1	63014.9	62952.9	63014.9
	10 2 1 20 A 5	354	42646.6	43157.29	120	42646.6	43142.64	10	42646.6	42646.6	42646.6
	10 2 1 20 B 1	1	50153.2	50239.27	1	50153.2	50245.33	1	50153.2	50153.2	50153.2
	10 2 1 20 B 2	34	66808.4	69890.75	177	66808.4	69890.75	1	66808.4	66808.4	66808.4
	10 2 1 20 B 3	10	39222.6	39501.82	2	39222.6	39499.54	1	39222.6	39222.6	39222.6
	10 2 1 20 B 4	14	66168.2	66630.57	5	66168.2	66554.25	2	66168.2	66168.2	66168.2
	10 2 1 20 B 5	1	96760.9	96819.73	1	96760.9	96878.27	0	96760.9	96760.9	96760.9
	10 2 1 40 A 1	24	120976.0	122507.30	7	120976.0	122507.30	2	120976.0	120900.9	120976.0
	10 2 1 40 A 2	3602	140280.1	140724.40	10800	140280.1	140767.07	4	140280.1	140265.2	140280.1
	10 2 1 40 A 3	10800	129716.8	130029.78	10800	129701.7	130043.32	15	129716.8	129671.4	129716.8
	10 2 1 40 A 4	10800	117036.9	117461.17	10800	117040.9	117517.68	7	117058.6	116991.3	117058.6
	10 2 1 40 A 5	10800	119352.6	120463.36	10800	119352.6	120463.36	4	119352.6	118932.1	119352.6
	10 2 1 40 B 1	662	123614.6	123877.36	225	123614.6	123860.80	2	123614.6	123614.6	123614.6
	10 2 1 40 B 2	149	145580.0	145976.50	11	145580.0	146025.68	2	145580.0	145580.0	145580.0
	10 2 1 40 B 3	142	116211.1	116682.73	300	116211.1	116682.73	1	116211.1	116211.1	116211.1
	10 2 1 40 B 4	64	133112.9	133606.82	3	133112.9	133624.16	1	133112.9	133092.9	133112.9
	10 2 1 40 B 5	9	132110.9	132339.03	66	132110.9	132339.03	1	132110.9	132106.9	132110.9
	10 2 3 20 A 1	9228	55731.1	59032.02	6668	55731.1	59057.12	696	55731.1	55077.7	55731.1
	10 2 3 20 A 2	766	43172.7	44543.94	594	43172.7	44639.25	24	43172.7	43043.7	43172.7
	10 2 3 20 A 3	817	34143.2	34901.19	348	34143.2	34939.55	13	34143.2	34035.5	34143.2
	10 2 3 20 A 4	2358	82928.1	83613.29	256	82928.1	83591.71	77	82928.1	82919.3	82928.1
	10 2 3 20 A 5	4	72423.5	73148.79	3	72423.5	73139.52	2	72423.5	72423.5	72423.5
	10 2 3 20 B 1	16	76852.7	77041.72	11	76852.7	77101.17	2	76852.7	76852.7	76852.7
	10 2 3 20 B 2	3	66410.9	66861.85	3	66410.9	66863.66	1	66410.9	66410.9	66410.9
	10 2 3 20 B 3	14	51749.9	52105.77	17	51749.9	52105.77	2	51749.9	51749.9	51749.9
	10 2 3 20 B 4	1	37576.4	37703.78	1	37576.4	37703.78	0	37576.4	37576.4	37576.4
	10 2 3 20 B 5	123	69330.7	69648.50	56	69330.7	69648.50	5	69330.7	69306.3	69330.7
	10 2 3 40 A 1	2152	91031.9	91460.86	10094	91031.9	91491.49	3	91031.9	90948.0	91031.9
	10 2 3 40 A 2	5752	76895.1	77478.31	3064	76895.1	77538.06	10	76895.1	76485.6	76895.1
	10 2 3 40 A 3	6370	107914.6	108588.55	3383	107914.6	108592.47	47	107914.6	107914.6	107914.6
	10 2 3 40 A 4	268	95022.1	97279.62	217	95022.1	97279.62	5	95022.1	94948.4	95022.1
	10 2 3 40 A 5	1560	118961.0	120371.75	3225	118961.0	120371.75	21	118961.0	118506.5	118961.0
	10 2 3 40 B 1	18	79260.6	80307.68	53	79260.6	80307.68	1	79260.6	79260.6	79260.6
	10 2 3 40 B 2	118	104039.9	104593.14	48	104039.9	104593.14	1	104039.9	104039.9	104039.9
	10 2 3 40 B 3	17	96649.2	97001.79	26	96649.2	97001.99	2	96649.2	96617.2	96649.2
	10 2 3 40 B 4	263	129859.7	130081.73	69	129859.7	130120.73	1	129859.7	129851.7	129859.7
	10 2 3 40 B 5	484	127246.9	127679.46	1279	127246.9	127703.46	1	127246.9	127246.9	127246.9
	20 2 1 40 A 1	8357	326654.6	327143.68	1927	326654.6	327178.62	18	326654.6	326357.8	326654.6
	20 2 1 40 A 2	10800	282515.6	298001.39	10800	290902.7	298070.51	120	296421.1	294855.6	296421.1
	20 2 1 40 A 3	10800	438999.1	450484.82	10800	439346.8	450537.67	899	449480.1	448793.2	449480.1
	20 2 1 40 A 4	10800	308698.8	309571.25	10800	308717.2	309559.45	105	308726.8	308249.2	308726.8
	20 2 1 40 A 5	7792	201315.3	202357.52	3789	201315.3	202384.96	10	201315.3	201217.3	201315.3
	20 2 1 40 B 1	429	236502.3	237806.16	343	236502.3	237813.78	4	236502.3	236478.2	236502.3
	20 2 1 40 B 2	47	309385.9	311197.70	25	309385.9	311225.39	2	309385.9	309384.5	309385.9
	20 2 1 40 B 3	418	348011.8	348296.62	419	348011.8	348296.74	2	348011.8	347965.7	348011.8
	20 2 1 40 B 4	32	317274.1	317570.09	22	317274.1	317614.07	3	317274.1	317223.4	317274.1
	20 2 1 40 B 5	10800	283812.3	284821.72	9580	283812.3	284874.76	9	283812.3	283686.9	283812.3
	20 2 1 80 A 1	10800	-120636.7	765303.50	10800	-120636.7	765335.54	294	764294.5	762965.0	764294.5
	20 2 1 80 A 2	10800	-510542.4	526812.51	10800	-510542.4	526907.73	648	524862.7	521644.7	524862.7
	20 2 1 80 A 3	10800	-139492.8	618782.86	10800	-139492.8	618818.27	65	617111.2	614963.3	617111.2
	20 2 1 80 A 4	10800	-206213.4	851621.30	10800	838356.9	851665.51	195	851001.1	846333.1	851001.1
	20 2 1 80 A 5	10800	-642506.8	564660.32	10800	-642506.8	564810.52	10800	562342.3	532015.6	562452.8
	20 2 1 80 B 1	10800	-143552.3	769706.77	4124	769511.4	769727.29	6	769511.4	769316.7	769511.4
	20 2 1 80 B 2	1182	706851.6	707266.37	5599	706851.6	707308.20	6	706851.6	706455.9	706851.6
	20 2 1 80 B 3	3052	688801.4	689291.04	10800	-193415.9	689368.98	5	688801.4	688509.3	688801.4
	20 2 1 80 B 4	220	699114.8	699272.01	1745	699114.8	699305.94	3	699114.8	699007.4	699114.8
	20 2 1 80 B 5	10800	690793.0	692218.43	10800	673941.0	692205.58	4	690799.9	690626.2	690799.9
	20 2 3 40 A 1	10800	282056.9	296812.75	10800	288845.4	296990.16	10800	289644.5	289408.5	295616.2
	20 2 3 40 A 2	322	282694.9	283227.65	2133	282694.9	283241.57	3	282694.9	282629.9	282694.9
	20 2 3 40 A 3	10800	347369.9	348060.75	9455	347369.9	348067.21	71	347369.9	347168.9	347369.9
	20 2 3 40 A 4	10800	284474.9	285630.36	5012	284963.0	285658.56	68	284963.0	284626.5	284963.0

A instance of the cumulative scheduling problem consists of a single resource with a given capacity C and a set J of n jobs where each job j J has a release date r j , a deadline d j , a processing time p j , and a capacity resource requirement a j . The problem is to determine if there exists a schedule of all the jobs satisfying the timing and resource capacity constraints.

A plan associated with task i defines a feasible schedule for i by setting an execution mode m M i (and, by induction, a duration d im and a technician requirement q im ) and a consistent start date t such that i can be executed during every period t 1 such that t ¤ t 1 t d im (i.e., γ t I i 1).

If for technician r there exists t 1 , t 2 T , t 1 t 2 and l L such that for all t T , t 1 ¤ t ¤ t 2 , we have π t r 0 and l t r l, then we create a single job pl, t 1 , t 2 , Sr, tru, 1q.

We found an instance-not part of our testbed-and a solution x of rRMPs where the optimal value of rSP LR 2 pxqs is 0 whereas the optimal value of rSP 2 pxqs is 1.