# Reducing the Research Space of Possible Order Release Dates for Multi-level Assembly Systems under Stochastic Lead Times

Oussama Ben-Ammar, Alexandre Dolgui, Hélène Marian, Dash Wu

► To cite this version:

Oussama Ben-Ammar, Alexandre Dolgui, Hélène Marian, Dash Wu. Reducing the Research Space of Possible Order Release Dates for Multi-level Assembly Systems under Stochastic Lead Times. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2014, Ajaccio, France. pp.368-374, 10.1007/978-3-662-44733-8_46. emse-01061104

HAL Id: emse-01061104

https://hal-emse.ccsd.cnrs.fr/emse-01061104

Submitted on 25 Oct 2016

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
Reducing the research space of possible order release
dates for multi-level assembly systems under stochastic
lead times

Oussama Ben Ammar¹, Hélène Marian¹, Alexandre Dolgui¹, Dash Wu²

¹ École Nationale Supérieure des Mines, EMSE-FAYOL, CNRS UMR6158, LIMOS, F-42023, Saint-Étienne, France
{obenammar, marian, dolgui}@emse.fr

² University of Toronto, Canada
dwu@fields.utoronto.ca

**Abstract.** This paper proposes tools which will be used to optimize multi-level assembly under lead time uncertainty. One type of finished products and several types of components are considered. We suppose that each component has a fixed unit inventory cost and the finished product has backlogging and inventory holding costs per unit of time. The lead times of components are discrete random variables, and the customer's demand of the finished product is known. A reduced space of research is presented to strengthen optimization methods which have been applied for minimizing the sum of the average inventory holding cost for components and the average backlogging and inventory holding costs for the finished product.

**Keywords:** Stochastic lead times, multi-level assembly system, reduced space of research.

# 1 Introduction and related publications

For assembly systems, the lead times of components may be an uncer-
tain parameter; it is rarely deterministic and mostly has a variable val-
ue. This unpredictability may be caused by technical problems such as
machines breakdowns, limited capacity, delay of transport, etc.

Various techniques such as safety stocks and safety lead times are used
by planners in order to lead the better anticipation of lead time uncer-
tainties. For example Koh and Saad (2006) specified that the safety lead
time can be used to handle uncertainties in supply chain, such as late
delivery. Molinder (1997) showed that both the uncertainty of the lead
time and demand variability involve the level of optimal safety lead times and optimal safety stocks.

Dolgui et al. (2008) studied the MRP parameterization problem for two-level assembly systems with random component procurement times. They explained that lead time uncertainties seem to be insuffi- ciently studied for a long time, favouring the study of demand uncer- tainties.

In the literature few researchers have studied lead time variability for assembly systems. Ould Louly and Dolgui (2002), Dolgui et al. (2009), and Ould Louly et al. (2008a) proposed a discrete Newsboy model for one-level assembly systems to minimize the average inventory holding cost for components while maintaining a high customer service level for the finished product. The same problem was solved by a Branch and Bound procedure in Ould Louly and al (2008b).

Hnaien et al. (2009) and Fallah-Jamshidi et al. (2011) modelled and optimized two-level assembly systems, in particular for a fixed de- mand, a known due date and an unlimited capacity. The same problem, but for multi-level assembly systems, is studied by Ben Ammar et al. (2012) and Ben Ammar et al. (2013a). Authors proposed analytical and simulation models to calculate the expected value of the cost which is the sum of the average component holding cost and the average fin- ished product backlogging and holding costs. To minimize this ex- pected cost, the proposed models are coupled with a GA which Hnaien et al. (2009) used in their studies. The same problem was solved by a Branch and Bound approach (Ben Ammar et al., 2013b). However, a reduction of the search space seems be necessary to improve these re- sults.

A multi-level assembly system with stochastic lead times at each level is studied in this paper. It continues the work of Ben Ammar et al., (2013a). We propose a reduced space of research which depends on finished product costs.

The rest of paper is organized into five sections. Firstly, we describe the problem (section 2). The initial space of research is given in section 3. Some results are shown in section 4. Finally, we outline the work done in the conclusion and give some perspectives of future research.
## 2 Problem description

