# Key performance indicators for supply planning of multilevel serial systems with stochastic lead times

Faicel Hnaien, Alexandre Dolgui, Mohamed-Aly Louly

► To cite this version:

Faicel Hnaien, Alexandre Dolgui, Mohamed-Aly Louly. Key performance indicators for supply planning of multilevel serial systems with stochastic lead times. Control and Cybernetics, 2010, 39 (1), pp.133-148. emse-00673976

HAL Id: emse-00673976

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

Submitted on 9 Jun 2021

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
# Key Performance Indicators for Supply Planning of Multilevel Serial Systems with Stochastic Lead Times

by

**Faicel Hnaien**<sup>1</sup>, **Alexandre Dolgui**<sup>1,*</sup> and **Mohamed Aly O. Louly**<sup>2</sup>

<sup>1</sup>Ecole des Mines de Saint Etienne

Centre for Industrial Engineering and Computer Science
158 cours Fauriel, F-42023 Saint Etienne Cedex 2, France

<sup>2</sup>King Saud University

College of Engineering - Industrial Engineering Department
P.O.B 800, Riyadh 11421, Kingdom of Saudi Arabia

**Abstract:** This paper examines a supply planning problem for multilevel serial production systems under lead time uncertainties. The techniques used in industry are often based on the assumption that the lead times are known. However, in a supply chain the lead times are often random variables. Therefore, it is necessary to evaluate the influence of the planned lead times on the total cost. An exact performance evaluation technique is developed to calculate the total cost as a function of the planned lead times when the actual lead times are random discrete variables. The sum of the average component holding and tardiness costs at each level, plus the average finished product backlogging cost is considered. Several properties of this function are proven. A numerical example is reported.

**Keywords:** Multilevel Serial Systems, Random Lead Times, Performance Evaluation, Newsboy Model, Generalizations.

## 1. Introduction

Uncertainty in lead times (or delivery times from an external supplier) is a major problem in production systems. These times vary due to many factors, including machine breakdowns, transport delays, poor quality, etc. A late

<footnote>* Corresponding author: dolgui@emse.fr</footnote>
component may delay all subsequent level processes and too early availability engenders overstocking. The effects of lead time uncertainty are particularly problematic in multilevel production systems (see Bullwhip effect, Chen et al., 2000). To minimize the influence of these random lead times, firms can implement safety lead times. The safety lead time is defined as the difference between the planned and expected lead times. Nevertheless, excess the safety lead times creates stocks and stocks are expensive. Therefore, the problem is to optimize stock at each level by assigning adequate values of planned lead times.

In this paper, the planned lead time analysis is considered for a multilevel serial supply chain with unlimited number of levels and random component lead times for each level. The demand of the finished product is assumed to be fixed and known. The lead time of each component (delivery time for the next level) is supposed to be a discrete random variable. No restrictive hypothesis is made on such random variables; only that one supposes that the distribution probabilities are known.

The holding as well as tardiness costs are considered. Tardiness costs can be due to the cost of revising a schedule. For the first level (level 1), i.e., which corresponds to the finished product, tardiness means backlog, so for the finished product backlogging cost is introduced. Thus, the problem is to minimize the sum of expected holding, tardiness and backlogging costs. The decision variables are the planned lead times for components at each level. An exact performance evaluation model is proposed.

A similar multilevel production system (supply chain) was already studied by Yano (1987ab). However, in that case, the lead times of components were continuous random variables. Yano limited the study to two and three stage (level) serial systems due to the difficulties to express the objective function in a closed form when the number of stages exceeds two.

The model suggested in this paper differs from (Yano, 1987ab) as follows: we consider a discrete model with no restriction on the number of levels and our model offers the expression of objective function in a closed form.

The rest of the paper is organized as follows. Section 2 presents related publications. Section 3 deals with problem description. Section 4 presents the Key Performance Indicators (KPI). In Section 5, some interesting properties of the problem are presented. A numerical example is reported in Section 6. Finally, some concluding remarks are given in Section 7.

## 2. Related publications

In literature on supply planning, as far as can be determined, the number of publications on the considered problem with random lead times is modest at best in spite of its significance, in contrast with many models for a random demand. Mula *et al.* (2006) have done a review for this domain; an extensive state of the
art on the supply planning under uncertainties is also given in (Dolgui and Prodhon, 2007).

Earlier work includes simulation studies by Whybark and Williams (1976). They suggest that, in a multi-level production-inventory system when the production and replenishment times are stochastic, safety lead times mechanism may perform better than that of safety stocks. Nevertheless, simulation studies of Grasso and Taylor (1984) reached the opposite conclusion and preferred safety stocks.

