# Chance Constrained Programming Model for Stochastic Profit-Oriented Disassembly Line Balancing in the Presence of Hazardous Parts

Mohand Lounes Bentaha, Olga Battaïa, Alexandre Dolgui

► To cite this version:

Mohand Lounes Bentaha, Olga Battaïa, Alexandre Dolgui. Chance Constrained Programming Model for Stochastic Profit-Oriented Disassembly Line Balancing in the Presence of Hazardous Parts. 20th Advances in Production Management Systems (APMS), Sep 2013, State College, PA, United States. pp.103-110, 10.1007/978-3-642-41266-0_13 . emse-00880909

HAL Id: emse-00880909

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

Submitted on 2 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
Chance Constrained Programming Model
for Stochastic Profit-Oriented Disassembly Line
Balancing in the Presence of Hazardous Parts

Mohand Lounes Bentaha, Olga Battaïa, and Alexandre Dolgui

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

**Abstract.** A Stochastic Partial profit-oriented Disassembly Line Balancing Problem (SP-DLBP) in the presence of hazardous parts is considered. The goal is to assign disassembly tasks of the best selected disassembly alternative to a sequence of workstations while respecting precedence and cycle time constraints. An AND/OR graph is used to model the disassembly alternatives and the precedence relations among tasks. Task times are assumed independent random variables with known normal probability distributions. Cycle time constraints are to be satisfied with at least a certain probability level fixed by the decision maker. The objective is to maximize the profit produced by the line. It is computed as the difference between the positive revenue generated by retrieved parts and the line operation cost considered as negative revenue. The line cost includes the workstations operation costs as well as additional costs of workstations handling hazardous parts of End of Life (EOL) product. To deal with uncertainties, a Chance Constrained Programming formulation is developed.

**Keywords:** Sustainable Manufacturing; Product Recovery; Disassembly; Line Design; Cone and Chance Constrained Programming; Interior-point Algorithm.

# 1 Introduction

Disassembly lines play a key role in the selective separation of parts and materials of EOL products. The success of the product recovery depends partially on the economical efficiency of such lines. However, their design presents a complex optimization problem requiring adapted mathematical tools to obtain efficient solutions.

A first study on disassembly line considering task failures was presented by Güngör and Gupta [6]. Later, the deterministic version of the Disassembly Line Balancing Problem (DLBP) was studied in [10–13]. Several performance criteria were considered including minimization of the number of stations needed and variation in idle times between the stations of the line. The following solution methods were developed and compared: exhaustive search, genetic algorithm, ant
colony metaheuristics, a greedy algorithm, greedy/hill-climbing and greedy/2-optimal hybrid heuristics. Altekin et al. [3] defined and solved the profit-oriented DLBP. The problem was modeled via a mixed-integer programming formulation and its solution simultaneously determined the number of stations and cycle time along with the assignment of the tasks to the stations. Upper and lower bounding schemes were also developed. Koc et al. [7] proposed two exact (MIP and DP) formulations to solve DLBP with the objective of minimizing the number of stations. They used an AND/OR graph to model EOL product data and showed that the use of such a graph allowed obtaining better solutions in comparison with a single precedence diagram. Altekin and Akkan [2] considered task-failure driven rebalancing of disassembly lines. A mixed-integer programming based predictive-reactive approach was proposed. In the first step, a predictive balance was created and then, in the second step, given a task failure, the tasks of the disassembled product with that task failure were reselected and re-assigned to the stations. Agrawal and Tiwari [1] considered the case of a mixed-model U-shaped disassembly line with stochastic task times. They proposed a collaborative ant colony optimization technique to simultaneously determine the sequencing of the models and assign the tasks to the stations.

The literature exposed above shows that no adequate mathematical model taking into account simultaneously the stochasticity of disassembly task times, the partial disassembly and maximizing the profit produced by the line can be found. To fill this gap, this paper aims to provide such a model where some of disassembled parts are considered hazardous and require a particular treatment incurring a supplementary cost. An adapted solution method to find efficient design solutions is presented. The paper is organized as follows. Section 2 presents the problem formulation. Section 3 describes the solution method. Section 4 analyzes the numerical experiments. Conclusions are given in Section 5.

