Computers & Industrial Engineering 98 (2016) 30–39

Contents lists available at ScienceDirect

Computers & Industrial Engineering

journal homepage: www.elsevier.com/locate/caie

Overhaul planning and exchange scheduling for maintenance services

with rotable inventory and limited processing capacity
Murat Erkoc a,⇑, Kadir Ertogral b
a
Department of Industrial Engineering, University of Miami, 1251 Memorial Drive, Coral Gables, FL 33146, USA
b
Department of Industrial Engineering, TOBB University of Economics & Technology, Söğütözü Cad. No: 43, Ankara 06560, Turkey

a r t i c l e i n f o a b s t r a c t

Article history: Maintenance, repair and overhauling (MRO) of high cost equipment used in many industries are typically
Received 27 November 2015 subject to regulations set by local governments or international agencies. For example in the aviation
Received in revised form 10 May 2016 industry, critical equipment must be overhauled at certain intervals for continuing permission of use.
Accepted 11 May 2016
As such, the overhaul must be completed by strict deadlines. Since the overhaul is typically a long pro-
Available online 13 May 2016
cess, MRO companies may implement exchange programs where they carry so called rotable inventory
for exchanging expensive modules that require overhaul so that the equipment can continue its services
Keywords:
with minimal interruption. The extracted module is overhauled in a capacitated facility and rotated back
Maintenance planning
Rotable inventory
to the inventory for a future exchange. Since both the rotable inventory and the overhaul process capacity
Full-delay scheduling are limited, it may be necessary to carry out some of the exchanges earlier than their deadlines. Early
Earliness exchanges results in a decrease in the maintenance cycle time of the equipment, which is not desirable
Aviation for the equipment user. In this paper, we propose an integer programming model so as to minimize total
earliness by generating optimal overhaul start times for rotables on parallel processing lines and
exchange timetables for orders. We show that the LP relaxation of the proposed model has the integrality
property. We develop a practical exact solution algorithm for the model based on a full-delay scheduling
approach with backward allocation. The proposed procedure is demonstrated through both a numerical
study and a case study from the airline MRO service industry.
Ó 2016 Elsevier Ltd. All rights reserved.

1. Introduction significant cost item especially in the aviation industry with a sub-
stantial business volume (Guajardo, Cohen, Kim, & Netessine,
Industrial maintenance and repair includes all the technical and 2012). Therefore, airline companies focus on reducing MRO costs
managerial activities carried out to keep a production or service while ensuring that they do not compromise the safety of the air-
resource available, functional, and safe. Industrial maintenance is planes that they operate. Airline companies either carry out MRO
especially important in capacity intensive industries with sizeable in their in-house facilities or outsource it to independent MRO ser-
investments, such as airlines, wafer fabs, and railways. In airlines vice companies. An important MRO cost factor for airline compa-
industry, in particular, maintenance repair and overhaul (MRO) nies is the disruption of the use of equipment during the MRO
operations are crucial for both ensuring safety and reducing oper- process. For example, in the commercial airline industry, the
ational disruptions. The maintenance activities are usually subject opportunity costs due to downtimes of the planes can amount
to regulations and scrutiny enforced by governments or interna- from a few ten-thousands to hundred thousand dollars per day,
tional organizations. Both military and commercial aircrafts must depending on the type of the plane and its commercial use. There-
go through MRO at certain intervals defined by either time or flight fore, reducing turnaround time (TAT) is a key objective in MRO
volume. planning.
The effective management of MRO is not only important in Inventory management is a crucial factor in MRO for reducing
regards to quality and safety, but also from the economic sustain- TAT. An important difference between a typical manufacturing sys-
ability perspective of the airliners. MRO operations constitute a tem and a MRO system is the fact that MRO systems use so called
rotable component inventories or modules, in addition to the reg-
⇑ Corresponding author. ular inventory items (expendables). The rotable inventories consist
E-mail addresses: [email protected] (M. Erkoc), [email protected] of expensive components or modules that can be used as loan-outs
(K. Ertogral). or exchanges with the customers. The exchange minimizes the TAT

http://dx.doi.org/10.1016/j.cie.2016.05.021
0360-8352/Ó 2016 Elsevier Ltd. All rights reserved.
 M. Erkoc, K. Ertogral / Computers & Industrial Engineering 98 (2016) 30–39 31

