# Integrated Procurement–Disassembly Problem

Muhammad Khakim Habibi, Olga Battaïa, Van-Dat Cung, Alexandre Dolgui

► To cite this version:

Muhammad Khakim Habibi, Olga Battaïa, Van-Dat Cung, Alexandre Dolgui. Integrated Procurement–Disassembly Problem. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2014, Ajaccio, France. pp.482-490, 10.1007/978-3-662-44736-9_59 hal-01387922

HAL Id: hal-01387922

https://inria.hal.science/hal-01387922

Submitted on 26 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
Integrated Procurement–Disassembly Problem

*Muhammad Khoirul Khakim Habibi, *Olga Battaïa, **Van-Dat Cung, and
*Alexandre Dolgui

*École Nationale Supérieure des Mines de Saint-Étienne,
Lab. LIMOS, CNRS UMR6158,
42023 Saint-Étienne cedex 2, France

**Univ. Grenoble Alpes, G-SCOP, F-38000 Grenoble, France,
CNRS, G-SCOP, F-38000 Grenoble, France,
{muhammad.habibi,battaia,dolgui}@emse.fr
van-dat.cung@grenoble-inp.fr

**Abstract.** This paper proposes a novel problem called integrated pro-
curement-disassembly problem. The problem combines vehicle routing
problem and disassembly line balancing problem for collecting and dis-
assembling End-of-Life (EOL) products, respectively. The integration of
those problems is motivated by the necessity to reduce total cost in
reverse supply chain context. After collecting the EOL products from
suppliers, the disassembly process begins to release the demanded parts.
The objective function aims to minimize the total cost consisting product
collection and opening disassembly workstations. The constraints con-
sider vehicle routing problem to supply the disassembly line with EOL
products, disassembly line and balancing inventory coordinating those
problems. The decision variables include trips sequences associated to
collect the products, disassembly task assignment into workstations, and
the inventory level.

**Keywords:** Vehicle routing, disassembly, line design and balancing, inventory control, End-of-Life product

# 1 Introduction

Electronic and electrical manufacturing sector are encouraged to consider the
environmental aspect of its production process. This condition is caused by the
shrinking life cycle of electronic and electrical equipments (EEEs) henceforth in-
creases the amount of waste electrical and electronics equipments (WEEEs). The
main reasons are government's mandates to extend the responsability of manu-
facturer (mainly in EU, USA, Australia, Japan and South Korea), consumers'
consciousness [1-3] and the potential worthwhile of EOL products.

The disassembly process is considered to deal with this condition. It is a set
of activity for disassembling the EOL product in order to release its precious and
hazardous parts. Since it is expensive and time consuming activity, optimization
is required for attaining the profitable state. Our research focuses on a field of
disassembly process known as disassembly line balancing problem (DLBP).
DLBP is the assignment of disassembly tasks into a sequence of stations such that the returned product is disassembled based on the desired level of disassembly respecting the disassembly precedence relations and some measure of effectiveness [4]. Researches have been conducted in several related factors such as demanded and hazardous part priorititation, task failure, profit orientation etc.

However, the studies on DLBP are usually not connected with other decisions in reverse supply chain. Since the studies on forward supply chain show that the decisions integration permits the cost reduction [5–8], the same idea should be investigated in the reverse supply chain.

For this purpose, this work is intended to deal with the collection and the disassembly process of EOL products. This research proposes an integrated model for Capacitated Vehicle Routing Problem based waste collection (w-VRP) and DLBP called integrated procurement-disassembly problem. The model minimizes the total cost corresponding to EOL products collection and disassembly process related to w-VRP and DLBP, respectively. During products collection process, we assume only one available vehicle and several suppliers who have EOL product to be collected. The model admits partial disassembly since it aims to release the demanded parts only. To the best of our knowledge, it is the first work proposes the integration between collection process and disassembly balancing problem.

The next sections are organized as follows. Section 2 gives an overview of related literature. Section 3 describes our mixed integer linear programming formulation. Section 4 provides computational results. The last section gives a conclusion and some prospects for future work.

