1. INTRODUCTION
During the last decades, the environmental issues associated with endofuse/life products have been emerged due to the decrease in product lives, the requirement of material and product recovery, the shortages of dumping and incineration sites, the legislation pressures to collect and upgrade endofuse/life products in an environmentally conscious way, and so on. Among the endofuse/life product issues, researchers and practitioners focus on remanufacturing since it is the most advanced option that recovers the original functions of products while giving economic profits by enlarging market shares through lower prices and reducing the amount of resource and energy consumptions. In other words, unlike the material recycling option in which endofuse/life products are destroyed and their constituent materials are reused, remanufacturing can give both economic and environmental benefits since it retains the geometrical form of the original product. See Lund (1984) and Steinhilper (1998) for more details on remanufacturing.
Remanufacturing, alternatively called refurbishing, reconditioning and overhauling, is recycling by manufacturing new products from endofuse/life products, i.e. reprocessing endofuse/life products in such a way that their qualities are as good as new in the aspects of appear ance, reliability and performance. Here, the criterion as good as new is the critical one when defining remanufacturing (Parkinson and Thompson, 2003). Remanufacturing technologies are being applied to various product types, which can be classified as automotive, industrial equipment, commercial products, residual products and so on. Among them, automotive components such as engines, starters and transmissions account for two thirds of the remanufacturing industry (Steinhilper and Hieber, 2001). See Parkinson and Thompson (2003) for remanufacturing practices.
In a typical remanufacturing system, an endofuse/ life product is remanufactured according to three interdependent processes, i.e. disassembly, reprocessing and reassembly. The endofuse/life product, called a core in the remanufacturing industry, is completely separated into their components in the disassembly process, and then, usable ones are inspected, cleaned, reconditioned and tested in the reprocessing process. Finally, in the reassembly process, reprocessed and new components, if required, are assembled into the remanufactured product fully equivalent in performance and ready for use by customers. As explained in Steinhilper (1998), remanufacturing is different from repair in that it is an industrialized process, not a simple mechanical work, with an overall restoration to likely new conditions after products are disassembled completely. Figure 1 shows the configuration of the typical remanufacturing system.
As in other manufacturing systems, the decision problems in remanufacturing systems can be classified into three major ones: design, planning and scheduling/ control. Among them, this study focuses on the planning problem that pursues the efficient use of resources in response to fluctuating market demands of remanufactured products. More specifically, this study considers the problem of determining dynamic lotsizes that satisfy the demands of remanufactured products over a planning horizon. Since the remanufacturing process consists of disassembly, reprocessing and reassembly, the lotsize must be determined for each of the three processes, i.e. how much and when to disassemble endofuse/life products, reprocess their components and reassemble remanufactured products.
Unlike the previous studies on dynamic lotsizing in traditional manufacturing systems, not much work has been done on the problem in remanufacturing systems. See Guide (2000) for more details on the importance of production planning in remanufacturing systems. Most previous research articles simplify the problem by aggregating the three processes into a single process with returns of endofuse/life products. For example, Richter and Sombrutzki (2000) define a dynamic lotsizing problem for singlestage remanufacturing systems with return flows and suggest the solution algorithms that modify the wellknown Wagner/Whitin algorithm. Later, it is extended by Richter and Weber (2001), Golony et al. (2001), Richter and Gobsch (2003), Konstantaras and Papachristos (2007), Schulz (2011), Helmrich et al. (2014), Iwao and Kusukawa (2014), Sifaleras et al. (2015), Lee et al. (2015), Piñeyro and Viera (2015), Kwak (2015) and Cunha and Melo (2016). Also, some other articles consider the problem in disassembly process, called the disassembly scheduling in the literature, which is the problem of determining the quantities and timings of ordering and disassembling endofuse/life products. See Lee et al. (2001) and Kim et al. (2007) for literature reviews on disassembly scheduling.
Although the singlestage models have a merit in that the return flows of endofuse/life products are explicitly considered according to the remanufacturing process, they have a critical limitation in that the detailed material flows through the three subprocesses are not considered. To overcome the limitation, other articles suggest multistage models. Clegg et al. (1995) suggest a linear programming model for the problem of determining disassembly and reassembly lotsizes, together with the amounts of purchasing new components, in a manufacturing system with remanufacturing capability for the objective of maximizing the profit. Kim et al. (2006) propose a mixed integer programming model for production planning in manufacturing systems in which components can be supplied from external suppliers or reprocessing the components of endofuse/life products. Jayaraman (2006) suggest a linear programming model for the problem of determining the amounts of disassembling, disposing, remanufacturing and acquiring endofuse/life products with probabilistic quality levels over a planning horizon and report a case study on a mobile telephone remanufacturing system. Doh and Lee (2010) suggest linear programming relaxation heuristics for the problem of determining the number of endofuse/life products to be disassembled and disposed of, the number of components to be reprocessed, disposed of and newly purchased, and the number of remanufactured products to be reassembled over a planning horizon for the objective of maximizing the total profit. Also, Ahn et al. (2011) develop a threestage dynamic lotsizing model for a remanufacturing system with a single disassembly facility, parallel reprocessing facilities and a single reassembly facility, and suggest heuristic algorithms that minimize the sum of setup and inventory holding costs.
This study considers multistage dynamic lotsizing in a remanufacturing system with a single disassembly facility, parallel reprocessing facilities and a single reassembly facility. The problem is to determine disassembly, reprocessing and reassembly lotsizes over a planning horizon for the objective of minimizing the sum of setup, operation and inventory holding costs. In fact, the problem considered in this study is an extension of Ahn et al. (2011) in that the processing time capacity of each facility is explicitly considered. As in other lotsizing problems, the capacity constraint must be considered, so that the resulting solutions are more realistic and applicable to real remanufacturing systems. To the best of the authors’ knowledge, there is no previous study on the problem.
To represent the problem mathematically, a mixed integer programming model is suggested. Then, due to the problem complexity, we suggest heuristic algorithms using the fixandoptimize approach that fixes a portion of binary variables with a certain method and solves the resulting problems iteratively. To show the performances of the heuristics, computational experiments were done on various test instances, and the results are reported.
The rest of this paper is organized as follows. In the next section, the system and problem are explained in more detail, together with a mixed integer programming model. The solution algorithms and their test results are presented in Sections 3 and 4, respectively. Finally, Section 5 summarizes the paper and suggests some future research directions.
2. SYSTEM AND PROBLEM DESCRIPTIONS
This section explains the remanufacturing system considered in this study. Then, the problem is described in more details, together with a mixed integer programming model.
As explained earlier, the system considered in this study consists of a single disassembly facility, parallel reprocessing facilities and a single reassembly facility. As explained in Ahn et al. (2011), the configuration is the most typical one that represents the relationships among an endofuse/life product, its components and the corresponding remanufactured product. Figure 2 shows the material flows of the remanufacturing system considered in this study. As can be seen in the figure, endofuse/life products, collected through a reverse logistics channel, are separated into their components at the single disassembly facility, and then each component is reprocessed to the likenew one at one of the parallel reprocessing facilities. It is assumed that the reprocessing facilities are dedicated, i.e. each component can be reprocessed at its prespecified reprocessing facility. Finally, the reprocessed components are reassembled into remanufactured products ready for use by customers at the single reassembly facility.
Now, the problem considered in this study can be described as follows. For the remanufacturing system with a single disassembly facility, parallel reprocessing facilities and a single reassembly facility, the problem is to determine disassembly, reprocessing and reassembly lotsizes that satisfy the processing time capacity of each facility and the dynamic demands over a given planning horizon with discrete time periods for the objective of minimizing the sum of setup, operation and inventory holding costs.
The lotsizes imply the quantity of endofuse/life product to be disassembled at the disassembly facility, the quantities of the components to be reprocessed at each of parallel reprocessing facilities and the quantity of remanufactured product to be reassembled at the reassembly facility in each period of the planning horizon. Note that the three types of lotsizes are determined at the same time, so that the three remanufacturing processes can be managed in an integrated manner. The objective function consists of setup, operation and inventory holding costs. The setup costs are those required for preparing disassembly, reprocessing and reassembly operations. As in other lotsizing models, the setup costs occur in a period if any operation is performed in that period. Also, the operation costs, which are proportional to the labor time or machine processing time required for the corresponding operations, are required to perform the disassembly, reprocessing or reassembly operations. Finally, the inventory holding costs, computed by the endofperiod inventory levels, are those incurred to store disassembled components, reprocessed components and remanufactured products over the planning horizon. It is assumed that the operation and inventory holding costs are linear in the amounts of operations and inventory levels, respectively.
The dynamic lotsizing problem considered in this study has two major constraints, i.e. demand requirements and capacity constraints. The demand constraint is to satisfy the dynamic demands of remanufactured product over the planning horizon. It is assumed that the demands are deterministic and given in advance and shortages are not allowed, i.e. demand must be satisfied in each period of the planning horizon. Also, the capacity constraints imply that there are upper limits on the available times to perform setup and operation at each of disassembly, reprocessing and reassembly facilities. More specifically, the sum of setup and processing times at each facility must not exceed the available time limit in each period of the planning horizon.
As a beginning study on the problem, this study considers the deterministic version of the problem, i.e. all parameters are deterministic and given in advance. The other assumptions made for the problem are: (a) there are no shortages of endofuse/life products, i.e. endofuse/ life products can be supplied whenever ordered; (b) disassembly, reprocessing and reassembly operations can be carried out within a single time period; and (c) defectives are not considered.
To describe the problem more clearly, we suggest a mixed integer programming model. Before describing the model, the notations used are summarized below.
Indices
Parameters