for the airplanes as it only consists of the time spent for unin- 2. Literature review
stalling the used module and installing the new module, without
any delays due to other MRO processes. Here we do not consider Over the past couple of decades a significant volume of research
uninstallation or installation activities of the components, assum- tackled problems regarding MRO management from a variety of
ing that these activities are carried out by a separate team or pro- viewpoints. Early work in MRO area is generally about planning
duction unit, and we only tackle both scheduling of the overhauls activities for internal MRO needs in a company. Dekker (1996)
and planning the exchanges of rotables. summarizes this line of research. The author underlines that most
The exchanged module that requires overhaul joins the MRO of the models and solution approaches were introduced in 80s and
firm’s rotable inventory and, directly or after some waiting period, 90s and estimates a growing role of MRO in the future due to
enters the overhaul process. Once the overhaul process is com- increased use of high capital equipment both in manufacturing
pleted for the component, it is ready to be used for a future and service sectors. In a following work, Dekker and Scarf (1998)
exchange. Thus, the total number of rotable components in MRO discuss applications of several models in MRO area and shows
system is always constant and a rotable component is in one of the importance of the optimization models in MRO in comparison
the three states; awaiting overhaul, undergoing overhaul process, to the use of more qualitative approaches. They demonstrate the
and ready-to-exchange. The exchange and overhaul schedules power of analytical models needed to tackle complex problems
determine the formation of these states for all rotables. On one prevalent in MRO management. A more recent review is reported
hand, MRO companies aim to operate with low levels of the in Nicolai and Dekker (2008).
high-value rotable component inventories to avoid high costs. On Many studies regarding MRO in aviation in recent years focus
the other hand, they must ensure adequate level of customer on the MRO supply chains specifically pertaining to the spare parts
service. and component inventory management. Related research tackles
As pointed out above, the interval times between consecutive forecasting spare parts consumption (Ghobbar & Friend, 2003;
MRO’s for airliners are strictly regulated. These intervals often Regattieri, Gamberi, Gamberini, & Manzini, 2005), inventory con-
times are translated into hard deadlines for MRO services that can- trol with cost and downtime minimization (Safaei, Banjevic, &
not be violated. For example, the requirement to remove and over- Jardine, 2011; MacDonnell & Clegg, 2011; van Jaarsveld,
haul a landing gear is every 8–15 years depending on aircraft’s use Dollevoet, & Dekker, 2012; Gu, Zhang, & Li, 2015), integrated rota-
and model. From the cost efficiency perspective, airline companies ble inventory control and overhaul capacity management
prefer using this interval times fully and do not want to stop the (Buyukkaramikli, van Ooijen, & Bertrand, 2013), and strategies
cycle shorter than the enforced duration. However, the MRO facil- for inventory pooling and integration across aviation supply chains
ities may be compelled to ask some of their customers to bring (Kilpi & Vepsäläinen, 2004; MacDonnell & Clegg, 2007; Kilpi, Töyli,
their airplanes for MRO earlier than their end of cycles due to lim- & Vepsäläinen, 2009).
ited inventory and process capacity. Although feasible, this is not Our research in this study primarily focuses on MRO planning,
preferable for the airline companies. As such, MRO firms need to where we explicitly incorporate capacity and inventory constraints
efficiently schedule their overhaul operations under their given into the optimal scheduling of the overhaul processes. We specifi-
rotable inventory and process capacity limitations, with the objec- cally consider rotables that can be exchanged with the components
tive of minimizing the early exchanges. In this work, we precisely that require overhaul so as to eliminate downtimes. The most rel-
address this problem. evant works to the current study are due to Luh, Yu, Soorapanth,
For a given set of required overhauls and their due dates by the Khibnik, and Rajamani (2005), Joo (2009), Joo and Min (2011),
airliners, we propose an integer programming model that mini- and Arts and Flapper (2015). Luh et al. (2005) suggest a mathemat-
mizes the total earliness under rotable inventory and process ical programming approach that integrates scheduling exchanges
capacity constraints. In this context, earliness is defined as the dif- and inventory control problems. The solution approach is a Lagran-
ference between the required exchange deadline (end of cycle) for gian relaxation scheme. Unlike our model, in this study the due
a rotable in an airplane and the scheduled exchange date for that dates of the overhaul requests are taken as the arrival times, and
equipment. Ideally, there should be no gap between the deadlines they did not consider early arrivals of requests. The scheduling part
and the actual exchange dates. However, due to limited number of of their work concentrates on planning service activities in order to
rotables and processing lines, a gap may be inevitable to obtain a meet the requests. Again unlike our model, their approach allows
feasible solution where no exchange deadlines are violated. We delays in satisfying a request with an associated penalty. However,
show that the LP relaxation of the proposed mathematical model the general tendency in aviation MRO practice is to minimize the
has the integrality property. As such, the optimal solution can be delays in meeting requests through exchange policies. Joo (2009)
directly obtained from the LP relaxation of the model. tackles the problem of scheduling exchange of a single type rotable
We also propose a practical exact solution algorithm based on a with the objective of minimization of the earliness. Similar to our
so called full-delay scheduling for the problem, which can be easily setting, the rotables are scheduled to be exchanged with rotable
implemented without the need of using any mathematical solver components for a given a set of aircraft fleet of similar type with
or special computer software. We illustrate the algorithm’s imple- overhaul deadlines. The deadlines are not allowed to be violated
mentation using a real-life problem and present a sensitivity anal- to avoid downtimes. As such, the exchanges are to be scheduled
ysis that investigates the joint impact of capacity and rotable no later than their respective deadlines. For a given initial inven-
inventory on the optimal exchange and overhaul processing tory of rotables, the author proposes a polynomial time algorithm
schedule. that optimally schedules the exchange times and overhaul pro-
In the next section, we discuss the relevant literature. In cesses. The generation of the schedule is constrained by the avail-
Section 3, we present the proposed mathematical programming ability of rotable inventory level only. However, his model
model. We discuss the properties of the optimal solution and pre- implicitly assumes unlimited number of processing lines and thus,
sent our exact solution algorithm with an illustrative example in unlimited maintenance capacity. In another paper, Joo and Min
Section 4. In Section 5, we apply the solution algorithm on a case (2011) extend this model by incorporating rotable inventory
based on real life application from an MRO service company, and decision by means of a budget constraint. They employ a goal
investigate the impact of rotable inventory and processing capacity programming approach, where the due date satisfaction and
on the optimal solution. We present our conclusions in Section 6. budget constraints are taken as soft constraints. The resulting
32 M. Erkoc, K. Ertogral / Computers & Industrial Engineering 98 (2016) 30–39