## 2 Literature Review

DLBP has been investigated by researchers in many cases. Such as assembly line balancing problem (ALBP), one of the objectives is to minimize the number of workstations required to reach a given cycle time [9]. Altekin et al. [4] proposed a profit-oriented partial DLBP model to maximize the earned profits of released part while taking into consideration the cost of performing disassembly task as well as fixed cost caused by opening workstations. Partial disassembly is represented by associating the disassembly task with its incurred cost. Bentaha et al. [10–15] offered novel models of profit-oriented partial DLBP based on transformed AND/OR graph of [16] under stochastic condition. The objective of [11–13] was to minimize the total fixed cost of opening workstations and recourse cost caused by task failure. The revenue of released products was considered in [10, 15]. The cost of handling hazardous parts was taken into account [14].

New issues combining several decisions related DLBP are emerged. Özceylan et al. [17] dealt with closed-loop supply chain (CLSC) and DLBP. The proposed model aims to determine the material distribution in forward and reverse flows as well as to balance disassembly line through tasks assignment. Özceylan et al. [18] proposed a model under undeterministic condition concerning task cost, inventory level, demand and reverse rates.
The decisions integration was principally studied for forward supply chain. Boudia et al. [5, 6] and Boudia and Prins [7] worked on IPDP by minimizing the routing and production cost. Bard and Nananukul [8] considered time windows into IPDP. Shiguemoto and Armentano [19] considered the cost of production and inventory at the production facility as well as consumers. Varthanan et al. [20] proposed IPDP model under stochastic demand. Gharehyakeh and Tavakkoli-Moghaddam [21] took into consideration the uncertainty of demand, machine and labor level with time windows. However, no study proposes a model integrating procurement - disassembly problem although these problems are interdependent due to their sequential decisions.

### 3 Problem Description

Before being disassembled, the EOL products are collected from suppliers to disassembly plant. Subsequently, the products are stored at the inventory and will be disassembled in order to release the demanded parts. A single vehicle and a product type are considered. The data concerning product collection and disassembly process are known and deterministic.

In this section, a mixed integer linear programming (MILP) model of integrated procurement-disassembly problem is presented. The problem is defined on weighted and undirected graph network $G = (N, E, D)$. $N$ is the set of node denoting the considered suppliers and the inventory of facility plant. This inventory is denoted as node 1. $E$ is the set of edges and $D_{ab}$ is the distance between node $a$ and node $b$ where $D_{ab} = D_{ba}$, $a \in N$, $b \in N$. The plant disassemblies a single product type during planning horizon $T$. A single vehicle with capacity $C$ and unit running cost $RC$ is used for collecting EOL products from suppliers. A supplier $a$ has certain amount of EOL products at period $t$ denoted as $S_{at}$. A single vehicle visits each supplier at most once for each period. The collected products are stored at the inventory with unlimited capacity where the inventory level at the end of period $t$ is denoted as $I_t$, $t \in T$.

At the beginning of period $t$, the disassembly process begins based on the required demand of part $l$ denoted by $d_{lt}$, $l \in L$, $t \in T$. Our model requires binary variable $d_{lt}^b$, $l \in L$, $t \in T$ which is equal to 1 if $d_{lt}$ is greater than 0. Since it is assumed that each product consists of exactly one part of type $l$, the minimum amount of products stored at inventory $d_{t}^{max}$, $t \in T$, before performing disassembly process at the beginning of period is the biggest amount for all required part at period $t$.

Our model adopts the AND/OR graph (AOG) in [16] where auxiliary node $A_k$, $k \in K$ represents subassembly and basic node $B_i$, $i \in I$ denotes disassembly task. The relations between subassemblies and disassembly tasks are presented in AOG. The dummy task $s$ is introduced to indicate that disassembly process at period $t$ is finished due to the consideration of partial disassembly. $P_k$ is the set of tasks which precedes subassembly $A_k$, $k \in K$. $S_k$, $k \in K$, denotes the set of tasks which succeeds $A_k$, $k \in K$. Our model requires the set of tasks which permits to release part $l$, $l \in L$, denoted as $P_l$.
Disassembly task times $time_i$ are known where the time of dummy task s, $time_s$ is 0. At period t, each required disassembly is assigned to a workstation. Workstation time is less than the given cycle time $CT$. $FC$ denotes the fixed cost of opening a workstation. In our model, the decision variables are:

