Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.44 No.2 pp.24-35
DOI : https://doi.org/10.11627/jkise.2021.44.2.024

A Heuristic for Service-Parts Lot-Sizing with Disassembly Option

Jin-Myeong Jang^*

, Hwa-Joong Kim^*†

, Dong-Hoon Son^**

, Dong-Ho Lee^***

^*Graduate School Logistics, Inha University
^**Department of Civil Engineering, The Hong Kong University of Science and Technology
^***Department of Industrial Engineering, Hanyang University, Korea

^†Corresponding Author : hwa-joong.kim@inha.ac.kr

Received 06/05/2021 Finally Revised 28/05/2021 Accepted 31/05/2021

Abstract

Due to increasing awareness on the treatment of end-of-use/life products, disassembly has been a fast-growing research area of interest for many researchers over recent decades. This paper introduces a novel lot-sizing problem that has not been studied in the literature, which is the service-parts lot-sizing with disassembly option. The disassembly option implies that the demands of service parts can be fulfilled by newly manufactured parts, but also by disassembled parts. The disassembled parts are the ones recovered after the disassembly of end-of-use/life products. The objective of the considered problem is to maximize the total profit, i.e., the revenue of selling the service parts minus the total cost of the fixed setup, production, disassembly, inventory holding, and disposal over a planning horizon. This paper proves that the single-period version of the considered problem is NP-hard and suggests a heuristic by combining a simulated annealing algorithm and a linear-programming relaxation. Computational experiment results show that the heuristic generates near-optimal solutions within reasonable computation time, which implies that the heuristic is a viable optimization tool for the service parts inventory management. In addition, sensitivity analyses indicate that deciding an appropriate price of disassembled parts and an appropriate collection amount of EOLs are very important for sustainable service parts systems.

Key Words : Service Parts Logistics , Reverse Supply Chain , Lot-Sizing , Disassembly , Simulated Annealing

분해옵션 포함 서비스부품 로트사이징 휴리스틱

장 진명^*, 김 화중^*†, 손 동훈^**, 이 동호^***

^*인하대학교 물류전문대학원
^**홍콩과학기술대학교 토목환경공학과
^***한양대학교 산업공학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1. Introduction

Due to increasing awareness on the treatment of end-ofuse/ life products (EOLs), disassembly has been a fast-growing research area of interest for many researchers over recent decades. Disassembly is the environmental process of retrieving and recovering valuable parts or components from EOLs that are returned from end users. Due to its importance, major car makers such as BMW and Volkswagen operate sustainable disassembly processes within their companies. IBM also operates the disassembly process to obtain service parts through disassembling returned EOLs such as PCs, large computers, network servers, and printers [3].

This paper addresses a service-parts lot-sizing problem with the disassembly option (SLSD). Lot-sizing is a midterm production planning to determine production quantity or lot size and production timing over a planning horizon. In the SLSD, the demand for the service parts can be satisfied by newly manufactured parts, but also by disassembled parts. The disassembled parts are the ones that are recovered through recovery operations such as test and upgrade operations after the disassembly of EOLs, as depicted in <Figure 1>. Returned EOLs are kept in inventory, valuable (non-defective) parts are retrieved through disassembly and recovery operations, while defective parts are disposed of. The SLSD was motivated from Fleischmann et al. [3] that addressed the IBM cases. Research areas closely related to the SLSD are disassembly lot-sizing and lot-sizing with remanufacturing option. The two problems are the special case of the SLSD in the problem setting.

The literature on the disassembly lot-sizing, called as disassembly scheduling in the literature, has been growing in recent decades. From a modelling point of view, the key difference from the conventional lot-sizing is the existence of the multiple demand source of parts taken from the disassembly of EOLs. This characteristic of the multiple demand source in the problem is called the divergence characteristic, i.e., a divergence of EOLs into multiple parts/components [14]. The literature on the disassembly lot-sizing can be classified by the existence of parts commonality implying that a product and subassembly shares parts or components. For the case without parts commonality, Gupta and Taleb [8] suggested a reverse MRP procedure. Lee and Xirouchakis [18] proposed a two-phase heuristic for the objective of minimizing the costs related to disassembly operations. Kim et al. [13] suggested a polynomial algorithm for the two-level disassembly problem. Kim et al. [16] proved that the multi- level disassembly lot-sizing problem is NP-hard and suggested a branch and bound algorithm. For the case with parts commonality, Taleb and Gupta [28] and Taleb et al. [29] proposed reverse MRP heuristic. Neuendorf et al. [23] proposed a Petri-net based heuristic. Kim et al. [17] suggested a heuristic algorithm based on a linear programming relaxation. Lee et al. [21] suggested integer programs which are the reverse version of the multi-level lot-sizing model. Kim et al. [15] proposed a two-phase heuristic by extending the algorithm of Kim et al. [17]. Langella [19] extended the heuristic of Taleb and Gupta [28] by considering a purchase quantity limit and disposal options. Finally, several literatures considered the resource capacity restrictions [9, 10, 12, 18, 22] and random demand [11], and recently extended the problem to economic order quantity models, namely economic disassembly quantity models [5, 6, 27].

Along with the disassembly lot-sizing, the literature on the lot-sizing with remanufacturing option has been also growing in recent decades. Remanufacturing is another environmental process of recovering EOLs almost up to the level of newly produced products. The key characteristics of the lot-sizing with remanufacturing option is that the demand can be satisfied by producing new products and/or by remanufacturing EOLs. Golany et al. [7] proved the NP-hardness of the problem with general concave costs and solved the problem as a dynamic programming (DP). Teunter et al. [30] considered two different setup-cost cases: a joint setup cost for manufacturing and remanufacturing; and separated setup costs. They suggested a polynomial-time DP algorithm for the problem with a time-invariant joint-setup cost and has shown that the problem with separated setup costs is NP-hard. Yang et al. [31] also proved that the problem with concave costs is NP-hard. Pan et al. [24] has shown that the problem with disposal or remanufacturing is convertible to a capacitated lot-sizing problem and polynomially solvable if the capacity is constant. Pineyro and Viera [25] suggested a Tabu-search heuristic for the problem with one-way substitution implying that the demand for remanufactured products can be fulfilled by new products, but not vice versa. Heuristics or reformulations have been suggested by Baki et al. [2], Sifaleras and Konstantara [26], and Attila et al. [1].

