# A Stochastic Model for a Two-Level Disassembly
Lot-Sizing Problem Under Random Lead Time

Ilhem Slama, Oussama Ben-Ammar, Alexandre Dolgui, Faouzi Masmoudi

► To cite this version:

Ilhem Slama, Oussama Ben-Ammar, Alexandre Dolgui, Faouzi Masmoudi. A Stochastic Model for a Two-Level Disassembly Lot-Sizing Problem Under Random Lead Time. IFIP International Conference on Advances in Production Management Systems (APMS), Aug 2020, Novi Sad, Serbia. pp.275-283, 10.1007/978-3-030-57993-7_32 . hal-02923308

HAL Id: hal-02923308

https://hal.science/hal-02923308

Submitted on 19 Apr 2022

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A stochastic model for a two-level disassembly lot-sizing problem under random lead time

Ilhem Slama<fnref n="1" />, Oussama Ben-Ammar<fnref n="2" />, Alexandre Dolgui<fnref n="1" />, and Faouzi Masmoudi<fnref n="3" />

**Abstract.** The purpose of this research is to propose an optimization method for the stochastic disassembly lot-sizing problem under uncertainty of lead time. One type of end-of-life (EoL) product is disassembled to satisfy a dynamic and known demand of items over a planning horizon. The tactical problem is considered as a random optimization problem in order to minimize the expected total cost. A sample average approximation (SAA) approach, is developed to model the studied random optimization problem and minimize the average total cost. The effectiveness of the solution approach has successfully tested and proved.

**Keywords:** Disassembly lot-sizing · Random lead time · Stochastic programming · Monte Carlo simulation.

## 1 Introduction

Managing uncertainty is becoming one of the most important challenges in optimizing the disassembly process. Uncertainty leads to several difficulties in production planning and inventory management. The sources of uncertainty are diverse and can be found at several levels of the disassembly process: variability of demand, probabilistic recovery rates of items, delivery times, quality problems, etc. In this paper we consider the situation where demand on items/parts must be satisfied from the disassembly of EoL products. According to the classification proposed by [2], the studied problem enters into the classification of disassembly lot sizing problem (DLS) problem that consists in finding when and how much EoL products to disassemble to meet demand for the items while minimizing the costs associated with the disassembly system.

Without trying to do an exhaustive review of the literature, we highlight the works on DLS problem under uncertainty. The stochastic literature review

<footnote n="1">¹ IMT Atlantique, LS2N-CNRS, La Chantrerie, 4 rue Alfred Kastler - B.P. 20722, 44307 Nantes, France
{ilhem.slama,alexandre.dolgui}@imt-atlantique.fr</footnote>

<footnote n="2">² Department of Manufacturing Sciences and Logistics, Mines Saint-Etienne, University Clermont Auvergne, CNRS, UMR 6158 LIMOS CMP, Gardanne, France
oussama.ben-ammar@emse.fr</footnote>

<footnote n="3">³ Engineering School of Sfax, Laboratory of Mechanic, Modeling and Production (LA2MP), University of Sfax, Tunisia
masmoudi.fawzi@gmail.com</footnote>
can be split into four different cases: (i) the uncertainty of demand [1,5], (ii) the uncertainty of disassembly yield (see for example the paper of [4,3]), (iii) the uncertainty of yield and demand [7] and (iv) the uncertainty of disassembly lead time (DLT) [9,10]. This latter can be defined as the time difference between placing a disassembly order and receiving the disassembled items. The DLT is crucial parameter in disassembly planning. However, their variability strongly affect the disassembly system efficiency and it can affect the customer orders with a random availability of disassembled items. Managing disassembly opera- tion under uncertainty of DLT is very challenging in practice. Indeed, when an EOL product is disassembled, it is fundamental to ensure that it is the right model to be supplied under uncertain DLT in order to manage disassembly and delivery process. In order to position our research in the existing literature, we will only review in detail the previous works on the stochastic DLS problem un- der uncertainty of DLT. Only two papers populated this category. The paper of [9] is the first to treat this problem type. The case of two-level disassembly sys- tem is studied under unlimited disassembly capacity. The problem is formulated as a minimization problem and then converted to a Monte Carlo-mixed integer programming model. The Model is used to determine the optimal quantity for EoL products in order to minimize the average total cost over the planning hori- zon. Recently, [10] proposed a generalization of the discrete Newsboy formulae to find the optimal release date when the disassembly lead time of the EoL product is random variable. This study deals with a single-period disassembly to-order problem with known and fixed demand for components, when the disassembly capacity is unlimited.