- $I_t$ inventory level at the end of period t;

- $Y_{at}$ cumulative load of vehicle after visiting node a at period t;

- $X_{abt} = \begin{cases} 1 & \text{if the vehicle visits node a just before node b at period t;} \\ 0 & \text{otherwise.} \end{cases}$

- $x_{ijt} = \begin{cases} 1 & \text{if disassembly task i is assigned to workstation j at period t;} \\ 0 & \text{otherwise.} \end{cases}$

- $z_{jt} = \begin{cases} \text{CT if } x_{sjt} = 1; \\ 0 & \text{otherwise.} \end{cases}$

$$ \textbf{Minimize} \quad Z = RC \sum_{t \in T} \sum_{b \in N} \sum_{a \in N} D_{ab} \cdot X_{abt} + FC \sum_{t \in T} \sum_{j \in J} j \cdot z_{jt} \quad (1) $$

Subject to:

$$ I_t = I_{t-1} + \sum_{b \in N} \sum_{a \in N \setminus \{1\}} X_{abt} \cdot S_{at} - d_t^{max} \quad \forall t \in T, a \neq b; \quad (2) $$

$$ \sum_{a \in N} X_{abt} \leq 1 \quad \forall b \in N \setminus \{1\}, \forall t \in T, a \neq b; \quad (3) $$

$$ \sum_{a \in N} X_{act} = \sum_{b \in N} X_{cbt} \quad \forall c \in N, \forall t \in T, c \neq a, c \neq b; \quad (4) $$

$$ \sum_{a \in S} \sum_{b \in S} X_{abt} \leq |S| - 1 \quad \forall t \in T, \forall S \subseteq N \setminus \{1\} : |S| \geq 2; \quad (5) $$

$$ Y_{bt} - S_{bt} - Y_{at} \geq - \left( \sum_{l \in L} d_{lt} \right) \cdot (1 - X_{abt}) \quad \forall a \in N, \forall b \in N \setminus \{1\}, \forall t \in T, a \neq b; \quad (6) $$

$$ Y_{bt} - S_{bt} - Y_{at} \leq \left( \sum_{l \in L} d_{lt} \right) \cdot (1 - X_{abt}) \quad \forall a \in N, \forall b \in N \setminus \{1\}, \forall t \in T, a \neq b; \quad (7) $$

$$ Y_{at} \leq C \quad \forall a \in N, \forall t \in T; \quad (8) $$

$$ Y_{1t} = 0 \quad \forall t \in T; \quad (9) $$

$$ \sum_{j \in J} \sum_{i \in P_l} x_{ijt} \geq d_{lt}^b \quad \forall l \in L, t \in T; \quad (10) $$

$$ \sum_{j \in J} \sum_{i \in S_0} x_{ijt} = 1 \quad \forall t \in T; \quad (11) $$
$$ \sum_{j \in J} x_{ijt} \le 1 \qquad \forall i \in I, \forall t \in T; \qquad (12) $$

$$ \sum_{i \in S_k} x_{ivt} \le \sum_{i \in P_k} \sum_{j=1}^{v} x_{ijt} \qquad \forall k \in K \setminus \{0\}, \forall v \in J, \forall t \in T; \qquad (13) $$

$$ \sum_{i \in S_k} \sum_{j \in J} x_{ijt} \le \sum_{i \in P_k} \sum_{j \in J} x_{ijt} \qquad \forall k \in K \setminus \{0\}, \forall t \in T; \qquad (14) $$

$$ \sum_{j \in J} x_{sjt} = 1 \qquad \forall t \in T; \qquad (15) $$

