# A Stochastic Formulation of the Disassembly Line Balancing Problem

Mohand Lounes Bentaha, Olga Battaïa, Alexandre Dolgui

► To cite this version:

Mohand Lounes Bentaha, Olga Battaïa, Alexandre Dolgui. A Stochastic Formulation of the Disassembly Line Balancing Problem. 19th Advances in Production Management Systems (APMS), Sep 2012, Rhodes, Greece. pp.397-404, 10.1007/978-3-642-40352-1_50. emse-00766872

HAL Id: emse-00766872

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

Submitted on 21 Feb 2017

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 Formulation of the Disassembly Line Balancing Problem

Mohand Lounes Bentaha, Olga Battaïa, Alexandre Dolgui

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

**Abstract.** The disassembly line balancing problem is studied under uncertainty. Disassembly task times are assumed random variables with known probability distributions. An AND/OR graph is used to model the precedence relations among tasks. The goal is to assign the disassembly tasks to workstations while respecting precedence and cycle time constraints. The objective is to minimize the total line cost including the incompletion cost arising from task incompletion within the cycle time. A stochastic linear mixed integer programming formulation is developed.

**Keywords:** Sustainable Development; Disassembly Line Design; Stochastic Programming; L-shaped Method.

## 1 Introduction

The growing amount of postconsumer products poses challenges for business and society at large [7]. To decrease the amount of waste to be sent to landfills, more and more manufacturers turn to end-of-life processing of products [6]. The selective separation of desired parts and materials, executed by disassembly, is a mandatory step before recycling or remanufacturing [8]. As a consequence, disassembly systems tend to play an important role in industry. Since their design results in complex optimization problems, including disassembly planning, balancing and sequencing, efficient mathematical tools are needed in order to improve their performances and their cost effectiveness. Such tools must take into account the high degree of uncertainty in the structure and the quality of the products to be disassembled because of varying conditions affecting them before they arrive in a disassembly system. This paper deals with the uncertainty related to the disassembly task times and proposes a new mathematical formulation for the stochastic disassembly line balancing problem (DLBP) as well as an exact method to solve it efficiently.
## 2 Problem Formulation

The Disassembly Line Balancing Problem considered here aims to assign a given set of disassembly tasks $I = \{1,2,...,N\}$ to an ordered sequence of workstations $J = \{1,2,...,M\}$ under precedence and cycle time constraints. A task cannot be split between two workstations. Disassembly task times $t_i$ are assumed random variables with normal probability distributions having known mean $\mu$ and variance $\sigma^2$, i.e. $t_i = \tilde{\zeta}_i, \zeta_i \sim N(\mu_i, \sigma_i)$, $t_i > 0, i \in I$, [5], [12-13]. The task times of set I are modeled by random vector $\tilde{\xi} = (\tilde{\zeta}_1, \tilde{\zeta}_2, ..., \tilde{\zeta}_N)$ varying over a set $\Xi \subset \mathbb{R}_+^N$ in given probability space $(\Xi, \mathcal{F}, P)$. Random variables $\tilde{\zeta}_i, i \in I$ are assumed to be mutually independent. Let $\tilde{\zeta}_i = \alpha_i(\tilde{\xi})$, $i \in I$.

The precedence relations among tasks are given by an AND/OR Graph (AOG), [2], [10], see Fig. 1. Each subassembly of the product to be disassembled is represented by an auxiliary node $A_i$ in the AOG. Each disassembly task gives a basic node $B_i$. Two types of arcs define the precedence relations between the subassemblies and the disassembly tasks. AND-type arcs (in bold) dictate the normal precedence relation. OR-type arcs (remaining arcs) permit the selection of any of the successors. A dummy task $S$ is introduced into the precedence graph as a sink node, see the figure below.

<figure><img src="image_2.png" /><figcaption>Fig. 1. AND/OR precedence graph.</figcaption></figure>

The following notations have to be introduced.

**Parameters.**

$I = \{1,2,...,N\}$, disassembly tasks' index set, $N \in \mathbb{N}^*$;

$J = \{1,2,...,M\}$, workstations' index set, $M \in \mathbb{N}^*$;

$K = \{0,1,...,G-1\}$, index set of the AND/OR precedence graph's auxiliary nodes, $G \in \mathbb{N}^*$;

$A_k$: Auxiliary node of the AND/OR graph, $k \in K$;

$B_i$: Disassembly task, $i \in I$;

$S$: The AND/OR graph's sink node, $t_S = 0$;

$F_c$: Fixed cost per unit time of operating the workstations;
$q_j$: cost per unit time of exceeding $C_t, j \in J$;

$C_t$: Cycle time, $C_t > 0$;

$\alpha_i(\xi)$: Random task time of $B_i, i \in I$;