In this paper, we aim to contribute to the literature by addressing the SLSD that no previous literatures have studied to the best of our knowledge. Specifically, we consider the SLSD with the two-level disassembly structure and parts commonality. The two-level structure defined in <Figure 2> implies that there is no intermediate subassembly between EOLs and parts in the disassembly product structure. From a modeling point of view, the lot-sizing with remanufacturing option is a special case of the SLSD, and hence SLSD is also NP-hard according to the above literature review. However, we prove in this paper that even the single-period problem of the SLSD is NP-hard. In addition, we suggest an efficient heuristic by combining a simulated annealing algorithm and a linear-programming relaxation approach. Finally, we observe some meaningful insights through sensitivity analyses.

In the next section, we present first a detailed explanation of the problem and then an integer programming model. In Sections 3, we present the NP-hardness of the problem and the solution algorithm. We then present the results of computational experiments in Section 4, which evaluates the performance of the suggested heuristic and sensitivity to input parameters. Finally, we conclude with some key remarks and potential future studies.

2. Problem description

In this section, we first introduce the disassembly product structure and define the SDSL. We then provide the integer programming model.

The SLSD is based on a two-level disassembly product structure, in which the first level represents EOLs to be disassembled and the second level does a set of parts obtained from disassembling the EOLs. This means that there are no intermediate subassemblies in the structure. The two-level disassembly product structure has been considered in the literature [5, 6, 11, 13, 19, 27]. <Figure 2> shows an example of the two-level disassembly product structure. In the figure, three EOLs are disassembled into five different parts 1, 2, 3, 4, and 5, i.e., EOL 1 is disassembled to parts 1, 2, and EOL 3 to parts 4, 5. In parentheses (a, b), a represent the total unit obtained from disassembling one unit of an EOL if no defectives exist, and b represents non-defective units out of a. For example, EOL 2 is disassembled into two units of part 1 as its total unit and one unit as its non-defective unit. Defective parts are sorted out and disposed of by paying disposal costs. It is assumed that non-defective parts are fully recovered up to the resalable state through remanufacturing processes. The shaded parts are common items, i.e., part 4 can be obtained from disassembling EOL 1 or 4. It is also assumed that the same parts are substitutable for each other with different prices when fulfilling the demand of that part. That is, part 2 in the set of new parts and part 2 in the set of disassembled parts are the same parts and hence they can be used to meet the demand of part 2.

Now, the SLSD is formally defined as follows: for a given two-level disassembly structure, the problem is to determine the quantity and period of producing new service parts and disassembling parts from returned EOLs. The objective is to maximize the total profit, i.e., the revenue of selling the service parts minus the cost of production setup, disassembly setup, production, disassembly, inventory holding, and disposal generated over a planning horizon. The revenue is gained from selling the new and disassembled service parts. There are two types of setup costs: production setup and disassembly setup costs. The production (disassembly) setup cost is a fixed cost incurred in a period if any production (disassembly) is performed in that period. The production cost is the cost of producing new service parts varying with the production quantity while the disassembly cost is the variable cost of disassembling EOLs and recovering parts. The inventory holding cost occurs if parts or EOLs are stocked to satisfy future demands and they are counted based on the end-of-period stock level. The disposal cost is the cost incurred for disposing of defects leftover from a disassembly process.

The notations used in the integer program are summarized below.

Set

Ω_i set of parent EOLs of part i
E set of EOLs
P set of service parts
T set of periods

Parameters

a_ei total number of units of part i taken from disassembling one unit of EOL e
b_ei non-defectives out of a_ei
$c_{i}^{N}$ unit production cost of new service part i
$c_{e}^{D}$ unit disassembly cost of EOL e
d_it demand of service part i in period t
$h_{i}^{N}$ unit inventory holding cost of new service part i
$h_{i}^{D}$ unit inventory holding cost of disassembled service part i
$h_{e}^{R}$ unit inventory holding cost of EOL e
M arbitrarily large number
$p_{i}^{N}$ unit revenue of new service part i
$p_{i}^{D}$ unit revenue of disassembled service part i
r_et returned amount of EOL e in period t
$s_{i}^{N}$ production setup cost of new service part i
$s_{e}^{D}$ disassembly setup cost of EOL e
w_i unit disposal cost of part i

Decision variables

D_it sales amount of disassembled service part i in period t
$I_{i t}^{N}$ inventory level of new service part i at the end of period t
$I_{i t}^{D}$ inventory level of disassembled service part i at the end of period t
$I_{e t}^{R}$ inventory level of EOL e at the end of period t
N_it sales amount of new service part i in period t
W_it disposed amount of part i in period t
$X_{i t}^{N}$ production amount of new service part i in period t
$X_{e t}^{D}$ disassembly amount of EOL e in period t
$Y_{i t}^{N}$ equals 1 if any production of new service part i occurs in period t and zero, otherwise
$Y_{e t}^{D}$ equals 1 if any disassembly of EOL e occurs in period t and zero, otherwise

The integer programming model for the SLSD is as follows.

[P] Maximize

\begin{array}{l} \sum_{i \in P} \sum_{t \in T} p_{i}^{N} N_{i t} + \sum_{i \in P} \sum_{t \in T} p_{i}^{D} D_{i t} - \sum_{i \in P} \sum_{t \in T} s_{i}^{N} Y_{i t}^{N} - \sum_{e \in E} \sum_{t \in T} s_{e}^{D} Y_{e t}^{D} \\ - \sum_{i \in P} \sum_{t \in T} c_{i}^{N} X_{i t}^{N} - \sum_{e \in E} \sum_{t \in T} c_{e}^{D} X_{e t}^{D} - \sum_{i \in P} \sum_{t \in T} h_{i}^{N} I_{i t}^{N} \\ - \sum_{i \in P} \sum_{t \in T} h_{i}^{D} I_{i t}^{D} - \sum_{e \in E} \sum_{t \in T} h_{e}^{R} I_{e t}^{R} - \sum_{i \in P \cup W} \sum_{t \in T} w_{i} W_{i t} \end{array}

subject to

\begin{matrix} N_{i t} + D_{i t} = d_{i t} & \forall i \in P, t \in T \end{matrix}