$$ \sum_{j \in J} j \cdot x_{ijt} \le \sum_{j \in J} j \cdot x_{sjt} \qquad \forall i \in I, \forall t \in T; \qquad (16) $$

$$ z_{jt} = CT \cdot x_{sjt} \qquad \forall j \in J, \forall t \in T; \qquad (17) $$

$$ \sum_{i \in I} x_{ijt} \cdot time_i \le CT \qquad \forall j \in J, \forall t \in T; \qquad (18) $$

$$ I_t \ge 0 \qquad \forall t \in T; \qquad (19) $$

$$ X_{abt} \in \{0, 1\} \qquad \forall a \in N, \forall b \in N, \forall t \in T, a \neq b; \qquad (20) $$

$$ Y_{at} \ge 0 \qquad \forall a \in N, \forall t \in T; \qquad (21) $$

$$ x_{sjt}, x_{ijt} \in \{0, 1\} \qquad \forall i \in I, \forall j \in J, \forall t \in T; \qquad (22) $$

$$ z_{jt} \in \{0, CT\} \qquad \forall j \in J, \forall t \in T; \qquad (23) $$

The objective function (1) aims to minimize the total cost consisting to-tal procurement cost and total cost of opening workstations for entire planning horizon. Constraint set (2) balances the plant inventory at each period. At each period, constraint set (3) imposes that each supplier is visited at most once. Constraint set (4) guarantees that the vehicle leaves a node after visiting it. Constraint set (5) eliminates the subtour occurrence. Constraint sets (6–7) up-date the vehicle load after visiting a node at each period. Constraint set (8) limits the vehicle load during its trips. After leaving the plant as depot of the trip, constraint set (9) resets the vehicle load as zero. Constraints sets (10) describe the relation between part demand and its predecessors. Constraint sets (11–18) are simplification of the model in [12]. Constraint set (11) selects the first tasks succeeding EOL product. Constraint set (12) assigns the disassembly task into at most a workstation. The precedence relations between disassembly tasks and subassemblies are described by constraint set (13). Constraint set (14) selects only one OR successor. Constraint set (15) assigns sink node into a workstation. Constraint set (16) guarantees that each disassembly task is assigned into a workstation with lower or equal index of sink node’s workstation. The value of $z_{jt}$ is determined by constraints set (17). Constraint set (18) denotes the limitation of workstation time. Constraint sets (19–23) describe the nature of decision variables.
## 4 Computational Results

Since no benchmark instance exists for our problem, we considered the following example based on [13]. A compass consisting seven parts is studied. Ten tasks permits to release one or some parts. At first period, the plant has 20 products available in the inventory. The cycle time is 0.61 second. The opening cost of workstation is 7 euros/second. A vehicle with 5000 capacity is used with running cost as 5 euro/km. Table 1 and 2 present the data of demand, part and supplier.

<table><caption>Table 1. Part and Demand Data</caption><thead><tr><th rowspan="2">Part</th><th rowspan="2">Predecessor</th><th colspan="4">Demand(*1000)</th></tr><tr><th>t = 1</th><th>t = 2</th><th>t = 3</th><th>t = 4</th></tr></thead><tbody><tr><td>1</td><td>3,5,7,9</td><td>2</td><td>6</td><td>2</td><td>2</td></tr><tr><td>2</td><td>7,9</td><td>0</td><td>3</td><td>6</td><td>0</td></tr><tr><td>3</td><td>3,9,10</td><td>4</td><td>0</td><td>5</td><td>2</td></tr><tr><td>4</td><td>2,4,8</td><td>1</td><td>4</td><td>0</td><td>1</td></tr><tr><td>5</td><td>2,4,8</td><td>2</td><td>7</td><td>3</td><td>7</td></tr><tr><td>6</td><td>1,6,10</td><td>0</td><td>1</td><td>0</td><td>0</td></tr><tr><td>7</td><td>1,6,10</td><td>4</td><td>2</td><td>6</td><td>2</td></tr></tbody></table>