multi objective model is solved directly with a commercial solver. been a growing trend in recent years for airlines and MRO compa-
They use weighted objectives aiming at minimization of the viola- nies establishing exchange programs where the equipment owner
tion of these soft constraints. In our study, for practical relevance, exchanges its equipment that needs overhaul with a recently over-
we explicitly incorporate the capacity constraint into the schedul- hauled equipment from the MRO company’s rotable inventory, at a
ing problem and propose an exact solution procedure for the specific date which is no later than the customer’s deadline
exchanges and the overhaul processes. (Mwanalushi, 2012). Determining the exchange date depends on
In a more recent study, Arts and Flapper (2015) introduce an the company’s available rotable inventory stocks as well as the
aggregated production planning model which considers both the customer’s deadline. Following an exchange, each received equip-
rotable inventory and workforce planning decisions in a long term ment set enters the overhaul process and becomes ready for the
planning context. The model uses two time buckets; month and next exchange on completion of its overhaul. The turnover time
year. The workforce capacity levels can only be changed at the depends on the overhaul processing time and the available capac-
beginning of the years with an associated cost. The model does ity. Ideally, an exchange takes places exactly at the company’s
not consider exact timing of the rotable requests but rather it deadline. However, limited levels of rotable stocks and capacity
focuses on satisfying monthly total demand by varying the work- may compel the MRO company request that some of the orders
force levels. The objective of the model that the authors employ to arrive earlier for the exchange.
minimizes the sum of several cost factors, such as labor, material, We propose a mathematical optimization model that minimizes
and inventory costs, throughout the life cycle of the fleet of vehi- the total earliness of exchange dates. We assume that there are
cles, whereas we focus on earliness. The model tries to determine known set of customer orders with due dates, overhaul process
the workforce levels for each period in order to provide the total times, capacity, and rotable inventory. Table 1 lists the nomencla-
required capacity for maintenance operations, and not the exact ture employed in the proposed model. All orders are for the same
scheduling of the overhauls and the exchanges for each individual rotable type, and each rotable module requires an overhaul pro-
request. Compared to this setting, our model provides a lower res- cessing time denoted by p. In this setting, we consider a line corre-
olution operational scheduling framework that tries to meet each sponds to a team of special workers handling explicitly an overhaul
individual request on time with the total earliness objective and for a particular high-value rotable component, which constitutes a
takes teams of workers as a single unit process capacity. large portion of the overall MRO operations, such as overhauling a
special type of landing gear. The number of rotable inventories car-
ried by the company is represented by s. As mentioned above, each
3. Problem formulation
time an exchange takes place, the received equipment needs to be
overhauled. The MRO firm’s capacity dedicated for the product
We consider a MRO company that adopts an ‘‘exchange” pro-
type is limited by the number of parallel lines, each of which can
gram to deliver the overhaul services to its customers. There has
process one module at a time and no preemption is allowed during
Table 1 the process. As such, the overhaul process of a particular rotable
Nomenclature. inventory item can only start when at least one of the parallel lines
Sets: is available.
I Set of exchange orders for the rotable module At any given period, inventory is composed of three groups
T Set of time periods in the planning horizon depending on the state of the module at hand; 1. Exchange-ready
Parameters: inventory is the group of equipment whose overhaul is completed
s Initial number of the rotable modules in inventory and ready-to-go. 2. Equipment modules that are currently under-
k Number of parallel overhaul lines
going the overhaul process make up the in-process inventory. 3.
p Number of periods to complete an overhaul process for a rotable module
di Due date for the exchange of the ith order The inventory received from the customer following an exchange
awaiting overhaul. We refer to this group as the on-hold inventory.
Decision variables
Xit 1 if the exchange for order i is made at period t and 0 otherwise A given rotable inventory is in this state either because there is no
Yt Number of overhaul starts at the beginning of period t available processing line for its overhaul or its scheduled start time
Ht Inventory ready for exchange at the end of period t is delayed in the production schedule.
Bt Inventory of rotables waiting for overhaul at the end of period t As we mention above, at a given period t the rotables are
Wt Inventory of rotables being overhauled at period t
composed of exchange-ready inventory (denoted by Ht), on-hold

Inventory Waing to be MRO Process on Rotables Ready

Overhauled Parallel Lines for Exchange

B1 H1

Customer
B2 H2

Bn Hn

Fig. 1. Flow of rotables.

 M. Erkoc, K. Ertogral / Computers & Industrial Engineering 98 (2016) 30–39 33

inventory (denoted by Bt), and in-process inventory (denoted by Constraints (7) and (8) limit the number of exchanges for any
Wt). Clearly, at any period it holds that S = Ht + Bt + Wt. The flow given period by the finished inventory level which contains
of rotables is illustrated in Fig. 1. In a period, the spread of the exchange-ready modules. Constraints (9) and (10) set the initial
inventory can be changed by three types of events. First, an equip- conditions for the finished and on-hold inventories, respectively.
P
ment exchange may take place ( i2I xit ). The number of exchanges Without loss of generality, it is assumed that all rotable inventory
is limited by the exchange-ready inventory level. The equipment items are ready for exchange at the beginning of the planning
received from the customer(s) is either added to the on-hold horizon.
inventory or enter into the overhaul process directly. The module The model employs a constant processing time for all rotables
(s) that enter into the overhaul process (yt ) are deducted from since a single job type is assumed. One can see that we can have
the on-hold inventory. Clearly, the size of this group is limited by some deviations in overhaul times due to randomness of the nat-
the number of available process lines (i.e., Wt 6 K). The third event ure of the work content. Our model assumes this randomness is
that leads to the replenishment of the exchange-ready inventory not significant. Even if we have high variation in overhaul times,
occurs when any overhaul processes started exactly p periods ear- the results of the model are still valuable due to the fact that what
lier are completed (ytp ). As in the previous case, this number is determines the completion time of a particular overhaul is really
also limited by the number of available process lines. the accumulation of the overhauls times executed in a process
The setting explained above indicates that the overall timeli- lines, not an individual overhaul time, and coefficient of the varia-
ness of equipment exchanges are mainly constrained by the num- tion of the total overhaul time will get smaller as the number of
ber of equipment sets that the service company rotates its overhauls increases.
inventory (s) and the number of the processing lines (k) that it One major advantage of the above model is that it has the inte-
operates. As expected, higher inventory leads to improved timeli- grality property as shown below:
ness for exchanges. Moreover, the throughput of the rotation is
determined by the number of processing lines. An efficient sched- Proposition 1. LP relaxation of model P has the integrality property.
ule of the overhaul operations and the exchange dates should be
generated within these operational constraints.
The optimization model presented below aims to minimize the Proof. Let A be the matrix of coefficients for the decision variables
total earliness; in the constraints of P with relaxed integrality restrictions. Every
entry of A is 1, 0, or +1, and therefore, all square sub matrixes
XX
di
ðPÞ min ðdi  tÞxit ð1Þ of A have a determinant of 0, +1 or 1 implying that A is totally
i2I t¼1 unimodular. Hence, every basis of A has a determinant of 1 or
X
di +1. Since the right hand side vector of the model is composed of
s:t: xit ¼ 1; 8i 2 I ð2Þ integers, we conclude that all extreme points of set A will corre-
t¼1 spond to an integer basic feasible solution. h
X
Bt ¼ Bt1 þ X it  W t ; 8t 2 T n f0g ð3Þ The above result reveals that the optimal solution to the Linear
i2I Programming (LP) model obtained by relaxing the integrality con-
X
Ht ¼ Ht1  X it ; 8t 2 T n f0g : t < p ð4Þ straints in (11) is feasible and optimal for P as well. As such, the
i2I proposed model is effective in finding optimal solutions with com-
X
Ht ¼ Ht1  X it þ W tP ; 8t 2 T : t P p ð5Þ putational efficiency.
i2I Next, we introduce a special algorithm that can be used to find
X
tþp1 the optimal solution to the above model. The advantage of the
W l 6 k; 8t 2 T : t 6 jTj  p þ 1 ð6Þ algorithm is that it does not require any mathematical solver or
l¼t
X special computer software and it can be easily implemented using
X it 6 Ht1 ; 8t 2 T : t < p ð7Þ simple scripts or cataloging. Moreover, the algorithm does not
i2I require much data processing and memory which would be the
X
X it 6 Ht1 þ W tP ; 8t 2 T : t P p ð8Þ case with the mathematical model especially for large size
i2I instances.
H0 ¼ s ð9Þ
B0 ¼ 0 ð10Þ 4. The exact solution algorithm
X it 2 f0; 1g; W t ; Ht ; Bt P 0 and integer ð11Þ
When process capacity is ample, that is, when the number of
The objective function given in (1) returns the sum of the differ- parallel processing lines exceeds the number of rotables at hand,
ence between the time of exchange and the deadline for each the above problem can be solved easily (i.e. k P s). Joo (2009) pro-
exchange. The summation gives the total earliness. First constraint poses a polynomial time exact solution algorithm for this case. The
ensures that all exchanges take place before their deadlines. Con- algorithm is based on a backward allocation where the equipment
straints (3)–(5) establish the flow balance for the on-hold and fin- exchange with the latest due date is scheduled first. In this setting,
ished inventories. While any exchanged equipment joins the on- all exchanges are scheduled as close to their due dates as possible,
hold inventory waiting to be overhauled, the overhaul starts are and each exchange is assigned to a certain rotable in the exchange-
removed from on-hold inventory and join the in-process inventory. ready inventory. Some of the exchanges must be scheduled early in
At the same time, finished inventory level decreases when an order to make the timely (i.e., feasible) delivery of the subsequent
exchange takes place and increases when an overhaul process is exchanges possible.
completed for any in-process module. Inequality (6) forms the Having k P s is equivalent to the uncapacitated problem since
capacity constraint. It requires that the number of overhaul starts we cannot simultaneously process more than s rotables at any
during any time interval with length of the unit overhauling time given period. However, it typically is more common to have k < s.
(i.e., p) cannot exceed the number of parallel process lines (k). In Since establishing each overhaul process line would mean both
other words, the constraint ensures that the maximum in- making high investments for special equipment and machinery
process inventory level is limited by the number of processing lines and keeping a team of skilled workers with high salaries on payroll,
at any period during the planning horizon. it makes financially much more sense to have some extra inventory
34 M. Erkoc, K. Ertogral / Computers & Industrial Engineering 98 (2016) 30–39