To get closer to the industrial methods of planning, we consider a discrete temporal environment. The Figure 1 shows that the finished product is produced from components themselves obtained from other components. We limit our study into a single period. We assume that both the due date *T* and the demand for the finished product are deterministic and known. A unit backlogging cost and a unit inventory holding cost for the finished product, and a unit inventory cost for each component are considered. Actual lead times are modelled as independent random discrete variables with known probability distributions.

<figure><img src="image_2.png" /><figcaption>Fig. 1. A multi-level assembly system</figcaption></figure>

In this model, the MRP system is considered as a push-system. Thus, for each level, when all the necessary components are available, level *m* delivers the components to level *m* − 1 with a random discrete lead time. When the semi-finished product arrives at the final level (level 0), it undergoes the necessary operations and afterwards the finished product is delivered to the customer in order to satisfy the demand. It is assumed that each component of level *m* is used to assemble only one type of component at level *m* − 1.

The objective is to find the order release dates for components at level *m* which minimize the expected value of the total cost (it is given in Ben Ammar et al. (2013b)) which equals to the sum of the inventory
holding cost for components and the backlogging and inventory hold-
ing costs for the finished product (see the example in Figure 2).

<figure><img src="image_3.png" /><figcaption>Fig. 2. A three-level assembly system</figcaption></figure>

3 Reduced space of research

Let $u_{i,l}$ the maximum value of $L_{i,l}$ and $U_{i,m}$ the longest time between the release date for component $c_{i,m}$ and $T$. Each $L_{i,l}$ varies in $[1, u_{i,l}]$ and each order release date $X_{i,m}$ varies in $[T - U_{i,m}, T - m]$.

The idea is to reduce this search space of all feasible solutions. That is
why we rely on the property related to the distribution of lead times.
For this we decompose the multi-level assembly system (Figure 1) to
$N_m$ (the number of components at level $m$) multi-level linear supply
chains (Figure 3). Each linear chain is composed of $m$ components and
delivers a finished product on a specified delivery date.

Let $c_{i,m}$ a component at level $m$ whose lead time is equal to $L_{i,m}$.
This component is necessary to make the component $c_{i,m-1}$ (its lead
time is equal to $L_{i,m-1}$) ; itself compound the component $c_{i,m-2}$
etc. The availability date of the product of this linear chain is equal to $\psi_{i,m} = L + X_{i,m,m}$ with $L = L_{i_1,1} + L_{i_2,2} + \cdots + L_{i_{m-1},m-1} + L_{i_m,m}$.

<figure><img src="image_4.png" /><figcaption>Fig. 3. Decomposition of the assembly system to several multi-level linear chains</figcaption></figure>

Let $b$ the unit backlogging cost for the finished product and $r$ the inventory holding cost for the finished product. For each linear chain:

- The total expected cost $E[X_{j,m}]$, which is equal to the sum of $b$ and $r$, can be deduced from the proposition (2) in Hnaien et al. (2008) by changing the unit inventory holding cost at level 1 by the unit inventory holding cost for the finished product.

- The optimal solution $X_{j,m}^*$ which minimizes $E[X_{j,m}]$ is also given in proposition (3) in Hnaien et al. (2008). It satisfies the optimality condition for the discrete Newsboy model, where the cumulative distribution function $F(\cdot)$ of the total lead time $L$ is used:

$$F(T - X_{j,m}^* - 1) \le \frac{b}{b+r} \le F(T - X_{j,m}^*) \quad (1)$$

For each order release date $X_{j,m}$ for component $c_{j,m}$ in the assembly system, $X_{j,m}^*$ can be the upper limit and the initial research space of possible solutions $[T - U_{j,m}, T - m]$ can be reduced to $[T - U_{j,m}, X_{j,m}^*]$. By contradiction, it can be easily proven. The complete proof will be published soon.
## 4 Experimental results

We study the example mentioned in Figure 2 with $m = 3, N_3 = 3, N_2 = 2, u_{i,j} = 5, b = 1500, r = 150$ and $T = 15$. The probability distribution of lead time of each component is given in the table 1.