The model was implemented in Java 7 using GNU Linear Programming Kit (GLPK) 4.9 on a PC with processor Intel® Core™ i7 CPU 2.9 GHz and 4 Go RAM under Windows 7 Professional.

<table><caption>Table 2. Supplier Data</caption><thead><tr><th rowspan="2">Node</th><th colspan="2">Coordinate</th><th colspan="4">Supply(*1000)</th></tr><tr><th>X</th><th>Y</th><th>t = 1</th><th>t = 2</th><th>t = 3</th><th>t = 4</th></tr></thead><tbody><tr><td>Depot</td><td>30</td><td>40</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Supplier 1</td><td>37</td><td>52</td><td>1</td><td>1</td><td>4</td><td>4</td></tr><tr><td>Supplier 2</td><td>49</td><td>49</td><td>5</td><td>3</td><td>1</td><td>1</td></tr><tr><td>Supplier 3</td><td>52</td><td>64</td><td>4</td><td>1</td><td>2</td><td>2</td></tr><tr><td>Supplier 4</td><td>20</td><td>26</td><td>1</td><td>1</td><td>3</td><td>3</td></tr></tbody></table>

The optimal solution is obtained in 85.25 seconds with the total cost 1232.83 euros. Only 2 workstations are opened during four periods considered. The vehicle's trips and disassembly tasks assignment are presented in table 3 and 4, respectively.

## 5 Conclusion

This work addresses integrated procurement-disassembly problem. It combines w-VRP and DLBP for collecting and disassembling the EOL product. A capacitated vehicle collects EOL product from suppliers. The vehicle begins its trip
<table><caption>**Table 3. Vehicle Trip**</caption><thead><tr><th rowspan="2">Vehicle Trip</th><th colspan="4">Period</th></tr><tr><th>1</th><th>2</th><th>3</th><th>4</th></tr></thead><tbody><tr><td>First trip</td><td>1, 4, 2, 1</td><td>1, 3, 1</td><td>1, 2, 1</td><td>1, 2, 1</td></tr><tr><td>Second trip</td><td>1, 3, 1</td><td>-</td><td>1, 4, 1</td><td>-</td></tr></tbody></table>

<table><caption>**Table 4. Task Assignment**</caption><thead><tr><th rowspan="2">Workstation</th><th colspan="4">Period</th></tr><tr><th>1</th><th>2</th><th>3</th><th>4</th></tr></thead><tbody><tr><td>1</td><td>2,6</td><td>1</td><td>1</td><td>2,6</td></tr><tr><td>2</td><td>9</td><td>4,9</td><td>4,9</td><td>9</td></tr></tbody></table>

with zero load. Its capacity forces the vehicle to return back into the inventory for disposing its load. If the inventory level of EOL products is sufficient, the disassembly process begins releasing the demanded parts. The proposed model considers partial DLBP under deterministic condition with single product type.

The objective function minimizes the total cost of product collection and disassembly process through vehicle routing determination and disassembly task assignment. The model takes into account the constraints of DLBP, w-VRP and the balancing constraints coordinating these problems.

Some prospects concerning the proposed model are derived in order to approach the reality. For the next step, the model should be extended to the case of multiple products and multiple vehicles. Then, it should be tested on the industrial data. Moreover, since the uncertainty is major in disassembly process as well as EOL products collection, this factor has to be taken into account.

## Acknowledgement

This work has been supported by Région Rhône-Alpes, France.

## References

1. Sasikumar, P., Kannan, G.: Issues in Reverse Supply Chains, Part I: End-of-Life Product Recovery and Inventory Management-an Overview. International Journal of Sustainable Engineering. 1, 154-172 (2008)

2. Yang, G., Wang, Z., Li, X.: The Optimization of the Closed-Loop Supply Chain Network. Transportation Research Part E: Logistics and Transportation Review. 45, 16-28 (2009)

3. Ilgin, M.A., Gupta, S.M.: Performance Improvement Potential of Sensor Embedded Products in Environmental Supply Chains. Resources, Conservation and Recycling. 55, 580-592 (2011)

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