(1)

\begin{matrix} I_{i t}^{N} = I_{i, t - 1}^{N} + X_{i t}^{N} - N_{i t} & \forall i \in P, t \in T \end{matrix}

(2)

\begin{matrix} I_{i t}^{D} = I_{i, t - 1}^{D} + \sum_{e \in Ω_{i}} b_{e i} X_{e t}^{D} - D_{i t} & \forall i \in P, t \in T \end{matrix}

(3)

\begin{matrix} I_{e t}^{R} = I_{e, t - 1}^{R} + r_{e t} - X_{e t}^{D} & \forall e \in E, t \in T \end{matrix}

(4)

\begin{matrix} X_{i t}^{N} \leq M \cdot Y_{i t}^{N} & \forall i \in P, t \in T \end{matrix}

(5)

\begin{matrix} X_{e t}^{D} \leq M \cdot Y_{e t}^{D} & \forall e \in E, t \in T \end{matrix}

(6)

\begin{matrix} W_{i t} = \sum_{e \in Ω_{i}} (a_{e i} - b_{e i}) X_{e t}^{D} & \forall i \in P, t \in T \end{matrix}

(7)

\begin{matrix} N_{i t}, D_{i t}, I_{i t}^{N}, I_{i t}^{D}, X_{i t}^{N}, W_{i t} \geq 0 & \forall i \in P, t \in T \end{matrix}

(8)

\begin{matrix} X_{e t}^{D} \geq 0 and integer & \forall e \in E, t \in T \end{matrix}

(9)

\begin{matrix} Y_{i t}^{N}, Y_{e t}^{D} \in {0, 1} & \forall i \in P, e \in E, t \in T \end{matrix}

(10)

The objective function denotes maximizing the total profit, i.e., revenues minus setup, production, disassembly operation, inventory holding, and disposal costs. Constraint (1) represents that the demand is fulfilled by selling the new and/or disassembled service parts. Constraints (2)~(4) represent the inventory flow conservation that defines the inventory level at the end of each period of new service parts, disassembled parts, and EOLs, respectively. Constraints (5) and (6) guarantee that a setup cost in a period is incurred if there is any production or disassembly operation at that period. Constraint (7) determines the amount of defective parts. Finally, the other constraints (8)~(10) are the conditions on the decision variables.

3. NP-Hardness and Heuristic Algorithm

As described above, the lot-sizing with remanufacturing option from a modeling point of view is a special case of the SLSD, and hence SLSD is also NP-hard. However, we prove here that even the single-period problem of the SLSD is NP-hard.

Proposition 1.The single-period problem of the SLSD [P] is NP-hard.

Proof. The decision version of the integer knapsack problem is NP-Complete [4]. We show that the integer knapsack problem is a special case of problem [P]. Define an instance of problem [P] with EOLs, 1, 2, … n, one part (indexed n+1), the number of periods |T| = 1 where |Ÿ| is the cardinality of set Ÿ, and no new service part. The yield rate of part n+1 from all EOLs is set to one, and the return amount is infinite. The revenue, the setup cost, the inventory holding cost, and the disposal cost are set to zero. Finally, the rest is the same as problem [P]. For a clear definition, the model of the instance problem is given as follows.

[I1] Minimize $\sum_{i = 1}^{n} c_{i}^{D} X_{i 1}^{D}$

subject to

I_{n + 1, 1}^{D} = I_{n + 1, 0}^{D} + \sum_{j = 1}^{n} b_{i}, N + 1 X_{i 1}^{D} - d_{n + 1, 1}

(11)

I_{i t}^{D} \geq 0

(12)

X_{i t}^{D} \geq 0 and integer

(13)

Integrating (11) and (12) results in

[I2] Minimize $\sum_{i = 1}^{n} c_{i}^{R} X_{i 1}^{D}$

subject to $\sum_{j = 1}^{n} b_{i, n + 1} X_{i 1}^{D} \geq d_{n + 1, 1} - I_{n + 1, 0}^{D}$ and (13).

The model [I2] is clearly the same as the model of the integer knapsack problem. This completes the proof. ■

Since the SLSD is NP-hard, we try to focus on developing an efficient heuristic. The following subsections present an overview of the simulated annealing (SA) algorithm and the method of generating an initial solution and neighborhood solutions.

3.1 Overview of the SA Algorithm

An initial solution is generated using the linear programming (LP) relaxation approach in Section 3.2 and it is set to a current solution. Then, the SA algorithm generates a new neighborhood solution of the current solution using the method in Section 3.3. The move to the new neighborhood solution is accepted if the solution is improved. Otherwise, the moving is accepted with a probability controlled by a temperature. As in many SA algorithms, our SA algorithm starts with a high initial temperature decreased by a certain rule called the cooling schedule. The temperature is kept at the same for some iterations called the epoch length. The epoch length L is set to $α | T | (| T | - 1) / 2$ where α is a parameter. The initial temperature t₀ is set as $t_{0} = - Δ / ln F_{0}$ where Δ is the average increase in the objective value obtained after |T| moves and F₀ is a parameter to be determined. The temperature at the k-th epoch is set as $t_{k} = β \cdot t_{k - 1}$ where β is a parameter called the cooling ratio. The SA algorithm is terminated if the best solution is not updated for a certain iteration Q.

3.2 Initial Solution Generation

The initial solution for the SA algorithm is generated through the LP relaxation approach. That is, the integer program [P] is solved using a commercial optimization solver like CPLEX after relaxing constraints (5), (6), (9), and (10). The obtained LP solution (real values) is then rounded down. The rounded-down solution is modified so as to obtain a good feasible solution while considering the profit changes.

For the modification, we first define balance as follows.

Definition 1. Based on the rounded-down solution, the balances ( $B_{i t}^{S}$ , $B_{i t}^{N}$ , $B_{i t}^{D}$ , B_et ) are defined as

