| 1. |
- Almgren, Torgny, 1962, et al.
(författare)
-
Optimization models for improving periodic maintenance schedules by utilizing opportunities
- 2012
-
Ingår i: Proceedings of 4th Production and Operations Management World Conference, July 2012.
-
Konferensbidrag (refereegranskat)abstract
- We present mathematical models for finding optimal opportunistic maintenance schedules for systems, in which components are assigned maximum replacement intervals. Our mod- els are applied to safety-critical components in an aircraft engine, for which maintenance opportunities naturally arise since entire modules are sent to the workshop when mainte- nance is required on one or more components. Case study results illustrate the advantage of the mathematical models over simpler policies, the benefit of coordinating the maintenance in economically dependent systems, and that our models can be utilized also for strategic investment decision support.
|
|
| 2. |
- Almgren, Torgny, 1962, et al.
(författare)
-
The opportunistic replacement problem: analysis and case studies
- 2011
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- We consider an optimization model for determining optimal opportunistic maintenance (that is, component replacement) schedules when data is deterministic. This problem generalizes that of Dickman, Epstein, and Wilamowsky [21] and is a natural starting point for the modelling of replacement schedules when component lives are non-deterministic. We show that this basic opportunistic replacement problem is NP-hard. We show that the convex hull of the set of feasible replacement schedules is full-dimensional, and that all the necessary inequalities also are facet-inducing. We show that when maintenance occasions are fixed, the remaining problem can be stated as a linear program; when maintenance costs are monotone with time, the latter is solvable through a greedy procedure. Results from a series of case studies performed in the areas of aircraft engine and wind turbine maintenance are also reported. These illustrate the advantages of utilizing opportunistic maintenance activities based on a complete optimization model, as compared to simpler policies.
|
|
| 3. |
- Almgren, Torgny, 1962, et al.
(författare)
-
The opportunistic replacement problem: theoretical analyses and numerical tests
- 2012
-
Ingår i: Mathematical Methods of Operations Research. - : Springer Science and Business Media LLC. - 1432-2994 .- 1432-5217. ; 76:3, s. 289-319
-
Tidskriftsartikel (refereegranskat)abstract
- We consider a model for determining optimal opportunistic maintenance schedules with respect to a maximum replacement interval. This problem generalizes that of Dickman et al. (J Oper Res Soc India 28:165–175, 1991) and is a natural starting point for modelling replacement schedules of more complex systems. We show that this basic opportunistic replacement problem is NP-hard, that the convex hull of the set of feasible replacement schedules is full-dimensional, that all the inequalities of the model are facet-inducing, and present a new class of facets obtained through a {0,1/2}-Chvátal–Gomory rounding. For costs monotone with time, a class of elimination constraints is introduced to reduce the computation time; it allows maintenance only when the replacement of at least one component is necessary. For costs decreasing with time, these constraints eliminate non-optimal solutions. When maintenance occasions are fixed, the remaining problem is stated as a linear program and solved by a greedy procedure. Results from a case study on aircraft engine maintenance illustrate the advantage of the optimization model over simpler policies. We include the new class of facets in a branch-and-cut framework and note a decrease in the number of branch-and-bound nodes and simplex iterations for most instance classes with time dependent costs. For instance classes with time independent costs and few components the elimination constraints are used favorably. For fixed maintenance occasions the greedy procedure reduces the computation time as compared with linear programming techniques for all instances tested.
|
|
| 4. |
- Almgren, Torgny, 1962, et al.
(författare)
-
The replacement problem: A polyhedral and complexity analysis. The complete version
- 2009
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- We consider an optimization model for determining optimal opportunistic maintenance (that is, component replacement) schedules when data is deterministic. This problem, which generalizes that of Dickman et al., is a natural starting point for the modelling of replacement schedules when component lives are non-deterministic, whence a mathematical study of the model is of large interest. We show that the convex hull of the set of feasible replacement schedules is full-dimensional, and that all the necessary inequalities are facet-inducing. Additional facets are then provided through Chvatal-Gomory rounding. We show that when maintenance occasions are fixed, the remaining problem reduces to a linear program; in some cases the latter is solvable through a greedy procedure. We further show that this basic replacement problem is NP-hard.
|
|
| 5. |
|
|
| 6. |
- Besnard, Francois, 1983, et al.
(författare)
-
A stochastic model for opportunistic maintenance planning of offshore wind farms
- 2011
-
Ingår i: 2011 IEEE PES Trondheim PowerTech: The Power of Technology for a Sustainable Society, POWERTECH 2011; Trondheim; 19 June 2011 through 23 June 2011. - 9781424484195
-
Konferensbidrag (refereegranskat)abstract
- A sound maintenance planning is of crucial importance for wind power farms, and especially for offshore locations. This paper presents a stochastic optimization model for opportunistic service maintenance of offshore wind farms. The model takes advantage of 7 days wind production ensemble forecast and opportunities at corrective maintenance activities in order to perform the service maintenance tasks at the lowest cost. The model is based on a rolling horizon, i.e. the optimization is performed on a daily basis to update the maintenance planning based on the updated production and weather forecasts. An example based on real wind data is used to demonstrate the value of the proposed approach. In this example, it is shown that 32% of the cost for production losses and transportation could be saved. © 2011 IEEE.
|
|
| 7. |
- Besnard, Francois, et al.
(författare)
-
An Optimization Framework for Opportunistic Maintenance of Offshore Wind Power System
- 2009
-
Ingår i: 2009 IEEE BUCHAREST POWERTECH, VOLS 1-5. - NEW YORK : IEEE. - 9781424422340 ; , s. 2970-2976
-
Konferensbidrag (refereegranskat)abstract
- A sound maintenance planning is of crucial importance for wind power farms, and especially for offshore locations. There is a large potential in cost savings by maintenance optimization to make the projects more cost-efficient. This paper presents an opportunistic maintenance optimization model for offshore wind power system. The model takes advantage of wind forecasts and corrective maintenance activities in order to perform preventive maintenance tasks at low costs. The approach is illustrated with an example to demonstrate the value of the optimization. In this example 43% of the cost to perform preventive maintenance could be saved using the proposed method.
|
|
| 8. |
|
|
| 9. |
- Gollowitzer, S., et al.
(författare)
-
A Comparison of Several Models for the Hamiltonian p-Median Problem
- 2014
-
Ingår i: Networks. - : Wiley. - 0028-3045 .- 1097-0037. ; 63:4, s. 350-363
-
Tidskriftsartikel (refereegranskat)abstract
- The Hamiltonian p-median problem consists of determining p disjoint cycles of minimum total cost covering all vertices of a graph. We present several new and existing models for this problem, provide a hierarchy with respect to the quality of the lower bounds yielded by their linear programming relaxations, and compare their computational performance on a set of benchmark instances. We conclude that three of the models are superior from a computational point of view, two of which are introduced in this article. (C) 2014 Wiley Periodicals, Inc.
|
|
| 10. |
- Gollowitzer, Stefan, et al.
(författare)
-
New Models for and Numerical Tests of the Hamiltonian p-Median Problem
- 2011
-
Ingår i: Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 9783642215261 ; 6701/2011, s. 385-394
-
Konferensbidrag (refereegranskat)abstract
- The Hamiltonian p-median problem (HpMP) was introduced by [Branco90]. It is closely related to two well-known problems, namely the Travelling Salesman problem (TSP) and the Vehicle Routing problem (VRP). The HpMP is to find exactly p node-disjoint cycles of minimum edge cost, such that each node of the graph is contained in exactly one cycle. We present three new models for the HpMP problem which differ with regard to the constraints that enforce a maximum number of cycles. We demonstrate that one of the models (SEC) is dominated by another model (PCON) with regard to the LP relaxation. Further, we introduce a class of symmetry breaking constraints. We present results regarding the quality of the lower bounds provided by the respective LP relaxations for two of the models, and provide computational results that demonstrate the computational efficiency.
|
|
| 11. |
- Gustavsson, Emil, 1987, et al.
(författare)
-
Preventive maintenance scheduling of multi-component systems with deterioration costs
- 2012
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- We introduce the preventive maintenance scheduling problem with interval costs (PMSPIC), which is to schedule preventive maintenance of components of a system over a finite discretized time horizon, given a common set-up cost and component costs dependent on the lengths of the maintenance intervals. We present a 0-1 integer linear programming (0-1 ILP) model for the PMSPIC which was originally presented by Joneja (1990) to model the joint replenishment problem. We show that most of the integrality constraints can be relaxed and that the linear inequality constraints define facets of the convex hull of the feasible set. We present three applications demonstrating that the PMSPIC can be used to model several types of maintenance problems with deterioration costs. The first considers rail grinding. If the interval between the grinding occasions increases, then the sizes of the rail cracks increase, which implies that more grinding passes must be performed, generating a higher maintenance cost. We presume a deterministic model for crack growth and optimize the scheduling of the rail grinding on a set of track sections. Our second application concerns two approaches for the scheduling of component replacements in aircraft engines. In the first approach a bi-objective problem, simultaneously minimizing the cost for the scheduled preventive maintenance and the probability of unexpected stops, is formulated. The second approach considers the minimization of the sum of costs of preventive and expected corrective maintenance, without rescheduling. We also demonstrate that if rescheduling is allowed, then the 0-1 ILP model can be used as a policy by re-optimizing the schedule at a component failure, thus utilizing the opportunity for preventive maintenance. We evaluate the use of such a strategy in a simulation of the engine. The third approach considers components’ replacement in wind mills in a wind farm, extending the PMSPIC to consider several systems with a joint set-up cost. As for the aircraft engine application, we use the 0-1 ILP model as a policy for deciding upon replacement decisions allowing for rescheduling, and evaluate it by simulating the joint system. In each of the three applications, the use of the 0-1 ILP model is compared with age or constantinterval policies, resulting in a reduction of maintenance costs by up to 15% compared with the respective best simple policy.
|
|
| 12. |
- Gustavsson, Emil, 1987, et al.
(författare)
-
Preventive maintenance scheduling of multi-component systems with interval costs
- 2014
-
Ingår i: Computers & industrial engineering. - : Elsevier BV. - 0360-8352. ; 76, s. 390-400
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce the preventive maintenance scheduling problem with interval costs (PMSPIC), which is to schedule preventive maintenance (PM) of the components of a system over a finite and discretized time horizon, given a common set-up cost and component costs dependent on the lengths of the maintenance intervals. We present a 0–1 integer linear programming (0–1 ILP) model for the PMSPIC; the model is identical to that presented by Joneja (1990) for the joint replenishment problem within inventory management. We study this model from a polyhedral and exact solutions’ point of view, as opposed to previously studied heuristics (e.g. Boctor, Laporte, & Renaud, 2004; Federgruen & Tzur, 1994; Levi, Roundy, & Shmoys, 2006; Joneja, 1990).We show that most of the integrality constraints can be relaxed and that the linear inequality constraints define facets of the convex hull of the feasible set. We further relate the PMSPIC to the opportunistic replacement problem, for which detailed polyhedral studies were performed by Almgren et al. (2012a). The PMSPIC can be used as a building block to model several types of maintenance planning problems possessing deterioration costs. By a careful modeling of these costs, a polyhedrally sound 0–1 ILP model is used to find optimal solutions to realistic-sized multi-component maintenance planning problems. The PMSPIC is thus easily extended by side constraints or to multiple tiers, which is demonstrated through three applications; these are chosen to span several levels of unmodeled randomness requiring fundamentally different maintenance policies, which are all handled by variations of our basic model. Our first application considers rail grinding. Rail cracks increase with increasing intervals between grinding occasions, implying that more grinding passes must be performed—thus generating higher costs. We optimize the grinding schedule for a set of track sections presuming a deterministic model for crack growth; hence, no corrective maintenance (CM) will occur between the grinding occasions scheduled. The second application concerns two approaches for scheduling component replacements in aircraft engines. The first approach is bi-objective, simultaneously minimizing the cost for the scheduled PM and the probability of unexpected stops. In the second approach the sum of costs for PM and expected CM—without rescheduling—is minimized. When rescheduling is allowed, the 0–1 ILP model is used as a policy by re-optimizing the schedule at a component failure, which then constitutes an opportunity for PM. The policy manages the trade-off between costs for PM and unplanned CM and is evaluated in a simulation of the engine. The third application considers components’ replacement in wind mills in a wind farm, extending the PMSPIC to comprise multiple tiers with joint set-up costs. Due to the large number of components unexpected stops occur frequently, thus calling for a dynamic rescheduling, which is evaluated through a simulation of the system. In each of the three applications, the use of the 0-1 ILP model is compared with age or constant-interval policies; the maintenance costs are reduced by up to 16% as compared with the respective best simple policy. The results are strongest for the first two applications, possessing low levels of unmodeled randomness.
|
|
| 13. |
|
|
| 14. |
- Jakobsson, Stefan, 1970, et al.
(författare)
-
A method for simulation based optimization using radial basis functions
- 2010
-
Ingår i: Optimization & Engineering. - : Springer Science and Business Media LLC. - 1573-2924 .- 1389-4420. ; 11:4, s. 501-532
-
Tidskriftsartikel (refereegranskat)abstract
- We propose an algorithm for the global optimization of expensive and noisy black box functions using a surrogate model based on radial basis functions (RBFs). A method for RBF-based approximation is introduced in order to handle noise. New points are selected to minimize the total model uncertainty weighted against the surrogate function value. The algorithm is extended to multiple objective functions by instead weighting against the distance to the surrogate Pareto front; it therefore constitutes the first algorithm for expensive, noisy and multiobjective problems in the literature. Numerical results on analytical test functions show promise in comparison to other (commercial) algorithms, as well as results from a simulation based optimization problem.
|
|
| 15. |
- Nilsson, Julia, et al.
(författare)
-
An evaluation approach for opportunistic maintenance optimization models for nuclear power plants
- 2010
-
Ingår i: Power and Energy Society General Meeting, 2010 IEEE. - : IEEE. - 9781424483570
-
Konferensbidrag (refereegranskat)abstract
- Nuclear power constitutes one of the main electricity production sources in several countries, e.g. in Sweden, with about half of today's electricity production. Driving forces for cost-efficiency have pushed the development of new methods for maintenance planning and optimization forward. Reliability Centered Asset Management (RCAM) is one of these new approaches, and maintenance optimization is one way to perform quantitative analysis which is a feature of RCAM. This paper proposes a stochastic framework for evaluating opportunistic maintenance optimization models for the generation of replacement schedules for shaft seals in feed-water pump systems in nuclear power plants. Results show that the extended discounted model has a good overall performance, when compared to other strategies. Moreover, it is shown that it is the best strategy for high values of the constant cost for maintenance and the second best for lower values of the constant cost.
|
|
| 16. |
|
|
| 17. |
- Nilsson, Julia, et al.
(författare)
-
An Opportunistic Maintenance Optimization Model for Shaft Seals in Feed-Water Pump Systems in Nuclear Power Plants
- 2009
-
Ingår i: 2009 IEEE Bucharest PowerTech. - New York : IEEE. - 9781424422340 ; , s. 2962-2969
-
Konferensbidrag (refereegranskat)abstract
- Nuclear power is one of the main electricity production sources in Sweden today. Maintenance management is one tool for reducing the costs for operation of a power plant. Driving forces for cost-efficiency has pushed the development of new methods for maintenance planning and optimization forward. Reliability Centered Asset Management (RCAM) is one of these new approaches, and maintenance optimization is one way to perform quantitative analysis which is a feature of RCAM. This paper proposes a model for opportunistic maintenance optimization where replacement schedules for shaft seals in feed-water pump systems in nuclear power plants are constructed. The feed-water pump system is important for the availability of the entire nuclear power plant. Results show that the optimization model is dependent on e.g. the discount interest and a limit for when the optimal solution goes from non-opportunistic to opportunistic is calculated. The circumstances for which opportunistic maintenance could be used have been investigated given different values of discount rates and remaining life at start of the planning period.
|
|
| 18. |
- Patriksson, Michael, 1964, et al.
(författare)
-
The opportunistic replacement problem with individual component lives
- 2011
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- We consider an extension of the opportunistic replacement problem, which has been studied by Dickman, Epstein and Wilamowsky [3], Andréasson [2], and Andréasson et al. [1], that allows the individuals of the same component to have nonidentical lives. Formulating and solving this problem defines a first step towards solving the opportunistic replacement problems with uncertain component lives. We show that the problem is NP-hard even with time independent costs, and present two mixed integer linear programming models for the problem. We show that in model I the binary requirement on the majority of the variables can be relaxed; this is in contrast to model II and Andréasson’s [2] model. We remove all superfluous variables and constraints in model I and show that the remaining constraints are facet inducing. We also utilize a linear transformation of model I to obtain a stronger version of model II, model II+, that inherits the polyhedral properties of model I. Numerical experiments show that the solution time of model I is significantly lower than the solution times of both model II and Andréasson’s model. It is also somewhat lower than the solution time of model II+.
|
|
| 19. |
- Patriksson, Michael, 1964, et al.
(författare)
-
The stochastic opportunistic replacement problem: A two-stage solution approach
- 2011
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- In Almgren et al. 2009 we studied the opportunistic replacement problem, which is a multicomponent maintenance scheduling problem with deterministic component lives. The assumption of deterministic lives is a strong simplification, but valid in applications where critical components are assigned a technical life after which replacement is enforced. Here, we study the stochastic opportunistic replacement problem, which is a more general setting in which component lives are allowed to be stochastic. We consider a stochastic programming approach for the minimization of the expected cost over the remaining planning horizon. Further, we present a means to compute lower bounds on the recourse function. The lower bounds are used in the construction of a decomposition method which extends the integer L-shaped method to incorporate stronger optimality cuts. In order to obtain a computationally tractable model, a two-stage sample average approximation scheme is utilized. Numerical experiments on problem instances from the wind power and aviation industry as well as on two test instances are performed. The results show that the decomposition method is faster than solving the deterministic equivalent on the three more complex instances out of the four instances considered. Furthermore, the numerical experiments show that decisions based on the stochastic programming approach yield a lower average total maintenance cost compared to that of decisions based on simpler maintenance.
|
|
| 20. |
- Patriksson, Michael, 1964, et al.
(författare)
-
The stochastic opportunistic replacement problem, part I: models incorporating individual component lives
- 2015
-
Ingår i: Annals of Operations Research. - : Springer Science and Business Media LLC. - 1572-9338 .- 0254-5330. ; 224:1, s. 25-50
-
Tidskriftsartikel (refereegranskat)abstract
- We consider an extension of the opportunistic replacement problem, which has been studied by Dickman et al. (The Journal of the Operational Research Society of India, 28:165–175, 1991), Andréasson (Optimization of opportunistic replacement activities in deterministic and stochastic multi-component systems, Licentiate thesis, Department of Mathematical Sciences, Chalmers University of Technology and University of Gothenburg, Göteborg, Sweden, 2004), and Almgren et al. (The opportunistic replacement problem: analysis and case studies, Preprint, Department of Mathematical Sciences, Chalmers University of Technology and University of Gothenburg, Göteborg, Sweden, 2011), that allows the individuals of the same component to have non-identical lives. Formulating and solving this problem constitute a first step towards solving the opportunistic replacement problem with uncertain component lives. We show that the problem is NP-hard even with time independent costs, and present two 0–1 integer programming models for the problem. We show that in model I the integrality requirement on a majority of the variables can be relaxed; this is in contrast to model II and the model from Andréasson (Optimization of opportunistic replacement activities in deterministic and stochastic multi-component systems, Licentiate thesis, Department of Mathematical Sciences, Chalmers University of Technology and University of Gothenburg, Göteborg, Sweden, 2004). We remove all superfluous variables and constraints in model I and show that the remaining constraints are facet inducing. We also utilize a linear transformation of model I to obtain a stronger version of model II, i.e., model II+, which inherits the polyhedral properties of model I. Numerical experiments show that the solution time of model I is significantly lower than those of both model II and Andréasson’s model. It is also slightly lower than the solution time of model II+.
|
|
| 21. |
- Patriksson, Michael, 1964, et al.
(författare)
-
The stochastic opportunistic replacement problem, part II: a two-stage solution approach
- 2015
-
Ingår i: Annals of Operations Research. - : Springer Science and Business Media LLC. - 1572-9338 .- 0254-5330. ; 224:1, s. 51-75
-
Tidskriftsartikel (refereegranskat)abstract
- In Almgren et al. (The opportunistic replacement problem: analysis and case studies, preprint, Department of Mathematical Sciences, Chalmers University of Technology and University of Gothenburg, Göteborg, Sweden, 2011) we studied the opportunistic replacement problem, which is a multi-component maintenance scheduling problem with deterministic component lives. The assumption of deterministic lives is a substantial simplification, but valid in applications where critical components are assigned a technical life after which replacement is enforced. Here, we study the stochastic opportunistic replacement problem, which is a more general setting in which component lives are allowed to be stochastic. We consider a stochastic programming approach for the minimization of the expected cost over the remaining planning horizon. Further, we present a means to compute lower bounds on the recourse function. The lower bounds are used in the construction of a decomposition method which extends the integer L-shaped decomposition method to incorporate stronger optimality cuts. In order to obtain a computationally tractable model, a two-stage sample average approximation scheme is utilized. Numerical experiments on problem instances from the wind power and aviation industry as well as on two test instances are performed. The results show that the decomposition method is faster than solving the deterministic equivalent on all four instances considered. Furthermore, the numerical experiments show that decisions based on the stochastic programming approach compared with simpler maintenance policies yield maintenance decisions with a significantly lower expected total maintenance cost on two out of the four instances tested, and an equivalent maintenance cost compared to the best policy on the remaining two instances.
|
|
| 22. |
- Reichenberg, Lina, 1976, et al.
(författare)
-
Geographic aggregation of wind power—an optimization methodology for avoiding low outputs
- 2017
-
Ingår i: Wind Energy. - : Wiley. - 1099-1824 .- 1095-4244. ; 20:1, s. 19-32
-
Tidskriftsartikel (refereegranskat)abstract
- This work investigates macro-geographic allocation as a means to improve the performance of aggregated wind power output. The focus is on the spatial smoothing effect so as to avoid periods of low output. The work applies multi-objective optimization, in which two measures of aggregated wind power output variation are minimized, whereas the average output is maximized. The results show that it is possible to allocate wind power so that the frequency of low outputs is substantially reduced, while maintaining the average output at around 30% of nameplate capacity, as compared with the corresponding output of 20% for the present allocation system. We conclude that in a future, fully electrically integrated Europe, geographic allocation can substantially reduce instances of low aggregate output, while impairing little on capacity factor and at the same time providing reduction in of short-term jumps in output.
|
|
| 23. |
- Wojciechowski, Adam, 1982
(författare)
-
On the optimization of opportunistic maintenance activities
- 2010
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Maintenance is a source of large costs; in the EU the maintenance costs amountto between 4% and 8% of the total sales turnover. Opportunistic maintenance is anattempt to lower the maintenance cost by considering the failure of onecomponent as an opportunity to replace yet non-failed components in order toprevent future failures. At the time of failure of one component, a decision is to be made on which additional components toreplace in order to minimize the expected maintenance cost over a planningperiod.This thesis continues the work of Dickman et. al. (1991) and Andreasson (2004) on the opportunistic replacement problem. In Paper I, we show thatthe problem with time-dependent costs is NP-hard and present a mixed integerlinear programming model for the problem. We apply the model to problems withdeterministic and stochastic component lives with data originating from theaviation and wind power industry. The model is applied in a stochastic settingby employing the expected values of component lives. In Paper II, a first steptowards a stochastic programming model that considers components with uncertain lives istaken by extending the problem to allow non-identical lives for component individuals.This problem is shown to be NP-hard even with time-independent costs. We present amixed integer linear programming model of the problem. The solution time of the model is substantially reduced compared to the model presented in Andreasson (2004). In Paper III, we then study the opportunisticreplacement problem with uncertain component lives and present a two-stagestochastic programming approach. We present a deterministic equivalent model anddevelop a decomposition method. Numerical studies on the same data as in Paper I from the aviation and wind power industry show that the stochastic programming approachproduces maintenance decisions that are on average less costly than decisions obtained from simple maintenance policies and the approach used in Paper I. The decomposition method requires less CPU-time than solving the deterministic equivalent on three out of four problems.
|
|
| 24. |
- Wojciechowski, Adam, 1982
(författare)
-
Polyhedral and complexity studies in integer optimization, with applications to maintenance planning and location–routing problems
- 2012
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis develops integer linear programming models for and studies the complexity of problems in the areas of maintenance optimization and location–routing. We study how well the polyhedra defined by the linear programming relaxation of themodels approximate the convex hull of the integer feasible solutions. Four of the papers consider a series of maintenance decision problems whereas the fifth paper considers a location–routing problem.<\p> In Paper I, we present the opportunistic replacement problem (ORP) which is to find a minimum cost replacement schedule for a multi-component system given a maximum replacement interval for each component. The maintenance cost consists of a fixed/set-up cost and component replacement costs. We show that the problem is NP-hard for time dependent costs, introduce an integer linear programming model for it and investigate the linear programming relaxation polyhedron. Numerical tests on random instances as well as instances from aircraft applications are performed.<\p> The stochastic opportunistic replacement problem (SORP) extends the ORP to allow for uncertain component lives/maximum replacement intervals. In Paper II, a first step towards a stochastic programmingmodel for the SORP is taken by allowing for non-identical lives for component individuals. This problem is shown to be NP-hard also for time independent costs. A new integer linear programming model for this problem is introduced which reduces the computational time substantially compared to an earlier model.<\p> In Paper III,we study the SORP and present a two-stage stochastic programming solution approach, which aims at — given the failure of one component — deciding on additional component replacements. We present a deterministic equivalent model and a decomposition method; both of which are based on the model developed in Paper II. Numerical tests on instances fromthe aviation and wind power industries and on two test instances show that the stochastic programming approach performs better than or equivalently good as simpler maintenance policies.<\p> In Paper IV, we study the preventive maintenance scheduling problem with interval costs which again considers a multi-component system with set-up costs. As for the ORP, an optimal schedule for the entire horizon is sought for. Here, themaximum replacement intervals are replaced by a cost on the replacement intervals. The problem is shown to be a generalization of the ORP as well as of the dynamic joint replenishment problem from inventory theory. We present a model for the problem originally introduced for the joint replenishment problem. The model is utilized in three case studies from the railway, aircraft and wind power industries.<\p> Finally, in Paper V we consider the Hamiltonian p-median problem which belongs to the class of location–routing problems. It consists of finding p disjoint minimum weight cycles which cover all vertices in a graph. We present several new and existing models and analyze these from a computational as well as a theoretical point of view. The conclusion is that threemodels are computationally superior, two of which are introduced in this paper.<\p> The main contribution of this thesis is to develop models for maintenance decisions and thus take an important step towards efficient and reliable maintenance decision support systems.<\p>
|
|