S_{t}^{d} setup cost to disassemble endofuse/life products in period t ($)

S_{it}^{p} setup cost to reprocess component i in period t ($)

S_{t}^{r} setup cost to reassemble remanufactured products in period t ($)

O_{t}^{d} operation cost to disassemble one unit of the endofuse/life product in period t ($/unit)

O_{it}^{p} operation cost to reprocess one unit of component i in period t ($/unit)

O_{t}^{r} operation cost to reassemble one unit of remanufactured product in period t ($/unit)

h_{it}^{d} inventory holding cost of disassembled component i in period t ($/unit⋅period)

h_{it}^{p} inventory holding cost of reprocessed component i in period t ($/unit⋅period)

h_{t}^{r} inventory holding cost of remanufactured products in period t ($/unit⋅period)

d_{t} demand of remanufactured product in period t

π_{i} units of component i obtained from disassembling one unit of the endofuse/life product

u_{t}^{d} setup time to disassemble endofuse/life products in period t (hours)

u_{ii}^{p} setup time to reprocess component i in period t (hours)

u_{t}^{r} setup time to reassemble remanufactured products in period t (hours)

p_{t}^{d} operation time to disassemble one unit of the endofuse/life product in period t (hours)

p_{ii}^{p} operation time to reprocess one unit of component i in period t (hours)