\begin{array}{l} \begin{matrix} B_{i t}^{S} = N_{i t} + D_{i t} - d_{i t} & \forall i \in P, t \in T \end{matrix} \\ \begin{matrix} B_{i t}^{N} = I_{i t}^{N} - I_{i, t - 1}^{N} - X_{i t}^{N} + N_{i t} & \forall i \in P, t \in T \end{matrix} \\ \begin{matrix} B_{i t}^{D} = I_{i t}^{D} - I_{i, t - 1}^{D} - \sum_{e \in Ω_{i}} b_{e i} X_{e t}^{D} + D_{i t} & \forall i \in P, t \in T \end{matrix} \\ \begin{matrix} B_{e t} = I_{e t}^{R} - I_{e, t - 1}^{R} - r_{e t} + X_{e t}^{D} & \forall e \in E, t \in T \end{matrix} \end{array}

The balances defined above are used to check the feasibility of the rounded-down solution. More specifically, constraints (1)-(4) are feasible if and only if the balances equal zero where the rounded-down solution is used to calculate the balances. If a balance is non-zero, the corresponding rounded-down solution should be modified. The solution is modified by considering decision variables and the sign of the balance (positive and negative). We explain here only the method for the cases with a positive sign, i.e., $B_{i t}^{S}, B_{i t}^{N}, B_{i t}^{D}, B_{e t} > 0$ since negative sign cases can be considered easily by reversing positive sign cases.

Case 1 : Positive EOL balance caseB_et > 0. We start from the EOL, i.e., the method for the B_et > 0 case. In order to satisfy constraint (4), decreasing the values of $X_{e t}^{D}$ and/or $I_{e t}^{R}$ is needed while considering the profit increase defined as