$P(k)$: Predecessors index set of $A_k, k \in K$ i.e. $P(k) = \{i | B_i \text{ precedes } A_k\}$;

$S(k)$: Successors index set of $A_k, k \in K, S(k) = \{i | A_k \text{ precceeds } B_i\}$.

**Decision Variables.**

$$x_{ij} = \begin{cases} 1 & \text{if task from } B_i \text{ is assigned to workstation } j, \\ 0 & \text{otherwise.} \end{cases}$$

$$x_{Sj} = \begin{cases} 1 & \text{if sink task S is assigned to workstation } j, \\ 0 & \text{otherwise.} \end{cases}$$

$$z_j = \begin{cases} C_t & \text{if } x_{Sj} = 1, \\ 0 & \text{otherwise.} \end{cases}$$

The objective considered in this paper is to minimize the line cost including fixed workstation operating costs and recourse costs caused by exceeding $C_t$. A recourse variable $y_j(\xi), j \in J$, measures the amount of time exceeding $C_t$ if there is any.

The following model is used for the problem presented.

**Stochastic MIP Formulation (SMIP I).**

$$\min \left\{ F_c \sum_{j \in J} j z_j + \mathbb{E}_{\xi} \left[ \sum_{j \in J} q_j y_j(\xi) \right] \right\}$$

s.t.

$$z_j = C_t x_{Sj}, \forall j \in J \qquad (1)$$

$$\sum_{i \in S(0)} \sum_{j \in J} x_{ij} = 1 \qquad (2)$$

$$\sum_{j \in J} x_{ij} \le 1, \forall i \in I \qquad (3)$$

$$\sum_{i \in S(k)} \sum_{j \in J} x_{ij} = \sum_{i \in P(k)} \sum_{j \in J} x_{ij}, \forall k \in K \setminus \{0\} \qquad (4)$$

$$\sum_{i \in S(k)} x_{iv} \le \sum_{i \in P(k)} \sum_{j=1}^{v} x_{ij}, \forall k \in K \setminus \{0\}, \forall v \in J \qquad (5)$$

$$\sum_{j \in J} x_{Sj} = 1 \qquad (6)$$

$$\sum_{j \in J} j x_{ij} \le \sum_{j \in J} j x_{Sj}, \forall i \in I \qquad (7)$$
$$ \sum_{i \in I} \alpha_i(\xi) x_{ij} - y_j(\xi) \le C_t, \forall j \in J \quad (8) $$

$$ z_j \ge 0, \forall j \in J \quad (9) $$

$$ x_{Sj}, x_{ij} \in \{0,1\}, \forall i \in I, \forall j \in J \quad (10) $$

$$ y_j(\xi) \ge 0, \forall j \in J \quad (11) $$

The objective function includes fixed and recourse costs, where $\mathbb{E}_{\xi}$ stands for the expected value with the respect to the distribution of the random vector $\xi$:

$$ \mathbb{E}_{\xi} [\sum_{j \in J} q_j y_j(\xi)] = \int_{\Sigma} (\sum_{j \in J} q_j y_j(\xi)) dP \quad (12) $$

Note that the integral (12) makes the model nonlinear one.

Constraints (1) ensure the value of $z_j$ to be $C_t$ when dummy task $S$ is assigned to station $j$. Constraint (2) imposes the selection of only one disassembly task (OR- successor) to begin the disassembly process. Constraint set (3) indicates that a task is to be assigned to at most one workstation. Constraints (4) and (5) define OR- and AND-precedence relations, respectively. Constraint (6) imposes the assignment of the dummy task $S$ to one station. Constraints (7) ensure the precedence relations for dummy task $S$. The constraints (8) force the respect of the cycle time limitations. Sets (9)-(11) represent the trivial constraints.

Let $X = \{ x | \text{constraints (1)-(7), (9)-(10) are satisfied} \}$ and $L = \{1, 2, ..., L\}, L \in \mathbb{N}^*$. If $\tilde{\xi}$ has a finite discrete distribution $\{(\xi^l, p_l), l \in L\}, p_l > 0, \forall l \in L$ ($p_l$ is the realization probability of $\xi^l$ of $\tilde{\xi}$), then the model presented is an ordinary linear program with a so-called dual decomposition structure.

### Deterministic Equivalent (I').

$$ \min \left\{ F_c \sum_{j \in J} z_j + \sum_{l=1}^{L} p_l \sum_{j \in J} q_j y_j(\xi^l) \right\} $$

s.t.

$$ \sum_{i \in I} \alpha_i(\xi^l) x_{ij} - y_j(\xi^l) \le C_t, \forall j \in J, \forall l \in L $$