<table><caption>Table 1. The probability distributions of the lead times for all components.</caption><thead><tr><th>w</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th></tr></thead><tbody><tr><td>P[L<sub>1,1</sub> = w]</td><td>0.4</td><td>0.3</td><td>0.1</td><td>0.1</td><td>0.1</td></tr><tr><td>P[L<sub>2,1</sub> = w]</td><td>0.7</td><td>0.2</td><td>0.05</td><td>0.04</td><td>0.01</td></tr><tr><td>P[L<sub>1,2</sub> = w]</td><td>0.5</td><td>0.3</td><td>0.1</td><td>0.05</td><td>0.05</td></tr><tr><td>P[L<sub>2,2</sub> = w]</td><td>0.7</td><td>0.2</td><td>0.05</td><td>0.04</td><td>0.01</td></tr><tr><td>P[L<sub>1,3</sub> = w]</td><td>0.09</td><td>0.01</td><td>0.1</td><td>0.35</td><td>0.45</td></tr><tr><td>P[L<sub>2,3</sub> = w]</td><td>0.01</td><td>0.1</td><td>0.6</td><td>0.2</td><td>0.09</td></tr><tr><td>P[L<sub>3,3</sub> = w]</td><td>0.8</td><td>0.1</td><td>0.05</td><td>0.03</td><td>0.02</td></tr></tbody></table>

We decompose the three-level assembly system to 3 (the number of components at level 3) three-level linear supply chains. Thus, we obtain the cumulative distribution function of L which is as follows:

$$ \bullet c_{1.3} \rightarrow c_{1.2} \rightarrow c_{1.1} \rightarrow FP_1 $$

F(3)=0.018; F(4)=0.0443; F(5)=0.0832; F(6)=0.1937; F(7)=0.40875; F(8)=0.6129; F(9)=0.7543; **F(10)**=**0.86365**; **F(11)**=**0.94345**; F(12)=0.9785; F(13)=0.9915; F(14)=0.99775; F(15)=1.

$$ \bullet c_{2.3} \rightarrow c_{1.2} \rightarrow c_{1.1} \rightarrow FP_2 $$

F(3)=0.002; F(4)=0.0247; F(5)=0.1735; F(6)=0.3948; F(7)=0.58905; F(8)=0.74045; **F(9)**=**0.86385**; **F(10)**=**0.93865**; F(11)=0.97495; F(12)=0.99085; F(13)=0.99765; F(14)=0.99955; F(15)=1.

$$ \bullet c_{3.3} \rightarrow c_{2.2} \rightarrow c_{2.1} \rightarrow FP_3 $$

F(3)=0.084; F(4)=0.2865; F(5)=0.48175; F(6)=0.65045; **F(7)**=**0.841525**; **F(8)**=**0.927**; F(9)=0.966055; F(10)=0.987505; F(11)=0.99658; F(12)=0.998965; F(13)=0.99971; F(14)=0.99996; F(15)=1.

The optimal release date $X_{1,3}^*$ for the first linear supply chain $c_{1.3} \rightarrow c_{1.2} \rightarrow c_{1.1} \rightarrow FP_1$ is given by the expression (1):

$$ F(10) \leq F(15 - X_{1,3}^* - 1) \leq 0,909091 \leq F(T - X_{1,3}^*) \leq F(11) $$
The optimal release date $X_{1,3}^*$ is equal to 4. It is the upper limit for the order release date $X_{1,3}$ for component $c_{1,3}$ in the assembly system. The initial research space of possible solutions [0, 12] can be reduced to [0, 4]. $X_{2,3}^*$ and $X_{3,3}^*$ are determined in the same way and are equal to 5 and 7.

For each component, the upper limit $\sigma(X_{j,3}^*)$ of the initial research space $i$ is equal to 12 ($T - m$). Then, the cardinal of the initial space of research is thus equal to $13^3 ((T - m + 1)^{Nm})$ solutions. The cardinal of the reduced space of research is equal to $210 (5 \times 6 \times 7)$ and is reduced the initial space by 90%.

To study the influence of costs, we fix $r$ to 10 and vary $b$. Table 2 gives the upper limits of the reduced space of research.

<table><caption>**Table 2.** Upper bounds of the reduced space of research in function of inventory holding cost</caption><thead><tr><th>b</th><th>1</th><th>10</th><th>10<sup>2</sup></th><th>10<sup>3</sup></th><th>10<sup>4</sup></th><th>10<sup>5</sup></th></tr></thead><tbody><tr><th>σ(X<sub>1,3</sub><sup>*</sup>)</th><td>9</td><td>7</td><td>4</td><td>2</td><td>1</td><td>0</td></tr><tr><th>σ(X<sub>2,3</sub><sup>*</sup>)</th><td>10</td><td>8</td><td>5</td><td>3</td><td>1</td><td>0</td></tr><tr><th>σ(X<sub>3,3</sub><sup>*</sup>)</th><td>11</td><td>9</td><td>7</td><td>4</td><td>2</td><td>0</td></tr></tbody></table>