α_{e t} = {\begin{cases} \begin{matrix} \begin{matrix} c_{e}^{D} B_{e t} + s_{e}^{D} θ_{e t} + \sum_{i \in Φ_{e}} (a_{e i} - b_{e i}) w_{i} B_{e t} \\ + \sum_{i \in Φ_{e}} (| T | - t + 1) b_{e i} h_{i}^{D} B_{e t} \end{matrix} & if I_{e t}^{R} \geq B_{e t} \end{matrix} \\ \begin{matrix} \begin{matrix} c_{e}^{D} X_{e t}^{D} + s_{e}^{D} + \sum_{i \in Φ_{e}} (a_{e i} - b_{e i}) w_{i} X_{e t}^{D} \\ \begin{array}{l} + \sum_{i \in Φ_{e}} (| T | - t + 1) b_{e i} h_{i}^{D} X_{e t}^{D} \\ + (| T | - 1 + 1) (B_{e t} - X_{e t}^{D}) h_{e}^{R} \end{array} \end{matrix} & otherwise \end{matrix} \end{cases}

β_{e t} = {\begin{array}{l} (| T | - t + 1) h_{e}^{R} B_{e t} & if I_{e t}^{R} \geq B_{e t} \\ \begin{array}{l} (| T | - t + 1) h_{e}^{R} I_{e t}^{R} + c_{e}^{D} (B_{e t} - I_{e t}^{R}) + s_{e}^{D} θ_{e t} \\ + \sum_{i \in Φ_{e}} (a_{e i} - b_{e i}) (B_{e t} - I_{e t}^{R}) w_{i} \\ + \sum_{i \in Φ_{e}} (| T | - t + 1) (B_{e t} - I_{e t}^{R}) b_{e i} h_{i}^{D} \end{array} & otherwise \end{array}

where θ_et = 1 if $X_{e t}^{D}$ = B_et and 0 otherwise, and |T| is the cardinality of set T. Here, α_et and β_et denote the amount of profit increase when $X_{e t}^{D}$ and $I_{e t}^{R}$ are decreased up to ${X^{'}}_{e t}^{D}$ and ${I^{'}}_{e t}^{R}$ , respectively, defined as

\begin{array}{l} {X^{'}}_{e t}^{D} = {\begin{array}{l} X_{e t}^{D} - B_{e t} & if X_{e t}^{D} \geq B_{e t}, \\ 0 & o t h e r w i s e \end{array} \\ {I^{'}}_{e t}^{R} = {\begin{array}{l} I_{e t}^{R} - B_{e t} & if I_{e t}^{R} \geq B_{e t} . \\ 0 & o t h e r w i s e \end{array} \end{array}

We select the choice with more profit increase, i.e., $Δ_{e t} = m a x {α_{e t}, β_{e t}}$ . The balance B_et is updated into new balance B′_et defined below, and this routine continues until the balance becomes zero.

{B^{'}}_{e t} = {\begin{array}{l} B_{e t} - X_{e t}^{D} & if X_{e t}^{D} < B_{e t} and Δ_{e t} = α_{e t} \\ B_{e t} - I_{e t}^{D} & if I_{e t}^{D} < B_{e t} and Δ_{e t} = β_{e t} \\ 0 & o t h e r w i s e \end{array}

Case 2 : Positive disassembled-part balance case $B_{i t}^{D}$ > 0. Like Case 1, we consider decreasing the value of D_it and/or $I_{i t}^{D}$ to satisfy constraint (3). The profit increase is defined as

α_{i t} = {\begin{array}{l} p_{i}^{N} B_{i t}^{D} - p_{i}^{D} B_{i t}^{D} & if D_{i t} \geq B_{i t}^{D} \\ + (| T | - t + 1) h_{i}^{N} B_{i t}^{D} & and I_{i t}^{N} \geq B_{i t}^{D} \\ p_{i}^{N} B_{i t}^{D} - p_{i}^{D} B_{i t}^{D} + (| T | - t + 1) h_{i}^{N} I_{i t}^{N} & if D_{i t} \geq B_{i t}^{D} \\ - c_{i}^{N} (B_{i t}^{D} - I_{i t}^{N}) - s_{i}^{N} θ_{i t} & and I_{i t}^{N} < B_{i t}^{D} \\ p_{i}^{N} D_{i t} - p_{i}^{D} D_{i t} & if D_{i t} < B_{i t}^{D} \\ + (| T | - t + 1) (h_{i}^{N} D_{i t} + h_{i}^{D} (B_{i t}^{D} - D_{i t})) & and I_{i t}^{N} \geq D_{i t} \\ \begin{array}{l} p_{i}^{N} D_{i t} - p_{i}^{D} D_{i t} \\ + (| T | - t + 1) (h_{i}^{N} I_{i t}^{N} + h_{i}^{D} (B_{i t}^{D} - D_{i t})) \\ - s_{i}^{N} θ_{i t} - c_{i}^{N} (B_{i t}^{D} - D_{i t} - I_{i t}^{N}) \end{array} & otherwise \end{array}

β_{i t} = {\begin{array}{l} \begin{array}{l} (| T | - t + 1) h_{i}^{D} B_{i t}^{D} \\ (| T | - t + 1) (h_{i}^{D} I_{i t}^{D} + h_{i}^{N} I_{i t}^{N}) \end{array} & if I_{i t}^{D} \geq B_{i t}^{D} \\ + (p_{i}^{N} - p_{i}^{D}) (B_{i t}^{D} - I_{i t}^{D}) & if I_{i t}^{D} < B_{i t}^{D} and \\ - c_{i}^{N} (I_{i t}^{N} - (B_{i t}^{D} - I_{i t}^{D})) - s_{i}^{N} θ_{i t} & I_{i t}^{N} < B_{i t}^{D} - I_{i t}^{D} \\ \begin{array}{l} (| T | - t + 1) (h_{i}^{D} I_{i t}^{D} + h_{i}^{N} (B_{i t}^{D} - I_{i t}^{D})) \\ + (p_{i}^{N} - p_{i}^{D}) (B_{i t}^{D} - I_{i t}^{D}) \end{array} & otherwise \end{array}

where θ_it = 1 if $X_{i t}^{N} = 0$ and 0 otherwise. Here, α_it and β_it denote the amount of profit increase when D_it and $I_{i t}^{D}$ are decreased up to ${D^{'}}_{i t}$ and ${I^{'}}_{i t}^{D}$ , respectively, defined as

\begin{array}{l} {D^{'}}_{i t} = {\begin{array}{l} D_{i t} - B_{i t}^{D} & if D_{i t} \geq B_{i t}^{D} \\ 0 & o t h e r w i s e \end{array}, \\ {I^{'}}_{i t}^{D} = {\begin{array}{l} I_{i t}^{D} - B_{i t}^{D} & if I_{i t}^{D} \geq B_{i t}^{D} \\ 0 & o t h e r w i s e \end{array} . \end{array}

We consider also changing of $I_{i t}^{N}$ , N_it and $X_{i t}^{N}$ when calculating the profit increase as

\begin{array}{l} {I^{'}}_{i t}^{N} = {\begin{array}{l} I_{i t}^{N} - B_{i t}^{D} & if I_{i t}^{N} \geq B_{i t}^{D} \\ 0 & o t h e r w i s e \end{array}, \\ {N^{'}}_{i t} = {\begin{array}{l} N_{i t} + D_{i t} & if D_{i t} \leq B_{i t}^{D} \\ N_{i t} + B_{i t}^{D} & o t h e r w i s e \end{array}, \\ {X^{'}}_{i t}^{N} = {\begin{array}{l} X_{i t}^{N} + B_{i t}^{D} - I_{i t}^{D} & if D_{i t} \geq B_{i t}^{D}, I_{i t}^{N} < B_{i t}^{D} \\ X_{i t}^{N} - D_{i t} - I_{i t}^{D} & if D_{i t} < B_{i t}^{D}, I_{i t}^{N} < D_{i t} \\ X_{i t}^{N} + B_{i t}^{D} - D_{i t} - I_{i t}^{D} & if I_{i t}^{D} < B_{i t}^{D}, I_{i t}^{N} < B_{i t}^{D} - I_{i t}^{D} \end{array} \end{array}

We finally select the choice with more profit increase, max ${α_{i t}, β_{i t}}$ .

Case 3 : Positive demand balance case $B_{i t}^{S} > 0$ . To satisfy constraint (1), we consider decreasing the value of N_it by $B_{i t}^{S}$ , i.e., ${N^{'}}_{i t} = N_{i t} - B_{i t}^{S}$ and this results in $- B_{i t}^{S} p_{i}^{N}$ of the profit.

Case 4: Positive new-part balance case $B_{i t}^{N} > 0$ . To satisfy constraint (2), we consider increasing the value of $X_{i t}^{N}$ up to $B_{i t}^{N}$ , and/or decreasing the value of $I_{i t}^{N}$ and these results in profit increases, respectively as

\begin{array}{l} χ_{i t} = - s_{i}^{N} θ_{i t} - c_{i}^{N} B_{i t}^{N}, \\ δ_{i t} = {\begin{array}{l} \begin{array}{l} (| T | - t + 1) h_{i}^{N} B_{i t}^{N} \\ (| T | - t + 1) h_{i}^{N} I_{i t}^{N} \end{array} & if I_{i t}^{N} \geq B_{i t}^{N} \\ - s_{i}^{N} θ_{i t} - c_{i}^{N} (B_{i t}^{N} - I_{i t}^{N}) & otherwise \end{array} \end{array}

In each of the cases, the balance $B_{i t}^{D}, B_{i t}^{S}, B_{i t}^{N}$ are updated in a similar manner as in Case 1 and the routine inside that case continues until the corresponding balance becomes zero.

Now, an overall procedure of the LP relaxation heuristic is presented below.

Procedure 1 : LP relaxation heuristic.

Step 1. (LP relaxation and solution initialization) Solve the linear programming model after relaxing the constraint (5), (6), (9) and (10) of integer program [P] and obtain the LP solution $N_{i t}, D_{i t}, I_{i t}^{N}, I_{i t}^{D}, I_{e t}^{R}, X_{i t}^{N}, X_{e t}^{D}$ with real values. Obtain the rounded-down solution by applying the floor function to the LP solution.
Step 2. (Solution modification) From t = 1 to |T |, apply the following steps sequentially:
- 2-1. For all e∈E , calculate the balance B_et using the rounded-down solution obtained in Step 1. Modify the solution using the solution modification method of Case 1 if B_et ≠ 0.
- 2-2. For all i∈P , calculate the balance $B_{i t}^{D}$ and disposal quality W_it, and modify the solution using the Case-2 method if $B_{i t}^{D} \neq 0$ . Next, calculate the balance $B_{i t}^{S}$ and modify the solution using the Case-3 method if $B_{i t}^{S}$ ≠ 0. Finally, calculate the balance $B_{i t}^{N}$ and modify the solution using the Case-4 method if $B_{i t}^{N}$ ≠ 0.

After obtaining the solution of the LP relaxation heuristic, the solution of binary variables $Y_{i t}^{N}$ and $Y_{e t}^{D}$ is obtained using the below equations.

Y_{i t}^{N} = {\begin{array}{l} 1 & if X_{i t}^{N} > 0 \\ 0 & o t h e r w i s e \end{array} and Y_{e t}^{D} = {\begin{array}{l} 1 & if X_{e t}^{D} > 0 \\ 0 & o t h e r w i s e \end{array}

3.3 Neighborhood Solution Generation

To improve the initial solution (current solution), a neighborhood solution of the current solution is generated. The neighborhood solution is accepted if the solution is improved or with a specified probability as described earlier. A neighborhood solution is generated by three interchanging methods: single-period interchange, single-point interchange, and double-point interchange. The three interchanging methods apply to the setup decisions for new parts and EOLs. The best solution obtained by applying all combinations of the three interchange methods for all new parts and EOLs is selected as a neighborhood solution.

Single-period interchanging method. A period is randomly chosen and the setup of the chosen period is cancelled, i.e., $Y_{i t}^{N} = 0$ if $Y_{i t}^{N} = 1$ or $Y_{e t}^{D} = 0$ if $Y_{e t}^{D} = 1$ in the current solution, and vice versa. Then, the following LP model [NP] is directly solved based on modified setup variables and the LP solution of model [NP] is modified into the feasible solution of the original problem [P] using Procedure 1.

[NP] Maximize

\begin{array}{l} \sum_{i \in P} \sum_{t \in T} p_{i}^{N} N_{i t} + \sum_{i \in P} \sum_{t \in T} p_{i}^{D} D_{i t} - \sum_{i \in P} \sum_{t \in T} c_{i}^{N} X_{i t}^{N} - \sum_{e \in E} \sum_{t \in T} c_{e}^{D} X_{e t}^{D} \\ - \sum_{i \in P} \sum_{t \in T} h_{i}^{N} I_{i t}^{N} - \sum_{i \in P} \sum_{t \in T} h_{i}^{D} I_{i t}^{D} - \sum_{e \in E} \sum_{t \in T} h_{e}^{R} I_{e t}^{R} \\ - \sum_{i \in P \cup W} \sum_{t \in T} w_{i} W_{i t} - \sum_{i \in P} \sum_{t \in T} s_{i}^{N} {Y^{'}}_{i t}^{N} - \sum_{e \in E} \sum_{t \in T} s_{e}^{D} {Y^{'}}_{e t}^{D} \end{array}

subject to

\begin{array}{l} X_{i t}^{N} \leq M \cdot {Y^{'}}_{i t}^{N} & \forall i \in P, t \in T \\ X_{e t}^{D} \leq M \cdot {Y^{'}}_{e t}^{D} & \forall e \in E, t \in T \\ X_{e t}^{D} \geq 0 & \forall e \in E, t \in T \end{array}

and (1)-(4), (7), (8).

where ${Y^{'}}_{i t}^{N}$ and ${Y^{'}}_{r t}^{D}$ are the setup solution modified by the interchanging method.

Single-point interchanging method. It randomly chooses a period and two items, i.e., two new parts, one new part and one EOL, or two EOLs. The setup values in later periods and the chosen period are interchanged between the two chosen items in the current solution. Then, the same method as in the single-period method is applied to obtain a feasible solution.

Double-point interchanging method. It randomly chooses two periods and two items, i.e., two new parts, one new part and one EOL, or two EOLs. The setup values in the periods between the chosen two periods are interchanged between the two chosen items in the current solution. Then, the same method as in the single-period method is applied to obtain a feasible solution.

4. Computational Experiment

To show the performance of the SA algorithm suggested in our paper, we performed computational tests using randomly generated problems. We used CPLEX 12.8.0, a commercial software package to solve problems for comparing our algorithm suggested in this paper. The algorithm and integer program were coded in C and the tests were conducted on a personal computer with Intel® Core^™ i5-8400U, 8GB RAM, 2.80GHz.

We randomly generated 45 test instances, i.e., 5 instances for each of combination of three levels of the number of service parts (10, 20, 30) and three levels of the number of periods (10, 20, 30). The number of EOLs generated from DU (5, 10) and the number of parent EOLs of part i are generated from DU (|E|/2, |E|), where DU (c, d) is the discrete uniform distribution with [c, d]. The total number of units of parts and non-defectives taken from disassembling one unit of an EOL were generated from DU (3, 5) and DU (1, 3), respectively. For the new service part, the unit production cost and inventory holding cost were generated from DU (150, 300) and DU (20, 30), whereas for the disassembled part, the unit disassembly cost and the unit inventory holding cost were generated from DU (75, 125) and DU (15, 20). The unit revenue for new and disassembled parts were generated from DU (800, 1200) and DU (600, 800). The unit inventory holding cost of EOLs was generated from DU (5, 10) and the unit disposal cost for defective parts was generated from DU (1, 3). The setup costs per the setup of new parts and EOLs were generated as ${\bar{c}}^{N} U$ (10, 15) and ${\bar{c}}^{D} U$ (1, 5) respectively where ${\bar{c}}^{N}$ and ${\bar{c}}^{D}$ are the averages of unit production cost of new service parts and unit disassembly cost of EOLs, respectively, and U (c, d) is the uniform distribution with [c, d]. The demand for service parts was generated from DU (50, 200) and the returned amount of EOLs was generated DU (5, 15). In the SA algorithm, parameters F₀, α , and β, Q were set 0.64, 5, 0.99 and 200 respectively after a series of preliminary tests.

The performance of the SA algorithm is evaluated using two performance measures: the percentage gap from the optimal solution value (or lower bound if any optimal solution could not be obtained within the time limit 3600s) and CPU seconds. We set 3600s of time limit for each run of the CPLEX to avoid excessive computation time. The percentage gap was defined as (O_CPX−O_SA)/O_CPX․100 where O_CPX and O_SA are the solution value of CPLEX and the SA algorithm, respectively. The results are summarized in <Table 1>. As can be seen in <Table 1>, the SA algorithm gives near-optimal solutions for all test problems, i.e., all percentage gaps are less than 0.3%. The computation time of the SA algorithm was significantly shorter than that of CPLEX, i.e., the maximum computation time of the SA algorithm and CPLEX are 26 sec. and 3600 sec., respectively. The percentage gap increases along with the number of parts as expected whereas there is no apparent relationship between the gap and the number of periods. The computation time increases along with the number of parts and periods.

We further performed sensitivity analyses to analyze the effect of changes in the price and the amount of returned EOLs. The analyses were conducted based on the solution of the SA algorithm because the heuristic gave a near-optimal solutions within reasonable time whereas CPLEX required excessive computation time as discussed above. They are also based on the problem with maximum size in the test set in <Table 1> with 30 parts and periods.

Firstly, to analyze the effect of change in the price of the disassembled parts, their prices were varied from 65% to 100% of the new parts’ price in increments of 5%, and 5 test problems were generated on the same percentage. Let price rate be for simplicity the price of the disassembled part over that of the new part. For this analysis, we obtained the sales share of the disassembled part out of all sales, the amount share of the non-disassembled EOLs out of all EOL returns, and the change rate in the total profit, which is calculated based on a price rate of 80%. The results are summarized in <Table 2>. The sales share of the disassembled part is zero and EOL is not disassembled at a price rate of 65%. Then, as the price rate increases, the sales share increases and the share of the amount of non-disassembled EOLs decreases, but they are saturated after the price rate of 90%. These results imply that disassembling EOLs and selling disassembled parts are not economical at a very low price of disassembled parts. Although the sales share of disassembled parts increases along with the price rate in general, there is a certain price rate where the sales share of disassembled parts increases no longer and even decreases. Therefore, appropriate pricing of disassembled parts is important to make the disassembly process economical and sustainable. However, the total profit increases as the price rate becomes higher as expected.

Next, the effect of change in the amount of returned EOLs is analyzed by multiplying the current return amount used in the above experiments and multipliers ranging from 1 to 8. 5 test problems were generated on the same multiple. The price rate was set to 90% of the new part’s price because sales share of the disassembled part and share of non-disassembled EOL are not changed significantly after that rate. The results are summarized in <Table 3>. The non-disassembled EOLs increase as the multiplier value increases as expected. However, the sales share of the disassembled parts and the total profit sharply increase. After multiplier value 5 until the multiplier value increases from 1 to 4, but they decrease slightly after multiplier value 5. The concavity may be because gathering EOLs a lot may incur excessive inventories. Therefore, like the effect of change in the price of the disassembled parts, deciding an appropriate amount of gathering EOLs is also important to make the disassembly process economical and sustainable.

5. Concluding Remarks

This study introduced a novel lot-sizing problem that has not been studied in the literature, named the service-parts lot-sizing with disassembly option. The disassembly option implies that the demands of the service parts can be fulfilled by newly manufactured parts but also by disassembled parts. We proved that the single-period version of the problem is NP-hard and suggested a heuristic by combining simulated annealing and linear-programming relaxation heuristics. Computational experiment results have shown that the heuristic is a time-efficient method of obtaining near-optimal solutions. Through sensitivity analyses, we observed that disassembling EOLs and selling disassembled parts were not economical at the very low price of disassembled service parts; there is a certain price of disassembled parts where no more disassembly is performed; and there is a certain amount of EOLs where gathering EOLs more is not economical anymore due to the inventory holding cost of EOLs. Those results of the sensitivity analyses imply that an appropriate pricing of disassembled parts and an appropriate gathering of EOLs are economical for sustainable service parts systems.

The service parts lot-sizing problem with disassembly option considered in this paper is expected to gain interest from practitioners in various industrial fields. For example, increasing returns of EOL electric vehicle battery has encouraged car manufacturers to retrieve valuable batteries from the EOL electric vehicle. Furthermore, the problem can also motivate electronic device manufacturers to find a cost-efficient aftersales supports, e.g., repairing and warranty service, with the disassembled and newly-procured service parts. Applications of the lot-sizing problem require practitioners to incorporate a variety of real-world operational issues into the problem.

In this sense, this paper can be extended in several different ways. First, we assumed that the quantity and return period of EOLs, as well as the quantity of defective parts, are deterministic. These assumptions are by no means necessary for the presented model and solution algorithm. However, relaxing them results in the stochastic problem which is challenging from a modeling point of view, but meaningful from a practical point of view. Second, the problem can be extended to account for more general cost structures like the literatures for the lot-sizing with remanufacturing option. The problem with general concave costs is also challenging because it cannot be directly solved as an integer program. Third, we analyzed the effects of change in the price of disassembled parts in the experiments. Therefore, it is important and meaningful to determine the optimal price of disassembled parts from a practical point of view. The pricing problem is however challenging since it may be formulated as a non-linear program. Finally, it may be meaningful to address the problem of determining the optimal amount and timing of gathering EOLs by considering the activity costs of gathering EOLs. In this problem, it may be needed to consider the availability of EOLs, which is random in practice.

Acknowledgement

This work was supported by the Ministry of Education of the Republic of Korea and the National Research Foundation of Korea (NRF-2017S1A5A2A01024245).

Figure

<Figure 1>.

Service Parts Inventory System with Disassembly Option

<Figure 2>.

Two-Level Disassembly Structure and Service Parts

Table

<Table 1>.

Performance of the SA Algorithm

<Table 2>.

Effect of Change in the Price of the Disassembled Parts

<Table 3>.

Effect of Change in the Returned Amount of EOLs

Reference

Attila, O.N., Agra, A., Akartunalı, K., and Arulselvan, A., Robust Formulations for Economic Lot-Sizing Problem with Remanufacturing, European Journal of Operational Research, 2021, Vol. 288, No. 2, pp. 496-510.
Baki, M.F., Chaouch, B.A., and Abdul-Kader, W., A Heuristic Solution Procedure for the Dynamic Lot Sizing Problem with Remanufacturing and Product Recovery, Computers and Operations Research, 2014, Vol. 43, pp. 225-236.
Fleischmann, M., Van Nunen, J.A., and Grave, B., Integrating Closed-Loop Supply Chains and Spare-Parts Management at IBM, Interfaces, 2003, Vol. 33. No. 6, pp. 44-56.
Garey, M.R. and Johnson, D.S., Computers and Intractability : A Guide to the Theory of NP-Completeness, W.H. Freeman & Company, New York, 1979.
Godichaud, M. and Amodeo, L., Economic Order Quantity for Multistage Disassembly Systems, International Journal of Production Economics, 2018a, Vol. 199, pp. 16-25.
Godichaud, M. and Amodeo, L., EOQ Inventory Models for Disassembly Systems with Disposal and Lost Sales, International Journal of Production Research, 2018b, Vol. 57, No. 18, pp. 5685-5704.
Golany, B., Yang, J. and Gang, Y., Economic Lot-Sizing with Remanufacturing Options, IIE Transactions, 2001, Vol. 33, No. 11, pp. 995-1003.
Gupta, S.M. and Taleb, K.N., Scheduling Disassembly, International Journal of Production Research, 1994, Vol. 32, No. 8, pp. 1857-1866.
Jeon, H.-B., Kim, J.-G., Kim, H.-J., and Lee, D.-H., A Two-Stage Heuristic for Disassembly Scheduling with Capacity Constraints, International Journal of Management Science, 2006, Vol. 12, No. 1, pp. 95-112.
Ji, X., Zhang, Z., Huang, S. and Li, L., Capacitated Disassembly Scheduling with Parts Commonality and Start-Up Cost and its Industrial Application, International Journal of Production Research, 2016, Vol. 54, No. 4, pp. 1225-1243.
Kim, H.-J. and Xirouchakis, P., Capacitated Disassembly Scheduling with Random Demand, International Journal of Production Research, 2010, Vol. 48, No. 23, pp. 7177- 7194.
Kim, H.-J., Lee, D.-H., and Xirouchakis, P., A Lagrangean Heuristic Algorithm for Disassembly Scheduling with Capacity Constraints, Journal of the Operational Research Society, 2006b, Vol. 57, pp. 1231-1240.
Kim, H.-J., Lee, D.-H., and Xirouchakis, P., An Exact Algorithm for Two-Level Disassembly Scheduling, Journal of Korean Institute of Industrial Engineers, 2008, Vol. 34, No. 4, pp. 414-424.
Kim, H.-J., Lee, D.-H., and Xirouchakis, P., Disassembly scheduling : Literature Review and Future Research Directions, International Journal of Production Research, 2007, Vol. 45, pp. 4465-4484.
Kim, H.-J., Lee, D.-H., and Xirouchakis, P., Two-Phase Heuristic for Disassembly Scheduling with Multiple Product Types and Parts Commonality, International Journal of Production Research, 2006a, Vol. 44, pp. 195-212.
Kim, H.-J., Lee, D.-H., Xirouchakis, P., and Kwon, O.-K., A Branch and Bound Algorithm for Disassembly Scheduling with Assembly Product Structure, Journal of the Operational Research Society, 2009, Vol. 60, No. 3, pp. 419-430.
Kim, H.-J., Lee, D.-H., Xirouchakis, P., and Zust, R., Disassembly Scheduling with Multiple Product Types, CIRP Annals-Manufacturing Technology, 2003, Vol. 52, No. 1, pp. 403-406.
Kim, J.-G., Jeon, H.-B., Kim, H.-J., Lee, D.-H., and Xirouchakis, P., Disassembly Scheduling with Capacity Constraints : Minimizing the Number of Products Disassembled, Proceedings of the Institution of Mechanical Engineers, 2006c, Vol. 220, pp. 1473-1481.
Langella, I.M., Heuristics for Demand-Driven Disassembly Planning, Computers and Operations Research, 2007, Vol. 34, No. 2, pp. 552-577.
Lee, D.-H. and Xirouchakis, P., A Two-Stage Heuristic for Disassembly Scheduling with Assembly Product Structure, Journal of the Operational Research Society, 2004, Vol. 55, No. 3, pp. 287-297.
Lee, D.-H., Kim, H.-J., Choi, G., and Xirouchakis, P., Disassembly Scheduling : Integer Programming Models, Proceedings of the Institution of Mechanical Engineers, Journal of Engineering Manufacture-Part B, 2004, Vol. 218, No. 10, pp. 1357-1372.
Lee, D.-H., Xirouchakis, P., and Zust, R., Disassembly Scheduling with Capacity Constraints, CIRP Annals-Manufacturing Technology, 2002, Vol. 51, No. 1, pp. 387-390.
Neuendorf, K.-P., Lee, D.-H., Kiritsis, D., and Xirouchakis, P., Disassembly Scheduling with Parts Commonality Using Petri Nets with timestamps, Fundamenta, Informaticae, 2001, Vol. 47, pp. 295-306.
Pan, Z., Tang, J., and Liu, O., Capacitated Dynamic Lot Sizing Problems in Closed-Loop Supply Chain, European Journal of Operational Research, 2009, Vol. 198, No. 3, pp. 810-821.
Pineyro, P. and Viera, O., The Economic Lot-Sizing Problem with Remanufacturing and One-Way Substitution, International Journal of Production Economics, 2010, Vol. 124, No. 2, pp. 482-488.
Sifaleras, A., Konstantaras, I. and Mladenovic, N., Variable Neighborhood Search for the Economic lot Sizing Problem with Product Returns and Recovery, International Journal of Production Economics, 2015, Vol. 160, pp. 133-143.
Son, D.-H., An, S.-B., Kim, H.-J., and Jang, J.-M., Push and Pull Disassembly Quantity Models in a Reverse Supply Chain : The Case of an Automobile Disassem bly System in Korea, International Journal of Logistics Research and Applications, 2021, pp. 1-26.
Taleb, K.N. and Gupta, S.M., Disassembly of Multiple Product Structures, Computers & Industrial Engineering, 1997, Vol. 32, pp. 949-961.
Taleb, K.N., Gupta, S.M., and Brennan, L., Disassembly of Complex Product Structures with Parts and Materials Commonality, Production Planning and Control, 1997, Vol. 8, pp. 255-269.
Teunter, R.H., Bayindir, Z.P., and van den Heuvel, W., Dynamic Lot Sizing with Product Returns and Remanufacturing, International Journal of Production Research, 2006, Vol. 44, No. 20, pp. 4377-4400.
Yang, J., Golany, B., and Yu, G., A Concave-Cost Production Planning Problem with Remanufacturing Options, Naval Research Logistics, 2005, Vol. 52, No. 5, pp. 443- 458.