in order to avoid delays in exchanges. In our study, we propose an Case I: rk  h < p

optimal solution methodology for this more general case where the In this case we cannot shift the start of overhaul any further to
process capacity is important. For k < s, the exchange process is not the right in the schedule because of processor availability.
only constrained by the availability of the rotables but also by the
available processing lines. Therefore, the timing of the exchanges Case II: rk  h P p
should be determined based on the processing capacity in addition In this case, shifting the overhaul to the right as much as
to availability of the exchange inventory. In what follows, we dis- possible and setting fi = rk will improve the total earliness. h
cuss the properties of the problem which help us construct an effi- Based on Proposition 3, we try to construct so called full-delay
cient exact solution procedure for scheduling module exchanges schedules where no overhaul can be shifted to the right without
and their designated MRO processes optimally. affecting the schedule of other overhauls. Optimality of the solu-
tion algorithm is based on fact that the suggested backward
4.1. Problem properties scheduling procedure uses the moves that do not violate the opti-
mality based on the last two propositions In other words, the pro-
We present two essential optimality properties. The proposed cedure repeats the moves in line with two propositions. Therefore
algorithm is developed based on these properties. In describing the moves do not cut out the optimal solution (or solutions) and
the properties below, we use the term ‘‘partial schedule”. The par- the final solution found by applying these moves is guaranteed
tial schedule is the incomplete schedule where only a subset of the to be optimal, if the solution is feasible. A constructed solution is
jobs is allotted to the processors. It is generated by assigning avail- feasible if the start time of the first overhaul is greater than or
able rotable inventories to the requests from latest to the earliest equal to the first period in the planning horizon.
in their due dates, while scheduling overhauls of rotables in a back- The solution algorithm considers the requests one by one from
ward fashion in time. latest to the earliest in a backward fashion. It tries to satisfy the lat-
est open request first by an overhaul which finishes as close as pos-
Proposition 2. In a partial schedule, we do not violate the optimality sible to the due date of the latest unsatisfied request. Therefore, if it
of a solution if we always assign an available rotable to the latest converges to a feasible solution, the converged solution must be an
unsatisfied request whose due date is greater than or equal to the optimal solution. We give the details of the full-delay scheduling
period the rotable becomes available. algorithm below.

4.2. Full-delay scheduling algorithm