Note that the backlogging cost for the finished product influences the cardinality of the space of research. For a fixed inventory holding cost, an increase of backlogging cost decreases significantly the cardinality of the space of research. In other words, we should order as soon as possible when the backlogging cost increases.

# 5 Conclusions

This paper deals with the reducing of the research space of order release dates of components which compound a multi-level assembly system under a fixed demand and uncertain lead times for components.

The reduced space of research will be used to choose the appropriate method to optimize multi-level assembly systems. For example, Local Search or a Branch and Bound method may be sufficient when the backlogging cost much greater than the inventory holding cost. For other cases, Genetic Algorithms coupled with others heuristics may optimize this problem.
Our future work will focus on the analysis of the correlation between
different costs and the number of components in the level *m* of the no-
menclature to choose the appropriate method to minimize the expected
cost.

References

1. Ben Ammar O., Marian H., Dolgui A. (2013a), *Optimization for supply planning in multi-level assembly systems with stochastic lead-times*. 5th International Conference on Industrial Engineering and System Management (IESM'13). Morocco, October 28-30, 10p.

2. Ben Ammar O., Marian H., Wu D., Dolgui A. (2013b), *Mathematical Model for Supply Planning of Multi-level Assembly Systems with Stochastic Lead Times*. Invited keynote paper for a special session, Proceedings of the IFAC Conference on Manufacturing Modeling, Management and Control (MIM'2013), St Petersburg, Russia, June 19-21, 2013, N. Bakhtadze, A. Dolgui, V. Lototsky (Eds.), Elsevier Science, 2013, IFAC-PapersOnline.net (ISSN 1474-6670), 6 pages.

3. Ben Ammar O., Marian H., Dolgui A. (2012), *Configuration d'un système d'assemblage multi-niveau sous incertitudes des délais d'approvisionnement*. 9th International Conference on Modeling, Optimization and SIMulation (MOSIM'12). Bordeaux (France), June 6-8, 2012. 10 pages.

4. Dolgui, A. and Prodhon, C. (2007), Supply planning under uncertainties in MRP environ-
ments: A state of the art. *Annual Reviews in Control*, 31:269-279.

5. Dolgui, A., Hnaien, F., Ould Louly, M., and Marian. H. (2008). Parameterization of MRP for supply planning under uncertainties of lead times. In (Ed.). V. K., editor. Supply Chain. p. 247–262. ISBN 978-3-902613-22-6. I-Tech Education and Publishing.

6. Koh, S., and Saad, S. (2006), Managing uncertainty in ERP-controlled manufacturing environments in SMES. *International Journal of Production Economics*. 101(1):109-127.

7. Hnaien, F., Dolgui, A., and Ould Louly, M. (2008). Planned lead time optimization in material requirement planning environment for multilevel production systems. *Journal of Systems Science and Systems Engineering*, 17(2):132–155.

8. Hnaien, F., Delorme, X., and Dolgui, A. (2009). Genetic algorithm for supply planning in two-level assembly systems with random lead times. *Engineering Applications of Artificial Intelligence*, 22:906–915.

9. Fallah-Jamshidi, S., Karimi, N., and Zandieh, M. (2011), A hybrid multi-objective genetic algorithm for planning order release date in two-level assembly system with random lead times. *Expert Systems with Applications*.

10. Molinder. A. (1997), Joint optimisation of lot-sizes. Safety stocks and safety lead times in an MRP system. *International Journal of Production Research*. 35:983–994.

11. Ould Louly, M. and Dolgui, A. (2002), Generalized newsboy model to compute the optimal planned lead times in assembly systems. *International Journal of Production Research*, 40(17):4401–4414.

12. Ould Louly, M., Dolgui, A., and Hnaien, F. (2008a), Supply planning for single-level as-
sembly system with stochastic component delivery times and service level constraint. *International Journal of Production Economics*, 115(1):236–247.

13. Ould Louly, M., Dolgui, A., and Hnaien, F. (2008b), Optimal supply planning in MRP en-
vironments for assembly systems with random component procurement times. *International Journal of Production Research*, 46(19):5441–5467.