## 2 Problem Statement

The SP-DLBP aims to assign a set of disassembly tasks, $I = \{1, 2, ..., N\}, N \in N^*$ to an ordered sequence of workstations, $J = \{1, 2, ..., M\}, M \in N^*$ under precedence relationships constraints among tasks. Cycle time ($C_0 > 0$) limitation at each station is satisfied with a certain probability level fixed by the decision maker. Task times are assumed mutually independent random variables with known normal probability distributions, i.e. $t_i(\xi) \sim N(\mu_i, \sigma_i), t_i(\xi) > 0, i \in I$; the random variables are modeled by a random vector $\xi = (\tilde{t}_1, \tilde{t}_2, ..., \tilde{t}_N)$ varying over a set $\Xi \subset \mathbb{R}^N$ given a probability space $(\Xi, \mathcal{F}, P)$ introduced by $\xi$. A disassembly task $i \in H \subset I$ is called hazardous if its execution generates a hazardous subassembly or component. All possible alternatives for disassembly process and precedence relationships among tasks and subassemblies are modeled by an AND/OR graph [5]. An example for such a graph is given in Fig. 1. To simplify the graph, without information loss, subassemblies with one component are not shown. Each subassembly of single type EOL product to be disassembled is represented by a node $A_k, k \in K = \{0, 1, ..., K\}, K \in \mathbb{N}$ in the graph and each
<figure><img src="image_2.png" /><figcaption>Fig. 1. AND/OR graph of the piston and connecting rod</figcaption></figure>

disassembly task gives a node $B_i$, $i \in I$. Two types of arcs define the precedence relations between the subassemblies and tasks: AND-type and OR-type arcs. For instance, if a disassembly task generates two sub-assemblies, or more, then it is related to these subassemblies by AND-type arcs. If, for a given subassembly, one or more disassembly tasks can be performed, but only one must be selected, this subassembly is related to these disassembly tasks by OR-type arcs. In order to consider the case of partial disassembly, where the product is not necessarily disassembled till obtaining single parts, a dummy task $s$ is introduced into the precedence graph as a sink node, as illustrated in Fig. 1. Since the case of partial disassembly is considered, not all existing tasks have to be assigned. The level of the disassembly depends on the profit generated by the corresponding line. The recycling or reuse of certain parts or subassemblies bring its benefit while the line cost is considered as a negative revenue. This cost includes two components: the cost of workstations used and additional cost entailed by the treatment of hazardous parts. For the problem defined, the following stochastic Mixed Integer Program with Joined Probabilistic Constraints (MIPJPC) has been developed.

## Parameters

$H$: Hazardous disassembly tasks' index set;

$L$: Parts' index set: $L = \{1, 2, \dots, L\}, L \in \mathbb{N}^*$;

$r_l$: Revenue generated by part $l$, $l \in L$;

$L_i$: Set of retrieved parts by the execution of disassembly task $B_i$, $i \in I$;

$F_c$: Fixed cost per unit time of operating workstations, $F_c > 0$;
$C_h$: Additional cost for stations handling hazardous parts, $C_h > 0$;

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

$S_k$: Successors index set of $A_k$, $k \in K$, $S_k = \{i | A_k$ precedes $B_i\}$.

## Decision Variables

$$x_{ij} = \begin{cases} 1, & \text{if disassembly task } B_i \\ 0, & \text{is assigned to workstation } j; \text{ otherwise.} \end{cases} \quad x_{sj} = \begin{cases} 1, & \text{if dummy task s is assigned} \\ 0, & \text{to workstation } j; \text{ otherwise.} \end{cases}$$