Proof. Consider a partial schedule constructed in a backward fash-
ion from right to the left in time. Let fi be the overhaul finish time
In this section, we introduce a single-pass constructive
for a last overhaul (i) in a partial schedule and fi1 the overhaul fin-
polynomial-time algorithm that can be used to obtain the exact
ish time for the rotable that comes second to the last overhaul.
solutions for real-life size problems. The approach to construct
Also, let dk and dk1 be the due dates of the latest unsatisfied
the schedule of overhauls and exchanges is based on two proper-
request (k) and the second latest unsatisfied requests (k  1),
ties in line with the propositions given above;
respectively (dk P dk1). There could be two cases regarding the
finish time of the last overhaul;
(1) Schedule the exchanges from latest due date to the earliest
Case I: dk1 6 fi 6 dk and designate each overhaul of a rotable for a particular
In this case, it is obviously optimal to assign the rotable to the exchange order.
latest request in order to minimize the total earliness. (2) Schedule the start of the designated overhaul as late as pos-
Case II: fi 6 dk1 6 dk sible without violating the exchange due dates and the
In this case, we can either assign the rotable to open request k capacity constraints.
or k  1. If we assign it to open request k the marginal contribution
of this assignment (mc1) to the total earliness objective will be We refer to this proposed algorithm as Earliest Due-Date Full-
mc1 = (dk  fi) + (dk1  fi1). If, on the other hand, we assign the Delay (EDF) scheduling, where beginning with the exchange order
rotable to request k  1, the marginal contribution of the assign- with latest due date, overhaul task for the designated rotable
ment will be mc2 = (dk1  fi) + (dk  fi1). It is easy to see that, inventory to be used in the exchange is always scheduled at the
since the processing times are identical, mc1 = mc2. Therefore, in latest possible time slot on one of the parallel processors. Full-
this case as well, we would not violate optimality if we assign any delay ensures that all exchanges are carried out as late as possible
available rotable to the latest unsatisfied request. h but before their due dates. Since the overhaul times are identical,
the optimal solution is guaranteed.
Based on the proposition we conclude that we must consider the
To help explain the proposed full-delay scheduling algorithm,
exchange requests from latest to earliest when we assign available
we use a numerical example. The example includes 13 overhaul
rotable inventory as we construct the schedule in a backward fashion.
exchanges with due dates in days as given in Table 2. The overhaul
process for each item (p) is 30 days. Suppose the MRO company
Proposition 3. In a partial schedule, delaying an overhaul of a
carries four rotable items as initial inventory (S = 4) and has two
rotable as late as possible without violating the processor constraint so
parallel lines (K = 2) to carry out the overhaul processes.
that the finish time of the rotable is closest to the due date of the latest
Before the execution of the scheduling algorithm, all exchange
unsatisfied request, does not violate the optimality of the partial
orders are ordered from the latest due date to the earliest. At each
schedule.
iteration, the overhaul task for an exchange order with the latest
deadline is scheduled. In this respect, the scheduling follows a
Proof. Let fi be the overhaul finish time for a last overhaul i in a backward process. In the proposed optimization algorithm, orders
partial schedule and let rk be the due date of the latest unsatisfied are indexed in descending order of their due dates (i.e., di P di+1).
requests k in a partial schedule (fi < r). In a given partial schedule, Let Lv denote the scheduled overhaul start time for the rotable
let h be the first point in time in between fi and rk such that the inventory item v (v = 1, . . . , S) in a partial schedule at any iteration.
number of processors busy drops to K  1, i.e. one processor Initially, we set the overhaul start times for all inventory equal to
becomes available at h. We can have two cases; the latest due date in the set of all orders (or any value greater than
 M. Erkoc, K. Ertogral / Computers & Industrial Engineering 98 (2016) 30–39 35

Table 2
Exchange due dates for the numerical example (in days).

Order # 1 2 3 4 5 6 7 8 9 10 11 12 13
Due date 215 192 176 164 152 150 150 137 124 104 81 81 77

the due date of the last order). We let EARLY represent the running the last scheduled overhaul process on this line has larger start
total for the earliness. We let Ui and Ei denote the start time of time than that of the other processing line.
overhaul process and the time of exchange for the rotable to be
used to satisfy exchange order i, respectively. Moreover, we define Step 2: Complete the scheduling for orders K + 1 to S
Mj as the last scheduled overhaul start time on processor j in the
for i = k + 1 to s {Ei di; Ui min(Ei, Mjmax)  p; Mjmax Ui;
partial schedule already constructed in any iteration. The initial
Li Ui}
step of the algorithm is given below:

Step 0: Initialize
We note that at any time no more than K modules can be in the
if k > s then k s
overhaul process. As such, the overhaul process of a rotable inven-
dmax d1
tory designated for an order can start just in time (i.e. Ui = Ei  p) if
for v = 1 to s {Lv d1}
and only if there is an available processing line at that time. Other-
EARLY = 0
wise, the start time is shifted back to the latest possible period
which is Mjmax  p. Mjmax is updated each time an overhaul process
is scheduled.
In the initialization step, we make sure that the inventory is over- Following Step 2, in our example, the exchange dates for orders
hauled on at most min(S, K) parallel lines. Clearly, when we have 3 and 4 are scheduled on time using rotables 3 and 4, respectively.
more lines than inventory, the excess lines cannot be used since The overhaul corresponding to order 3 is scheduled on processing
there will not be enough rotable modules to process. We recall that line 1 since this line has the largest start time in the partial sched-
this case corresponds to the uncapacitated setting discussed in Joo ule. The overhaul is scheduled to start at U3 = min(176, 185) 
(2009), where constraint (6) is redundant. 30 = 146 and thus, L3 = 146. At this point, the latest scheduled over-
Following the full-delay approach, the schedule is constructed haul start time on this processing line becomes 146 as well (i.e.,
in a way that the exchange periods for the first s orders (s orders M1 = 146). Consequently, now jmax = 2 since M2 > M1. Next, over-
with the latest due dates) are allocated to their respective due haul process associated with order 4 is scheduled with U4 = min
dates in a backward fashion. Therefore, once the initialization is (164, 162)  30 = 132, L4 = 132, and M2 = 132. At this point, jmax
completed, we construct the schedule in two main phases. We becomes 1 since now M1 > M2. While the overhaul process is com-
schedule the exchange of the first S orders just on time. For this, pleted just in time for the exchange of order 3, it needs to finish
we first schedule the overhaul processes for all k process lines before the date of the exchange for order 4 because the processing
for the first k orders (i = 1, . . . , k) and then schedule the overhaul line will be busy with another overhaul process at the time of the
processes for the following s  k orders (i = k + 1, . . . , s). After exchange.
scheduling the overhauls for the first S exchange orders, we sched- After overhaul start and exchange periods for the first S rotables
ule the overhauls for the remaining (N  S) orders as described are determined, the remaining N – S orders are scheduled continu-
below. ing with the backward process. For the remaining iterations, let
vmax represent the rotable inventory item with the highest process
Step 1: Schedule the overhaul starts and exchanges for start time in the current partial schedule, that is, vmax = -
argmaxv 2½1;S (Lv).
orders 1 to k
for i = 1 to k {Ei di; U i Ei  p; Mi Ui; Li Ui}
Step 3: Complete the scheduling for the remaining N  s
orders
for i = s + 1 to N  s {Ei min(Lvmax, di); Ui min(Ei, Mjmax) 
In this step all orders are exchanged on time with no earliness, and
p; Mjmax Ui; Lvmax Ui;
the algorithm schedules the corresponding overhaul processes in a
if Lvmax < 0 then break: solution is infeasible
way that they are completed just on time for the exchanges. To
EARLY = EARLY + (di  Ei)}
illustrate this, consider the example given in Table 2. At the end
for i = N  s to N {Ei min(Lvmax, di); Ui min(Ei, Mjmax)  p;
of the first step, exchange for the first two orders are scheduled
Mjmax Ui; Lvmax Ui;
(since k = 2), where E1 = 215 and E2 = 192. Hence, the corresponding
EARLY = EARLY + (di  Ei)}
overhaul starts are set at U1 = 215  30 = 185 and
U2 = 192  30 = 162 on processing lines 1 and 2, respectively. Con-
sequently, in the partial schedule, the processing lines 1 and 2
become busy at M1 = 185 and M2 = 162, respectively. Likewise, the We note that there is no need for overhaul scheduling for the last S
latest overhaul start times for rotables 1 and 2 are L1 = 185 and orders. Since these orders have the earliest s due dates, each corre-
L2 = 162, respectively. sponds to the initial exchange for each of the rotable items, which
At this point since we still have s  k available rotables, next are assumed to be ready for exchange at the beginning of the plan-
s  k orders can also be scheduled for on time exchanges. Let jmax ning period. However, a virtual overhaul schedule is nevertheless
represent the processing line with the highest scheduled process- generated for these orders so as to update vmax values and hence,
ing start time in the current partial schedule, that is, jmax = - their exchange dates. Therefore, feasibility check is needed for only
argmaxj2½1;K (Mj). The next overhaul start is always allocated to orders s + 1 thru N  s, not for the last s orders.
the line jmax under the adopted full-delay regime. For example, in In order to ensure full-delay, in Step 3, the algorithm selects the
the partial schedule of our numerical example jmax = 1 because rotable with the latest scheduled overhaul start in the partial
36 M. Erkoc, K. Ertogral / Computers & Industrial Engineering 98 (2016) 30–39

