Aggregate overhaul and supply chain planning for rotables

Abstract

We consider the problem of planning preventive maintenance and overhaul for modules that are used in a fleet of assets such as trains or airplanes. Each type of module, or rotable, has its own maintenance program in which a maximum amount of time/usage between overhauls of a module is stipulated. Overhauls are performed in an overhaul workshop with limited capacity. The problem we study is to determine aggregate workforce levels, turn-around stock levels of modules, and overhaul and replacement quantities per period so as to minimize the sum of labor costs, material costs of overhaul, and turn-around stock investments over the entire life-cycle of the maintained asset. We prove that this planning problem is strongly $\mathcal{NP}$-hard, but we also provide computational evidence that the mixed integer programming formulation can be solved within reasonable time for real-life instances. Furthermore, we show that the linear programming relaxation can be used to aid decision making. We apply the model in a case study and provide computational results for randomly generated instances.

Appendices

Appendix A: Proof of Proposition 2

We show that being able to solve the AROSCP will enable one to decide the BIN-PACKING decision problem, i.e. we reduce BIN-PACKING to AROSCP. The following decision problem, known as BIN-PACKING, is strongly $\mathcal{NP}$-complete (e.g. Garey and Johnson 1979): Given positive integers α ₁,…,α _m , β, and κ, is there a partition of {1,…,m} into disjoint sets ϒ₁,…,ϒ _κ such that $\sum_{j\in\Upsilon_{i}}\alpha_{j} \leq\beta$ for i=1,…,κ?

Now suppose we are given an instance of BIN-PACKING. Without loss of generality, we may assume that $\sum_{i=1}^{m} \alpha_{i}\leq\kappa\beta$ and α _i ≤β for all i∈{1,…,m}. From this instance of BIN-PACKING, we will show how to create an instance of AROSCP in polynomial time such that the answer to this instance of BIN-PACKING is yes, if and only if the optimal objective value of the corresponding instance of AROSCP equals 0. The basic idea behind this reduction is the following. By setting the initial number of non ready-for-use rotables sufficiently high, the release of overhaul orders is constrained only by available workforce capacity, i.e. by (29). This workforce capacity can be kept constant at β across periods by constraints (27) and (28). Now the problem can be viewed as packing overhaul order releases into several one period bins of fixed size β. By penalizing these order releases in all but κ periods, the objective becomes to pack as many order releases as possible in the κ periods in which the order releases are not penalized. If the optimal objective of AROSPC is 0, then it was possible to pack all overhaul order releases in κ periods and so the instance of BIN-PACKING is a yes-instance.

More formally, the reduction is as follows. Set Y={1,…,m+1} and $T^{Y}_{y}=\{y\}$ for all y∈Y; thus, aggregated and regular periods coincide. Set W ^d=β, and $\Delta_{y}^{l}=\Delta_{y}^{u}=\delta_{t}^{l}=\delta_{t}^{u}=1$. This ensures capacity is identical across periods. Set I={1,…,m} and set a _i =1, p _i =m+1, q _i =m+1, L _i =1, $H^{\mathrm{d}}_{i}=1$, $B^{\mathrm{d}}_{i}=0$, $n^{\mathrm{d}}_{i,0}=0$, $D^{\mathrm {d}}_{i,m+1}=1$ and r _i =α _i for all i∈I. Furthermore, set $D^{\mathrm{d}}_{i,t}=0$ for all i∈I and t∈{1,…,m}. Thus, each type of rotable needs to be replaced exactly once before or in the last period of the planning horizon. This instance of AROSCP is feasible because the following is a feasible solution: n _i,i =1 for i∈I and n _i,t =0 otherwise, x _i,m+1=1 for all i∈I and x _i,t =0 otherwise. (Note that all other variables are set by constraints). There are no acquisitions (a _i =1 for all i∈I) so $c^{a}_{i}$ does not need to be set. Most other cost parameters are set to 0; $c^{W}_{y}=0$ for all y∈Y and $c^{r}_{i,t}=0$ for all i∈I and $t\in T^{I}_{i}$. However, we set $c^{m}_{i,t}=1$ for all i∈I and t∈{1,…,m−κ} and set $c^{m}_{i,t}=0$ otherwise. Note that m−κ≥1 because, by assumption, $\sum_{i=1}^{m}\alpha_{i}\leq\kappa\beta$ and α _i ≤β for all i∈{1,…,m}. The objective function now reduces to $\textstyle\sum_{i\in I} \textstyle\sum_{t=1}^{m-\kappa} c^{m}_{i,t} n_{i,t}$. Let OPT denote the optimal solution to this instance of AROSCP. If OPT=0 then, necessarily n _i,t =0 for all i∈I and t∈{1,…,m−κ}. Furthermore, by constraint (25), $\sum_{i\in I_{t}}r_{i} n_{i,t}\leq w_{t}$ for all t∈T, which, by our choice of parameter values, implies ∑ _i∈I α _i n _i,t ≤β for all t∈{m−κ+1,…,m}. All rotables in this instance of AROSCP have to be overhauled exactly once in or before period m because of constraints (31), (32) and (35). Therefore, for each i∈I there is some t∈{m−κ+1,…,m} such that n _i,t =1. when OPT=0. Now it follows that a partition that satisfies the requirement of the original BIN-PACKING problem is given by:

