Abstract
In contrast to the production of new parts, for the regeneration of complex capital goods, various modes of regeneration are often available. They reflect, e.g., different repair technologies and/or different personal qualifications. In this paper, we describe solution approaches for the selection of efficient regeneration modes. Thereby, we simultaneously schedule maintenance tasks as they influence mode selection. Using the example of turbine blades of aircraft engines, we explain the problem setting and the need to consider the customer’s business model. For immobile capital goods such as wind turbines, the selection of efficient regeneration modes requires additional decisions concerning the transportation of personnel and material. We explain this adjacent problem setting and solution approaches. In this context, we include stochastic service times and weather conditions as well as the uncertain condition of the good.
You have full access to this open access chapter, Download chapter PDF
Keywords
- Maintenance, repair, and overhaul
- Maintenance scheduling
- Multi-modal routing
- Aircraft engines
- Wind turbines
1 Introduction
The maintenance, repair, and overhaul (MRO) of used products is an important topic for ecological and economic reasons. Particular challenges arise for planning the so-called regeneration processes of complex capital goods such as aircraft engines or wind turbines. Due to the high remaining value, decisions must be made on how to efficiently regenerate objects with unique deterioration. The specific condition of the good and the customer’s business model are important for the selection of such an efficient regeneration mode and the scheduling of associated activities. For example, a mainly time-sensitive customer has different requirements on the regeneration process and its outcome than a mainly quality-sensitive customer.
The regeneration of immobile capital goods, such as wind turbines, imposes additional requirements on the process planning as the teams and the tools need to be transported to the location of the capital good. Therefore, transportation times and costs must be considered when scheduling the tasks. There are also different modes available, as the implementation of the tasks depends on the qualification and on available tooling of the assigned team. For example, the rotor blade of a wind turbine can be repaired either on the rope or by using a hydraulic lifting platform. Planning is further complicated by the fact that bad weather can delay or even prevent the implementation of certain tasks. The start and duration of the repair is, therefore, subject to uncertainty. Again, the condition of the good must be taken into account. In Sect. 2 of this article, we focus on the selection of efficient regeneration modes in the context of aircraft engines to describe the problem setting in detail and to set the foundation for the rest of the paper. Section 3 considers the additional challenges for the regeneration of immobile capital goods such as wind turbines. We extend the problem setting by considering the condition of the good in Sect. 4 and by additionally considering the uncertainty of service times and weather in Sect. 5.
2 Fundamentals: Selection of Efficient Regeneration Paths for Turbine Blades of Aircraft Engines
For the regeneration of complex capital goods, such as turbine blades of aircraft engines, there are multiple technically permissible options available. These different regeneration modes lead to different process parameters, such as makespan and cost but also to different functional features of the regenerated good concerning performance and remaining lifetime.
The different regeneration paths for a turbine blade are shown in Fig. 1.1. Depending on the former condition of the good, there are up to seven different regeneration paths available. We assume that for one model turbine blade and one model customer, paths 1, 2, and 3 are not applicable due to the condition of the blade. The resulting model attributes of the remaining paths 4 to 7 are shown in Table 1.1. Regeneration path 4 leads to the highest possible remaining lifetime and a very good performance, so that the customer assigns the result with a quality level A. However, it has high costs of 4,000 e and a quite long duration of 674 minutes.
When choosing an efficient regeneration mode, the customer business model needs to be explicitly considered. The customer does not always demand or is willing to pay for the best functional state that can be achieved. For a quality- sensitive customer, path 4 would be the optimal path with a high quality and lower costs compared to a new part (path 7). In contrast, for a time- and quality-sensitive customer, path 5 may be a better choice with a much shorter duration compensating for the lower quality. This shows that the trade-off among functional condition, cost and duration must be considered to find a profit-maximizing solution for the specific customer. The customer’s business model is reflected by the time- and quality-dependent revenue.
In addition, the capacity utilisation on the shop floor and the limitation of the mobile handling system must be considered as different regeneration projects are coupled via those common capacities. Assume, for example, that path 6 is chosen for a time-sensitive customer leading to a quality level C. If the repair-coating, as shown in Fig. 1.1, is temporarily occupied, the resulting waiting time could be used for the preparation step of path 5 without a temporal extension of the whole process. Due to the higher quality level of path 5 compared to path 6, customer satisfaction could be improved by choosing this path. This shows that the optimal regeneration path is influenced by the resource competition of different regeneration orders.
To model the corresponding decision problem, our approach for scheduling flexible projects, as presented in Kellenbrink and Helber (2015), Kellenbrink and Helber (2016) and Hoffmann et al. (2020), can be used. In such projects, there are mandatory activities and optional activities reflected by decisions and caused activities, as shown in Fig. 1.2. The goal is to find a profit-maximising schedule including the decision on the implemented activities. Using heuristic solution approaches, such as genetic algorithms or simulated annealing, it is possible to efficiently schedule multiple regeneration projects. The approach is not limited to aircraft engines but can be applied to different mobile capital goods.
The abovementioned research has been carried out in subproject “D3: Selection of efficient regeneration modes” in the German Collaborative Research Centre (CRC) 871 “Product-Regeneration”. This research network aims to transform experience- based decisions on MRO processes into knowledge-based decisions using a virtual twin. To prove the operability of the concept, a physical system demonstrator was built up using the example of the aircraft engine and, in particular, the turbine blade. The described decision on an efficient regeneration path and on the scheduling of the process steps plays a central role in the system demonstrator. It supports the consolidation and coordination of the results from the other subprojects for the purpose of a holistic view of the regeneration processes. In Kellenbrink et al. (2022), we show that our approach can successfully be applied to select efficient regeneration modes in the context of this system demonstrator.
3 Selection of Efficient Regeneration Modes for Maintenance Actions at Multiple Distributed Wind Farms
3.1 Introduction
The question of how to select regeneration modes occurs not only for mobile complex capital goods such as aircraft engines but also for the regeneration of immobile capital goods such as wind turbines. Wind turbines are subject to wear and tear both during operation and downtime. In this case, the regeneration modes can also differ. They can be especially distinguished due to organizational aspects. For example, blade damage can be repaired by either climbing the blade using a rope or by getting access to the blade using a lifting ramp. Both options require specific skills from the team and special equipment to be placed inside the vehicle used by the team. In addition, the trade-off between lower costs, if a team is not equipped with all essential spare parts and the latest tools, and a longer processing time due to delivery times or slower processing is considered.
In addition to the selection of an efficient regeneration mode, which is reflected by the assignment of one specifically qualified and equipped team, an operator responsible for the maintenance of multiple wind parks must simultaneously schedule those activities by assigning suitable starting times to each activity. To regenerate all goods, a tour must be found in which all spatially distributed locations are visited.
The problem outlined is very similar to the established models and procedures from the literature on routing problems. However, the routing problem for the regeneration of immobile capital goods becomes challenging and cannot be solved by known methods as the different team-specific regeneration modes become available. In this situation, an interesting combination of routing and project scheduling arises.
3.2 Problem Setting
Different wind turbines must undergo necessary maintenance activities depending on the lifetimes of different expendable parts and on condition monitoring, which utilizes the data collected by multiple sensors at or near the turbine. The locations of those turbines are given. The driving times required by the teams to travel from the location of one wind turbine to the location of another turbine cannot be disregarded. The operator of the wind turbines must ensure that the combined availability and, thus, energy production of the turbines in a wind park is above a specific level. When a repair occurs too late, the turbine might have a significantly decreased power output or even cease to operate. Contrariwise, if the team attempts to execute an operation too early, it may interfere with the fixed interval of inspections and cause unnecessary costs. This leads to individual time windows for each operation.
As shown in Fig. 1.3, each team starts and finishes its tour at the depot of the operator, reflected by the dark blue dot. In the depot, the vehicles and equipment are stored when not being used. There are no turbines and therefore no tasks to be carried out at the depot. The qualifications of the teams are heterogeneous, and each team travels with a specific selection of tools and equipment in their vehicle. Therefore, the duration of maintenance operations and hourly wages differ between the teams. Based on historical data and information from wind turbine condition monitoring, a rough estimate is made of the expected scope of work in the different modes, i.e., for the different teams. Information from previous regeneration events can also be included if, for example, an uncritical error has already been identified but has not yet been remedied. Initially, it is assumed that all values are known in advance.
A solution is characterized by an assignment of a starting time (within its time window) and a responsible team for each maintenance activity at each turbine; thus, the team specific tours can be derived. In addition, the start and end working time of each team needs to be defined to compute the total working hours of each team. A model solution is shown in Fig. 1.4. The activities on turbines 2, 3 and 4 are executed by blue team 2. For example, the maintenance process on turbine 2 starts at day 2, and the activity on turbine 3 starts at day 7 after a transfer of this team from the location of turbine 2 to the location of turbine 3. The overall working hours of both teams in this schedule are 12 and 15 days, respectively. This results in personnel costs of 39 monetary units, assuming one day of team 2 costs 2 monetary units and team 1 is cheaper with 1 monetary unit per day.
We formally defined the introduced problem setting as a mixed-integer linear model. The first numerical results when solving instances to proven optimality using a commercial standard solver show an almost exponential increase in the required CPU times. This, in combination with the fact that multiple-hard problems are subproblems of this new problem, makes it very likely that no exact solution procedure will be able to identify the optimal solutions of this problem in an acceptable time. Therefore, it seems promising to develop problem-specific heuristic solution procedures for this problem to quickly obtain good solutions. Since both local search procedures and column-generation approaches have been applied successfully to similar problems, we now adapt these two inexact solution methods and evaluate their efficiency at solving this problem in a heuristic fashion.
3.3 Related Literature
The interest in renewable energy sources in general and wind energy in particular has been growing in recent years due to regulatory incentives, which are motivated by public concerns regarding climate change. Therefore, the number of publications dealing with issues related to wind turbines has significantly increased in recent years. Irawan et al. (2017), Dai et al. (2015), and Stålhane et al. (2015) investigated routing and scheduling for offshore windfarms. Turbines located in offshore parks are typically harder to maintain due to the weather-dependent accessibility of the sites. Kovács et al. (2011) integrate their scheduling with condition monitoring and error diagnosis. Sinha and Steel (2015) are performing a risk-based analysis of turbine outages. Byon et al. (2010) consider weather-related issues and Tautz-Weinert et al. (2019) the relevance of financial aspects. Salo et al. (2018) use text mining on historical data of turbines. None of the cited sources considers integrated routing and scheduling with heterogeneously qualified teams and time windows.
Multiple publications deal with the technical aspects of wind turbine repairs. A review of different methods for the repair of wind turbines can be found in Mishnaevsky Jr (2019). Ozturk and Fthenakis (2020) predict the frequency, repair times and costs for wind turbine failures using Bayesian updating. Colone et al. (2019) present predictive repair scheduling of wind turbine drive-train components based on machine learning.
In addition to the obvious proximity to routing problems, this problem is related to machine scheduling, in which orders are assigned to different machines. Travel times can be interpreted as sequence-dependent setup times, as shown by Brucker and Knust (2012).
3.4 Heuristic Solution Approaches
3.4.1 Local Search with Indirect Encoding
The problem setting can be interpreted as an integrated partitioning and sequencing problem. The maintenance tasks are partitioned into subsets whereby each subset corresponds to one team. The order of the wind turbines in such a set then defines the sequence of the maintenance actions. Decoding these sequences into an overall schedule is possible by using a schedule generation scheme, which derives the starting times for all maintenance activities.
The schedule is derived from that sequence by letting the team start its tour before the beginning of the first activity in its sequence so that it arrives exactly at the beginning of the time window belonging to the maintenance action at the turbine. The team then finishes processing and drives to the next activity in the sequence, again having a look at the feasible time window and so on. If the processing of one activity ends after the right-hand-side of the time window, the procedure aborts and sets the total working hours of team k to the number of teams K multiplied with planning horizon T as a penalty. After all activities are scheduled, the activities except the latest one are aligned to the right to ensure that the total working hours are not unnecessarily increased by the previous left alignment of activities. For example, the solution presented in Fig. 1.4 would be represented by the sequence 1, 5 for green team 1 and the sequence 2, 3, 4 for blue team 2.
As an indirect encoding, the shown representation was implemented in a problem- tailored heuristic solution approach using the commercial software LocalSolver, cf. www.localsolver.com. We compare this approach with solving the mixed-integer linear program (MIP) using the standard solver CPLEX for an instance with 24 tasks and 4 teams. Figure 1.5 contains a diagram showing the progression of the average gap to the best-known solution over time up to a time limit of 30 seconds. Both solution procedures start with a gap of 100%. LocalSolver is able to quickly improve upon the initial candidate solution and identifies solutions with a gap of under 10% after just 3 seconds of running time. The MIP solver CPLEX is significantly slower in finding better solutions. CPLEX is not able to overtake LocalSolver before reaching the time limit.
3.4.2 Column-Generation Based Problem Size Reduction
After the assignment of maintenance tasks to teams is finalized, there are no dependencies between the teams. Therefore, it seems promising to decompose the underlying problem into a set of subproblems dealing with the scheduling of the different teams. Of course, the choice of the actually implemented tasks can also be part of the subproblem of creating a schedule for a team. This decomposition can be used in a column-generation scheme, where the master problem consists of choosing a set of possible team schedules such that each task is covered by at least one chosen schedule and for each team, no more than one schedule is selected.
To generate new schedules with potentially reduced costs in the subproblems, the shadow prices depicted from the LP-relaxed version of the restricted master problem (RMP) are included in the objective function of the subproblem for each team. For example, they reflect the attraction of including a certain location in the solution of the subproblem. The objective computes the reduced costs by considering the actual costs of the newly generated schedule and subtracting the shadow prices πi and σk of the constraints for all covered tasks i and the selected team k, respectively. If the objective function value of any schedule is strictly negative, this schedule is added to the restricted master problem, and the loop of iteratively solving the master and the subproblem is started again.
The column-generation approach does not lead to feasible solutions, as only a relaxation of the master problem is solved. For this reason, the mixed-integer linear programming formulation of the original model is solved afterwards. The advantage of our approach is that the problem size can be heuristically reduced by fixing some variable bounds. Team-/task-assignments, which never occur in any selected schedule in the final master RMP solution, are forbidden by setting the upper bounds of the corresponding decision variables to zero.
3.4.3 Numerical Results
Figure 1.6 shows the required time and reached gap to the solution obtained with a MIP solver with a time limit of 3,600 seconds and an average computational time of 1,445.83 seconds for instances with 6 teams, 4 locations, and 12 tasks for three different solution methods. The first solution method uses LocalSolver and the integrated partition- and sequencing-problem approach to solve the problem monolithically. LocalSolver is able to reach a deviation of less than 1% in only approximately 7 seconds. The second solution method is a combination of mathematical programming for column generation and a MIP solver for the resulting reduced problem with for- bidden team-task associations. This approach requires slightly less time but results in a lower solution quality. As a third solution method, the final reduced problem is solved using LocalSolver. Here, the CPU times are higher, and the solution quality is lower.
The results show that all three methods are much faster than the MIP solver with less than 1% of its computational time and maintaining a very high quality. This shows that these approaches are useful for efficiently scheduling maintenance tasks on immobile capital goods. Using LocalSolver to solve the base problem seems the most promising. The column-generation approach can be used to obtain lower bounds in a Branch-and-Price approach to compute exact solutions. This is an interesting aspect for future research.
4 Condition-Based Planning of Maintenance Actions
4.1 Problem Setting
In the previous section, it was assumed that each turbine must be maintained within a defined time interval reflecting a certain service level for energy production. However, in reality, such hard time windows do not exist. Instead, there is a desired point in time for the maintenance of a certain wind turbine, and deviations from this time are feasible but should be avoided. On one hand, if a turbine is maintained too early, in long-term maintenance actions, the corresponding costs occur too often. On the other hand, if the desired time is exceeded due to the limited availability of the teams and requirements of other turbines, the turbine may fail. To avoid both situations, we penalize delays and earliness in the objective function. Thus, our approach allows for condition-based scheduling without limiting the possible solutions using hard time windows.
The desired maintenance time can be determined, for example, by evaluating automatically transmitted turbine condition data, which can be used to predict the failure time of a component. Nevertheless, in practice, the many uncertain factors, such as different wear of individual components due to different environmental conditions or production qualities, make an exact forecast of the desired maintenance time difficult. The desired maintenance time of each turbine is, therefore, considered a stochastic variable.
4.2 Related Literature
In Ahmad and Kamaruddin (2012b), Ahmad and Kamaruddin (2012a) as well as Bousdekis et al. (2015), general reviews on condition-based maintenance decision-making and its application in industry are given. An overview of condition-based maintenance strategies in the context of offshore wind energy with a focus on condition monitoring, fault diagnosis and prognosis, and maintenance optimization is given by Kang et al. (2019).
Zhang et al. (2015) presented a framework for the condition-based maintenance and operation of wind turbines. Zhou and Yin (2019) report a reduction of annual maintenance cost by 30–40% due to an opportunistic condition-based maintenance strategy for offshore wind farms.
Song et al. (2018) define a condition-based maintenance policy with periodic inspection intervals. Therefore, probabilistic models are built for stochastic wind speeds and directions. The preventive maintenance scheduling problem with interval costs is introduced by Bangalore and Patriksson (2018). It considers both age-based and condition-based models to provide more flexible maintenance schedules than the constant-interval approach. Likewise, the rolling horizon stochastic optimization model on a daily basis by Besnard et al. (2011) is able to minimize service maintenance costs compared to performing the maintenance during a fixed period.
Wang et al. (2021) analyse the cost advantages of grouped maintenance actions for a wind farm compared to the loss of revenue to do waiting times for single failed turbines. A genetic algorithm to solve the optimisation problem is presented. The combination of condition-based maintenance and time-based preventive maintenance can be used to find a cost-optimal degradation threshold and to avoid overuse or underuse of maintenance tasks, cf. Dao et al. (2021).
Ghamlouch et al. (2019) propose a decision-making procedure for condition- based maintenance planning in a dynamic environment and/or variable working conditions leading to stochastic deterioration and production processes. Tian et al. (2011) develop an approach to determine an optimal maintenance schedule given the failure probabilities for components and the system. A case study of a wind turbine gearbox is discussed in Byon and Ding (2010). The consideration of seasonal weather effects in the context of condition-based maintenance is able to improve the cost structure.
4.3 Scenario-Based Compensation Model
The stochastic model arising can be interpreted as a two-stage compensation model, cf. Gendreau et al. (1996) and Scholl (2001). In such a model, a distinction is made between deterministic first-stage decisions and stochastic second-stage decisions. In the first stage, the schedule is defined. In the second stage, the deviation between actual and (beforehand unknown) desired maintenance time is compensated by the penalty costs for earliness or tardiness. Please note that the second stage only is introduced as a fictitious stage to consider the stochastic nature of the problem setting. As the optimal desired maintenance time of a turbine is not observable, the penalties are interpreted as opportunity costs.
To include the penalty costs for the compensation measure on the first stage and to be able to formulate a deterministic substitute model solvable with standard methods, a scenario approach is used. In this method, many different fictitious scenarios with their associated probability of occurrence are considered even in the first-stage decision. The scenario approach makes it possible to work with several deterministic substitute values for the original stochastic value instead of only using the mean value. The objective function is no longer calculated for a single scenario, but a sum is minimised over all scenarios multiplied by the probability of occurrence of the scenario.
The generation of the individual scenarios is very important for the quality of the scenario approach. On one hand, the more scenarios that are generated, the more robust the final solution becomes. On the other hand, the computational effort also increases considerably with an increasing number of scenarios. In simple random sampling, in which a random sample is drawn independently from the given distribution, a useful distribution of the scenarios is not ensured, as shown in Fig. 1.7. In the descriptive sampling by Saliby (1990), the distribution function is divided into different quantiles, as shown by the dotted black lines in Fig. 1.8. As many quantiles of the same size are formed as scenarios are desired. Then, for each quantile, the value of the distribution function at the position of the medium value of the quantile is chosen; see green lines. In this way, a better representation of the stochastic distribution is achieved. For this reason, descriptive sampling is used to create the scenarios.
4.4 Numerical Analysis
The effect of the condition-based approach on the optimal maintenance time is examined for different ratios of the deviation costs for earliness and tardiness. To focus on the general behaviour, only one turbine that can be maintained by one team is considered. The only decision to be made is about the cost-optimal starting time over all scenarios.
The (unknown) desired maintenance times for the different scenarios are generated in the interval [3, 5]. As a fixed cost rate, the delay costs are set to cdelay = 20 monetary units. The earliness costs are drawn from the interval cpre = [1, 500] monetary units. Thus, ratios in the range cpre/cdelay [0, 25] are considered. The optimal maintenance times are plotted against this cost ratio cpre/cdelay; see Fig. 1.9. With a cost ratio of 1, the optimal maintenance time with a value of 4 reflects as expected the mean value of the linearly distributed scenarios. For ratios of cpre/cdelay < 1, it is attractive to maintain the turbine earlier than at the mean value, and for ratios above 1, the processing should start later than the mean value. For a model ratio cpre/cdelay = 5, it is five times more costly to regenerate the good one period too early than to delay the regeneration event by one period. In this case, the optimal regeneration time would be 4.5. The analysis shows that the optimal starting time cannot be determined linearly from the cost ratio, which justifies the usage of a scenario approach.
Of course, this analysis only focuses on the regeneration of one turbine. In the case of multiple spatially distributed wind parks and different teams, the selection of an optimal start of the regeneration process is substantially more complex but follows the same approach. It is done by integrating the described approach into the model reflecting the problem setting in Sect. 3.
5 Consideration of Stochastic Service Times and Weather-Dependent Availability
5.1 Problem Setting
The assumption of deterministic team-specific durations for the maintenance activities does not hold in practice since manual operations and unknown conditions may increase the actual time required for any maintenance activity. Therefore, the formerly deterministic parameter for the service time of a given team at a given location is now modelled as a random variable. A gamma distribution is able to represent stochastic service times very well. Figure 1.10 shows the density function of a gamma distribution, which is right-skewed. This means that small deviations from the service time are very likely, while very strong deviations are possible but rather unlikely.
In addition, we now explicitly model the weather situation. If at a certain location on a certain day the weather is so bad that it does not allow maintenance work, this location cannot be included in the tour on this day. To be able to take the single days into account, we assume a finer time structure with an exact modelling of the workdays with a maximum daily working time and a maximum weekly working time. In this situation, neither time windows nor penalties for earliness or tardiness are considered, as it is assumed that for this shorter planning horizon, all included turbines are schedulable and that the deviation from the desired starting time is no longer decision-relevant.
Again, we use a two-stage approach in a scenario-based decomposition model. The sequence of the locations as well as the team assignments are independent of the scenarios and reflect the decisions on the first stage. They are determined in advance before the service times are realised. For example, for one team, the sequence of locations could be defined as (2, 4, 3, 5, 1). In the second stage, the maintenance actions in the given sequence are assigned to specific days. Please note that the scenarios are no longer fictitious as for the conditions-based approach but that the realized service times can be observed ex-post.
Possible solutions for different scenarios are presented in Figs. 1.11 and 1.12. In scenario 1, the team travels from turbine 2 to turbine 4 and then to turbine 3 in the first tour, but in scenario 2, due to a longer duration of the maintenance actions on turbine 4, the team only visits turbines 2 and 4 in the first tour.
As a compensation measure to ensure that the decision on the first stage leads to feasible schedules for the second stage, we introduce the possibility of not visiting a location at all being associated with penalty costs.
5.2 Related Literature
In practical vehicle routing problems, the parameters are often not known or are subject to certain fluctuations. Most likely, the most commonly assumed source of uncertainty, according to Gendreau et al. (1996), is stochastic demand. In this case, the level of demand at the customer location is uncertain and may fluctuate. Other approaches include stochastic customers. In this case, the demand at each customer location is deterministic, but there may be a certain probability that customers are not present. Bertsimas (1992) consider both stochastic customers and stochastic demands, which consist of two stages. In the first stage, several routes are planned, with each of the routes starting and ending at the depot. In the second step, the customers’ actual absence and realized demand are considered. Han et al. (2013) present a tour planning model where travel times are uncertain. They also use a two- stage model, whereby the routes are determined in the first stage. In the second stage, the exact travel times are known, and penalty costs are calculated for the excessive duration of a route.
5.3 Heuristic Solution Approaches
5.3.1 Schedule Generation Scheme
Even for a very small instance with only twelve locations, the MIP solver Gurobi could not find an optimal solution within a given time limit of 3,600 seconds. This shows that again, a heuristic solution approach is necessary. The solution representation remains the same as described in Sect. 3.4.1, but there are small adjustments in the schedule generation scheme necessary. The scheduling takes place for each scenario. The maintenance tasks are scheduled one after the other in the given sequence until the maximum daily and/or weekly working time for the current day is exceeded. The remaining locations are then visited on the following day. Locations that cannot be visited due to bad weather are first put on hold, and an attempt is made to schedule them again the next day. For all locations that are not visited at all, penalty costs are added to the service and travel costs.
5.3.2 Genetic Algorithm
Genetic algorithms have been widely studied, cf., e.g., Holland (1992), and are also used to solve a route planning problem with stochastic elements, cf., e.g., Ando and Taniguchi (2006). In this approach, each individual represents a single solution. A population consists of multiple individuals and can be created by randomly assigning locations to teams for each individual. This ensures that all teams have a roughly identical number of locations.
To generate offspring, two parents are randomly selected from the population. Two offspring are produced using the Partially Mapped Crossover according to Mak and Guo (2004). The generated offspring can mutate with a certain probability. In the selection, the best individuals are selected from all parent and child individuals of the current generation to form the parents of the next generation. Once a maximum number of generations is reached, the algorithm is terminated, and the individual with the best objective function value represents the solution to the problem.
5.3.3 Tabu Search
According to Oyola and Arntzen (2017), tabu search is the most commonly used search strategy among local search strategy options. Approaches in this area are also able to find very good solutions to routing problems, cf., e.g., Gendreau et al. (1994). Therefore, tabu search was chosen as an alternative heuristic.
Tabu search is a local search method. Starting from a previously created initial solution, new neighbouring solutions are generated using the cross-exchange operator by Taillard et al. (1997). The order of the locations of two randomly chosen routes from different teams are exchanged with each other, resulting in a new solution. For each neighbouring solution, it is checked whether this solution is on the tabu list. If this is the case, it is deleted to prevent solutions from being visited repeatedly and the procedure from getting stuck in a local optimum. The solution with the best objective function value is adopted as the new solution and is added to the tabu list. This is independent of whether the new neighbouring solution is better or worse than the original solution so that a larger solution space is searched, cf. Scholl and Domschke (2010). When the maximum tabu length is reached, the first solution is deleted from the list. The next iteration starts until a termination criterion is reached.
5.3.4 Numerical Results
The numerical results are shown in Fig. 1.13. For the first instance with 12 wind turbines, the genetic algorithm (GA) and the tabu search (TS) were able to find a solution that is slightly worse than the solution of the MIP solver Gurobi. However, they took only approximately 5 seconds. For the second instance with 20 turbines, the genetic algorithm was able to find a solution with a better objective function value in a very short time of 11 seconds. The tabu search performed slightly worse than the genetic algorithm but was still able to find a better solution than the Gurobi model in only 5 seconds.
For the two larger instances, Gurobi could only find a solution in which no location is visited in the given time limit of one hour. The genetic algorithm and the tabu search were able to find remarkably better solutions. The solutions of the genetic algorithm are slightly better than those of the tabu search, but the genetic algorithm has slightly longer solution times of 22 and 35 seconds, respectively, while the tabu search is again terminated after five seconds.
In summary, it can be stated that with the deterministic replacement model, it is almost impossible to find an optimal solution due to the size of the model. The use of a heuristic solution procedure is significantly less time-consuming. The solutions of the genetic algorithm were slightly better than those of the tabu search. This shows that both approaches are very promising for solving the problem of scheduling maintenance tasks on distributed wind farms considering uncertainty in a reasonable amount of time.
6 Conclusions
In this paper, we addressed several variants of the selection of efficient modes for the regeneration of complex capital goods. For this efficient design of regeneration processes, the scarce capacities of the regeneration system and the teams need to be explicitly considered in the planning process. Using heuristic operations research methods such as simulated annealing, tabu search and genetic algorithms, it is possible to choose an efficient mode and to schedule the corresponding tasks quickly and with good solution quality.
We have demonstrated the practical applicability of our approach for the regeneration of turbine blades of aircraft engines by embedding it in the system demonstrator of CRC 871 with the customer business model as an important factor for determining the most efficient regeneration mode.
The general considerations and operations research methods are transferable to maintenance actions on immobile capital goods such as wind turbines. As the distances between the goods need to be considered, aspects of routing problems were included. In addition, the uncertainty arising in this context was explicitly included in a stochastic two-stage approach.
Future research should consider the maintenance processes on more complex capital goods with their additional challenges. For example, for a network of waste incineration plants in which domestic waste is thermally utilized to generate process steam, district heating, and electrical energy, specific and local waste input commitments and energy output commitments are given. They must be fulfilled even if a plant is regenerated. Therefore, balancing processes between the different plants must be considered. Again, with operation research methods, a decision support system can help select and schedule the associated operations.
References
Ahmad, R. and Kamaruddin, S. (2012a). An overview of time-based and condition-based maintenance in industrial application. Computers & Industrial Engineering, 63(1):135–149.
Ahmad, R. and Kamaruddin, S. (2012b). A review of condition-based maintenance decision-making. European Journal of Industrial Engineering, 6(5):519–541.
Ando, N. and Taniguchi, E. (2006). Travel time reliability in vehicle routing and scheduling with time windows. Networks and Spatial Economics, 6:293–311.
Bangalore, P. and Patriksson, M. (2018). Analysis of SCADA data for early fault detection, with application to the maintenance management of wind turbines. Renewable Energy, 115:521–532.
Bertsimas, D. (1992). A vehicle routing problem with stochastic demand. Operations Research, 40(3):574–585.
Besnard, F., Patriksson, M., Strömberg, A.-B., Wojciechowski, A., Fischer, K., and Bertling, L. (2011). A stochastic model for opportunistic maintenance planning of offshore wind farms. In 2011 IEEE Trondheim PowerTech, pages 1–8.
Bousdekis, A., Magoutas, B., Apostolou, D., and Mentzas, G. (2015). A proactive decision making framework for condition-based maintenance. Industrial Management & Data Systems, 115(7):1225– 1250.
Brucker, P. and Knust, S. (2012). Complex scheduling. GOR-Publications. Springer, Berlin Heidelberg.
Byon, E. and Ding, Y. (2010). Season-dependent condition-based maintenance for a wind turbine using a partially observed markov decision process. IEEE Transactions on Power Systems, 25(4):1823–1834.
Byon, E., Ntaimo, L., and Ding, Y. (2010). Optimal maintenance strategies for wind turbine systems under stochastic weather conditions. IEEE Transactions on Reliability, 59(2):393–404.
Colone, L., Dimitrov, N., and Straub, D. (2019). Predictive repair scheduling of wind turbine drive-train components based on machine learning. Wind Energy, 22(9):1230–1242.
Dai, L., Stålhane, M., and Utne, I. B. (2015). Routing and scheduling of maintenance fleet for offshore wind farms. Wind Engineering, 39(1):15–30.
Dao, C. D., Kazemtabrizi, B., Crabtree, C. J., and Tavner, P. J. (2021). Integrated condition-based maintenance modelling and optimisation for offshore wind turbines. Wind Energy, 24(11):1180–1198.
Gendreau, M., Hertz, A., and Laporte, G. (1994). A tabu search heuristic for the vehicle routing problem. Management Science, 40(10):1276–1290.
Gendreau, M., Laporte, G., and Seguin, R. (1996). Stochastic vehicle routing. European Journal of Operational Research, 88(1):3–12.
Ghamlouch, H., Fouladirad, M., and Grall, A. (2019). The use of real option in condition-based maintenance scheduling for wind turbines with production and deterioration uncertainties. Reliability Engineering & System Safety, 188:614–623.
Han, J., Lee, C., and Park, S. (2013). A robust scenario approach for the vehicle routing problem with uncertain travel times. Transportation Science, 48(3):373–390.
Hoffmann, L.-S., Kellenbrink, C., and Helber, S. (2020). Simultaneous structuring and scheduling of multiple projects with flexible project structures. Journal of Business Economics, 90(5):679–711.
Holland, J. (1992). Genetic algorithms. Scientific American, 267(1):66–72.
Irawan, C. A., Ouelhadj, D., Jones, D., Stålhane, M., and Sperstad, I. B. (2017). Optimisation of maintenance routing and scheduling for offshore wind farms. European Journal of Operational Research, 256(1):76–89.
Kang, J., Sobral, J., and Guedes Soares, C. (2019). Review of condition-based maintenance strategies for offshore wind energy. Journal of Marine Science and Application, 18:1–16.
Kellenbrink, C. and Helber, S. (2015). Scheduling resource-constrained projects with a flexible project structure. European Journal of Operational Research, 246(2):379–391.
Kellenbrink, C. and Helber, S. (2016). Quality- and profit-oriented scheduling of resource-constrained projects with flexible project structure via a genetic algorithm. European Journal of Industrial Engineering, 10(5):574–595.
Kellenbrink, C., Nübel, N., Schnabel, A., Gilge, P., Seume, J. R., Denkena, B., and Helber, S. (2022). A regeneration process chain with an in- tegrated decision support system for individual regeneration processes based on a virtual twin. International Journal of Production Research, https://doi.org/https://doi.org/10.1080/00207543.2022.2051089.
Kovács, A., Erdős, G., Viharos, Z. J., and Monostori, L. (2011). A system for the detailed scheduling of wind farm maintenance. CIRP Annals, 60(1):497–501.
Mak, K. and Guo, Z. (2004). A genetic algorithm for vehicle routing problems with stochastic demand and soft time windows. Proceedings of the 2004 IEEE Systems and Information Engineering Design Symposium, pages 183–190.
Mishnaevsky Jr, L. (2019). Repair of wind turbine blades: Review of methods and related computational mechanics problems. Renewable energy, 140:828–839.
Oyola, J. and Arntzen, H. und Woodruff, D. (2017). The stochastic vehicle rout- ing problem, a literature review, part II: solution methods. EURO Journal on Transportation and Logistics, 6(4):349–388.
Ozturk, S. and Fthenakis, V. (2020). Predicting frequency, time-to-repair and costs of wind turbine failures. Energies, 13(5):1149.
Saliby, E. (1990). Descriptive sampling: A better approach to monte carlo simulation.
The Journal of the Operational Research Society, 41:1133–1142.
Salo, E., McMillan, D., and Connor, R. (2018). Value from free-text maintenance records: converting wind farm work orders into quantifiable, actionable information using text mining. Analysis of Operating Wind Farms 2018.
Scholl, A. (2001). Robuste Planung und Optimierung: Grundlagen - Konzepte und Methoden - experimentelle Untersuchungen. Physica-Verlag, Heidelberg.
Scholl, A. and Domschke, W. (2010). Logistik: Rundreisen und Touren. Oldenbourg Wissenschaftsverlag GmbH, München.
Sinha, Y. and Steel, J. A. (2015). A progressive study into offshore wind farm maintenance optimisation using risk based failure analysis. Renewable and Sustainable Energy Reviews, 42:735–742.
Song, S., Li, Q., Felder, F. A., Wang, H., and Coit, D. W. (2018). Integrated optimization of offshore wind farm layout design and turbine opportunistic condition-based maintenance. Computers & Industrial Engineering, 120:288–297.
Stålhane, M., Hvattum, L. M., and Skaar, V. (2015). Optimization of routing and scheduling of vessels to perform maintenance at offshore wind farms. Energy Procedia, 80:92–99.
Taillard, E., Badeau, P., Gendreau, M., Guertin, F., and Potvin, J. (1997). A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation science, 31(2):170–186.
Tautz-Weinert, J., Yürüşen, N. Y., Melero, J. J., and Watson, S. J. (2019). Sensitivity study of a wind farm maintenance decision-a performance and revenue analysis. Renewable energy, 132:93–105.
Tian, Z., Jin, T., Wu, B., and Ding, F. (2011). Condition based maintenance optimiza- tion for wind power generation systems under continuous monitoring. Renewable Energy, 36(5):1502–1509.
Wang, J., Zhang, X., and Zeng, J. (2021). Optimal group maintenance decision for a wind farm based on condition-based maintenance. Wind Energy, 24(12):1517–1535.
Zhang, T., Dwight, R., and El-Akruti, K. (2015). Condition based maintenance and operation of wind turbines. In Tse, P. W., Mathew, J., Wong, K., Lam, R., and Ko, C., editors, Engineering Asset Management - Systems, Professional Practices and Certification, pages 1013–1025, Cham. Springer International Publishing.
Zhou, P. and Yin, P. (2019). An opportunistic condition-based maintenance strategy for offshore wind farm based on predictive analytics. Renewable and Sustainable Energy Reviews, 109:1–9.
Acknowledgements
Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Founda- tion) – SFB 871/3 – 119193472.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2025 The Author(s)
About this chapter
Cite this chapter
Kellenbrink, C., Schnabel, A., Hoppmann, M., Woidtke, J.N., Helber, S. (2025). Selection of Efficient Regeneration Modes for the Regeneration of Complex Capital Goods. In: Seume, J.R., Denkena, B., Gilge, P. (eds) Regeneration of Complex Capital Goods. Springer, Cham. https://doi.org/10.1007/978-3-031-51395-4_19
Download citation
DOI: https://doi.org/10.1007/978-3-031-51395-4_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-51394-7
Online ISBN: 978-3-031-51395-4
eBook Packages: EngineeringEngineering (R0)