$$z_j = \begin{cases} C_0, & \text{if } x_{sj} = 1; \\ 0, & \text{otherwise.} \end{cases} \quad h_j = \begin{cases} 1, & \text{if a hazardous task is assigned} \\ 0, & \text{to workstation } j; \text{ otherwise.} \end{cases}$$

## Stochastic Program

$$\max \left\{ \sum_{i \in I} \sum_{j \in J} \sum_{\ell \in L_i} r_{\ell} \cdot x_{ij} - F_c \cdot \sum_{j \in J} j \cdot z_j - C_0 C_h \cdot \sum_{j \in J} h_j \right\} \quad (\text{MIPJPC})$$

s.t.

$$z_j = C_0 \cdot x_{sj}, \forall j \in J \quad (1)$$

$$\sum_{i \in S_0} \sum_{j \in J} x_{ij} = 1 \quad (2)$$

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

$$\sum_{i \in S_k} \sum_{j \in J} x_{ij} \le \sum_{i \in P_k} \sum_{j \in J} x_{ij}, \forall k \in K \setminus \{0\} \quad (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 \quad (5)$$

$$\sum_{j \in J} x_{sj} = 1 \quad (6)$$

$$\sum_{j \in J} j \cdot x_{ij} \le \sum_{j \in J} j \cdot x_{sj}, \forall i \in I \quad (7)$$

$$h_j \ge x_{ij}, \forall j \in J, \forall i \in H \quad (8)$$

$$P\left(\sum_{i \in I} t_i(\tilde{\xi}) \cdot x_{ij} \le C_0, \forall j \in J\right) \ge 1 - \alpha \quad (9)$$

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

$$x_{sj}, x_{ij}, h_j \in \{0, 1\}, \forall i \in I, \forall j \in J \quad (11)$$

The terms of the objective function represent respectively the earned profit of retrieved parts, the cost of operating workstations and the additional cost for
handling hazardous parts. If the dummy task **s** is assigned to workstation *j*, which defines the number of processed stations, then $\sum_{j \in J} j \cdot z_j = j \cdot C_0$ and workstations operating cost becomes $j \cdot (F_c \cdot C_0)$. Constraints (1) ensure the value of $z_j$ to be $C_0$ when the 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) ensure that only one OR-successor is selected. Constraint set (5) defines the precedence relations among tasks. Constraint (6) imposes the assignment of the dummy task **s** to one station. Constraints (7) ensure that all the disassembly tasks are assigned to lower or equal-indexed workstations than the one to which **s** is assigned. Constraints (8) ensure the value of $h_j$ to be 1 if at least one hazardous task is assigned to a workstation *j*. Constraints (9) enforce the station operating time to remain within the cycle time, for all opened workstations, with a probability at least $(1 - \alpha)$ determined by the decision maker. Finally, sets (10)-(11) represent the trivial constraints.

### 3 Solution Method

Let $(1 - \alpha) = \bar{\alpha}$. Since disassembly task times are assumed mutually independent random variables with known normal probability distributions, then:

$$P\left(\sum_{i \in I} t_i(\tilde{\xi}) \cdot x_{ij} \le C_0, \forall j \in J\right) \ge \bar{\alpha} \iff \prod_{j \in J} P\left(\sum_{i \in I} t_i(\tilde{\xi}) \cdot x_{ij} \le C_0\right) \ge \bar{\alpha}$$

$$\iff \prod_{j \in J} P\left(\sum_{i \in I} t_i(\tilde{\xi}) \cdot x_{ij} \le C_0\right) \ge \bar{\alpha}^{1=\sum_{j \in J} y_j}, y_j \ge 0, \forall j \in J$$

$$\iff P\left(\sum_{i \in I} t_i(\tilde{\xi}) \cdot x_{ij} \le C_0\right) \ge \bar{\alpha}^{y_j}, \forall j \in J, \sum_{j \in J} y_j = 1.$$

$$P\left(\sum_{i \in I} t_i(\tilde{\xi}) \cdot x_{ij} \le C_0\right) \ge \bar{\alpha}^{y_j}, \forall j \in J$$

