<figure><img src="image_1.png" /></figure>

HAL
open science

# Don't Let It Expire: A 2-Competitive Online Algorithm for Perishable Kit Maintenance

Boris Detienne, Mickael Gaury, Gautier Stauffer

<figure><img src="image_2.png" /></figure>

## To cite this version:

Boris Detienne, Mickael Gaury, Gautier Stauffer. Don't Let It Expire: A 2-Competitive Online Algorithm for Perishable Kit Maintenance. 2025. hal-05180313

HAL Id: hal-05180313

https://inria.hal.science/hal-05180313v1

Preprint submitted on 23 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Don't Let It Expire: A 2-Competitive Online Algorithm for Perishable Kit Maintenance

Boris Detienne¹, Mickael Gaury¹, and Gautier Stauffer²

¹IMB UMR CNRS 5251, Inria Bordeaux Sud-Ouest, Université de Bordeaux, 200 Avenue de la Vieille Tour, Talence, 33405, France, boris detienne@u-bordeaux.fr, mickael gaury@u-bordeaux.fr

²Faculty of Business and Economics (HEC Lausanne), Department of Operations, University of Lausanne, Quartier UNIL-Chamberonne, 1015 Lausanne, Switzerland, gautier.stauffer@unil.ch

## Abstract

We introduce the Kit Update Problem, a new online optimization problem motivated by a real-world application at Doctors Without Borders. Emergency response kits—pre-packed sets of medical items—must be kept in a ready-to-ship state at all times. Since many items are perishable, maintaining readiness incurs both maintenance overhead (manual effort) and destruction costs (due to expired or prematurely replaced items). The objective is to minimize the cumulative cost incurred over time while ensuring that kits remain continuously operational. Our main contributions are as follows:

* We show that the deterministic version of the problem is NP-hard via a reduction from Vertex Cover. The problem shares structural similarities with the well-known Joint Replenishment Problem.

* We present a 2-approximation algorithm for the deterministic (offline) setting. The algorithm is simple and intuitive, relies only on local, non-predictive information, and builds on techniques inspired by the Joint Replenishment Problem. In contrast to the classical joint replenishment setting, however, our approach naturally extends to dynamic scenarios.

* Leveraging the structure of this approximation algorithm, we derive a 2-competitive online policy. The resulting method is robust to uncertainty and imprecise cost estimates, making it well-suited for real-world deployment.

* We evaluate the approach empirically using synthetic instances calibrated to reflect the distributional properties of real data from Doctors Without Borders. The online algorithm reduces total cost by 40% compared to current practices and performs nearly as well as a stochastic look-ahead policy requiring significantly more computational resources.

The proposed policy has been adopted and integrated into the organization's operations, where it has produced similar improvements in practice.
# 1 Introduction

MSF Logistique (MSF-Log) is responsible for supplying medical and non-medical items to the field when needed by MSF or other partner NGOs. Our focus here is on emergency response. As the first 72 hours after a disaster are crucial for an effective intervention, MSF has designed kits containing the necessary medical and non-medical items, which should be stored in appropriate quantities at MSF-Log and ready for shipment within 24-48 hours [9]. For more details on the interest of using kits in humanitarian contexts, see [18]. Medical items in the kits must maintain a minimum shelf life, typically ranging from 6 to 12 months, for the kit to be considered valid. This requirement is crucial because the short lead times associated with deploying kits during emergencies make it impractical to perform last-minute updates to ensure compliance with shelf-life standards. Consequently, regular updates are necessary to ensure the kits remain valid and ready for shipment at any time. At MSF-Log, kits with expired components are updated monthly to maintain their readiness. This process involves replacing medical components nearing their expiration dates with newer ones that have a longer shelf life. However, updating the kits is a time-consuming process. When a kit needs updating, it must be retrieved from the storage location, brought to the update area, opened, expired items disposed of, replaced with new ones (also sourced from the storage location), resealed, returned to its designated storage location, and accompanied by necessary paperwork. Additionally, expired items are usually destroyed (unless they can still be used for other operations), incurring costs.

This paper addresses the challenge of efficiently updating kits under a periodic-review policy. Our approach optimizes each kit in isolation. For clarity, we define a component’s “expiration month” as the calendar month in which it becomes invalid – specifically, six or twelve months before its actual expiry date. At each review period, the decision problem is whether to update a kit and, if so, which components to replace. We measure performance via a single economic metric that sums update time (valued at the hourly labor rate of the update personnel) and destruction costs for expired components.

The problem is inherently online, with an adversarially defined horizon driven by an unpredictable emergency demand. To assess the theoretical and empirical performance of our approach, we also investigate deterministic and stochastic variants. A kit component must be substituted before its expiration date, although it can be updated at any earlier time. In the online context, we assume an always-available stock-i.e., the inventory management policy for components maintains a 100% service level, which is typical-or nearly so-in humanitarian logistics. At any moment, multiple batches with differing expiration dates may be on hand. In the deterministic setting, complete information on all incoming batches and their expiration dates is known in advance over the planning horizon. By contrast, the stochastic setting relies on probabilistic forecasts of batch arrivals and expirations. Because opening a kit incurs a fixed setup cost, it can sometimes be optimal to replace an item before its very last permissible moment, thereby reducing future update effort. The resulting optimal policy typically leverages these “advance” substitutions. In the literature, such models are referred to as opportunistic replacement problems [1].

The closest existing model in the literature is the Opportunistic Replacement Problem (ORP), first introduced by [15], which has since been extensively studied across various fields. For a recent survey on maintenance optimization, one of its primary applications, see [4]. Initially, the problem was analyzed in a deterministic setting [5, 2] and later extended to stochastic environments [12, 13]. Numerous variants of ORP exist in the literature, differing primarily in the assumptions regarding the lifespan of replacement individuals and the time-dependency of replacement costs. For instance, the original works [5, 2] assume that all replacement individuals
of the same component share a common lifespan. In contrast, [12] introduced the Opportunistic Replacement Problem with Individual Lives (ORPIL), where each individual may have a distinct lifespan. They demonstrated that this variant is NP-hard and plays a pivotal role as a subproblem in the stochastic variant of the original ORP, where the lifespan of individuals is stochastic. Subsequently, the same authors [13] developed two-stage stochastic programming approximations to address the (multi-stage) stochastic version of the problem. This approach was later refined and improved in [7]. To the best of our knowledge, no online version of the problem exists.

It is important to stress that the uncertainty in our kit-update setting differs fundamentally from that in [12, 13, 7]. In those maintenance-oriented models, randomness lies in the lifetime of each component after replacement. In our context, however, a component's lifetime is deterministic and known at the moment it is drawn from stock, since it has a fixed expiration date. Instead, uncertainty derives from which batches will be available in stock at any given time – and what their expiration dates will be. Consequently, the stochastic methods developed for the classic ORP in [13] do not apply directly to our problem. Other stochastic approaches-dynamic programming, Markov decision processes, and reinforcement learning (e.g., [10, 3]; see [8] for a survey) – have been applied to maintenance optimization, but their uncertainty models diverge again significantly from ours. To underscore this distinction from the traditional Opportunistic Replacement Problem, we refer to our variants as Kit Update Problems.