To close to real industrial planning approach, the capacity restriction on dis-
assembly resources is an important consideration. As for approach, a sample
average formulation is necessary to approximate the expected objective value.
This paper is a continuation of our previous preliminary work [9]. The contribu-
tions of this study are as follow:

1. The problem is extended to a capacitated disassembly lot sizing (CDLS) problem and formulated as a minimization problem and converted to a Monte Carlo-Mixed-Integer Programming model (MC-MIP);

2. The sample average approximation algorithm based on Monte Carlo (MC) optimization approach is proposed.

In this article, we study the case of a two-level disassembly system with a lot-
sizing policy. The disassembled item requests are known and must be delivered
on predefined delivery dates. To meet the items requirements, a quantity of EoL
product Zt is ordered at the period t. Once the disassembly order is released, a
random real Lt is found in that period and the disassembled items are received
at period t' = t + Lt. Note that, a setup cost is generated if any disassembly
operation is released in period t. The DLT at each period are independent ran-
dom random discrete variables with known probability distributions and varying
between L- and L+. The randomness of the lead time is a classic problem for
industrial companies. If the date of recovery of an item during the disassembly
of the EoL product is lower than its planned delivery time, this item will be stored until this date. This situation usually occur in companies and generates holding costs. In the same manner, if an item is not received in time, a backlog- ing cost is incurred for it. Regarding the capacity, the disassembly quantity is limited by a certain capacity time in each period over the planning horizon. The rest of this paper is organized as follows. In section 2, the proposed stochastic programming model of the CDLS problem is described. MC optimization ap- proach is presented in section 3. Section 4 reports some preliminary results. Our conclusions are drawn in the final section.

## 2 Problem Formulation

To solve the studied problem under random lead time, a stochastic MIP is pro- posed to minimize the expected total cost ($E(TC)$). The list of notations used in this paper is given in Table 1:

<table><caption>Table 1: Notation.</caption><thead><tr><th colspan="2">Parameters</th></tr></thead><tbody><tr><td>T</td><td>Set of time periods of the planning horizon</td></tr><tr><td>N</td><td>Set of items</td></tr><tr><td>Ω</td><td>Set of possible scenarios</td></tr><tr><td>t</td><td>Index of period t, t ∈ T</td></tr><tr><td>i</td><td>Index of item i, i ∈ N</td></tr><tr><td>ω</td><td>Index of scenario ω, ω ∈ Ω</td></tr><tr><td>R<sub>i</sub></td><td>Number of units of i obtained from disassembling the EoL product</td></tr><tr><td>D<sub>i,t</sub></td><td>External demand for item i in period t</td></tr><tr><td>I<sub>i,0</sub></td><td>Starting inventory of item i</td></tr><tr><td>L<sup>ω</sup><sub>t</sub></td><td>Random disassembly lead time in period t under scenario ω</td></tr><tr><td>h<sub>i</sub></td><td>Per-period inventory holding cost of one unit of item i</td></tr><tr><td>s<sub>t</sub></td><td>Per-period setup cost in period t</td></tr><tr><td>b<sub>i</sub></td><td>Per-period backlogging cost of one unit of item i</td></tr><tr><td>G</td><td>Disassembly operation time</td></tr><tr><td>C<sub>t</sub></td><td>Available capacity in period t</td></tr><tr><td>M</td><td>A large number</td></tr></tbody></table><table><thead><tr><th colspan="2">Functions</th></tr></thead><tbody><tr><td>E(.)</td><td>Expected value</td></tr><tr><td>p<sub>ω</sub></td><td>Probability distribution for scenario ω, Σ<sub>ω∈Ω</sub> p<sub>ω</sub> = 1</td></tr></tbody></table><table><thead><tr><th colspan="2">Decision variable</th></tr></thead><tbody><tr><td>Z<sub>t</sub></td><td>Disassembly quantity ordered in period t</td></tr><tr><td>Y<sub>t</sub></td><td>Binary indicator of disassembly in period t</td></tr><tr><td>H<sup>ω</sup><sub>i,t</sub></td><td>Inventory level of item i at period t under scenario ω</td></tr><tr><td>B<sup>ω</sup><sub>i,t</sub></td><td>Backordered quantity of item i at period t under scenario ω</td></tr></tbody></table>
We note that the total number of scenarios is $|\Omega| = \prod_{t \in T}(L^+ - L^- + 1)$. Thus, $\mathbb{E}(TC)$ can be calculated by considering all possible values of $L_t^\omega$ and the objective function, expressed in Eq. (1), can be modeled as follows:

$$ \min \mathbb{E}(TC) = \sum_{t \in T} \left( \sum_{\forall i \in \mathcal{N}} \sum_{\omega \in \Omega} \frac{1}{|\Omega|} \left( h_i \cdot H_{i,t}^{\omega} + b_i \cdot B_{i,t}^{\omega} \right) + s_t \cdot Y_t \right) \quad (1) $$

Eq. (2) defines the inventory balance for each item $i$ at the end in each period $t$ under scenario $\omega$:

$$ I_{i,t}^{\omega} = H_{i,t}^{\omega} - B_{i,t}^{\omega} \quad \forall i \in \mathcal{N}, \forall t \in T, \forall \omega \in \Omega \quad (2) $$

where

$$ I_{i,t}^{\omega} = I_{i,0} + \sum_{\tau=1}^{t-L_{\tau}^{\omega}} R_{i} \cdot Z_{\tau} - \sum_{\tau=1}^{t} D_{i,\tau} $$

Constraints (3) represents the modeling constraint for disassembly indicator of the EOL product in period $t$:

$$ Z_t \le Y_t \cdot M \quad \forall t \in T \quad (3) $$

Constraints (4) represents the capacity constraint in each period $t$:

$$ G \cdot Z_t \le C_t \quad \forall t \in T \quad (4) $$

Constraints (5 to 7) provides the conditions on the decision variables:

$$ Z_t \ge 0 \quad \forall t \in T \quad (5) $$

$$ H_{i,t}^{\omega}, B_{i,t}^{\omega} \ge 0 \quad \forall i \in \mathcal{N}, \forall t \in T, \forall \omega \in \Omega \quad (6) $$

$$ Y_t \in \{0, 1\} \quad \forall t \in T \quad (7) $$

The complexity of the problem may increase exponentially if a large set of $|\Omega|$ is considered to represent the stochastic DLT and the resolution of (1) to (7) becomes impossible. The total cost can be estimated by an empirical average ($\bar{TC}$) by using: Monte Carlo (MC) simulation. It can provide an estimate of the criterion that converge to $\mathbb{E}(TC)$ calculated by the stochastic MIP.

**Proposition 1.** The MIP model can be converted to the following MC-MIP model:

$$ \bar{TC} = \sum_{\forall t \in T} \left( \sum_{\forall i \in \mathcal{N}} \sum_{\omega \in \vartheta} \frac{1}{K} \left( h_i \cdot H_{i,t}^{\omega} + b_i \cdot B_{i,t}^{\omega} \right) + s_t \cdot Y_t \right) \quad (8) $$

$$ I_{i,t}^{\omega} = H_{i,t}^{\omega} - B_{i,t}^{\omega} \quad \forall i \in \mathcal{N}, \forall t \in T, \forall \omega \in K \quad (9) $$

$$ H_{i,t}^{\omega}, B_{i,t}^{\omega} \ge 0 \quad \forall i \in \mathcal{N}, \forall t \in T, \forall \omega \in K \quad (10) $$

subject to (2), (3), (4), (5) and (7).
*Proof.* The MC-MIP is implemented with the following steps:

- Step 1: $\forall t \in \mathcal{T}$, generate the random samples for $L_t^\omega$ for $\omega \in \vartheta$ where $\vartheta$ is a set of random samples such that $\vartheta \subset \Omega$ and $|\vartheta| = K$,