schedule to determine the next overhaul start and exchange dates. rotable item 3, which is used for this exchange, is scheduled for
At this stage, exchange dates are constrained by the availability of overhaul start on day 146. The overhaul start scheduled for day
both the rotable items and the processing lines. The exchange for 146 is associated with the exchange of order 3. As such, the
order i must be carried out at an earlier date if on the day the exchange of order 7 cannot take place after day 146. Consequently,
exchange is due the rotable item is already assigned to an overhaul the exchange is scheduled for day 146, 4 days preceding the due
process corresponding to another order, that is, Lvmax < di. This can date of the order.
be illustrated in Table 3, which recaps the overall scheduling pro- Fig. 2 provides a visual depiction of the exact solution generated
cess for our numerical example. Orders 5 and 6 can be exchanged by the proposed algorithm for the numerical example. Note that, in
on time since the overhaul processes for rotable items 1 and 2 can Fig. 2, each row corresponds to a rotable inventory item and no
be started early enough. On the other hand, the exchange of order 7 more than two schedule blocks can overlap on a column since
must be scheduled earlier than its due date – day 150 – since the there are two processing lines. The minimum total earliness for
this problem results with 49 days. We note that the left-most
schedule blocks (overhauls) for the rotable items are not actual
Table 3 overhaul processes since the rotables are ready for exchange and
Completed schedule for the numerical example. the overhauls are not necessary prior to the first four exchanges.
Order Due Exchange Overhaul Process Rotable Earliness
date date (Ei) start (Ui) line (j) item (v)
(di) 5. A case study: MRO exchange schedule for landing gear
1 215 215 185 1 1 0
2 192 192 162 2 2 0 In this section, we apply the proposed algorithm to a real life
3 176 176 146 1 3 0 case in order to illustrate our solution methodology. We carry
4 164 164 132 2 4 0 out a sensitivity analysis to investigate the impact of rotable inven-
5 152 152 116 1 1 0
tory and processing capacity on the performance of the optimal
6 150 150 102 2 2 0
7 150 146 86 1 3 4
schedule. The case is built based on our research collaboration with
8 137 132 72 2 4 5 an industry partner who is among the top ten MRO companies in
9 124 116 56 1 1 8 the World operating in the airline industry. The name of the com-
10 104 102 – – 2 2 pany as well as the specifics of the module type is not disclosed in
11 81 81 – – 3 0
this study for privacy concerns. We focus on an exchange program
12 81 72 – – 4 9
13 77 56 – – 1 21 of the MRO program for landing gear of a specific regional jet type.
A regional jet (RJ) is a term used for a class of short to medium-

Day 0 Day 215

-4 26 56 116 146 185

#13 #5
#9
EARLY = 0
#1 v =1
EARLY = 21 EARLY = 8 EARLY = 0

42 102 162 192

#10 #6 #2
v=2
EARLY = 2 EARLY = 0 EARLY = 0

86 176
#11 #7 #3
EARLY = 0 EARLY = 4 EARLY = 0 v =3

12 72 132
#12 #8 #4
EARLY = 9 EARLY = 5 EARLY = 0 v =4

Fig. 2. Final schedule of overhaul processes and exchanges with two lines and four rotable inventory items (exchange days are indicated with D).

Table 4
Exchange due dates for the case study (in days).

Order Due Date Order Due Date Order Due Date Order Due Date Order Due Date Order Due Date Order Due Date Order Due Date
1 1829 11 1707 21 1485 31 1402 41 1331 51 1252 61 623 71 198
2 1806 12 1705 22 1481 32 1400 42 1307 52 1232 62 543 72 198
3 1790 13 1699 23 1481 33 1400 43 1303 53 1230 63 540 73 198
4 1768 14 1594 24 1478 34 1380 44 1302 54 1218 64 530 74 170
5 1766 15 1549 25 1455 35 1379 45 1295 55 847 65 513 75 78
6 1744 16 1542 26 1441 36 1377 46 1285 56 798 66 482 76 78
7 1710 17 1532 27 1428 37 1363 47 1282 57 758 67 467 77 75
8 1709 18 1523 28 1414 38 1345 48 1273 58 756 68 460 78 75
9 1708 19 1521 29 1405 39 1343 49 1271 59 711 69 439 79 48
10 1708 20 1518 30 1403 40 1337 50 1256 60 643 70 426 80 48
 M. Erkoc, K. Ertogral / Computers & Industrial Engineering 98 (2016) 30–39 37