We define the (deterministic) Kit Update Problem in Section 2 and establish its computational complexity. A 2-approximation algorithm is then presented in Section 3. To address the dynamic nature of the real-world setting, we introduce an online version of the problem in Section 4 and develop a 2-competitive algorithm. Section 5 discusses practical policies considered by MSF-Log and introduces a stochastic lookahead policy as an additional alternative. Finally, Section 6 evaluates the empirical performance of our online algorithm in comparison to these baselines, using instances generated from historical data.

*Basic notations and definitions:* In the following, given a positive integer $k$, we denote by $[k]$ the set $\{1, \dots, k\}$. Given a set $S \subseteq \mathbb{N}$, $u, v \in S$ with $u < v$ are said to be consecutive if $S \cap \{u+1, \dots, v-1\} = \emptyset$. An interval $[a, b]$ is said to cover a set $S$ if $S \subseteq [a, b]$.

## 2 The deterministic Kit Update Problem (KUP)

The essence of the Kit Update Problem, sketched in the previous section, can be captured by distinguishing between two types of costs: set-up costs and item substitution costs. Set-up costs are fixed and independent of the number of items being updated in the kit; these include activities such as retrieving the kit from its storage location, opening it, and completing the necessary paperwork. In contrast, item substitution costs arise from replacing components and may include expenses such as destruction and handling fees. We first consider a setting where the availability of future batches of components in the stock is known in advance. This leads to the following natural deterministic model.

<footnote n="1">¹No interval is contained in another one. This assumption is w.l.o.g.</footnote>
### Problem (P). The Deterministic KUP

**Input:** a set $\{0, 1, ..., T\}$ of time periods for some $T \in \mathbb{N} \setminus \{0\}$, $m$ different components numbered 1, ..., $m$, costs $K_i \ge 0$, for $i = 0, 1, ..., m$, and, for each $i \in [m]$, a set $I_i$ of proper¹ intervals, of the form $[u, v]$ for some $u, v \in \{0, 1, ..., T\}$ with $u \le v$, such that

$$ \bigcup_{I \in I_i} (I \cap \{0, 1, ..., T\}) = \{0, 1, ..., T\} \qquad (1) $$

**Output:** For each $i = 1, ..., m$, a subset of periods $S_i \subseteq \{1, ..., T\}$ which satisfy that, for each $u, v$ in $\{0\} \cup S_i \cup \{T+1\}$ with $u < v$ consecutive, there exists an interval of $I_i$ covering $[u, v-1]$ and that minimize $|\cup_{i=1}^n S_i| \cdot K_0 + \sum_{i=1}^n |S_i| \cdot K_i$

We sometimes call a feasible solution $(S_i)_{i \in [m]}$ to the problem above a schedule. In this model, an interval $[u, v]$ within $I_i$, for some $i \in [m]$, represents the availability of a batch of component $i$. Specifically, the batch becomes available at the beginning of period $u$ and remains valid until the end of period $v$. Updates to the kit are assumed to occur at the very beginning of each period. Property (1) ensures feasibility: there is continuous availability of component $i$ across all periods in the planning horizon.

It is worth noting that a component $i$ may represent a batch of identical components (with the same expiration dates) when multiple units of a component are required in a kit. In such cases, we assume that all elements within the batch will be updated simultaneously.

**Remark 1.** We may assume, without loss of generality, that for each $i \in [m]$, there is a unique interval in $I_i$ starting at 0 (the longest one), which corresponds to the remaining shelf life of component $i$ currently present in the kit. Indeed, in the model, we do not "pay" for updates at time 0.

KUP is closely related to the Joint Replenishment Problem with Deadlines (JRP-D). Consequently, we can adapt the proofs provided by Nonner and Souza [11], which establish a polynomial-time reduction from the Vertex Cover problem to JRP-D, to demonstrate similar results for KUP. For completeness, we include the detailed proof in Appendix A.

**Lemma 1.** The deterministic Kit Update Problem is NP-hard and, furthermore, APX-hard.

## 3 A simple 2-approximation algorithm

We now present a simple 2-approximation algorithm for KUP. That is, given any instance of KUP, we provide (in polytime) a feasible solution with cost no more than twice the cost of an optimal solution. In the following, we refer to an instance of KUP as a problem of the form (P) for a defined set of inputs, that is, for a choice of $T$, $m$, and, for each $i \in [m]$, $K_i$, $I_i$ satisfying property (1). The 2-approximation algorithm is inspired by an approach developed in [6] and [17] for the One-Warehouse Multi-Retailer problem and JRP-D.

We consider $m+1$ relaxations $(P_0), (P_1), ..., (P_m)$ of our original problem (P). Problem $(P_i)$ for $i \in [m]$ is the problem limited to component $i$ only, and where we pay fixed cost $K_i$. Problem $(P_0)$ is the original problem, but where we consider only the fixed cost $K_0$ (i.e., $K_1 = K_2 = ... = K_m = 0$). Note that in this case, we can assume w.l.o.g. that an optimal solution updates all components on each update, i.e., $S_i = S_j$ for all $i, j \in [m]$. Indeed, once
$K_0$ is paid to update a component, it does not cost anything additional to update another one.
More formally, we define for any instance of (P), a single item relaxation ($P_i$) for $i \in [m]$:

**Problem ($P_i$).**

**Input:** the set $\{0, 1, ..., T\}$ of time periods from (P), the cost $K_i$ of (P), and, the set $I_i$ of intervals of (P).

**Output:** a subset of (update) periods $S_i \subseteq \{1, ..., T\}$ which satisfy that, for each $u, v$ in $\{0\} \cup S_i \cup \{T+1\}$ with $u < v$ consecutive, there exists an interval of $I_i$ covering $[u, v-1]$ and that minimize $|S_i| \cdot K_i$.

We also define for any instance of (P), a multi-item problem relaxation ($P_0$).

**Problem ($P_0$).**

**Input:** the set $\{0, 1, ..., T\}$ of time periods from (P), the (fixed) cost $K_0$ of (P), and the set $I_i$ of intervals of (P).

**Output:** A subset of (update) periods $S_0 \subseteq \{1, ..., T\}$ which satisfy that, for each $u, v$ in $\{0\} \cup S_0 \cup \{T+1\}$ with $u < v$ consecutive, there exists an interval of $I_i$ covering $[u, v-1]$, for each $i \in [m]$ and that minimize $|S_0| \cdot K_0$.

Note that an optimal solution to ($P_0$), ($P_1$), ..., ($P_m$) can be obtained by solving the problems for $K_i = 1, i = 0, ..., m$. Indeed, an optimal solution $S_i$ to ($P_i$) is an optimal solution to the same problems where $K_i$ is set to one whenever $K_i > 0$, and any feasible solution to ($P_i$) is optimal when $K_i = 0$. Hence, all problems ($P_0$), ($P_1$), ..., ($P_m$) can be solved easily by postponing the updates as late as possible. More precisely, this means that, for problem ($P_i$), we can find an optimal solution $S_i$ iteratively using Algorithm 1.