In (Chen et al., 2000; Chatfield et al., 2004; Kim et al., 2006), simulations are also used for a multilevel serial production systems with stochastic lead times. Their main effort dealt with information sharing among levels.

Some analytical models were also suggested. Weeks (1981) developed a one-stage model with tardiness and holding costs in which the processing time is stochastic and demand is deterministic. The author proves that this is equivalent to the standard “Newsboy” problem.

Yano (1987a) used an analytic approach to determine optimal planned lead times in serial production systems in which the actual procurement and processing times may be stochastic, demand is deterministic, and the lot-for-lot policy is used. The distribution of lead times is supposed stationary. The considered cost is the sum of inventory holding and job tardiness costs. The author presents a general solution procedure for two stage serial systems.

A similar problem is studied by Yano (1987b) but another cost is incurred: the rescheduling costs at the intermediate stages. Then, the objective is to minimize the sum of holding costs, rescheduling costs arising from tardiness at intermediate stages of productions, and tardiness of delivery to the customer. The author studied two and three stage serial systems due to the difficulties of the problem and complexity of the model. One of the main difficulties for this model is to express the objective function in a closed form when the number of stages exceeds two.

To surmount this difficulty, Elhafsi (2002) develops a recursive scheme that evaluates the objective function efficiently for any number of levels without recurring to express it in a closed form. However, the computing time increases relatively quickly with the number of levels. To overcome this problem, the author presents a heuristic. For a special case of this continuous model, where the lead times are distributed exponentially, the author derived the objective function in a closed form.

Kim et al. (2004) suggested a model for constant demand and lead time with Erlang distribution for a single item inventory, and obtained an approximate solution. They launched an interesting conjecture that the behaviour of the analogous single-item inventory control model for the case where both demand and lead time are random can be calculated from the behaviours of the following
three models: (i) deterministic demand and lead time, (ii) random demand and deterministic lead time, and (iii) random lead time and deterministic demand.

He *et al.* (2005) studied the impact of lead time when demand is constant in one level assembly system. In this study the lead time is random and limited, and the economic order quantity (EOQ) policy is used. The authors have shown that the cost varies linearly in function of the deviation of time.

The problem of planned lead time calculation for one-level assembly systems was already studied in our previous work. In (Dolgui and Louly, 2002) a Markov model was proposed and in (Louly and Dolgui, 2002), a new generalization of the Discrete Newsboy model was suggested. For a more general case, a branch and bound algorithm was developed in (Louly et al., 2008).

**3. Problem description**

We consider a serial production system with *m* levels (see Figure 1). We suppose that the demand *D* of the finished product is fixed and its due date is known. To satisfy this demand, we need to launch the production processes composed of *m* serial stages (*m* levels) for a lot of *D* items. The level numbers are enumerated as follows: level *m* corresponds to the first production stage, level *m-1* to the second stage, and so on. The raw materials are released at level *m*, semi-finished products are processed at levels *m-1, m-2,..., 2* and finally, finished product is produced at level 1. After these *m* levels, the lot of *D* finished products is delivered to the customer.

<figure><img src="image_2.png" /><figcaption>**Figure 1: m-level serial production system**</figcaption></figure>

We assume also that the lead time at each level (delivery time for next level) is a discrete random variable. No restrictive hypothesis is made on such random variables; we only suppose that the distribution probabilities are known. The policy is the lot-for-lot for all levels. Level *m* delivers the semi-finished products to level *m-1* within a random lead time *L*<sub>m</sub>, level *j* delivers the semi-finished products to level *j-1* within a random lead time *L*<sub>j</sub>, *j*=2,...,*m*. When the items arrive
at the end of level 1, the customer demand *D* of finished products is satisfied.
There are stocks at each intermediate level (from level *m* to level 1).

If total lead time exceeds the planned lead time of the component at level *j*, *j* = 1,2,..., *m*, tardiness is incurred and therefore the corresponding tardiness costs for level *m* to level 2. For level 1 this is called backlogging cost and corresponds to the finished product backlog. Otherwise, we obtain stocks and therefore corresponding holding cost for each level (see Figure 2). Hence, the objective is to minimize the total cost composed of the holding, tardiness and backlogging costs.

<figure><img src="image_3.png" /><figcaption>**Figure 2:** An illustration of the cost incurred</figcaption></figure>

The following notations are introduced:

* $c_j$ components at level *j*, where *j* = 1,2,..., *m*;

* $d_j$ number of component *j* needed at level *j*-1;

* $b_1$ unit backlogging cost for finished product per period;

* $b_j$ unit tardiness cost for component *j*, $j=2,...,m$, per period;

* $h_j$ unit holding cost for component *j*, $j=1,...,m$ per period;