range turbofan powered airliners. The company has MRO contracts number of processing lines are sufficiently high, total earliness
with several customers who operate this type of jets. The contracts converges to zero. With four or more processing lines, the total ear-
stipulate a total of 80 exchanges with customer specified due-dates liness goes down to zero with 8 rotables. It would take 19 and 10
over a 5-year time horizon. As mentioned earlier, since these due rotables with 2 and 3 processing lines, respectively, to reach at zero
dates are typically governed by the Federal Aviation Administra- earliness. From these results, we observe that while total earliness
tion (FAA) regulations, all due-dates are considered as firm dead- may not always converge to zero with increasing number of pro-
lines. Overhaul time is given as 30 days. cessing lines, it always does so when the number of rotables gets
We normalize the due-date data with respect to time 0 (now). sufficiently high for a fixed number of processing lines, which is
The due date data are listed in Table 4 in descending order and also in line with the intuition.
depicted in Fig. 3. We apply our solution algorithm to this data set The marginal impact of rotables and processing lines on the
under varying numbers of initial rotable inventory and processing total earliness differ and are context specific. The gain from addi-
lines. Specifically, our analysis varies number of rotables, s, from 2 tional processing line does not always surpass the gain from an
to 9 and employs the same range for the number of processing additional rotable inventory. Comparison of the marginal gains is
lines, k. We note that with only one rotable, there is no feasible illustrated in Table 6 with three types of entries. A cell with ‘‘L”
solution for any k in f2 . . . 9g. Likewise, with a single processing indicates a higher gain to be realized by increasing the number
line, no feasible solution exists for any s in f2 . . . 9g. As such, we of processing lines, whereas ‘‘R” signifies that it is preferable to
take the minimum number of rotables and processing lines as 2. increase the rotable inventory. The entry ‘‘N” represents the cases
For the case problem, each instance involves 95,651 decision where the total earliness is zero and as such, no gain is realized by
variables and 7369 constraints. The resulting optimal total earli- increasing either the number of rotables or the number of process-
ness values are presented in Table 5. ing lines. For example, when the company has five rotables that
As expected, the total earliness is nonincreasing in both the can be overhauled on three lines, the decrease in total earliness
number of rotables and the processing lines. The data reveals that will be higher when an additional processing line is used (i.e., from
the total earliness does not improve beyond a certain number of 659 days to 118 days) compared to acquiring an additional rotable
processing lines for a given number of rotables. This is obvious (i.e., from 659 days to 411 days). Then with four processing lines,
for the case k P s, where the extra processing lines cannot be used the company is better off with an additional rotable (a decrease
since the simultaneous overhauling processes are limited by the from 118 days to 29 days). It is intuitive that as the company has
number of rotables. As such, the optimal solution for these cases more rotables in its inventory, the marginal gain from additional
will not change and will be identical to the case with k = s. How- processing lines increases since the processing lines becomes the
ever, we observe that capacity saturation may occur even when bottleneck. On the other hand when the number of processing lines
k < s, that is when there are more rotables than the processing is high enough, rotable inventory becomes the bottleneck.
lines. For example, with 6 rotables, the total earliness converges The comparison of the impacts of the rotables and the process-
to 29 days for 4 processing lines and does not improve with any ing lines is the typical comparison between inventory and capacity.
additional line. Such is also the case with 7 or more rotables. Clearly, both have impact on the performance in any production or
As exemplified in Fig. 4, the return from each additional rotable service operations and either one may become a bottleneck. To
diminishes. That is, the level of drop in earliness gets smaller as we gain further insights about the tradeoff between inventory and
increase the number of rotables. Same is also the case for process- capacity, we solve the same problem set with longer and shorter
ing lines. As expected, when both the number of rotables and the

Inventory vs Earliness
Due Date Data for 80 Orders 6000
Due Dates (Days from Now)

2000
1800 5000
Total Earliness

1600
4000
1400 K=2
1200 3000
1000 K=3
800 2000
K=4
600
1000 K=5+
400
200 0
0 1 2 3 4 5 6 7 8
80 70 60 50 40 30 20 10 0 Number of Rotable Inventories
Orders
Fig. 4. Impact of initial rotable inventory level on total earliness under varying
Fig. 3. Spread of due dates for the future exchanges. process capacities.

Table 5
Optimal total earliness values.
Table 6
RotablesnLines 2 3 4 5 6 7 8 9 Preferences for additional processing lines versus additional rotables (p = 30 days).

2 5243
3 4461 1331
4 3803 939 306
5 3259 659 118 84
6 2787 411 29 29 29
7 2395 216 2 2 2 2
8 2031 98 0 0 0 0 0
9 1691 23 0 0 0 0 0 0
38 M. Erkoc, K. Ertogral / Computers & Industrial Engineering 98 (2016) 30–39