<caption>**Algorithm 1:** Solving ($P_i$) for some $i \in [m]$</caption>

1. Set $t = 0$ and $S_i = \{\}$
2. **while** $t < T + 1$ **do**
3. &nbsp;&nbsp;&nbsp;&nbsp; $t = \max\{t' > t : \exists I \in I_i \text{ s.t. } [t, t' - 1] \subseteq I\}$
4. &nbsp;&nbsp;&nbsp;&nbsp; $S_i = S_i \cup \{t\}$
5. **end**
6. **return** $S_i$

For problem ($P_0$), similarly, we can build an optimal solution $S_0$ by looking at the earliest expiration time over all components at each step. Hence, we can set $S_0$ iteratively using Algorithm 2.

<caption>**Algorithm 2:** Solving ($P_0$)</caption>

1. Set $t = 0$ and $S_0 = \{\}$
2. **while** $t < T + 1$ **do**
3. &nbsp;&nbsp;&nbsp;&nbsp; $t = \max\{t' > t : \exists I \in I_i \text{ s.t. } [t, t' - 1] \subseteq I, \text{ for all } i \in [m]\}$
4. &nbsp;&nbsp;&nbsp;&nbsp; $S_0 = S_0 \cup \{t\}$
5. **end**
6. **return** $S_0$

For a period $t$ in $\{1, ..., T\}$ and a solution $S_0$, we define $p(t)$ to be the largest $u$ in $S_0 \cup \{0\}$
with $u \le t$ and $s(t)$ to be the smallest $u$ in $S_0 \cup \{T+1\}$ with $u \ge t$. We slightly abuse notations here as $p(t)$ and $s(t)$ also depend on $S_0$ and $T$, but in the following, $S_0$ and $T$ will always be clear from the context. We build a feasible solution to problem (P) using Algorithm 3.

<caption>**Algorithm 3:** Approximation algorithm for (P)</caption>

1 Compute $S_i$ for $i \in [m]$ with Algorithm 1

2 Compute $S_0$ with Algorithm 2

3 For $i \in [m]$, define $\bar{S}_i := \cup_{t \in S_i} \{p(t), s(t)\} \setminus \{T+1\}$

4 return Solution $(\bar{S}_1, ..., \bar{S}_m)$

**Theorem 1.** *Algorithm 3 is a 2-approximation.*

*Proof.* Observe that, for any $i \in [m]$, we have by construction that no $p(t)$ is equal to 0 for $t$ in $S_i$. Indeed, the minimum element in $S_0$ is no smaller than the minimum element in $S_i$. Moreover $\bar{S}_i \subseteq S_0$ for $i \in [m]$.

We first prove the feasibility of the solution returned by Algorithm 3. Consider $i \in [m]$ and two consecutive values $t < t'$ in $\{0\} \cup \bar{S}_i \cup \{T+1\}$. We want to prove that there exists an interval $I$ of $I_i$ covering $[t, t' - 1]$. Now we delve into two cases.

(i) Assume that $t = p(t'')$ for some $t'' \in S_i$ with $t < t'' < t'$. Note again that $t \ne 0$ by construction. Then, either $t' = s(t'')$ and $t, t'$ are two consecutive periods in $S_0$, or $t$ is the last period in $S_0$ and $t' = T+1$. In both cases, $I$ exists by the feasibility of $S_0$ in $(P_0)$.