* *D* demand of finished products per period (fixed and known);

* $L_j$ actual lead time of the component *j* (discrete random variable);

* $L'_j(x_{j+1}, x_{j+2}, ..., x_m)$ actual cumulative lead time of level *j* (proper lead time plus delays due to level *j*+1);

* $u_j$ upper value of $L_j$;
* $Q_j = d_j D$ lot size for components $j$;

* $x_j$ planned lead time for component $j$ (integer decision variable);

* $F_j(k) = \Pr(L_j \le k)$;

* $\Phi_j(k, x_{j+1}, \dots, x_m) = \Pr(L'_j \le k)$;

* $E(\cdot)$ mathematical expectation operator.

Let the lead time for components of level $j$ be a random discrete variable with known distribution: $\Pr(L_j = k), k = 1, 2, \dots, u_j$, where $u_j$ is the maximum planned lead time value, for $j = 1, \dots, m$. The lead time takes into account all processing times at the level $j$ plus transportation time between level $j$ and $j-1$. The actual cumulative lead time of the level $j$ is given in (1):

$$ \left\{ \begin{array}{l} L'_{j}(x_{j+1}, x_{j+2}, \dots, x_{m}) = L_{j} + (L'_{j+1}(x_{j+2}, x_{j+3}, \dots, x_{m}) - x_{j+1})^{+}, \text{ for } j=1, 2, \dots, m-1 \\ L'_{m} = L_{m} \end{array} \right. \qquad (1) $$

We present a model of this problem by analytically expressing the criterion to be optimized. This criterion considers the holding, component tardiness, and backlogging costs. For each type of component $j$, $x_j$ denotes the planned lead time.

Note that in Hnaien et al. (2007), we considered the same problem as in the current article but for the case of a Just in Time (JIT) policy where there are no holding costs at intermediate levels. For that problem, the objective was to find order release dates at level $m$ (sum of planned lead times for all levels).

## 4. Key Performance Indicators

PROPOSITION 1 The total cost is expressed as follows:

$$ C(X, L) = \sum_{j=1}^{m} Q_j [h_j(x_j - L'_j(x_{j+1}, x_{j+2}, \dots, x_m))] \\ + \sum_{j=1}^{m} Q_j [(b_j + h_j)(L'_j(x_{j+1}, x_{j+2}, \dots, x_m) - x_j)^+] \qquad (2) $$

where,

$$ X = (x_1, \dots, x_m) $$

$$ L = (L'_1, \dots, L'_m) $$

*Proof.* The cost is equal to the sum of the component holding, tardiness as well as finished product backlogging costs. If at a certain level, a job is completed before its planned due date, i.e. $(x_j - L'_j(x_{j+1}, x_{j+2}, \dots, x_m)) > 0$, then a holding cost is incurring. Thus, the component holding cost is equal to:
$$ \sum_{j=1}^{m} h_j Q_j (x_j - L'_j(x_{j+1}, x_{j+2}, \dots, x_m))^+ $$

There is a tardiness (respectively backlog) of components $j$ (respectively finished product) if the total lead time exceeds the planned lead time of the component at level $j, j = 1, 2, \dots, m$, i.e. $(L'_j(x_{j+1}, x_{j+2}, \dots, x_m) - x_j) > 0$.

Thus, the sum of component tardiness cost and the finished product backlog cost is equal to:

$$ \sum_{j=1}^{m} b_j Q_j (L'_j(x_{j+1}, x_{j+2}, \dots, x_m) - x_j)^+ $$

Then, the total cost is equal to:

$$ C(X, L) = \sum_{j=1}^{m} b_j Q_j (L'_j(x_{j+1}, x_{j+2}, \dots, x_m) - x_j)^+ + \sum_{j=1}^{m} h_j Q_j (x_j - L'_j(x_{j+1}, x_{j+2}, \dots, x_m))^+ $$

Note that $(-f)^+ = \max(-f, 0) = f^- = f^+ - f$.

So, if we consider $f = (x_j - L'_j(x_{j+1}, x_{j+2}, \dots, x_m))$, $C(X, L)$ can be rewritten as follows:

$$ C(X, L) = \sum_{j=1}^{m} (b_j + h_j) Q_j (L'_j(x_{j+1}, x_{j+2}, \dots, x_m) - x_j)^+ + \sum_{j=1}^{m} h_j Q_j (x_j - L'_j(x_{j+1}, x_{j+2}, \dots, x_m)) $$

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

The cost $C(X, L)$ is a random variable. Therefore, we will calculate the mathematical expectation of $C(X, L)$ noted $EC(X)$.

PROPOSITION 2 The expected cost can be expressed as follows:

$$ EC(X) = \sum_{j=1}^{m} Q_j \left[ h_j (x_j - E(L'_j(x_{j+1}, x_{j+2}, \dots, x_m))) \right] $$
$$ + \sum_{j=1}^{m} Q_j \left[ (b_j + h_j) \sum_{k \ge 0} (1 - \Phi_j(x_j + k, x_{j+1}, \dots, x_m)) \right] \quad (3) $$

where,

$$ \left\{ \begin{array}{l} \Phi_j(k, x_{j+1}, \dots, x_m) = \sum_{s=1}^{k} \Pr(L_j = s) \Phi_{j+1}(x_{j+1} + k - s, x_{j+2}, \dots, x_m), \text{ for } j=1, \dots, m-1 \\ \\ \Phi_m(k) = F_m(k) \end{array} \right. \quad (4) $$

*Proof.* From relation (2), we derive the total expected cost:

$$ EC(X) = E(C(X, L)) = \sum_{j=1}^{m} Q_j \left[ h_j (x_j - E(L'_j(x_{j+1}, x_{j+2}, \dots, x_m))) + (b_j + h_j) E(Z) \right] $$

Where:

$$ Z = (L'_{j}(x_{j+1}, x_{j+2}, \dots, x_{m}) - x_{j})^{+} $$

Z is a positive discrete random variable with a finite number of possible values, its mathematical expectation is:

$$ E(Z) = \sum_{i \ge 0} i \Pr(Z = i) = \sum_{i \ge 0} \sum_{k=0}^{i-1} \Pr(Z = i) = \sum_{k \ge 0} \sum_{i \ge k} \Pr(Z = i) = \sum_{k \ge 0} \Pr(Z > k) $$

Thus, we obtain:

$$ E(Z) = \sum_{k \ge 0} \Pr((L'_{j}(x_{j+1}, x_{j+2}, \dots, x_{m}) - x_{j})^{+} > k) $$

Given that

$$ \begin{align*} \Pr((L'_{j}(x_{j+1}, x_{j+2}, \dots, x_{m}) - x_{j})^{+} > k) &= \\ &= 1 - \Pr((L'_{j}(x_{j+1}, x_{j+2}, \dots, x_{m}) - x_{j})^{+} \le k) \\ &= 1 - (\Pr((L'_{j}(x_{j+1}, x_{j+2}, \dots, x_{m}) - x_{j}) \le k) \times \Pr(k \ge 0)) \end{align*} $$

Therefore:

$$ E(Z) = \sum_{k \ge 0} \left(1 - \Pr(L'_{j}(x_{j+1}, x_{j+2}, \dots, x_{m}) - x_{j} \le k) \times \Pr(k \ge 0)\right) $$
In the previous expression the sum is computed for $k \ge 0$, thus:

$$
\begin{align*}
E(Z) &= \sum_{k \ge 0} (1 - \Pr(L'_{j}(x_{j+1}, x_{j+2}, \dots, x_m) \le x_j + k)) \\
&= \sum_{k \ge 0} (1 - \Phi_j(x_j + k, x_{j+1}, \dots, x_m))
\end{align*}
$$

where,

$$
\begin{align*}
\Phi_j(k, x_{j+1}, \dots, x_m) &= \Pr(L'_j(x_{j+1}, x_{j+2}, \dots, x_m) \le k) \\
&= \Pr(L_j + (L'_{j+1}(x_{j+2}, \dots, x_m) - x_{j+1})^+ \le k) \\
&= \sum_{s=1}^{k} \Pr(L_j = s) \times \Pr((L'_{j+1}(x_{j+2}, \dots, x_m) - x_{j+1})^+ \le k-s) \\
&= \sum_{s=1}^{k} \Pr(L_j = s) \times \Pr(L'_{j+1}(x_{j+2}, \dots, x_m) - x_{j+1} \le k-s) \times \Pr(k-s \ge 0)
\end{align*}
$$

But, $k - s \ge 0$, thus:

$$
\Phi_j(k, x_{j+1}, \dots, x_m) = \sum_{s=1}^{k} \Pr(L_j = s) \Phi_{j+1}(x_{j+1} + k - s, x_{j+2}, \dots, x_m)
$$

Finally:

$$
EC(X) = \sum_{j=1}^{m} Q_j \left[ h_j(x_j - E(L'_j(x_{j+1}, x_{j+2}, \dots, x_m)) \right] \\
+ \sum_{j=1}^{m} Q_j \left[ (b_j + h_j) \sum_{k \ge 0} (1 - \Phi_j(x_j + k, x_{j+1}, \dots, x_m)) \right]
$$

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

Note that for the particular case of only one level, the total cost (2) can be
rewritten as follows:

$$
C(x_1, L_1) = Q_1 [h_1(x_1 - L_1) + (b_1 + h_1)(L_1 - x_1)^+] \quad (5)
$$

The corresponding expected cost (3) is as follows:
$$EC(X) = Q_1 \left[ h_1(x_1 - E(L_1)) + (b_1 + h_1) \sum_{k \ge 0} (1 - F_1(x_1 + k)) \right] \quad (6)$$

Hence, the optimal solution for one level system is given by the well known Newsboy model:

$$F_1(x_1 - 1) \le \left( \frac{b_1}{b_1 + h_1} \right) \le F_1(x) \quad (7)$$

# 5. Problem properties

Using the previous evaluation model, we present in this section some interesting properties for this problem.

## 5.1. Partial increments of cost functions

We will use the following partial increment functions (Louly et al., 2008):

$$G_j^+(X) = EC(x_1, \dots, x_j + 1, \dots, x_m) - EC(x_1, \dots, x_j, \dots, x_m) \quad (8)$$

$$G_j^-(X) = EC(x_1, \dots, x_j - 1, \dots, x_m) - EC(x_1, \dots, x_j, \dots, x_m) \quad (9)$$

These partial increments represent the evolution of the objective function due to increment or decrement of a decision variable. An optimal solution X must satisfy the requirements (10) and (11), otherwise there is a neighboring solution better than X.

$$G_j^+(X) \ge 0, \text{ for } j = 1, \dots, m \quad (10)$$

$$G_j^-(X) \ge 0 \text{ for } j = 1, \dots, m \quad (11)$$

**PROPOSITION 3** The function $G_j^+(X)$ can be rewritten as follows:

$$G_j^+(X) \le Q_j \left[ -b_j + (b_j + h_j) \Phi_j(x_j, x_{j+1}, \dots, x_m) \right] + \sum_{s=1}^{j-1} Q_s h_s \quad (12)$$

$$G_j^+(X) \ge Q_j \left[ -b_j + (b_j + h_j) \Phi_j(x_j, x_{j+1}, \dots, x_m) \right] - \sum_{s=1}^{j-1} Q_s (b_s + h_s) \quad (13)$$
Proof.

$$
\begin{aligned}
G_j^+(X) = & \sum_{s=1}^{m} Q_s [h_s(x_s - E(L'_s(x_{s+1}, \dots, x_j + 1, \dots, x_m))] \\
& + \sum_{s=1}^{m} Q_s \left[ (b_s + h_s) \sum_{k \ge 0} (1 - \Phi_s(x_s + k, \dots, x_j + 1, \dots, x_m)) \right] \\
& - \sum_{s=1}^{m} Q_s [h_s(x_s - E(L'_s(x_{s+1}, \dots, x_j, \dots, x_m))] \\
& - \sum_{s=1}^{m} Q_s \left[ (b_s + h_s) \sum_{k \ge 0} (1 - \Phi_s(x_s + k, \dots, x_j, \dots, x_m)) \right]
\end{aligned}
$$

This difference between these two costs can be calculated term by term
according to the value of the number *s*. The terms can be separated to facilitate the
calculation. Let's note $G_j^+(X) = A + B + C$.

The first term is for the values of *s* larger than *j*. The difference equals zero for
this group:

$$
\begin{aligned}
A &= \sum_{s=j+1}^{m} Q_s \left[ h_s(x_s - E(L'_s(x_{s+1}, \dots, x_m)) + (b_s + h_s) \sum_{k \ge 0} (1 - \Phi_s(x_s + k, \dots, x_m)) \right] \\
&\quad - \sum_{s=j+1}^{m} Q_s \left[ h_s(x_s - E(L'_s(x_{s+1}, \dots, x_m)) + (b_s + h_s) \sum_{k \ge 0} (1 - \Phi_s(x_s + k, \dots, x_m)) \right] \\
&= 0
\end{aligned}
$$

The second term is for $s = j$. The difference is as follows:

$$
\begin{aligned}
B ={}& Q_j[h_j(x_j + 1 - E(L'_j(x_{j+1}, x_{j+2}, \dots, x_m))] \\
     & + Q_j\left[(b_j + h_j)\sum_{k \ge 0} (1 - \Phi_j(x_j + 1 + k, x_{j+1}, \dots, x_m))\right] \\
     & - Q_j[h_j(x_j - E(L'_j(x_{j+1}, x_{j+2}, \dots, x_m))] \\
     & - Q_j\left[(b_j + h_j)\sum_{k \ge 0} (1 - \Phi_j(x_j + k, x_{j+1}, \dots, x_m))\right]
\end{aligned}
$$
$$= Q_j[h_j - (b_j + h_j)(1 - \Phi_j(x_j, x_{j+1}, \dots, x_m))]$$

$$= Q_j[-b_j + (b_j + h_j)\Phi_j(x_j, x_{j+1}, \dots, x_m)]$$

The third term is calculated for $s < j$, it is as follows:

$$C = \sum_{s=1}^{j-1} Q_s[h_s(x_s - E(L'_s(x_{s+1}, \dots, x_j+1, \dots, x_m)))] \\ + \sum_{s=1}^{j-1} Q_s\left[(b_s + h_s) \sum_{k \ge 0} (1 - \Phi_s(x_s + k, \dots, x_j + 1, \dots, x_m))\right] \\ - \sum_{s=1}^{j-1} Q_s[h_s(x_s - E(L'_s(x_{s+1}, \dots, x_j, \dots, x_m)))] \\ - \sum_{s=1}^{j-1} Q_s\left[(b_s + h_s) \sum_{k \ge 0} (1 - \Phi_s(x_s + k, \dots, x_j, \dots, x_m))\right] \\ = \sum_{s=1}^{j-1} Q_s h_s \left[E(L'_s(x_{s+1}, \dots, x_j, \dots, x_m)) - E(L'_s(x_{s+1}, \dots, x_j + 1, \dots, x_m))\right] \\ + \sum_{s=1}^{j-1} Q_s(b_s + h_s) \left[\sum_{k \ge 0} (1 - \Phi_s(x_s + k, \dots, x_j + 1, \dots, x_m))\right] \\ - \sum_{s=1}^{j-1} Q_s(b_s + h_s) \left[\sum_{k \ge 0} (1 - \Phi_s(x_s + k, \dots, x_j, \dots, x_m))\right]$$

$$\text{Or, } 0 \le E(L'_{s}(x_{s+1}, \dots, x_{j}, \dots, x_{m})) - E(L'_{s}(x_{s+1}, \dots, x_{j} + 1, \dots, x_{m})) \le 1$$

$$\text{and } 0 \le \sum_{k \ge 0} (1 - \Phi_s(x_s + k, \dots, x_j, \dots, x_m)) - \sum_{k \ge 0} (1 - \Phi_s(x_s + k, \dots, x_j + 1, \dots, x_m)) \le 1$$

Then, this last term C satisfies the following inequalities:

$$- \sum_{s=1}^{j-1} Q_s(b_s + h_s) \le C \le \sum_{s=1}^{j-1} Q_s h_s$$

Finally, we conclude:

$$G_j^+(X) \le Q_j[-b_j + (b_j + h_j)\Phi_j(x_j, x_{j+1}, \dots, x_m)] + \sum_{s=1}^{j-1} Q_s h_s$$

$$G_j^+(X) \ge Q_j[-b_j + (b_j + h_j)\Phi_j(x_j, x_{j+1}, \dots, x_m)] - \sum_{s=1}^{j-1} Q_s(b_s + h_s)$$
## 5.2. Properties of decisions variables

PROPOSITION 4 The following properties are valid:

* $\Phi_j(x_j, x_{j+1}, \dots, x_m) \ge \alpha_j \text{ for } j=1, \dots, m$ (14)

* $\Phi_j(x_j - 1, x_{j+1}, \dots, x_m) \le \beta_j \text{ for } j=1, \dots, m$ (15)

* $F_m(x_m) \ge \alpha_m$ (16)

* $F_m(x_m - 1) \le \beta_m$ (17)

* $F_j(x_j) \ge \alpha_j \text{ for } j=1, \dots, m,$ (18)

where $\alpha_j = \frac{Q_j b_j - \sum_{s=1}^{j-1} Q_s h_s}{Q_j (b_j + h_j)}$ and $\beta_j = \frac{Q_j b_j + \sum_{s=1}^{j-1} Q_s (b_s + h_s)}{Q_j (b_j + h_j)}$, for $j=1, \dots, m$

*Proof.* According to (12):

$$G_j^+(X) \le Q_j [-b_j + (b_j + h_j)\Phi_j(x_j, x_{j+1}, \dots, x_m)] + \sum_{s=1}^{j-1} Q_s h_s$$

Thus:

$$\frac{Q_j b_j - \sum_{s=1}^{j-1} Q_s h_s}{Q_j (b_j + h_j)} \le \Phi_j(x_j, x_{j+1}, \dots, x_m), \text{ for } j=1, \dots, m$$

Thus, the propriety (14) is proved.

As $G_j^-(X) = -G_j^+(x_1, \dots, x_j - 1, \dots, x_m)$, we can drive the following inequality from (11):

$$0 \le Q_j [b_j - (b_j + h_j) \Phi_j(x_j - 1, x_{j+1}, \dots, x_m)] + \sum_{s=1}^{j-1} Q_s (b_s + h_s)$$

Thus,

$$\Phi_j(x_j - 1, x_{j+1}, \dots, x_m) \le \frac{Q_j b_j + \sum_{s=1}^{j-1} Q_s (b_s + h_s)}{Q_j (b_j + h_j)}$$
Thus, the propriety (15) is proved.

Using (4), the property (16) is immediately derived from (14) and the property (17) is immediately derived from (15).

Using (4):

$$ \Phi_j(x_j, x_{j+1}, \dots, x_m) \le F_j(x_j), \text{ for } j=1, \dots, m. $$

Finally,

$$ \frac{Q_j b_j - \sum_{s=1}^{j-1} Q_s h_s}{Q_j (b_j + h_j)} \le F_j(x_j), \text{ for } j=1, \dots, m $$

We obtain the property (18).

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

Note: for $m=1$, the previous properties (15)-(18) are equivalent to well known Newsboy model.

## 6. Numerical example

We give an illustrative example with 2 levels ($m=2$). The lead time of each type of component is a discrete random variable which takes values from 1 to 5 ($u_1=u_2=5$), i.e., $1 \le L_j \le 5$. The unit holding costs are given in Table 1 and only one type of each component $j$ is needed to produce the finished product, i.e., $Q_j=1$. The distribution probabilities of all lead times are given in Table 2.

<table><caption>**Table 1:** Unit holding costs</caption><thead><tr><th>j</th><th>1</th><th>2</th></tr></thead><tbody><tr><td>h<sub>j</sub></td><td>10</td><td>10</td></tr></tbody></table>

<table><caption>**Table 2:** Probability distributions of the lead times</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>Pr (L<sub>1</sub>=w)</td><td>0.50</td><td>0.30</td><td>0.10</td><td>0.05</td><td>0.05</td></tr><tr><td>Pr (L<sub>2</sub>=w)</td><td>0.20</td><td>0.20</td><td>0.30</td><td>0.10</td><td>0.20</td></tr></tbody></table>
In the following table (Table 3, 4, and 5), the expected costs for different values of tardiness costs ($b_1=10$ and $b_2=5$; $b_1=20$ and $b_2=10$; $b_1=40$ and $b_2=20$) are reported.

We can see that the optimal solution of the first instance with $b_1=10$ and $b_2=5$ is (3, 2). The expected cost is 21.05.

<table><caption>**Table 3:** Expected costs for different values of $x_1$ and $x_2$ where $b_1=10$ and $b_2=5$</caption><thead><tr><th>x<sub>2</sub></th><th>x<sub>1</sub></th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th></tr></thead><tbody><tr><td>1</td><td></td><td>36.00</td><td>27.00</td><td>22.20</td><td>22.00</td><td>25.20</td></tr><tr><td>2</td><td></td><td>29.65</td><td>21.65</td><td><strong>21.05</strong></td><td>24.05</td><td>30.65</td></tr><tr><td>3</td><td></td><td>32.90</td><td>26.40</td><td>28.60</td><td>34.80</td><td>33.10</td></tr><tr><td>4</td><td></td><td>44.50</td><td>38.50</td><td>43.30</td><td>40.90</td><td>33.70</td></tr><tr><td>5</td><td></td><td>59.00</td><td>54.00</td><td>50.00</td><td>42.00</td><td>33.00</td></tr></tbody></table>

<table><caption>**Table 4:** Expected costs where $b_1=20$ and $b_2=10$</caption><thead><tr><th>x<sub>2</sub></th><th>x<sub>1</sub></th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th></tr></thead><tbody><tr><td>1</td><td></td><td>73.00</td><td>54.00</td><td>41.80</td><td>36.50</td><td><strong>36.30</strong></td></tr><tr><td>2</td><td></td><td>59.30</td><td>43.30</td><td>37.40</td><td>36.90</td><td>41.80</td></tr><tr><td>3</td><td></td><td>61.80</td><td>48.80</td><td>47.10</td><td>51.40</td><td>43.85</td></tr><tr><td>4</td><td></td><td>78.00</td><td>66.00</td><td>68.20</td><td>59.60</td><td>43.80</td></tr><tr><td>5</td><td></td><td>99.00</td><td>89.00</td><td>78.00</td><td>61.00</td><td>42.50</td></tr></tbody></table>

<table><caption>**Table 5:** Expected costs where $b_1=40$ and $b_2=20$</caption><thead><tr><th>x<sub>2</sub></th><th>x<sub>1</sub></th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th></tr></thead><tbody><tr><td>1</td><td></td><td>144.00</td><td>108.00</td><td>81.00</td><td>65.50</td><td>58.50</td></tr><tr><td>2</td><td></td><td>118.60</td><td>86.60</td><td>70.10</td><td>62.60</td><td>64.10</td></tr><tr><td>3</td><td></td><td>119.60</td><td>93.60</td><td>84.10</td><td>84.60</td><td>65.35</td></tr><tr><td>4</td><td></td><td>145.00</td><td>121.00</td><td>118.00</td><td>97.00</td><td>64.00</td></tr><tr><td>5</td><td></td><td>179.00</td><td>159.00</td><td>134.00</td><td>99.00</td><td><strong>61.50</strong></td></tr></tbody></table>

These results show that it is necessary to set big values for the planned lead times when the unit backlogging costs are quite large. As we can see, when the backlogging (tardiness) costs increase, the optimal solutions for planned lead times increase also until the upper values of lead times, (5, 5) in this example.

## 7. Conclusions

The problem of planned lead time evaluation has not been sufficiently studied, especially for multilevel production systems with random actual lead times. That was the motivation of this paper.
Here, multilevel supply planning was studied under lead time uncertainties for the case where the actual lead times are independent random discrete variables. The cost function was the sum of finished product backlogging, component holding and tardiness costs for all levels. A mathematical model for performance evaluation was suggested.

The proposed model takes into account the dependence among level inventories and is a generalization of the well-known discrete Newsboy model.

Further research will be dedicated to the development of efficient optimization algorithms using this evaluation model. It is also interesting to study the extensions of this approach for multilevel assembly systems. The main difficulty will be to represent in a treatable form the dependence among component inventories necessary to assemble the same semi-finished product. In this perspective, the models of this paper may be useful for an approximate approach which consists in cutting the bill of material (BOM) tree of the finished product into multi-level linear (branches).

**Acknowledgements.** This work is partially supported by Princess Fatimah Alnajras's Research Chair of Advanced Manufacturing Technology and the CODESNET coordination action. The authors thank also Chris Yukna for his help in English.

## References

Chatfield D., Kim J., Harrison T., Hayya J., (2004). The bullwhip effect in supply chains- impact of stochastic lead times, information quality, and information sharing: A simulation study. *Production and Operations Management*, 13 (4): 340-353.

Chen F., Drezner Z., Ryan J., Simchi-Levi D., (2000). Quantifying the bullwhip effect in assembly supply chain: the impact of forecasting, lead times and information. *Management Science*, 46 (3): 436-443.

Dolgui A., Louly M.A., (2002). A Model for supply planning under lead time uncertainty. *International Journal of Production Economics*, 78: 145-152.

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

Elhafsi M., (2002). Optimal leadtimes planning in serial production systems with earliness and tardiness costs. *IIE Transactions*, 34: 233-243.

Grasso E.T., Taylor B.W., (1984). A Simulation-Based Experimental Investigation of Supply/Timing Uncertainty in MRP Systems. *International Journal of Production Research*, 22 (3): 485-497.

He X.J., Kim J.G., Hayya J. C., (2005). The cost of lead-time variability: The case of the exponential distribution. *International Journal of Production Economics*, 97(2): 130-142.
Hnaien F., Dolgui A., Marian H., Louly M.A., (2007). Planning order release dates for multilevel linear supply chain with random lead times. *Systems Science*, 31 (1): 19-25.

Kim J.G., Sun D., He X.J., Hayya, J.C., (2004). The (s, Q) inventory model with Erlang time and deterministic demand. *Naval Research Logistics*, 51: 906–923.

Kim J.G., Chatfield D., Harrison T.P., Hayya J.C., (2006). Quantifying the bullwhip effect in a supply chain with stochastic lead time. *European Journal of Operational Research*, 173 (2): 617-636.

Louly M.A., 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.

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

Mula J., Poler R., Garcia-Sabater J.P., Lario F.C., (2006). Models for production planning under uncertainty: A review. *International Journal Production Economics*, 103: 271-285.

Whybark D. C., Williams J.G., (1976). Material Requirements Planning under uncertainty. *Decision Science*, 7: 595-606.

Weeks J.K., (1981). Optimizing Planned Lead Times and Delivery Dates, 21st annual Conference Proceeding, American Production and Inventory Control Society: 177-188.

Yano C.A., (1987a). Setting planned leadtimes in serial production systems with tardiness costs. *Management Science*, 33(1): 95-106.

Yano, C.A., (1987b). Planned leadtimes for serial production systems. *IIE Transactions*, 19(3): 300-307.