$$\iff P\left(\frac{\sum_{i \in I} t_i(\tilde{\xi}) \cdot x_{ij} - \sum_{i \in I} \mu_i \cdot x_{ij}}{\sqrt{\sum_{i \in I} \sigma_i^2 \cdot x_{ij}}} \le \frac{C_0 - \sum_{i \in I} \mu_i \cdot x_{ij}}{\sqrt{\sum_{i \in I} \sigma_i^2 \cdot x_{ij}}}\right) \ge \bar{\alpha}^{y_j}$$

$$\iff P\left(Z_j \le \frac{C_0 - \sum_{i \in I} \mu_i \cdot x_{ij}}{\sqrt{\sum_{i \in I} \sigma_i^2 \cdot x_{ij}}}\right) \ge \bar{\alpha}^{y_j}, Z_j \rightsquigarrow \mathcal{N}(0, 1), \forall j \in J$$

$$\iff \sum_{i \in I} \mu_i \cdot x_{ij} + \Phi^{-1}(\bar{\alpha}^{y_j}) \cdot \sqrt{\sum_{i \in I} \sigma_i^2 \cdot x_{ij}} \le C_0, \forall j \in J \quad (12)$$

Let $(v, w) \in \mathbb{R} \times \mathbb{R}^{l-1}$; the unit second-order convex cone of dimension *l* is defined as $Q^l = \left\{ \begin{pmatrix} w \\ v \end{pmatrix} \mid v \ge \|w\| \right\}$ where $\| \cdot \|$ refers to the standard Euclidean norm. Since $\alpha < 50\%$, which is justified by the fact that $\alpha$ represents the risk and mostly
$\alpha \le 10\%$, we have $\Phi^{-1}(\bar{\alpha}^{y_j}) > 0$, and since $x_{ij} \in \{0, 1\} \iff x_{ij}^2 \in \{0, 1\}$, then, inequality (12) is a second-order cone constraint of dimension $l = N + 1$:

$$
\begin{align*}
\sum_{i \in I} \mu_i \cdot x_{ij} + \Phi^{-1}(\bar{\alpha}^{y_j}) \cdot \sqrt{\sum_{i \in I} \sigma_i^2 \cdot x_{ij}} &\le C_0, \forall j \in J \\
\iff \mu^\top \cdot x_j + \Phi^{-1}(\bar{\alpha}^{y_j}) \cdot \|\Sigma^{\frac{1}{2}} \cdot x_j\| &\le C_0, \forall j \in J \\
\iff \|\Sigma^{\frac{1}{2}} \cdot x_j\| &\le \frac{1}{\Phi^{-1}(\bar{\alpha}^{y_j})} \cdot (C_0 - \mu^\top \cdot x_j), \forall j \in J \\
\iff \left\{ \left( \frac{\Sigma^{\frac{1}{2}}}{-\mu^\top} \right)_{x_j} + \left( \frac{\mathbf{0}}{\Phi^{-1}(\bar{\alpha}^{y_j})} \right) \right\} &\in \mathbb{Q}^{N+1}, \forall j \in J
\end{align*}
$$

where $\mu = (\mu_1, \dots, \mu_N)$, $x_j = (x_{1j}, \dots, x_{Nj})^\top$, $\forall j \in J$, $\Sigma^{\frac{1}{2}} = \begin{pmatrix} \sigma_1 & \mathbf{0} \\ \vdots & \vdots \\ \mathbf{0} & \sigma_N \end{pmatrix}$ is a diagonal matrix and $\Phi^{-1}(\cdot)$ is the inverse of the standard normal cumulative distribution function $\Phi(\cdot)$.

Let $x$ be a vector of the decision variables $x_{ij}$, $x_{sj}$, $h_j$, $z_j$ and $X = \{x| \text{ constraints } (1) - (8), (10) - (11) \text{ are satisfied}\}$. The Second Order Cone Mixed Integer Program given below represents an equivalent version of problem (MIPJPC) [4].