(ii) Assume now that we are not in case (i). Suppose first that $t \ne 0$. Then $t = s(t'')$ for some $t'' \le t$ (choose $t''$ maximum with this property) and there is no element of $S_i$ in $(t, t')$ (otherwise we are in case (i)). But then $t' = p(t''')$ for $t''''$ consecutive to $t''$ in $S_i$ or $t' = T+1$. In both cases, $I$ exists by the feasibility of $S_i$ in $(P_i)$. Suppose now that $t = 0$. Then $t' \le \min\{u : u \in S_i\} = \max\{u : [0, u-1] \in I_i\}$ (with the convention that $\min\{u : u \in S_i\} = T+1$ if $S_i = \emptyset$) as $\min_{i=1}^m \max\{u : [0, u-1] \in I_i\} \in S_0 \cup \{T+1\}$ by construction, and then $I$ exists by the feasibility of $S_i$ in $(P_i)$.

For a feasible solution $(T_1, ..., T_m)$ to (P), we denote by $C(T_1, ..., T_m)$ its cost in problem (P) and by $C_i(T_i)$ the cost of the (feasible) solution $T_i$ in problem $(P_i)$, for $i \in [m]$. For a solution $T_0$ to $(P_0)$, we denote by $C_0(T_0)$ its cost in problem $(P_0)$.

We now prove that the solution $(\bar{S}_1, ..., \bar{S}_m)$ built is no worse than twice the optimal solution to (P). $C(\bar{S}_1, ..., \bar{S}_m)$ is, by construction, no more than twice the sum of the costs of the optimal solutions to the problems $(P_0), (P_1), ..., (P_m)$. Indeed we have $\cup_{i=1}^m \bar{S}_i \subseteq S_0$ and $|\bar{S}_i| \le 2 \cdot |S_i|$. Thus $C(\bar{S}_1, ..., \bar{S}_m) = |\cup_{i=1}^m \bar{S}_i| \cdot K_0 + \sum_{i=1}^m |\bar{S}_i| \cdot K_i \le |S_0| \cdot K_0 + 2 \cdot \sum_{i=1}^m |S_i| \cdot K_i \le 2 \cdot \sum_{i=0}^m C_i(S_i)$. Besides, the sum of the optimal values to $(P_0), ..., (P_m)$ is a lower bound on the optimal value to (P). Indeed, an optimal solution $(S_1^*, ..., S_m^*)$ to KUP can be converted into (feasible) solutions $\tilde{S}_0 := \cup_{i=1}^m S_i^*$, $\tilde{S}_1 = S_1^*$, ..., $\tilde{S}_m = S_m^*$ to $(P_0), (P_1), ..., (P_m)$. We have $C(S_1^*, ..., S_m^*) = \sum_{i=0}^m C_i(\tilde{S}_i) \ge \sum_{i=0}^m C_i(S_i)$ (the inequality follows from optimality of $S_i$ for problem $(P_i)$, $i = 0, ..., m$). Overall we thus have $C(\bar{S}_1, ..., \bar{S}_m) \le 2 \cdot C(S_1^*, ..., S_m^*)$ and the algorithm above therefore yields a 2-approximation. $\square$

We now introduce a slight variation of Algorithm 3 that will reveal more interesting in an online setting. In Algorithm 3, the update periods for component $i \in [m]$ form a subset of $S_0$. We can thus substitute $\bar{S}_i$ with an optimal solution, say $S'_i$, to a variation of problem $(P_i)$ where we impose an update to form a subset of $S_0$. By optimality, the corresponding solution has
$|S'_i| \le |\bar{S}_i|$. The cost of the corresponding solution is thus at most $|S_0| \cdot K_0 + \sum_{i=1}^m |S'_i| \cdot K_i \le |S_0| \cdot K_0 + \sum_{i=1}^m |\bar{S}_i| \cdot K_i$ which is thus no more that twice the cost of the optimal solution to (P) by Theorem 1. Observe that, as in Algorithm 1, the solution $S'_i$ consists in postponing the update as late as possible (within $S_0$). The corresponding algorithm is formalized in Algorithm 4.

<caption>**Algorithm 4:** Variant of approximation algorithm for (P)</caption>

1. Set $S_i = \{\}$ for $i = 0, \dots, m$, $t_0 = 0$ and $t_i = \max\{u : [0, u-1] \in I_i\}$ for $i \in [m]$.
2. **while** $t_0 < T+1$ **do**
3. &nbsp;&nbsp;&nbsp;&nbsp;Set $t'_0 = \max\{u > t_0 : \exists I \in I_i \text{ s.t. } [t_0, u-1] \subseteq I, \text{ for all } i = 1, \dots, m\}$
4. &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 1, \dots, m$ **do**
5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $t_i < t'_0$ **then**
6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\tilde{S}_i = \tilde{S}_i \cup \{t_0\}$
7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end**
8. &nbsp;&nbsp;&nbsp;&nbsp;**end**
9. &nbsp;&nbsp;&nbsp;&nbsp;**end**
10. Set $t_0 = t'_0$ and, if $t'_0 \ne T+1$, $S_0 = S_0 \cup \{t'_0\}$
11. **end**
12. **return** Solution $(\tilde{S}_1, \dots, \tilde{S}_m)$
13. **p**

**Corollary 1.** *Algorithm 4 is a 2-approximation algorithm.*

Observe that by construction $0 \notin \tilde{S}_i$ and besides, for each $t \in S_0$ along the algorithm, there exists $i$ for which $t \in \tilde{S}_i$. Hence $\cup_i \tilde{S}_i = S_0$.

Now Algorithm 4 has several nice features. First, it does not depend on $K_0$ and $K_i$. The algorithm thus yields a 2-approximation for every choice of $K_0$ and $K_i$. It makes the algorithm extremely robust to the estimation of these costs. Second, it uses only information on the batches available in stock at update periods (periods $t'_0 \ne T+1$ in the algorithm) to make decisions. It can thus be implemented in an online setting. We discuss this in the next section.

We now give an example that shows that the analysis of the performance guarantees of Algorithms 3 and 4 cannot be improved. Consider a problem with two components with $K_1 = K_2 = 1$ and $K_0 = \epsilon$ for some $\epsilon > 0$. Let $K \in \mathbb{N}$ with $K \ge 1$. We define $I_1 := \{[0], [1, 3], [2, 4]\} \cup \{[4k, 4(k+1)-1], [4k+1, 4(k+1)], k = 1, \dots, K\}$ and $I_2 := \{[0, 1], [1, 2]\} \cup \{[4(k-1)+2, 4k+1], [4(k-1)+3, 4k+2], k = 1, \dots, K\}$ and $T = 4K+1$ (with the convention that if an interval ends after $T$, it is shortened to terminate $T$). It is not difficult to check that the optimal solutions to $(P_0), (P_1), (P_2)$ are respectively $S_0 = \{1, 3, 5, \dots, 4K+1\}$, $S_1 = \{1\} \cup \{4k, k = 1, \dots, K\}$ and $S_2 = \{2+4(k-1), k = 1, \dots, K\}$. It follows that $\bar{S}_1 = \{1, 3, 5, \dots, 4K+1\}$ and $\bar{S}_2 = \{1, 3, 5, \dots, 4K-1\}$. We have $|S_0| = 2K+1$, $|S_1| = K+1$, $|S_2| = K$, $|\bar{S}_1| = 2K+1$, $|\bar{S}_2| = 2K$ and $|S_1 \cup S_2| = 4K+1$. The solution where we update components 1 and 2 at period $S_1$ and $S_2$ respectively has cost $(4K+1) \cdot \epsilon + (K+1) + K$. The solution where we update components 1 and 2 at periods $\bar{S}_1$ and $\bar{S}_2$ respectively has cost $(2K+1) \cdot \epsilon + (2K+1) + 2K$. When $\epsilon$ tends to zero, this is $2K+1$ and $4K+1$ respectively, and the ratio between the cost of solution $(\bar{S}_1, \bar{S}_2)$ and solution $(S_1, S_2)$ tends to 2 as $K$ tends to infinity. We have thus instances with feasible solutions which are arbitrarily close to half the cost of our approximate solution. Note that the solutions returned by Algorithm 3 and 4 are identical in this case.
4 Extension to a 2-competitive online algorithm

We now frame a natural online version of the problem using the sequential decision framework
of Powell [14]. We use this framework as it unifies the treatment of the online and the stochastic
settings, and the latter will be investigated in the next section for the evaluation of the empirical
performances of the online algorithm.

The framework of Powell works as follows. Consider a discrete (possibly infinite) set of time
periods $H = \{0, 1, 2, ...\}$. At each time step $t \in H$, we make some decisions, denoted $x_t$, based
on available information $S_t$. $S_t$ is referred to as the state of the system at time $t$. Then, after
the decision $x_t$ is made, new information $W_{t+1}$, called exogenous information, becomes available.
With this information, the system transit to a new state $S_{t+1}$ according to some transition
function $M$, known as the system model: $S_{t+1} = M(S_t, x_t, W_{t+1})$. There is a cost $C(S_t, x_t)$
associated with taking decision $x_t$ in state $S_t$. One typically want to design a non anticipative
policy $\pi$, that is, a function $X_t^\pi(S_t) : (t, S_t) \mapsto x_t$ that minimizes some function of $C(S_t, X_t^\pi(S_t))$
over $H$ or, as is the case in this section, that is guaranteed to be no more than a certain factor
away from the a posteriori optimum.

In our specific online setting, we assume that:

* $S_t$ contains the information on the set of intervals available at the beginning of period $t$ for each component (i.e. all batches available in stock) and the information regarding the expiration dates of the component currently in the kit. Note that we assume there is always an interval in stock covering at least $t$ for each component: this can be considered as information available at any time. We denote by $I_i(t)$ the set of intervals available at the beginning of period $t$ for component $i \in [m]$, by $t_i(t)$ the latest possible update period for each component $i \in [m]$ in the kit (i.e. expiration period plus one), and we define $t_0(t) := \min_{i=1}^m t_i(t)$ (this is the latest possible update period given what is currently in the kit). $S_t = (I_i(t), t_i(t), i \in [m]; t_0(t))$;

* $x_t$ is a subset of $[m]$ representing which components are updated at (the beginning of) period $t$ and is such that we have at least $i \in x_t$ for each $i$ such that $t_i(t) = t$ as kits must remain valid anytime;

* $W_{t+1}$ contains information regarding whether horizon $H$ ends in period $t$ (i.e. whether the kit was required in the field during period $t$) and the intervals starting at time $t+1$ for each component $i=1,...,m$ (i.e. the batches that will become available at time $t+1$). We define $T=t$ if the horizon ends in period $t$. We assume that although we do not know when the horizon will end, it will end - this fact can be seen as information available at any time. We call $\Delta_i(t+1)$ the intervals starting at time $t+1$ for a component $i$;

* The transition function is defined such that, for all $i \in [m]: I_i(t+1) = \{[u,v] \in I_i(t): v \ge t+1\} \cup \Delta_i(t+1)$ and, $t_i(t+1) = t_i(t)$ if $i \notin x_t$ and $t_i(t+1) = \max\{v: [u,v-1] \in I_i(t) \text{ for some } u \le v-1\}$ if $i \in x_t$;

* The cost function $C(S_t, x_t)$ is equal to $K_0 \cdot \mathbf{1}_{x_t \neq \emptyset} + \sum_{i \in x_t} K_i$.

We want to find a (non-anticipative) policy $\pi$ with a performance guarantee on the value
of $\sum_{t=1}^{T} C(S_t, X_t^\pi(S_t))$ against an adversary with full information. We say that a policy $\pi$ is
$\alpha$-competitive, for some $\alpha \ge 1$, if $\sum_{t=1}^{T} C(S_t, X_t^\pi(S_t)) \le \alpha \cdot \sum_{t=1}^{T} C(S_t, x_t^*)$, where $x_t^*$ is the set
of component(s) updated in an optimal solution to the a posteriori deterministic KUP problem
with $I_i := \cup_{t=1}^{T} I_i(t)$ for $i \in [m]$. We apply Algorithm 5 to define a policy for the online setting.
<caption>**Algorithm 5:** Online policy for given $t$ and $S_t = (I_i(t), t_i(t), i \in [m]; t_0(t))$ (with $t \le T$)</caption>

1 $x_t = \emptyset$
2 **if** $t = t_0(t)$ **then**
3 &nbsp;&nbsp;&nbsp;&nbsp;$t'_0 = \max\{v : \exists I \in I_i(t) \text{ s.t. } [t, v-1] \subseteq I, \text{ for all } i = 1, \dots, m\}$
4 &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 1, \dots, m$ **do**
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $t_i(t) < t'_0$ **then**
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x_t = x_t \cup \{i\}$
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end**
8 **end**
9 **end**
10 **return** $x_t$

**Theorem 2.** *Algorithm 5 yields a (non-anticipative) feasible policy for the online problem described above, and it is 2-competitive.*

*Proof.* The policy is non-anticipative, and feasibility is guaranteed by the existence of an interval in stock covering at least $t$ for each component. To prove 2-competitiveness, we can compare to the optimal solution a posteriori. Suppose we know all the information revealed over time. In particular we know $T$ and all intervals $I_i := \cup_{t=1}^T I_i(t)$ for $i \in [m]$. Note that we also have $I_i(t) = \{[u, v] \in I_i : t \in [u, v]\}$ as no interval disappears before its expiration date in the model above. Hence, Algorithm 5 yields exactly the same solution as Algorithm 4. The result then follows from Corollary 1. □

**Remark 2.** *Note that we assume in our model that an interval only disappears upon reaching its expiration date, meaning the corresponding batch is not fully consumed by other demands within the interval. This assumption is crucial to ensuring 2-competitiveness; otherwise, an "adversary" could remove an interval from one period to the next, potentially forcing the need to "reserve" components prematurely. Such a situation could result in updates being performed earlier than necessary or desirable if there is a perceived risk of the batch being consumed before the intended update, leading to substitution with a batch of significantly shorter lifespan. Exploring alternative models that incorporate competition for component batches among other kits and products would be an interesting avenue for future research.*

## 5 Baseline policies

This section presents two alternative policies for the (online) Kit Update Problem, which will serve as baselines in our empirical evaluation. We first describe simple strategies either previously used by MSF-Log or suggested by them after reviewing our online algorithm. These approaches are easy to implement and compatible with the constraints of the existing information system. We then introduce a more computationally intensive policy based on a two-stage stochastic model that leverages distributional information about future uncertainty, in order to assess the potential benefits of incorporating such information when it is available.

**Myopic policies** MSF-Log's historical kit-update scheduling strategy relies on a simple myopic heuristic that replaces components only when they expire at the last possible moment. Formally, the policy at time $t$ is defined by $x_t = \{i \in [m] : t_i(t) = t\}$, where $t_i(t)$ denotes the expiration date
of component $i$ at time $t$. This heuristic can be slightly improved by opportunistically replacing, during an update at time $t$, not only components expiring at $t$ but also those scheduled to expire within the next $\alpha$ periods. The modified policy is given by:

$$x_t = \begin{cases} \{i \in [m] : t \le t_i(t) \le t + \alpha\} & \text{if } \exists i \in [m] \text{ such that } t_i(t) = t, \\ \emptyset & \text{otherwise.} \end{cases}$$

This opportunistic variant remains simple to implement and does not require forecasting, while potentially reducing the number of future updates. It was considered by MSF-Log, with values of $\alpha = 1$ or 2, after being introduced to our online approach to test the idea.

**Stochastic lookahead policy** The myopic decision rules above are not explicitly based on an objective function. In this section, we consider that our objective is to find a policy minimizing the total expected cost over the planning horizon: $\min_{\pi} \mathbb{E}_W[F_W^\pi]$, with $F_W^\pi := \sum_{t=1}^T C(S_t, X_t^\pi(S_t))$ denoting the cost of policy $\pi$ under random data $W$. This risk-neutral approach is appropriate when the distribution of the uncertain parameters can be reasonably approximated, the decisions are made a large number of times, in the long run, and no severe consequences stem from a particularly bad random outcome. Stochastic lookahead policies naturally arise in this context, taking the form of optimal solutions to multi-stage stochastic programs. However, such problems are often computationally intractable, as confirmed by preliminary experiments in our setting. We therefore resort to a two-stage approximation, which relaxes the non-anticipativity constraints beyond time $t$ (see, e.g., [14], Chapter 20). The first stage includes the decisions made at time $t$ only, while the second stage accounts for the rest of the time horizon and is scenario-dependent. Given the current state $S_t$ of the system at time $t$, we consider a sample set $\tilde{\Omega}_t$. Each scenario $\omega \in \tilde{\Omega}_t$ represents an observation of the random variables $W_{t+1}, W_{t+2}, \dots, W_{t+\bar{T}}$, where $\bar{T}$ is the (fixed) duration of the lookahead horizon. The two-stage problem defined on $\tilde{\Omega}_t$ is solved through an MILP model detailed in Appendix B. The policy is defined by setting $x_t$ to the set of components replaced at $t$ in an optimal solution of the MILP.

# 6 Case study

Our case study is based on historical data provided by MSF-Log, from which we derive 11 instances, each corresponding to a specific kit, along with 100 random scenarios per kit. Complete details on instance generation and the stochastic model are provided in Appendix C. We evaluate the performance of the different policies within a simulation framework over a set $\Omega$ of i.i.d. random stock trajectories defined over a fixed time horizon $\{1, \dots, T\}$. Each scenario $\omega \in \Omega$ consists of an initial state $S_1^\omega$ and a sequence of random events $W_1^\omega, \dots, W_{T-1}^\omega$. For each policy $\pi$, we simulate the sequential decision process described in Section 4 on each scenario $\omega$, resulting in a realized cost $F_{W^\omega}^\pi$. To assess (a posteriori) optimality gaps, we also compute the cost under the perfect information assumption by solving for the optimal offline policy in each scenario, yielding the benchmark value $F_{W^\omega}^* := \min_{\pi} F_{W^\omega}^\pi$ (see Appendix B).

We compare the performance, in terms of expected total cost, of six policies. Myopic0, Myopic1 and Myopic2 are the myopic policies with $\alpha = 0, 1$ and 2, respectively. Online is the proposed online policy. Lookahead_S10_A50 and Lookahead_S20_A100 are the stochastic lookahead policies with $|\tilde{\Omega}| = 10$ and $\bar{T} = 50$, and $|\tilde{\Omega}| = 20$ and $\bar{T} = 100$, respectively. Because of the heavy computational requirements of this approach, time limits of 30 seconds and 120 seconds, respectively, are imposed for the solution of the lookahead problem at each period, and
it is evaluated on instances with less than 15 components only. The sample set $\tilde{\Omega}$ is drawn independently of $\Omega$. The algorithms are implemented in Python, and the MILP models are solved using Gurobi 11. The tests are performed on a PC equipped with Intel(R) Core(TM) i7-9700K CPU and 128 GB RAM.

We tested various values of $K_0 \in \{15, 50, 200, 1000\}$, while using historical data for the remaining $K_i$ values ($i > 0$). These configurations reflect realistic scenarios, and as expected, the myopic policies perform increasingly poorly as $K_0$ grows. This is expected, as these policies primarily focus on minimizing the number of component replacements, rather than anticipating their long-term impact. Figure 1 shows the performance profile of each policy on instances with less than 15 components for two different choices of $K_0$ (more results are reported in Appendix D). Despite the very low computational and information requirements, the online algorithm performs remarkably well (and much better than its worst-case competitive ratio), since it outperforms the simplest lookahead policy and looks competitive compared to the less limited one, which is the best tested policy in this study. To evaluate the statistical relevance of this analysis, we computed stochastic optimality gaps in a Sample Average Approximation manner (see e.g. [16], chap. 5). More precisely, we estimate $E_W[(F_W^\pi - F_W^*)/F_W^*$] over all the instances and obtain confidence intervals. Myopic policies give 53 ± 4%, 35 ± 4% and 26 ± 2% gaps, the online policy gives 9 ± 1%, and the stochastic lookahead policies, 9.4 ± 1% and 4.6 ± 0.4% gaps, with 95% confidence.

<figure><img src="image_4.png" /><figcaption>Figure 1: Optimality gaps for instances with $m \le 15$, $K_0 = 50$ (on the left) and $K = 200$ (on the right). The curve of policy $\pi$ shows the observed probability $\mathbb{P}(F_W^\pi \le x \cdot F_W^*)$.</figcaption></figure>

The *in silico* case study demonstrates the strong performance of the proposed 2-competitive online algorithm on realistic instances. In addition to its theoretical guarantees, the policy requires minimal information and is simple enough to be implemented manually—an important feature for deployment at MSF-Log, where production operators apply such policies based on manual extraction of expiring components from the IT system.

The stochastic optimality gaps observed in our experiments indicate that a few percentage points of improvement may still be achievable: an area where the proposed stochastic lookahead policy shows strong potential. Designing such algorithms for larger-scale instances remains a promising challenge, both from practical and theoretical perspectives. Another natural research direction involves extending the model to a broader warehouse management setting, where resources are shared across multiple kits. Finally, we note that preliminary real-world experiments at MSF-Log indicate a 40% improvement when implementing the *Online* policy (or slight variations thereof) compared to the previously used *Myopic0* strategy. This outcome aligns with the findings of our *in silico* study and represents a noteworthy practical achievement.
# Acknowledgement

We are grateful to Delphine Espieussas, Director of Operations at MSF-Log Bordeaux, and her team for their trust, support, and collaboration, which made this research possible and led to impactful outcomes in practice.

# References

[1] Ab-Samat, H. and Kamaruddin, S. (2014). Opportunistic maintenance (om) as a new advancement in maintenance approaches: A review. *Journal of Quality in Maintenance Engineering*, 20(2):98-121.

[2] Andréasson, N. (2004). *Optimization of opportunistic replacement activities in deterministic and stochastic multi-component systems*. Chalmers Tekniska Hogskola (Sweden).

[3] Barde, S., Shin, H., and Yacout, S. (2016). Opportunistic preventive maintenance strategy of a multi-component system with hierarchical structure by simulation and evaluation. In *2016 IEEE 21st International Conference on Emerging Technologies and Factory Automation (ETFA)*, pages 1-8. IEEE.

[4] De Jonge, B. and Scarf, P. A. (2020). A review on maintenance optimization. *European journal of operational research*, 285(3):805-824.

[5] Dickman, B., Epstein, S., and Wilamowsky, Y. (1991). A mixed integer linear programming formulation for multi-component deterministic opportunistic replacement. *The Journal of the Operational Research Society of India*, 28(3):165-175.

[6] Gayon, J.-P., Massonnet, G., Rapine, C., and Stauffer, G. (2017). Fast approximation algorithms for the one-warehouse multi-retailer problem under general cost structures and capacity constraints. *Mathematics of Operations Research*, 42(3):854-875.

[7] Laksman, E., Strömberg, A.-B., and Patriksson, M. (2020). The stochastic opportunistic replacement problem, part iii: improved bounding procedures. *Annals of Operations Research*, 292:711-733.

[8] Marugán, A. P. (2023). Applications of reinforcement learning for maintenance of engineering systems: A review. *Advances in Engineering Software*, 183:103487.

[9] Michel et, S. and Bidan, M. (2018). Proposition de caractérisation de la logistique humanitaire à la lumière de msf log: un fort couplage du système d'information et de la supply chain. *Logistique & Management*, 26(3):156-167.

[10] Moghaddam, K. S. and Usher, J. S. (2011). Sensitivity analysis and comparison of algorithms in preventive maintenance and replacement scheduling optimization models. *Computers & Industrial Engineering*, 61(1):64-75.

[11] Nonner, T. and Souza, A. (2009). Approximating the joint replenishment problem with deadlines. *Discrete Mathematics, Algorithms and Applications*, 1(02):153-173.

[12] Patriksson, M., Strömberg, A.-B., and Wojciechowski, A. (2015a). The stochastic opportunistic replacement problem, part i: models incorporating individual component lives. *Annals of Operations Research*, 224:25-50.
[13] Patriksson, M., Strömberg, A.-B., and Wojciechowski, A. (2015b). The stochastic opportunistic replacement problem, part ii: a two-stage solution approach. *Annals of Operations Research*, 224:51–75.

[14] Powell, W. B. (2022). *Reinforcement Learning and Stochastic Optimization: A Unified Framework for Sequential Decisions*. John Wiley and Sons, Hoboken.

[15] Radner, R. and Jorgenson, D. W. (1962). Optimal replacement and inspection of stochastically failing equipment. *Studies in applied probability and management science*, pages 184–206.

[16] Shapiro, A., Dentcheva, D., and Ruszczyński, A. (2009). *Lectures on Stochastic Programming: Modeling and Theory*. Society for Industrial and Applied Mathematics.

[17] Stauffer, G. (2018). Approximation algorithms for k-echelon extensions of the one warehouse multi-retailer problem. *Mathematical Methods of Operations Research*, 88:445–473.

[18] Vaillancourt, A. (2016). Kit management in humanitarian supply chains. *International Journal of Disaster Risk Reduction*, 18:64–71.

## A Proof of Lemma 1

*Proof. We start with establishing the polytime reduction from vertex cover to KUP.*

Let $G = (V, E)$ be an undirected graph with $V = \{1, 2, ..., n\}$ and $E = \{e_1, e_2, ..., e_m\}$. We construct a KUP instance $K$ with $m+1$ components, $4n+3$ intervals, $n + 3$ periods $(0, 0', 1, ..., n, n+1)$, in this order (remark: $0'$ corresponds to period 1 in the KUP instance), and $K_i := 1$ for $0 \le i \le m+1$. For each component $1 \le i \le m$, we define $I_i := \{[0, r-1], [0', s-1], [r, n], [s, n+1]\}$, where $e_i = (r, s)$ for some $r, s \in V$ with $r < s$. For component $m+1$ we define $I_{m+1} := \{[0, 0], [0', n], [n+1, n+1]\}$.

Observe that, for any $i = 1, ..., m$, there is no set $S_i \subseteq \{0', 1, ..., n+1\}$ of cardinality one that satisfies property ($\mathcal{P}_i$). Besides, it is easy to see that the sets of cardinality two that achieve property ($\mathcal{P}_i$) contain $r$ (and a period in $[s+1, ..., n+1]$) or $s$ (and a period in $[0', r-1]$) or both $r$ and $s$. Moreover the only set $S_{m+1}$ that satisfy ($\mathcal{P}_{m+1}$) is $S_{m+1} = \{0', n+1\}$.

We can assume w.l.o.g. that an optimal schedule for $K$ is such that $S_i$ has cardinality two for any $i = 1, ..., m+1$. It is true for $i = m+1$ as we just observed that $S_{m+1} = \{0', n+1\}$ for a feasible schedule. Let us see for $i = 1, ..., m$. Any feasible schedule is such that $S_i \cap \{0', 1, ..., r\} \neq \emptyset$ and such that $S_i \cap \{s, ..., n+1\} \neq \emptyset$. Let $u \in S_i \cap \{0', 1, ..., r\}$ and $v \in S_i \cap \{s, ..., n+1\}$. Hence if $S_i$ is of cardinality greater or equal to three, we can substitute $S_i$ by $\{r, v\}$ if $r \in S_i$, by $\{u, s\}$ if $s \in S_i$ and by $\{r, v\}$ if $r, s \notin S_i$. For each $i$, we reduce the cardinality of $S_i$ by at least one and in the worst case we add one to the cardinality of $\bigcup_{i=1}^{m+1} S_i$ so overall, we cannot increase the objective value of $|\bigcup_{i=1}^{m+1} S_i| + \sum_{i=1}^{m+1} |S_i|$. The following Lemma then conclude the proof of NP-Hardness.

**Claim 1.** *The size of a minimum vertex cover for $G$ is $k$ iff an optimal schedule for $K$ has value $k+2m+2$. Besides, we can transform any schedule of size $c$ to $K$ into a vertex cover of size $c-2m-2$ in linear time.*

Consider a minimum vertex cover $C$ of $G$ of value $k$. For each $i = 1, ..., m$ and each edge $e_i = (r, s)$ of $G$ with $r < s$, there is a vertex of $C$ taking $r$ or $s$. We define: $u = \max\{w \in$
$\{1, ..., r\} : w \in C\}$ if $\{1, ..., r\} \cap C \neq \emptyset$ and $w = 0'$ otherwise; $v = \min\{w \in \{s, ..., n\} : w \in C\}$ if $\{s, ..., n\} \cap C \neq \emptyset$ and $v = n+1$ otherwise; and $S_i := \{u, v\}$. Observe that either $u = r$ or $v = s$ as $C$ is a vertex cover. We also define $S_{m+1} = \{0', n+1\}$. The sets $S_i$, $i = 1, ..., m+1$ form a feasible schedule for $K$ of cost $2m+2+k$. Vice versa, let us consider an optimal schedule for $K$ of cost $c$. We can assume w.l.o.g. that $S_i$ has cardinality two for each $i = 1, ..., m$ (by the discussion before the claim). But then, as discussed above, for each $i = 1, ..., m$, $S_i$ must contain $r$ or $s$ and thus $C := (\cup_{i=1}^{m+1} S_i) \setminus \{0', n+1\}$ is a vertex cover of $G$. Now $|C| = |(\cup_{i=1}^{m+1} S_i) \setminus \{0', n+1\}| = |\cup_{i=1}^{m+1} S_i| - 2$ (since both $0'$ and $n+1$ are in $\cup_{i=1}^{m+1} S_i$). But $c = |\cup_{i=1}^{m+1} S_i| + \sum_{i=1}^{m+1} |S_i| = |\cup_{i=1}^{m+1} S_i| + 2m$. Hence $|C| = c - 2m - 2$. ■

We now prove that the problem is actually APX-Hard.

We assume here that $G$ is d-regular. Let $k$ be the size of a minimum vertex cover for $G$. Since $G$ is d-regular, we have $k \ge \frac{m}{d}$. By Claim 1, there is a schedule for $K$ of cost $k+2m+2$. Now assume that for any $\epsilon > 0$, we have a polynomial time algorithm for KUP with approximation ratio $1 + \frac{\epsilon}{4(d+2)}$. In this case, we can compute, using $k \ge \frac{m}{d}$, a schedule for $K$ with cost $1 + \frac{\epsilon}{4(d+2)}(k+2m+2) \le (1+\epsilon)k+2m+2$ in polynomial time. Moreover, by Claim 1, we can transform this schedule into a vertex cover for $G$ of size $(1+\epsilon)k$ in linear time. Consequently, this gives us a $(1+\epsilon)$-approximation algorithm for vertex cover, for any $\epsilon > 0$, which contradicts the APX-hardness of vertex cover (it is apparently known for being hard to approximate in d-regular graphs, check the reference). Therefore, KUP is APX-hard as well.

□

## B Two-stage stochastic lookahead model

For all $\omega \in \tilde{\Omega}_t$ and $i \in [m]$, we let $I_i^\omega(\tilde{t})$ be the set of intervals of $i$ that are available at the beginning of period $\tilde{t}$ under scenario $\omega$ (we remark that $I_i^\omega(t) = I_i(t)$ for all $\omega$). We also introduce $\ell_i^\omega(\tilde{t}) = \max\{v : [u, v-1] \in I_i^\omega(\tilde{t})\}$, to be the latest possible update period for $i$ if it is updated at $\tilde{t}$ with an interval from the stock under scenario $\omega$. In the following MILP model, binary variable $y_{it}^\omega$ is equal to one if and only if component $i$ is replaced at period $\tilde{t}$, and $z_{it}^\omega$ is equal to one if and only if a kit update occurs during $\tilde{t}$, under scenario $\omega$. For the sake of readability, the formulation includes the explicit non-anticipativity constraints (4), although only first-stage variables $y_{it}$ and $z_t$ are required in practice to model decisions made at $t$. Constraints (2) ensure that valid components are present in the kit at any time, in any scenario, and a kit update is accounted for when a replacement is made, thanks to Constraints (3).

$$ (2SP(S_t, \tilde{\Omega}_t)) : \quad \min \quad \frac{1}{|\tilde{\Omega}|} \sum_{\omega \in \tilde{\Omega}_t} \sum_{\tilde{t}=t}^{t+\bar{T}} \left[ K_0 z_{\tilde{t}}^{\omega} + \sum_{i=1}^{m} y_{i\tilde{t}}^{\omega} \right] \\ \text{s.t.} \quad \sum_{u:\ell_i^\omega(u)>\tilde{t}} y_{iu}^\omega \ge 1 \quad \forall \tilde{t} \in [t, t+\bar{T}], i: t_i(t) \le \tilde{t}, \omega \in \tilde{\Omega}_t \quad (2) $$

$$ y_{i\tilde{t}}^{\omega} \le z_{\tilde{t}}^{\omega} \quad \forall i \in [m], \tilde{t} \in \{t, \dots, t+\bar{T}\}, \omega \in \tilde{\Omega}_t \quad (3) $$

$$ y_{it} = y_{i\tilde{t}}^{\omega}, z_t = z_{\tilde{t}}^{\omega} \quad \forall i \in [m], \omega \in \tilde{\Omega}_t \quad (4) $$

$y, z$ binary
Solving this approximation of the multistage problem is still numerically challenging. Therefore, our stochastic lookahead policy further relaxes the lookahead problem by dropping the integrality constraints in the second stage, allowing for considering more scenarios and a longer lookahead horizon (in our case study, preliminary experiments indicate that this strategy is beneficial). The policy is defined as $x_t = \{i \in [m] : y_{it}^* = 1\}$, with $y^*$ an optimal solution of $(2SP(t, \tilde{\Omega}_t))$.

**Perfect information model** To obtain the optimal value of the problem under perfect information in scenario $\omega$, one can solve problem $(2SP(S_1^\omega, \{(W_1^\omega, \dots, W_T^\omega)\}))$.

## C Data set

The raw data set from MSF-Log includes the list of components in each kit, the replacement cost of each component, and the observed remaining lifetime of component lots at their entry date in the stock, over a 10-year history. We extract intervals $[\tau_i^-, \tau_i^+]$ containing 90% of the observed lifetime of each component $i$. For a given kit, a random scenario is generated as follows. For each component $i$, the total lifetime in the kit, $\tau_i^0$, is drawn from the uniform distribution $U\{\tau_i^-, \tau_i^+\}$, and the initial latest possible update period for $i$, $t_i^\omega(1)$, is drawn from $U\{0, \tau_i^0\}$. To generate the interval data, we make the observation that lead times are sufficiently small in the MSF-Log practical context to allow for receiving, before the end of $t$, the components ordered at the beginning of month $t$. It leads to virtually considering available intervals as the ones present in the suppliers' stocks. This inspires a random data model that represents the evolution of the supplier stock of each component, which is subject to the supplier's production and other customers' consumption. Thus, the (virtual) stock of a scenario is composed of one interval starting at each period $t \in \{1, \dots, T\}$ for each component, which corresponds to the product lot that the supplier would ship if we placed an order at $t-1$. We further assume that the supplier adopts an earliest-expiration-date-first policy to serve the customers. Suppose that the interval starting at $t$ in stock ends at $v$. Then, the interval starting at $t+1$ ends at $v + \tilde{\delta}$, where $\tilde{\delta}$ is a non-negative random variable which can be interpreted as the number of products (expressed in months of production) the supplier shipped between $t$ and $t+1$. Assuming the independence of all customers' demands and that the supplier's stock is maintained in a steady state, where its production roughly equals the customers' demand in the long run, we choose a Poisson distribution with parameter 1 for $\tilde{\delta}$. This model has the advantage of requiring no other parameter estimation, and the one-sample Kolmogorov-Smirnov test confirms its consistency with the historical data. Under the formalism introduced above, if $[t, v] \in I_i^\omega(t)$, then $W_{t+1}^\omega$ is determined by $\Delta_i^\omega(t+1) := \{[t+1, v+\delta_{it}^\omega]\}$, $i \in [m]$, where $\delta_{it}^\omega$ is drawn from Pois(1). Finally, we remark that $S_1^\omega$ is obtained by generating $I_i^\omega(1)$, $i \in [m]$, which is done by drawing the intervals of $i$ starting from $t = t_i^\omega(1) - \tau_i^0 + 1$ to $t = 0$.

Eleven instances are generated this way from the raw data set, for 11 kits composed of 6 to 95 components each, with 100 stochastic scenarios for each kit. This relatively small number of scenarios turns out to be sufficient to obtain accurate confidence intervals for the stochastic optimality gaps. The planning horizon is fixed to $T = 150$, while the typical component's lifetimes range between $\min_i \tau_i^- = 11$ and $\max_i \tau_i^+ = 120$. The replacement costs $K_i$, $i \in [m]$, are directly taken from historical data. The value $K_0$ is associated with the human workload involved in each kit update. To account for different management strategies, we vary $K_0$ in $\{15, 50, 200, 1000\}$, with $K_0 = 15$ representing purely the estimated wage cost, 50 and 200 taking into account the limited human workforce dedicated to various operations in the warehouse and
1000 as an extreme point of view where the material cost is considered negligible. We remark that this can be considered as the scalarization approach to bi-objective optimization to balance the economic cost restricted to kit updates and the workforce that is not available for other tasks in the company.

D Additional numerical experiments

Figure 2 illustrates the performance profiles of the less computationally heavy policies. Myopic and online policies are explicitly agnostic to the values of $K_i$, $i \in \{0, \dots, m\}$. However, myopic policies are by design oriented towards minimizing the number of component replacements, while the online policy aims at minimizing the number of kit updates without adding too many component replacements. This is reflected in these numerical results, with the myopic policy (with $\alpha \ge 1$) dominating the online policy for the smallest value of $K_0$, while the latter clearly outperforms the former in the other cases.

<figure><img src="image_5.png" /><figcaption>Figure 2: Optimality gaps for all instances with different values of $K_0$. The curve of policy $\pi$ shows the observed probability $\mathbb{P}(F_{W^\omega}^\pi \le x \cdot F_{W^\omega}^*)$.</figcaption></figure>