$$ x \in X, y_j(\xi^l) \ge 0, \forall j \in J, \forall l \in L $$

Depending on the number of realizations of $\tilde{\xi}$, L, this linear mixed integer program, may become very large in scale, but its particular block structure can be exploited by specially designed algorithms such as the L-shaped method, [1], [3-4], [9], [11] which will be developed in the next session.
# 3 Solution Method

## 3.1 The L-shaped Method

The main idea of the L-shaped method is to approximate the nonlinear term in the objective function of the two-stage stochastic problems [3]. Assume a finite realizations set $\Xi$ of the stochastic vector $\tilde{\xi}$ such as $|\Xi| = L$. The L-shaped method for the DLBP can be written as follows.

### L-shaped Algorithm

**Step 0.** Set $r = \mathfrak{h} = v = 0$.

**Step 1.** Set $v = v + 1$. Solve the following LP:

$$ \min\{c^T x + \varphi\} $$

s.t.

$$ A x = b $$

$$ D_v x \geq d_v, v = 1, \dots, r \qquad (13) $$

$$ \varepsilon_v x + \varphi \geq e_v, v = 1, \dots, \mathfrak{h} \qquad (14) $$

$$ x \text{ binary, } \varphi \geq 0 $$

Let $(x^v, \varphi^v)$ be an optimal solution.

**Step 2.** For $l = 1, \dots, L$ solve the following LP:

$$ \min \quad Z = a^T u^+ + a^T u^- $$

s.t.

$$ W y + I u^+ - I u^- = h_l - T_l x^v $$

$$ y \geq 0, u^+ \geq 0, u^- \geq 0 $$

$a = (1, \dots, 1)^T$, until for some $l$ the optimal value $Z > 0$. In this case, let $\sigma^v$ be the associated simplex multipliers, define

$$ D_{r+1} = (\sigma^v)^T T_l $$

and

$$ d_{r+1} = (\sigma^v)^T h_l $$

in order to generate a constraint called a feasibility cut of type (13). Set $r = r + 1$, add constraint type (13) and return to **Step 1**. If for all $l \in L$, $Z = 0$, go to **Step 3**.

**Step 3.** For $l = 1, \dots, L$, solve the LP:
$$ \min \mathcal{W} = q_l^T y $$

$$ W y = h_l - T_l x^v $$

$$ y \ge 0 $$

Let $\omega_l^v$ be the simplex multipliers associated with the optimal solution of problem $l$ above and define

$$ \varepsilon_{\mathfrak{h}+1} = \sum_{l \in L} p_l (\omega_l^v)^T T_l $$

and

$$ e_{\mathfrak{h}+1} = \sum_{l \in L} p_l (\omega_l^v)^T h_l. $$

Let $\theta^v = e_{\mathfrak{h}+1} - \varepsilon_{\mathfrak{h}+1} x^v$. If $\varphi^v \ge \theta^v$, stop; $x^v$ is an optimal solution. Else, generate a constraint called *optimality cut* of type (14), set $\mathfrak{h} = \mathfrak{h} + 1$, add constraint type (14) and return to *Step 1*.

This method approximates $\mathbb{E}_{\tilde{\xi}}[\sum_{j \in J} q_j y_j(\tilde{\xi})] = \int_{\tilde{\Sigma}} (\sum_{j \in J} q_j y_j(\tilde{\xi})) dP$ using an outer linearization.

Two types of constraints are sequentially added:

* feasibility cuts (13) determining $\{x | \mathbb{E}_{\tilde{\xi}}[\sum_{j \in J} q_j y_j(\tilde{\xi})] < +\infty\}$;

* optimality cuts (14), which are linear approximations to $\mathbb{E}_{\tilde{\xi}}[\sum_{j \in J} q_j y_j(\tilde{\xi})]$.

# 4 Example

The method presented has been applied to the compass example illustrated in Fig. 2. It is made of seven components: (1) wheel, (2) left leg, (3) right leg, (4) left fixation screw, (5) lead, (6) tip and (7) right fixation screw. The AOG for this example is shown in Fig. 1. The input data for the DLBP is presented in Table 1.
<figure><img src="image_3.png" /><figcaption>Fig. 2. The Compass example.</figcaption></figure>