Table 7 and requirements. In the airline industry, the MRO of the airplane
Preferences for additional processing lines versus additional rotables (p = 20 days). parts and components must be carried out in specific intervals
defined with time windows or flying hours. As such, the MRO ser-
vice for aircraft components has to be completed before hard dead-
lines. The MRO service providers are expected not only to satisfy
these enforced deadlines but also deliver with short turnaround
times for their customers’ efficient utilization of the equipment.
To minimize the customers’ downtime, some service providers
adopt exchange programs where customer’s equipment is
exchanged with a ready-to-go module and the uninstalled compo-
nent enters into the overhaul process as a rotable item for a future
exchange. Because of the constrained overhaul capacity and lim-
Table 8 ited number of rotables, the MRO companies may be compelled
Preferences for additional processing lines versus additional rotables (p = 40 days). to ask for an exchange before the customer’s deadline. However,
this practice ends the equipment’s operational cycle early and as
such, is not preferable for the customer.
In this paper, we introduce an integer programming model, as
the first model of the problem to the best of our knowledge, for
optimal overhaul and exchange scheduling that minimizes the
total earliness of exchange times under capacity and inventory
constraints. The capacity is defined by the number of parallel pro-
cessing lines, and the inventory is composed of finite number of
rotables. We also introduce an exact polynomial time algorithm
processing times, namely with p = 20 days and p = 40 days. The for the problem and illustrate its implementation using a case from
marginal impact comparison tables for these cases are given in a real-life practice. We present a sensitivity analysis that investi-
Tables 7 and 8. Both tables reveal that when the overhaul process- gates the joint impact of capacity and inventory on the optimal
ing times are short, rotable inventory becomes the bottleneck more schedule. The analysis shows that the marginal benefit of an addi-
often than the processing lines. On the other hand, if the processing tional rotable inventory or an additional process line is context
times are longer, additional processing lines contribute to the ear- specific and depends on which one is the bottleneck for the MRO
liness performance relatively more in higher number of cases. The firm.
intuition is that longer processing times lead to lower inventory The problem can be extended in different directions. For a
turnovers for each processing line relatively reducing the marginal future work direction one can generalize our model to include mul-
benefit of additional inventory. Such comparison can be used to tiple module types with varying overhaul process requirements.
help MRO firms decide on the direction of capacity expansion espe- Another direction is to incorporate rotable inventory decisions into
cially under budget constraints. the problem with budget constraints or using multi-objective
With the proposed exact solution algorithm, each instance in models. Uncertainty in demand arrivals and processing times are
the above analysis can be solved almost instantaneously using a also potential extensions to our work.
PC with Intel Core i5 processor and 16 GB of 1.6 GHz memory. In
order to demonstrate the computational efficiency of the proposed
Acknowledgments
model and the full-delay algorithm, we used AMPL/CPLEX (version
12.6) and a simple AMPL code (without calling any solver) respec-
This research was partially supported by the Science Fellow-
tively. We used the case study problem discussed above as the base
ships & Grant Programs Department of The Scientific & Technolog-
problem and generated additional instances with larger problem
ical Research Council of Turkey (TUBITAK), BIDEB #2221. We are
sizes by adding jobs. Specifically, we ran the mathematical model
grateful to two anonymous referees whose comments have signif-
for instances with 80, 160, 240, 320, 400, 480, 720, and 880 jobs.
icantly contributed to improvement of our paper.
For the larger instances, the due date of each additional job was
generated by adding a random interval to the previous job’s due
date, where these random intervals range from 0 to 40 days, uni- References
formly distributed. We observed that while the computation times
varied from a couple of seconds to 10 min with the mathematical Arts, J., & Flapper, S. D. (2015). Aggregate overhaul and supply chain planning for
rotables. Annals of Operations Research, 224, 77–100.
model and CPLEX, the proposed full-delay algorithm was able to Buyukkaramikli, N. C., van Ooijen, H. P. G., & Bertrand, J. W. M. (2013). Integrating
solve all instances altogether under one fourth of a second on the inventory control and capacity management at a maintenance service provider.
same workstation. Our analysis indicates that both approaches Annals of Operations Research. forthcoming.
Dekker, R. (1996). Applications of maintenance optimization models: A review and
are computationally efficient. However, the full-delay algorithm analysis. Reliability Engineering and System Safety, 51, 229–240.
does not require any professional solver tool and allows for practi- Dekker, R., & Scarf, P. A. (1998). On the impact of optimisation models in
cal implementation on widely available tools (such as MS Excel/ maintenance decision making: The state of the art. Reliability Engineering and
System Safety, 60, 111–119.
VBA).
Ghobbar, A. A., & Friend, C. H. (2003). Evaluation of forecasting methods for
intermittent parts demand in the field of aviation: A predictive model.
Computers & Operations Research, 30, 2097–2114.
6. Conclusions Gu, J., Zhang, G., & Li, K. W. (2015). Efficient aircraft space parts inventory
management under demand uncertainty. Journal of Air Transport Management,
42, 101–109.
MRO of critical and high-value equipment is an inescapable Guajardo, J. A., Cohen, M. A., Kim, S.-H., & Netessine, S. (2012). Impact of
support activity for continuation of uninterrupted operations for performance-based contracting on product reliability: An empirical analysis.
many manufacturers and service providers. In industries, where Management Science, 58(5), 961–979.
Joo, S. J. (2009). Scheduling preventive maintenance for modular designed
safety is the crucial part of the operations, the maintenance and components: A dynamic approach. European Journal of Operational Research,
overhaul of the equipment used is subject to stern regulations 192, 512–520.
 M. Erkoc, K. Ertogral / Computers & Industrial Engineering 98 (2016) 30–39 39

Joo, S. H., & Min, H. (2011). A multiple objective approach to scheduling the Mwanalushi, K. (2012). Managing rotable inventories. AviTrader MRO. November
preventive maintenance of modular aircraft components. International Journal issue.
of Services and Operations, 9(1), 18–31. Nicolai, R., & Dekker, R. (2008). Optimal maintenance of multi-component systems:
Kilpi, J., Töyli, J., & Vepsäläinen, A. P. J. (2009). Cooperative strategies for the A review. In Complex System Maintenance Handbook (pp. 263–286). London:
availability services of repairable aircraft components. International Journal of Springer.
Production Economics, 117, 360–370. Regattieri, A., Gamberi, M., Gamberini, R., & Manzini, R. (2005). Managing lumpy
Kilpi, J., & Vepsäläinen, A. P. J. (2004). Pooling of spare components between airlines. demand for aircraft spare parts. Journal of Air Transport Management, 11,
Journal of Air Transport Management, 10, 137–146. 426–431.
Luh, P. B., Yu, D., Soorapanth, S., Khibnik, A. I., & Rajamani, R. (2005). A Lagrangian Safaei, N., Banjevic, D., & Jardine, A. K. S. (2011). Workforce-constrained
relaxation based approach to schedule asset overhaul and repair services. IEEE maintenance scheduling for military aircraft fleet: A case study. Annals of
Transactions on Automation Science and Engineering, 2(2), 145–167. Operations Research, 186, 295–316.
MacDonnell, M., & Clegg, B. (2007). Designing a support system for aerospace van Jaarsveld, W., Dollevoet, T., & Dekker, R. (2012). Spare parts inventory control for
maintenance supply chains. Journal of Manufacturing Technology Management, an aircraft component repair shop Working Paper.Rotterdam, Netherlands:
18, 139–151. Erasmus University.
MacDonnell, M., & Clegg, B. (2011). A new inventory model for aircraft spares. In N.
Altay & L. A. Litteral (Eds.), Service parts management. London: Springer-Verlag.