- Step 2: Each expected inventory level, noted by $\mathbb{E}(I_{i,t})$, is estimated by $\bar{I}_{i,t}$.

Of particular interest is to study the Monte Carlo optimal solution convergence, we describe in the next section the convergence provided by the SAA algorithm based on MC optimization approach.

## 3 “Exact” Monte Carlo Optimization Method

In this section we present an almost exact method to solve the stochastic problem, referred to as the true optimization problem using MC-MIP. This approach is also known as the stochastic counterpart or the sample path method [8]. The evidence from this study points towards the idea incorporates an optimal algorithm to solve the problem under a large set of samples [6]. Thus, the excepted total cost developed in Eq. (1) can be approximated by SAA based on MC optimization steps:

- Step 1: Solve the MC-MIP model: Let $X^*$ be the optimal solution and $\bar{TC}^*$ the obtained optimal average cost,

- Step 2: $\forall t \in \mathcal{T}$, generate $\mathcal{B}$ large random samples of $L_t: L_t^1, \dots, L_t^B$ $|\omega \in \mathcal{B}|$,

- Step 3: Evaluate the “Exact” optimal cost $\hat{TC}_B$ of the optimal solution $X^*$, using Eq. (11):

$$ \hat{TC}_B = \sum_{\forall t \in \mathcal{T}} \left( \sum_{\forall i \in \mathcal{N}} \sum_{\omega \in \mathcal{B}} \frac{1}{\mathcal{B}} \left( h_i \cdot H_{i,t}^\omega + b_i \cdot B_{i,t}^\omega \right) + s_t \cdot Y_t \right) \quad (11) $$

subject to (9), (4) and (10).

*Remark 1.* According to [6], “By the law of large numbers, $\bar{I}_{i,t}$ (respectively $\bar{TC}$) converges with probability 1 to $\mathbb{E}(I_{i,t})$ (respectively $\mathbb{E}(TC))$ as $K$ increases”.

## 4 Computational Experiments and Result

In order to investigate the speed convergence of the solution provided by the MC optimization, this section presents numerical results that prove our findings. All approaches were solved using optimization software for small instances. All formulations are implemented in C using Concert Technology and are solved by IBM CPLEX 12.4 on a PC with processor Intel (R) Core™ i7-5500 CPU @ 2.4 GHz and 8 Go RAM under Windows 10 Professional.

We considered a finite planning horizon with 5 periods and a disassembly system with 3 items (See Fig. 1). The number in parentheses represents the number of items obtained from the EoL product. The number of scenarios $K$
takes a value in [2, 10, 30, 50, 150, 200, 400, 600, 1000]. For each K, we performed 100 independent runs of the MC-MIP to provide 100 optimal solutions X* and the related average costs. The “exact” cost of each X* was evaluated using a big number of scenarios (10⁵ samples), i.e., $\bar{T}C_B \approx E(TC)$ with $B=10^5$ (See [6]). To obtain $E(TC)$, the stochastic MIP was solved with $|\Omega| = 3125$ scenarios and the $E(TC)$ takes a value equal to 70955 (see Fig. 2).

The tests are carried out under the parameter costs listed in Table 2. The inventory and backlogging costs of one unit of item i are 3 and 87, respectively. Starting inventory for each item is assumed to be zero. We note that the capacity is 180 for all periods.

<figure><img src="image_2.png" /><figcaption>Fig. 1: A two-level disassembly system.</figcaption></figure>

<caption>Table 2: Characteristics of the data set.</caption>

(a) Demands and setup costs.

<table><thead><tr><th>Period</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th></tr></thead><tbody><tr><td>Demand A1</td><td>17</td><td>28</td><td>34</td><td>15</td><td>9</td></tr><tr><td>Demand A2</td><td>56</td><td>25</td><td>0</td><td>76</td><td>12</td></tr><tr><td>Demand A3</td><td>12</td><td>58</td><td>74</td><td>13</td><td>69</td></tr><tr><td>s<sub>t</sub></td><td>100</td><td>0</td><td>200</td><td>100</td><td>300</td></tr></tbody></table>