<table><caption>**Table 1.** Input data</caption><thead><tr><th>Task</th><th>μ</th><th>σ</th><th>Subassembly</th><th>Component</th><th></th></tr></thead><tbody><tr><td>1</td><td>0.21</td><td>0.05</td><td>1:5</td><td>6:7</td><td>|Ξ| = 1024</td></tr><tr><td>2</td><td>0.21</td><td>0.05</td><td>1:3,6,7</td><td>4:5</td><td>J = {1,2,3}</td></tr><tr><td>3</td><td>0.50</td><td>0.10</td><td>2,4,5</td><td>1:3</td><td>K = {0,1,...,5}</td></tr><tr><td>4</td><td>0.21</td><td>0.05</td><td>1:3</td><td>4:5</td><td>F<sub>c</sub> = 5</td></tr><tr><td>5</td><td>0.50</td><td>0.10</td><td>2,4,5/3,6,7</td><td>1</td><td>q<sub>j</sub> = 7, j ∈ J</td></tr><tr><td>6</td><td>0.21</td><td>0.05</td><td>1:3</td><td>6:7</td><td>C<sub>t</sub> = 0.51</td></tr><tr><td>7</td><td>0.50</td><td>0.10</td><td>3,6,7</td><td>1:2</td><td></td></tr><tr><td>8</td><td>0.21</td><td>0.05</td><td>--</td><td>2:4:5</td><td></td></tr><tr><td>9</td><td>0.50</td><td>0.10</td><td>--</td><td>1:2:3</td><td></td></tr><tr><td>10</td><td>0.21</td><td>0.05</td><td>--</td><td>3:6:7</td><td></td></tr></tbody></table>

The L-shaped method was implemented in Microsoft Visual C++ 2008. ILOG CPLEX 12.4 was used to solve the model on a PC with Pentium(R) Dual-Core CPU 2.30 GHz and 3Go RAM. The optimal solution contains 2 workstations. Task 5 is assigned to the 1st workstation and tasks {8,10} to the second one. The total line cost is 5.342 when the recourse cost is 0.242. The resolution time was 58 s. The overall idle time of the disassembly line, if mean time of each task selected is considered, is 0.10.

# 5 Conclusion and Perspectives

The disassembly line balancing problem was formulated under uncertainty. A two-stage stochastic linear mixed integer program with fixed recourse was developed to solve it. The formulation presented can be easily adapted for the stochastic assembly
line balancing problem as well. Then, the model can be considered for the disassem-
bly task times given by, for example, triangular distribution.

Further research work should be done in order to refine the proposed mathematical model and solution method in order to approach real-world problems where uncertainty does not only concern the disassembly task times but the quantity and the quality of the inputs and outputs of the disassembly line as well.

Acknowledgement

This work was partially supported by Research Cluster on Operational Research (GDR RO) of the National Centre for Scientific Research, France.

References

1. Ahmed, S., Shapiro, A.: The Sample Average Approximation Method for Stochastic Programs with Integer Recourse. Technical Report, School of Industrial & Systems Engineering, Georgia Institute of Technology. 1-24 (2002).

2. Altekin, F.T., Kandiller, L., Ozdemirel, N.E.: Profit-Oriented Disassembly-Line Balancing. International Journal of Production Research. 46, 10, 2675-2693 (2008).

3. Birge, J.R.: Stochastic Programming Computation and Applications. INFORMS Journal on Computing. 9, 2, 111-133 (1997).

4. Birge, J.R., Tang, H.: L-shaped Method for Two-stage Problems of Stochastic Convex Programming. Technical Report 93-22, (1993).

5. Dolgui, A., Proth, J.-M.: Supply Chain Engineering: Useful Methods and Techniques. Springer London Ltd, London (2010).

6. Güngör, A., Gupta, S.M.: A Solution Approach to the Disassembly Line Balancing Problem in the Presence of Task Failures. International Journal of Production Research. 39, 7, 1427-1467 (2001).

7. Güngör, A., Gupta, S.M.: Issues in Environmentally Conscious Manufacturing and Product Recovery: a Survey. Computers & Industrial Engineering. 36, 811-853 (1999).

8. Güngör, A., Gupta, S.M.: Disassembly Line in Product Recovery. International Journal of Production Research. 40, 11, 2569-2589 (2002).

9. Kall, P., Wallace, S.W.: Stochastic Programming. John Wiley & Sons, Chichester (1994).

10. Koc, A., Sabuncuoglu, I., Erel, E.: Two Exact Formulations for Disassembly Line Balancing Problems with Task Precedence Diagram Construction Using an AND/OR Graph. IIE Transactions. 41, 10, 866-881 (2009).

11. Ntaimo, L.: Fenchel Decomposition for Stochastic Mixed-Integer Programming. Texas A&M University. 1, 1-23 (2010).

12. Sarin, S.C., Erel, E., Dar-el, E.M.: A Methodology for Solving Single-Model, Stochastic Assembly Line Balancing Problem. The International Journal of Management Science. 27, 525-535 (1999).

13. Silverman, F.N., Carter, J.C.: A Cost-based Methodology for Stochastic Line Balancing with Intermittent Line Stoppages. Management Science. 32, 4, 455-463 (1986).