$$ \max \left\{ \sum_{i \in I} \sum_{j \in J} \sum_{l \in L_i} r_l \cdot x_{ij} - F_c \cdot \sum_{j \in J} j \cdot z_j - C_0 C_h \cdot \sum_{j \in J} h_j \right\} \quad (\text{SOCMIP}) $$

s.t.

$$
\begin{align*}
x &\in X \\
v_j &\le \frac{1}{\Phi^{-1}(\bar{\alpha}^{\frac{1}{M}})} \cdot (C_0 - \mu^{\top} \cdot x_j), \quad \forall j \in J \\
w_{ij} &\ge \sigma_i \cdot x_{ij}, \quad \forall i \in I, \forall j \in J \\
v_j &\ge \|w_j\|, \quad \forall j \in J \\
v_j &\ge 0, \quad w_{ij} \ge 0, \quad \forall i \in I, \forall j \in J
\end{align*}
$$

where $v_j, w_{ij}, \forall i \in I, \forall j \in J$ are intermediate variables, $w_j = (w_{1j}, \dots, w_{Nj})^\top$, $\forall j \in J$. We consider the case where cycle time constraint is to be satisfied with the same probability for each station of the line, i.e. $y_j = \frac{1}{|J|} = \frac{1}{M}, \forall j \in J$. The resulted (SOCMIP) is then solved using the interior point algorithm [14] of CPLEX 12.4.

# 4 Numerical Results

The program (SOCMIP) was implemented in Microsoft Visual C++ 2008 and ILOG CPLEX 12.4 was used to solve the model on a PC with Intel(R) Core(TM)
<table><caption>**Table 1.** Problem instances and obtained results</caption><thead><tr><th rowspan="2"></th><th rowspan="2">N</th><th rowspan="2">K, L</th><th rowspan="2">arcs</th><th colspan="3">AND-relations</th><th rowspan="2">M</th><th rowspan="2">C<sub>0</sub></th><th rowspan="2">obj.</th><th rowspan="2">tasks</th><th rowspan="2">stat.</th><th rowspan="2">H-stat.</th><th rowspan="2">CPU time</th></tr><tr><th>0</th><th>1</th><th>2</th></tr></thead><tbody><tr><td>MJKL11</td><td>37</td><td>22, 33</td><td>68</td><td>4</td><td>27</td><td>6</td><td>3</td><td>40</td><td>20</td><td>7</td><td>3</td><td>1</td><td>0.50</td></tr><tr><td>L99a</td><td>30</td><td>18, 28</td><td>56</td><td>2</td><td>26</td><td>2</td><td>3</td><td>50</td><td>75</td><td>7</td><td>3</td><td>1</td><td>0.03</td></tr><tr><td>BBD13</td><td>25</td><td>11, 27</td><td>49</td><td>4</td><td>18</td><td>3</td><td>2</td><td>120</td><td>640</td><td>3</td><td>2</td><td>0</td><td>0.05</td></tr><tr><td>KSE09</td><td>23</td><td>13, 20</td><td>47</td><td>4</td><td>5</td><td>14</td><td>2</td><td>20</td><td>53</td><td>4</td><td>2</td><td>0</td><td>0.05</td></tr><tr><td>L99b</td><td>20</td><td>13, 23</td><td>40</td><td>5</td><td>9</td><td>6</td><td>3</td><td>10</td><td>72</td><td>7</td><td>3</td><td>1</td><td>0.22</td></tr><tr><td>BBD12</td><td>10</td><td>5, 12</td><td>18</td><td>3</td><td>6</td><td>1</td><td>2</td><td>0.51</td><td>18.39</td><td>2</td><td>2</td><td>1</td><td>0.05</td></tr></tbody></table>