(b) Disassembly lead time probability distribution.

<table><thead><tr><th>ω</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th></tr></thead><tbody><tr><td>Pr(L<sub>t</sub> = ω)</td><td>0.245</td><td>0.48</td><td>0.255</td><td>0.01</td><td>0.01</td></tr></tbody></table>

Let us now compare the convergence of $\bar{T}C$. Fig. 2 shows that $\bar{T}C_B$ decreases when K is increasing. The findings of this study support the idea that $\bar{T}C$ converges to the optimal solution $E(TC)$ and is quite robust if a large number of samples is used, for example if $K \ge 200$. Our work has led us to conclude that our proposed optimization method can provide the convergence of the solution to the optimal one as the set of scenarios increases.
<figure><img src="image_3.png" /><figcaption>Fig. 2: Convergence cost.</figcaption></figure>

As expected, our experiments show that for $K = 10^3$, the MC-MIP approach can generate a good approximate solution for the stochastic problem. As previously noted, we realized 100 independent runs of the same data set of the MC-MIP with $10^3$ scenarios. Then, 100 optimal estimated solutions are obtained ($Sol_{1000}$). Among these solution, the Best Known Solution (BKS) is selected.

As Fig. 3 witnesses, the results founded are stable and the average gap from BKS is no more than 4% for all runs.

# 5 Conclusion

In this work, we studied a stochastic CDLS problem with several items disassembled from one type of EoL. We assumed that the items-demand is known. The DLT are an independent random variables whose probability distribution is known and bounded. The combination of MC-MIP approach has been developed. A SAA based on MC optimization provides almost optimal solutions using a modest number of scenarios in order to minimize the average total cost. Our model can easily be implemented in practice to define the DLT in a disassembly planning and control system. Our experiments show clear that the average total cost can be tends to the expected one as the number of scenarios increases. The stability of the proposed model is also verified. In the future, we will try to treat the randomness of demand and/or disassembly yield in the study of the multi-level disassembly systems and multi type EOL products.
<figure><img src="image_4.png" /><figcaption>Fig. 3: Validation of MC simulation approach.</figcaption></figure>

References

1. Barba-Gutiérrez, Y., Adenso-Díaz, B.: Reverse MRP under uncertain and imprecise demand. The International Journal of Advanced Manufacturing Technology 40(3-4), 413–424 (2009)

2. Ilgin, M.A., Gupta, S.M.: Environmentally conscious manufacturing and product recovery (ecmpro): A review of the state of the art. Journal of environmental management 91(3), 563–591 (2010)

3. Inderfurth, K., Langella, I.M.: Heuristics for solving disassemble-to-order problems with stochastic yields. OR Spectrum 28(1), 73–99 (2006)

4. Inderfurth, K., Vogelgesang, S., Langella, I.M.: How yield process misspecification affects the solution of disassemble-to-order problems. International Journal of Production Economics 169, 56–67 (2015)

5. Kim, H.J., Xirouchakis, P.: Capacitated disassembly scheduling with random demand. International Journal of Production Research 48(23), 7177–7194 (2010)

6. Lamiri, M., Xie, X., Dolgui, A., Grimaud, F.: A stochastic model for operating room planning with elective and emergency demand for surgery. European Journal of Operational Research 185(3), 1026–1037 (2008)

7. Liu, K., Zhang, Z.H.: Capacitated disassembly scheduling under stochastic yield and demand. European Journal of Operational Research 269(1), 244–257 (2018)

8. Ruszczyński, A., Shapiro, A.: Stochastic programming models. Handbooks in operations research and management science 10, 1–64 (2003)

9. Slama, I., Ben-Ammar, O., Masmoudi, F., Dolgui, A.: Scenario-based stochastic linear programming model for multi-period disassembly lot-sizing problems under random lead time. IFAC-PapersOnLine 52(13), 595–600 (2019)

10. Slama, I., Ben-Ammar, O., Dolgui, A., Masmoudi, F.: Newsboy problem with two-level disassembly system and stochastic lead time. ROADEF (2020)