$$\begin{aligned} \Upsilon_j = \{i\in I|n_{i,m-\kappa+j}=1\},\quad j\in\{1,\ldots,\kappa\}. \end{aligned}$$

In an analogous manner, it is possible to construct an optimal solution with objective 0 to an instance of AROSCP if the corresponding instance and truth certificate of BIN-PACKING is given, by setting all x _i,t and n _i,t to 0, except x _i,m+1=1 for all i∈I and n _i,m−κ+j =1 if i∈ϒ _j . Thus, we have shown that an instance of BIN-PACKING is a yes-instance if and only if the corresponding AROSCP problem has an optimal objective of 0. Observing further that the reduction above is a pseudo-polynomial reduction as defined by Garey and Johnson (1979, p. 101), and that BIN-PACKING is strongly $\mathcal{NP}$-complete, completes the proof.  □

Appendix B: Details on the random instance generator

2.1 B.1 Rotable characteristics

First, we generate the number of different rotable types that are already in the field at the beginning of the planning horizon, |I ₁|, from $\mathcal{UD}(25,40)$. Then for each i∈I ₁, we draw p _i , q _i , r _i and L _i as shown in Table 5. Note that for i∈I ₁, a _i =1 by definition and needs not be generated randomly.

Some of the rotables i∈I ₁ may belong to assets that will be disposed of before the end of the planning horizon, i.e., possibly p _i <360 for some i∈I ₁. If this is the case, we assume that this asset will be replaced by a new type of asset, which consists of rotables with identical characteristics that will remain current for the remainder of the planning horizon. For example, if 1∈I ₁, p ₁=270, a ₁=1, q ₁=120, r ₁=200, L ₁=1, and |I ₁|=32, then we add rotable type 33 to I and set a ₃₃=p ₁+1=271, p ₃₃=p ₁=360, q ₃₃=q ₁=120, r ₃₃=r ₁=200, and L ₃₃=L ₁=1. This procedure is shown formally in Table 5 using set expressions and the fact that I is generated to contain a sequence of integers. We note that it is also possible that a rotable type that is replaced some time during the planning horizon is replaced with a rotable type that has different characteristics. In particular, new rotable types are likely to be more reliable due to technological advancements. The models can also accommodate these scenarios. However, we make the conservative assumption that rotable types are replaced rotable types with identical characteristics.

2.2 B.2 Initial conditions and flexibility

For each type of rotable i∈I, there are revisions already due. We assume the worst case scenario that the first upcoming revision of any one rotable type are due in a single period. For rotable type i∈I, this single period is a _i +τ _i and τ _i is generated as $\tau_{i}=\mathcal{UD}(10,q_{i})$. The number of revisions due in period a _i +τ _i is drawn from $\mathcal{UD}(30,600)$. This means that for each i∈I, $D^{\mathrm{d}}_{i,t}=0$ if t≠τ _i and $D^{\mathrm{d}}_{i,\tau_{i}}=\mathcal{UD}(30,600)$.

Again as a worst case scenario, $U^{\mathrm{d}}_{i}=0$ and $n^{\mathrm {d}}_{i,t}=0$ for all relevant i and t, meaning that there are no recent order releases and that there have been no replacements ahead of time. Initially, for each i∈I ₁ there is no stock of non-ready for use rotables, i.e., $H^{\mathrm{d}}_{i}=0$ for all i∈I ₁. The initial ready-for-use stock of i∈I ₁ is generated as a fraction of the first peak number of revisions due in period a _i +τ _i : $B^{\mathrm{d}}_{i} = \lceil\mathcal{U}(0.1,0.3)\cdot D^{\mathrm {d}}_{i,\tau_{i}} \rceil$, where ⌈x⌉ is x rounded up to the nearest integer.

The bounds $\Delta^{l}_{y}$ and $\Delta^{u}_{y}$ are obtained by generating Δ^l (Δ^u) as $\mathcal{U}(0.7,0.95)$ $(\mathcal{U}(1.05,1.3))$ and setting $\Delta^{l}_{y} = \Delta^{l}$ and $\Delta^{u}_{y}=\Delta^{u}_{y}$ for all y∈Y∖{|Y|}. Similarly $\delta^{l}_{t}$ ($\Delta^{u}_{t}$) are obtained by generating δ ^l (δ ^u) as $\mathcal{U}(0.7,0.95)$ ($\mathcal {U}(1.05,1.3)$) and setting $\delta^{l}_{t}=\delta^{l}$ and $\delta^{u}_{t}=\delta^{u}$ for all t∈T. Finally, in each case, W ^d is set as 150000. We do not generate this parameter randomly, because the r _i are already generated randomly.

2.3 B.3 Costs parameters

The costs parameters are discounted on a yearly basis by the discount parameter α. Within a year however, there is no discounting, so that for a period t∈T, the corresponding year is ⌈t/12⌉.