p_{t}^{r} operation time to reassemble one unit of remanufactured product in period t (hours)

C_{t}^{d} available capacity at disassembly facility in period t (hours)

C_{it}^{p} available capacity at reprocessing facility i in period t (hours)

C_{t}^{r} available capacity at reassembly facility in period t (hours)

_{i}_{0}^{d} initial inventory level of disassembled component i

_{i}_{0}^{p} initial inventory level of reprocessed component i

I_{0}^{r} initial inventory level of remanufactured product

M large number
Decision variables

y_{t}^{d} = 1 if setup is done to disassemble endofuse/ life product in period t, and 0 otherwise

y_{it}^{p} = 1 if setup is done to reprocess component i in period t, and 0 otherwise

y_{t}^{r} = 1 if setup is done to reassemble remanufactured product in period t, and 0 otherwise

x_{t}^{d} disassembly lotsize in period t

x_{it}^{p} reprocessing lotsize of component i in period t

x_{t}^{r} reassembly lotsize in period t

I_{it}^{p} inventory level of disassembled component i at the end of period t

I_{t}^{r} inventory level of reprocessed component i at the end of period t

inventory level of remanufactured product at the end of period t
Now, the mixed integer programming model is given below.
subject to
The objective function represents the sum of setup, operation and inventory holding costs at the disassembly, reprocessing and reassembly facilities over the planning horizon. Constraints (1), (2) and (3) represent the inventory balances of disassembled components, reprocessed components and remanufactured products, respectively. For example, the inventory balance constraint (1) implies that the inventory level of a disassembled component at the end of each period is the inventory in a period before, increased by the amount of the component obtained from disassembling the products in that period and decreased by the amount reprocessed at that period. Also, the demand requirements are represented by the inventory balance constraint (3). Constraints (4), (5) and (6) ensure that a setup in a period occurs whenever at least one disassembly, reprocessing or reassembly operation is performed in that period. Constraints (7), (8) and (9) denote the capacity constraints at disassembly, reprocessing and reassembly facilities, respectively. In other words, the sum of setup and operation times in a period must not exceed the available time limit in that period. Finally, constraints (10), (11) and (12) represent the conditions of decision variables.
3. SOLUTION ALGORITHMS
The problem [P] can be solved directly using a commercial software package, but it requires an excessive amount of time due to the large number of binary setup variables, i.e. y_{t}^{d}, y_{it}^{p} and y_{t}^{r}. In fact, the problem is NPhard since its subproblem is the single item capacitated lot sizing problem that is known to be NPhard (Florian et al., 1980; Bitran and Yanasse, 1982). Therefore, instead of solving the original formulation, we suggest heuristic algorithms based on the fixandoptimize approach that obtains the solutions by fixing a portion of binary variables using a certain systematic method and solving the resulting mixed integer programming problems with the fixed variables in an iterative manner. In this study, we adopted the fixandoptimize approach since it gives good solutions for various lotsizing problems. In particular, it is recommended to refer Helber and Sahling (2010) and Helber et al. (2013) for its successful applications to other capacitated lotsizing problems.
The fixandoptimize approach proposed in this study works as follows. In the first step, an initial solution is obtained by solving the model [P] after fixing all the binary setup variables to 1, i.e. y_{t}^{d}, y_{it}^{p} and y_{t}^{r} = 1 for all i and t. In the second step, the setup variables are selected using a variable selection method and then, they are freed to binary variables. In this study, we propose three methods to select the setup variables to be freed because the performance of the fixandoptimize heuristic highly depends on the method to select the binary variables to be freed. Note that the three fixandoptimize heuristics are different in the method to select the setup variables to be freed, and the three variable selection methods are developed using the characteristics of the remanufacturing system considered in this study. The variable selection methods proposed in this study are explained below. Recall that I and T denote the numbers of reprocessing facilities and periods, respectively. Also, the parameters used in the methods were set using the results of preliminary experiments. Note that it may be needed to develop systematic methods to set the parameters of the three variable selection methods.
3.1 PartialPeriod Method
From disassembly to reassembly facility, ⌈T/2⌉ binary setup variables are selected for each facility in the nonincreasing order of setup costs over the planning horizon, where ⌈•⌉ is the smallest integer larger than or equal to •. Then, in the next iteration, T – ⌈T/2⌉ setup variables are selected and hence variable selections are done two times for each facility. Figure 3 shows an example with 8 reprocessing facilities and 8 periods, i.e. I = 8 and T = 8. In this example, 4 binary setup variables are freed at each iteration, i.e. ⌈T /2⌉ = ⌈8/2⌉ = 4, which results in 20 iterations in maximum.
3.2 FullPeriod Method
From disassembly to reassembly facility, all the binary setup variables are selected for each facility over the planning horizon, and hence variable selection is done one time for each facility. Figure 4 shows the same example with 8 reprocessing facilities and 8 periods. In this case, there exist 10 iterations in maximum.
3.3 OverlappedPeriod Method
From facility combination 1 to I, u consecutive setup variables are selected from the first period of the planning horizon while overlapping the last v variables in the next iteration. Here, facility combination i is defined as the set of disassembly facility, reprocessing facility i, reassembly facility. Figure 5 shows the same example in which u = 4 and v = 2, which results in 24 iterations in maximum.
freed to binary ones and an incumbent solution is obtained by solving the resulting problem with fixed and freed variables optimally using a mixed integer programming solver. Here, the unnecessary positive setup variables are set to 0 to reduce unnecessary setup costs, i.e. set y^{d}_{t} (y^{p}_{it}, y^{r}_{t}) = 0 if x^{d}_{t} (x^{p}_{it}, x^{r}_{t}) = 0. Also, the solution is updated if the incumbent solution improves the current one. Finally, the algorithm is stopped if there is no improvement for a certain consecutive number of iterations.
The detailed procedure of the fixandoptimize solution approach is given below. Recall that three fixandoptimize heuristics are proposed according to the three methods to select the setup variables to be freed.
Procedure 1. (Fixandoptimize solution approach)