5. Boudia, M., Dauzere-Peres, S., Prins, C., Louly, M.A.O.: Integrated Optimization of Production and Distribution for Several Products. In: International Conference on Service Systems and Service Management 2006, pp. 272 - 277. Troyes (2006)
6. Boudia, M., Louly, M.A.O., Prins, C.: A Reactive GRASP and Path Relinking for a Combined Production-Distribution Problem. Computers & Operations Research. 34, 3402-3419 (2007)

7. Boudia, M., Prins, C: A Memetic Algorithm with Dynamic Population Management for an Integrated Production-Distribution Problem. European Journal of Operational Research. 195, 703-715 (2009)

8. Bard, J.F., Nananukul, N.: A Branch-and-Price a Algorithm for an Integrated Production and Inventory Routing Problem. Computers & Operations Research. 37, 2202-2217 (2010)

9. Dolgui, A., Proth, J.: Supply Chain Engineering: Useful Methods and Techniques. Springer, London (2010)

10. Bentaha, M.L., Battaïa, O., Dolgui, A.: A Decomposition Method for Stochastic Partial Disassembly Line Balancing with Profit Maximization. IEEE International Conference on Automation Science and Engineering 2013. 404-409 (2013)

11. Bentaha, M.L., Battaïa, O., Dolgui, A.: A Sample Average Approximation Method for Disassembly Line Balancing Problem under Uncertainty. Computers & Operations Research. 51, 111-122 (2014)

12. Bentaha, M.L., Battaïa, O., Dolgui, A.: L-Shaped Algorithm for Stochastic Disassembly Line Balancing Problem. In: 7th IFAC Conference on Modelling, Management, and Control, pp. 407-411. Saint Petersburg (2013)

13. Bentaha, M.L., Battaïa, O., Dolgui, A.: A Stochastic Formulation of The Disassembly Line Balancing Problem. In: Emmanouilidis, C., Taisch, M., Kiritsis, D. (eds.) APMS 2012. IFIP AICT, vol. 397, pp. 397-404. Springer, Heidelberg (2013)

14. Bentaha, M.L., Battaïa, O., Dolgui, A.: Chance Constrained Programming Model for Stochastic Profit-Oriented Disassembly Line Balancing in the Presence of Hazardous Parts. In: Prabhu, V., Taisch, M., Kiritsis, D. (eds.) APMS 2013. IFIP AICT, vol. 414, pp. 103-110. Springer, Heidelberg (2013)

15. Bentaha, M.L., Battaïa, O., Dolgui, A.: Dealing with Uncertainty in Disassembly Line Design. CIRP Annals - Manufacturing Technology. 63, 21-24 (2014)

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

17. Özceylan, E., Paksoy, T., Bektaş, T.: Modeling and Optimizing the Integrated Problem of Closed-Loop Supply Chain Network Design and Disassembly Line Balancing. Transportation Research Part E: Logistics and Transportation Review. 61, 142-164 (2014)

18. Özceylan, E., Paksoy, T.: Interactive fuzzy programming approaches to the strategic and tactical planning of a closed-loop supply chain under uncertainty. International Journal of Production Research. 1-25 (2013)

19. Shiguemoto, A., Armentano, V.A.: A Tabu Search Procedure for Coordinating Production, Inventory and Distribution Routing Problems. International Transactions in Operational Research. 17, 179-195 (2010)

20. Varthanan, P.A., Murugan, N., Kumar, G.M.: A Simulation Based Heuristic Discrete Particle Swarm Algorithm for Generating Integrated Production-Distribution Plan. Applied Soft Computing. 12, 3034-3050 (2012)

21. Gharehyakheh, A., Tavakkoli-Moghaddam, R.: A Fuzzy Solution Approach for A Multi-objective Integrated Production-Distribution Model with Multi Products and Multi Periods Under Uncertainty. Management Science Letters. 2, 2425-2434 (2012)