i5-2400 CPU 3.10 GHz and 8Go RAM. It has been applied to the problem instance illustrated in Fig. 1 and to 5 available in the literature benchmark problems containing process alternatives for disassembly. The names of the problem instances were respectively composed of the first letters of authors' names and year of publication, i.e. BBD12 [5], KSE09 [7], L99a and L99b from [8], MJKL11 [9]. BBD13 corresponds to the piston and connecting rod product instance, see Fig. 1. The input data for each problem instance is given in Table 1. The columns 'AND-relations' report the number of disassembly tasks with no successor in column 0, with one AND-type arc in column 1, and with two AND-type arcs in column 2, column 'arcs' gives the total number of AND-type and OR-type arcs.

The interior-point algorithm of CPLEX was applied to each instance for $\alpha = 10\%$. Cost of operating workstations $F_c$ was fixed to 5 and cost for stations handling hazardous parts $C_h = 3$ for all instances. The results obtained are also presented in Table 1 where columns 'obj., tasks, stat., H-stat., CPU time' report respectively the optimal profit of the line, the number of selected tasks, the number of opened stations, the number of hazardous stations and solution time in seconds. All instances were solved in less than 1 second.

## 5 Conclusion

In this paper, partial profit-oriented disassembly line balancing problem in the presence of hazardous parts was studied under uncertainty. A second-order cone mixed integer program was developed. Disassembly task times were assumed mutually independent random variables with known normal probability distributions, where cycle time constraints were to be jointly satisfied with at least a probability level fixed by the decision maker. To solve the problem, the interior point algorithm and CPLEX solver were used. The solution method was evaluated on a set of 6 problem instances taken from the literature. All instances were solved in less than 1 second.

Our future objective is to develop an exact solution algorithm for the problem considered based on branch & cut method and compare it to interior point CPLEX algorithm.
References

1. Agrawal, S., Tiwari, M.K.: A collaborative ant colony algorithm to stochastic mixed-model U-shaped disassembly line balancing and sequencing problem. International Journal of Production Research 46(6) (2006) 1405-1429

2. Altekin, F.T., Akkan, C.: Task-failure-driven rebalancing of disassembly lines. International Journal of Production Research 50(18) (2011) 4955-4976

3. Altekin, F.T., Kandiller, L., Ozdemirel, N.E.: Profit-oriented disassembly line balancing. International Journal of Production Research 46(10) (2008) 2675-2693

4. Atamtürk, A., Narayanan, V.: Conic mixed-integer rounding cuts. Math. Program. **122** (2010) 1–20

5. Bentaha, M.L., Battaïa, O., Dolgui, A.: A stochastic formulation of the disassembly line balancing problem. In: Proceedings of the International Conference on Advances in Production Management Systems. (2012)

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) (2001) 1427-1467

7. 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) (2009) 866-881

8. Lambert, A.J.D.: Linear programming in disassembly/clustering sequence generation. Computers & Industrial Engineering **36**(4) (1999) 723-738

9. Ma, Y.S., Jun, H.B., Kim, H.W., Lee, D.H.: Disassembly process planning algorithms for end-of-life product recovery and environmentally conscious disposal. International Journal of Production Research **49**(23) (2011) 7007-7027

10. McGovern, S.M., Gupta, S.M.: Combinatorial optimization analysis of the unary NP-complete disassembly line balancing problem. International Journal of Production Research **45**(18-19) (2007) 4485-4511

11. McGovern, S.M., Gupta, S.M.: Ant colony optimization for disassembly sequencing with multiple objectives. The International Journal of Advanced Manufacturing Technology **30**(5-6) (2006) 481-496

12. McGovern, S.M., Gupta, S.M.: A balancing method and genetic algorithm for disassembly line balancing. European Journal of Operational Research **179**(3) (2007) 692-708

13. McGovern, S.M., Gupta, S.M.: The Disassembly Line, Balancing and Modeling. 2011 edn. McGraw-Hill Companies, New York (2011)

14. Nesterov, Y.E., Nemirovski, A.S.: Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics, Philadelphia (1994)