Step 1. (Initialization) Obtain an initial solution by solving the problem [P] after fixing all the binary setup variables to 1, i.e. y_{t}^{d}, y_{it}^{p} and y_{t}^{r} = 1 for all i and t.

Step 2. (Selecting free setup variables) Select the binary setup variables to be freed using one of the variable selection methods explained earlier.

Step 3. (Obtaining an incumbent solution) Obtain an incumbent solution by solving the problem obtained after freeing the selected setup variables optimally and set the unnecessary positive setup variables to 0. Maintain the best setup patterns at the next iteration.

Step 4. (Updating the solution and terminating the algorithm) Update the solution if the incumbent solution improves the current one. Stop the algorithm if there is no improvement for a certain consecutive number of iterations. Otherwise, go to Step 2.
4. COMPUTATIONAL RESULTS
To show the performances of the three variants of the fixandoptimize heuristic, computational experiments were done on various test instances and the results are reported in this section. The heuristics were coded in C++ with CPLEX 12.5 solver and the tests were done on a personal computer with an Intel Core i5 processor operating at 2.8 GHz clock speed and 4 GB of main memory.
In this test, two performance measures were used: (a) percentage deviations from optimal solution values or lower bounds; and (b) CPU seconds. Here, lower bounds were used when CPLEX could not give the optimal solutions within 3600 seconds. More formally, the percentage deviation from optimal solution value or lower bound for an instance is calculated as
where C_{h} is the solution value obtained from heuristic h and C_{b} is the optimal solution value or lower bounds obtained by solving the mixed integer programming model [P] using CPLEX.
For the test, 10 instances were generated randomly for some combinations of 7 levels of the number of components (5, 10, 15, 20, 30, 40 and 50), 6 levels of the number of periods (5, 10, 15, 20, 30 and 40) and 3 levels of capacity tightness (loose, regular and tight). Here, the test instances were classified into the smallsized ones when the optimal solutions could be obtained using CPLEX within 3600 seconds and the largesized ones when the optimal solutions could not be obtained. The detailed data were generated based on those of Jayaraman (2006), which are summarized in Table 1. In the table, DU(a, b) denotes the discrete uniform distribution with a range [a, b]. Also, the algorithms were terminated when there is no improvement for 10 (20, 30, 40 and 50) consecutive iterations for the instances with 5 and 10 (15/20, 30, 40 and 50) components. Also, in the overlappedperiod method, parameters u and v were set to ⌈T/2⌉ and 2 using the results of preliminary experiments.
Test results for the smallsized instances are summarized in Table 2 that shows the percentage deviations from the optimal solution values. It can be seen from the table that the fixandoptimize heuristics give near optimal solutions. Among the three variable selection methods, the overlappedperiod method outperforms the others since it explores the larger solution spaces in a broader way. In fact, the overall average percentage gaps of the best fixand optimize heuristic were 1.69%, 1.54% and 1.13% for the test instances with regular, loose and tight capacities, respectively. Also, it gave smaller range between the maximum and the minimum percentage gaps than the others, which shows the stability of the overlappedperiod based fixandoptimize heuristic. Interestingly, the performances of the fixandoptimize heuristics get better as the capacity tightness increases.
Table 3 summarizes the test results for the largesized instances that the optimal solutions could not be obtained within 3600 seconds. As can be seen in Table 3, the test results are similar to those for smallsized ones. In other words, the overlappedperiod based fixandoptimize heuristic gave better solutions than the others, and its overall average percentage gaps from the lower bounds were 3.39%, 3.64% and 3.03% for the test instances with regular, loose and tight capacities, respectively. Also, it gave smaller range between the maximum and the minimum percentage gaps than the others.
Finally, we can expect that the overlappedperiod based fixandoptimize heuristic requires longer CPU seconds than the others due to its larger search space. Nevertheless, the best heuristic gave the solutions within 385 seconds for the largest test instances with 50 components and 40 periods. In summary, it can be concluded from the test results that the fixandoptimize approach, especially with the overlappedperiod variable selection method, is effective in terms of solution quality and computation time for capacitated dynamic lotsizing for remanufacturing systems with a single disassembly facility, parallel reprocessing facilities and a single reassembly facility.
5. CONCLUDING REMARKS
This study considered the capacitated dynamic lotsizing problem in a typical remanufacturing system that consists of a single disassembly facility, parallel reprocessing facilities and a single reassembly facility. The problem is to determine disassembly, reprocessing and reassembly lotsizes at the same time for the objective of minimizing the sum of setup, operation and inventory holding costs while satisfying the dynamic remanufactured product demands over a planning horizon. As an extension of Ahn et al. (2011), we considered the processing time capacity of each facility explicitly. A mixed integer programming model was developed to describe the problem mathematically, and then three variants of the fixandoptimize solution approach were proposed in which the solutions are obtained by fixing a portion of binary setup variables and solving the resulting problems in an iterative manner. Computational experiments were done on various test instances and the results showed that the fixandoptimize heuristic based on the overlappedperiod variable selection method outperforms the others and gives near optimal solutions within a reasonable amount of computation time.
As a beginning study on capacitated dynamic lotsizing problem in remanufacturing systems with a single disassembly facility, parallel reprocessing facilities and a single reassembly facility, this study can be extended in several ways. First, in the theoretical aspect, it is needed to develop an optimal solution algorithm after characterizing the optimal solution properties. Second, the model proposed in this study can be extended to the one with multiple product types. Third, the uncertainty, such as defectives components, safety stocks and other stochastic parameters, is an important consideration in remanufacturing systems. Finally, case studies are needed to show the applicability of the model and solution algorithms.