Introduction

Disassembly, one of the basic material and product recovery processes, represents a way of obtaining constituent materials, parts, subassemblies, or other groupings from used or end-of-life products with necessary sorting operations. Owing to environmental and economic reasons, a number of manufacturing firms have been paying considerable attention to disassembly. That is, the growth of environmental concerns forced countries to pass laws for regulating the treatment of end-of-life products. Therefore, companies take back their products from customers and recycle, reuse, and remanufacture them. Also, companies may gain economic benefits from obtaining valuable components and/or materials from end-of-life products or by giving a new life to the end-of-life products by remanufacturing.

Among the environmental and economical issues of used or end-of-life products, disassembly is important because it should be done in advance before they are recycled, remanufactured, and even disposed of. Note that disassembly is required in the disposal process since hazardous materials and/or parts should be separated before disposal. A number of researches have been conducted on various disassembly areas such as design for disassembly, disassembly process planning, disassembly scheduling, etc. For literature reviews on these problems, see Boothroyd and Alting (1992); Jovane et al (1993); O'Shea et al (1998); Lee et al (2001); Santochi et al (2002), and Lambert (2003).

This paper focuses on the problem of determining the quantity and timing of disassembling (used or end-of-life) products in order to satisfy the demand of their parts or components over a planning horizon, which is called disassembly scheduling in the literature. Disassembly scheduling is one of the important mid-term (or short-term) planning problems in disassembly systems (Lee et al, 2001). Compared with assembly systems in which parts/components converge into a single demand source of a product, the disassembly systems have the special characteristic that a product diverges into multiple demand sources of parts/components. This makes the disassembly scheduling problem more complex than the production planning problems in assembly systems (Gupta and Taleb, 1994).

Several previous research articles have been published on the disassembly scheduling problem. Overall, they can be divided into uncapacitated and capacitated models although most of them do not consider the resource capacity constraints. For the uncapacitated models, the literature can be classified according to the number of product types (single and multiple) and parts commonality (with and without). Here, the parts commonality implies that products or subassemblies share their parts and/or components and makes the problem much more difficult. For the case of single product type without parts commonality, Gupta and Taleb (1994) suggest a reversed form of the material requirement planning (MRP) algorithm without an explicit objective function, and Lee (2005) emphasized the importance of cost-based objective function. Recently, Lee and Xirouchakis (2004) suggested a heuristic algorithm for the objective of minimizing various costs related with the disassembly process. As a variant of the problem with single product type, the case with parts commonality is considered in Taleb et al (1997) and Neuendorf et al (2001). Taleb et al (1997) suggest another MRP-like algorithm for the objective of minimizing the number of products to be disassembled, and Neuendorf et al (2001) suggest an improved Petri-net-based algorithm for the same problem as Taleb et al (1997). For the case of multiple product types and parts commonality, Taleb and Gupta (1997) suggest a two-phase heuristic algorithm for the objective of minimizing disassembly costs of products. Also, Kim et al (2003) suggest a heuristic algorithm based on a linear programming relaxation approach with the objective of minimizing the sum of set-up, disassembly operation, and inventory holding costs, and show its performance using a case study, and it was improved by Kim et al (2005). Recently, Lee et al (2004) presented integer programming models for all the uncapacitated cases together with their performances.

As stated earlier, most previous research is concerned with the uncapacitated version of the problem. As in the production planning problems in assembly systems, the resource capacity restrictions should be considered in the disassembly scheduling so that the resulting solution is more applicable. However, to the best of our knowledge, there is only one published article on the capacitated problem. For the case of the single product type without parts commonality, Lee et al (2002) consider the capacitated problem, and suggest an integer programming model. Although the model can give optimal solutions, its application is limited only to small-sized problems. In fact, the computational results show that it is not adequate for practical-sized problems due to its excessive computation times.

This paper focuses on the capacitated problem for the case of single product type without parts commonality. The objective is to minimize the sum of set-up, disassembly operation, and inventory holding costs, which are ordinary cost factors considered in production planning problems in assembly systems. This paper extends the research result of Lee et al (2002) with respect to two points. First, we consider the fixed set-up costs incurred whenever disassembly operations are done over the planning horizon. In general, the set-up costs are important and high in practical disassembly processes (Kang et al, 2001, 2002, 2003), but make the problem more complex to handle mathematically. Second, as pointed out in further research in Lee et al (2002), we suggest a Lagrangean heuristic algorithm that can give near optimal solutions for up to large-sized problems within a reasonable amount of computation time.

Problem description

This section begins with explaining the disassembly product structure. Its root item represents the product to be disassembled and the leaf items are the parts or components to be demanded and not to be disassembled further. A child item denotes an item that has one parent and a parent item is an item that has more than one child item. Note that each child item has only one parent in the problem considered in this paper, that is, the problem without parts commonality. Figure 1 shows an example of the disassembly product structure, obtained from Gupta and Taleb (1994). In Figure 1, item 1 is the root item, and items 6–12 are leaf items. The number in parenthesis represents the yield of the item when its parent is disassembled, for example, one unit of item 5 is disassembled into three units of item 10, two units of item 11, and three units of item 12. Here, item 5 is called parent item, while items 10, 11, and 12 are called child items. Also, the disassembly lead time (DLT) of a parent item implies the total time required to receive the item after placing an order of disassembling the item.

Figure 1.

Disassembly structure.

Full figure and legend (16K)

According to the disassembly structure described above, the capacitated disassembly scheduling problem considered in this paper can be defined as follows: for a given disassembly structure, the problem is to determine the quantity and timing of disassembling each parent item to meet the demand of leaf items over a planning horizon while satisfying the capacity restriction in each period of the planning horizon. The capacity restriction of a period is considered in the form of a limit to assign in a disassembly operations to that period. That is, there is an upper limit on the available time in each period of the planning horizon, and each disassembly operation assigned to a period consumes a portion of the available time of that period. The objective is to minimize the sum of set-up, disassembly operation, and inventory holding costs. The set-up cost implies the cost required for preparing the corresponding disassembly operation. It is assumed that the set-up cost occurs in a period if any disassembly operation is performed in that period. The disassembly operation cost is the cost proportional to the labour or machine processing time required for performing the corresponding disassembly operation, and the inventory holding cost occurs when items are stored to satisfy future demand, and they are computed based on the end-of-period inventory.

It is assumed that the disassembly structure is given in advance from the corresponding disassembly process plan that specifies all parts/subassemblies and their necessary disassembly operations. See Xirouchakis and Kiritsis (1996, 1997); O'Shea et al (1998); Erdös et al (2001); Lee et al (2001), and Santochi et al (2002) for more details on disassembly process planning. Additional assumptions made in this problem are summarized as follows: (a) there is no shortage of the root items, that is, used products can be obtained whenever they are ordered; (b) demand of leaf items is given and deterministic; (c) backlogging is not allowed and hence demands are satisfied on time; (d) parts/components are perfect in quality, that is, no defective parts/components are considered; and (e) each disassembly operation is done in one and only one period and cannot be done over two- or more periods.

To describe the problem mathematically, we present an integer programming model. In the model, without loss of generality, all items are numbered with integers 1, 2, ... i_l, ... N, where 1 and i_l denote the indices for the root item and the first leaf item, respectively. Hence, the indices that are larger than or equal to i_l represent leaf items. The notations used are summarized below.

Parameters

s_i

set-up cost of parent item i

p_i

disassembly operation cost of parent item i

h_i

inventory holding cost of item i

g_i

disassembly operation time of parent item i

K_t

capacity in period t

d_it

demand of leaf item i in period t

a_ij

yield (number of units) of item j obtained from disassembling one unit of item i

I_i0

initial inventory of item i

l_i

disassembly lead time of item i

(i)

parent of item i (Only one parent exists for each child item in the disassembly structure without parts commonality.)

M

arbitrary large number

Decision variables

X_it

amount of disassembly operations of item i in period t

Y_it

=1 if there is a set-up for item i in period t, and 0 otherwise

I_it

inventory level of item i at the end of period t

Now, the integer program is given below.

The objective function to be minimized denotes the sum of set-up, disassembly operation, and inventory holding costs. Constraints (1) and (2) define the inventory level of non-root items at the end of each period, called the inventory flow conservation constraint. Note that no inventory flow conservation constraint is needed for the root item since its surplus-inventory of the root item results in unnecessary cost increase. Also, constraint (3) represents the capacity constraint in each period. That is, the total time required to perform the disassembly operations assigned to each period should be less than or equal to the given time capacity of that period. Constraint (4) guarantees that a set-up cost in a period is incurred if any disassembly operation is performed at that period. Constraints (5), (6), and (7) represent the conditions on the decision variables. In particular, constraint (7) ensures that backlogging is not allowed.

Solution algorithm

Problem [P1] can be solved directly using a commercial software package. In this paper, however, a Lagrangean heuristic algorithm is suggested since the commercial software package requires an excessive amount of computation time. (Results of computational tests will be reported later.) First, the original problem [P1] is reformulated as another integer program so that the Lagrangean relaxation technique can be applied more effectively. Note that the relaxed problem obtained from the reformulation can be decomposed into the single item lot-sizing problems that can be solved easily with a polynomial time algorithm. Second, the Lagrangean relaxation heuristic algorithm is presented, together with a method to find good feasible solutions (obtained from changing the solutions of the relaxed problem) while considering the trade-offs among the relevant costs.

Problem reformulation

As stated earlier, the original problem [P1] is reformulated as another integer program so that the Lagrangean relaxation technique is applied more effectively. The first step is to replace the inventory variables of the original formulation [P1] using the following equation:

where Q_it=X_it for i=2, 3, ..., i_l-1 and t=1, 2, ..., T, and Q_it=d_it for i=i_l, i_l+1, ..., N and t=1, 2, ..., T. Then, the objective function of [P1] becomes

By rearranging the above terms, we obtain

where c_1t=p₁+(T-t-l₁+1)_kH(1)h_ka_1k and c_it=p_i+(T-t-l_i+1)_kH(i)h_ka_ik– (T-t+1)h_i for the root (i=1) and the non-root parent items (i=2, 3, ..., i_l-1), respectively. Here, c_it implies the marginal disassembly operation cost of item i in period t, and H(i) denotes the set of child items of parent i. Also, the term remains constant, and hence can be removed without further consideration. Also, the nonnegative constraint (7) can be reformulated as

which can be obtained directly from (7) and (8). By changing the indices, that is, i and k are used instead of (i) and i, the above constraint can be changed into

Hereafter, the above constraint is called the demand constraint since it can be used to satisfy the demand requirements in the reformulation.

In the second step, a new demand constraint, which represents the constraint that the disassembly quantity of a parent should be at least more than or equal to the demand of its leaf items, is added to the reformulation since it is needed in the Lagrangean relaxation technique suggested in this paper. To explain the new demand constraint, let L(i) and P(i, j) denote the set of leaf items among successors of parent item i and the path from parent item i to leaf item j, respectively. For example, L(2)={8, 9, 10, 11, 12} and P(2, 12)=2 5 12 in Figure 1. Then, the new demand constraint for item i in period t can be represented as the new demand constraint for item i in period t can be represented as

where D_it^e and A_i0^e denote the transformed demand and the transformed initial inventory of item i in period t associated with the demand of leaf item e. More specifically,

and

Then, the constraint (9) should be further changed as

since the demand requirement of each of the items in L(i), that is, leaf items among successors of parent item i, can be satisfied by disassembling item i to the maximum amount to satisfy the demand requirements of all the leaf items in L(i). The transformed demand and the transformed initial inventory are explained with an example. In Figure 1, from the demand constraint defined earlier, we can obtain the following relations between items 2 and 5 such that 5H(2) in the path P(2, 12).

By combining them, the first inequality becomes

and hence the transformed demand and the transformed initial inventory of leaf item 12 with respect to item 5 are and , respectively. Also, after dividing the above equation by a_2,5, we obtain

Also, since and , the above equation becomes

Now, the integer program [P1] can be reformulated as follows:

and (3), (4), (5) and (6).

In the reformulation [P2], the new constraint (10) does not affect the optimal solution since all demand requirements can be satisfied with only constraint (7'). However, it is added to the reformulation because we design the solution algorithm to satisfy the demand requirements after the constraint (7') is relaxed. In fact, our algorithm is based on the relaxation of the constraints (7') and (3), and hence there is no way to satisfy demand requirements of leaf items in the relaxed problem without the constraint (10).

The Lagrangean heuristic

As stated earlier, the Lagrangean relaxation approach used in this paper is based on the relaxation of (7') and (3) in the reformulation [P2]. First, the objective function of the relaxed problem becomes

where _itk and _t are the Lagrangean multipliers corresponding to (7') and (3), respectively. By arranging the terms, the objective function becomes

where for the root item 1, for the non-root parent i=2, 3, ...i_l-1, and . Here, the last term F' is a constant and can be removed without further consideration.

Then, the relaxed problem is summarized in the following:

and t=1, 2, ...,T

(4), (5) and (6), and (10)

where and denote the vectors representing the Lagrangean multipliers.

The relaxed problem [LR] can be decomposed into the following mutually independent subproblems [SP1_i], i=1, 2, ...i_l-1.

Each of the subproblems [SP1_i], i=1, 2, ... i_l-1, is the single item lot-sizing problem that can be solved easily in a polynomial time using the algorithm suggested by Wagelmans et al (1992). In fact, the above formulation [SP1_i] is the same as that of Wagelmans et al (1992) except for the maximum term. Note that the maximum term in the formulation can be calculated in advance and hence our formulation is the same as that of Wagelmans et al (1992). Therefore, a lower bound can be obtained by solving subproblems [SP1_i] for i=1, 2, ... i_l-1, and the best one can be obtained with

which is called a Lagrangean dual problem.

The Lagrangean multipliers are updated using the subgradient optimization algorithm on which computational performance and theoretical convergence properties are discussed in Held et al (1974) and Goffin (1977). Subgradient optimization algorithm generates a sequence of Lagrangean multipliers using the following rule,

where _itk^w+1 and _t^w+1 denote the values of the multipliers updated at iteration w, and X_it^* for i=1, 2, ...i_l-1, and t=1, 2, ...T denote the optimal solution of the relaxed problem at iteration w. Also, _w and _w denote the step sizes at iteration w, updated by

where is the best upper bound, ^w and ^w denote the vectors of the Lagrangean multipliers at iteration w, and _w, 0_w2, is a constant. In general, the constant _w is set to 2 initially and is halved if the lower bound has not been improved in a predetermined number of iterations.

Now, we explain the Lagrangean heuristic that makes the solution of the relaxed problem [LR] feasible. Note that the Lagrangean solutions obtained from the relaxed problem are rarely feasible with respect to the original problem, and the heuristics that make those solutions feasible are called Lagrangean heuristics. To obtain a feasible one using the solution of the relaxed problem, two main steps are suggested in this paper. The first one is to generate a solution feasible to demand constraints, and the second one is to generate a solution feasible to capacity constraints.

To generate a solution feasible to the demand constraint (7'), we solve the following problem [SP2_i] from parent item i_l-1 to the root item 1.

To solve [SP2_i] as in the lower bound calculation, the algorithm suggested by Wagelmans et al (1992) can be used since [SP2_i] is also the single item lot-sizing problem. Note that in the problem [SP2_i], another demand constraint is used instead of

since the demand requirement of each of item i's child items can be also satisfied by disassembling item i to the maximum amount to satisfy the demand requirements of its child items. Also, the difference between [SP2_i] and [SP1_i] is that the demand constraints are used instead of the transformed demand constraints. Therefore, we can see that the demand requirements Q_kt, kH(i) can be satisfied since the problem [SP2_i] is solved recursively from parent item i_l-1 to the root item 1.

In the second step, the solution obtained from the first step is modified iteratively in such a way that the capacity constraint is satisfied. This is done by moving the amount of the overloaded disassembly quantity in an earlier or later period, called backward and forward moves in this paper.

Backward move

In this move, the overloaded disassembly quantity of an item assigned to the selected period is moved to one period earlier while considering the demand constraints (7') and the cost changes associated with the move. This is done for each of the items assigned to the selected period, and the best one that gives the minimum cost increase is selected. In this move, it is required to keep the feasibility of the inventory constraints and to calculate the disassembly quantity to be moved and its cost changes. The backward move is started from the last overloaded period, and continues to the first one until all the overloaded disassembly quantities are eliminated.

First, we explain the method to satisfy the demand constraints after the backward move. Consider a parent item i assigned to the overloaded period t. According to the definition of the backward move, a portion of the disassembly quantity X_it of parent item i in period t is moved to period t-1. Let X'_it and X_it be the disassembly quantities of item i in period t after and before the move, respectively. Then, using the demand constraint (7'), we can see that the following inequality in period t-1 should be satisfied after the move for the non-root parent items, that is, i=2, 3, ... i_l

Note that it is enough to consider the demand constraint only in period t-1 since those in the other periods including period t remain the same. Now, we have the relation between and , and hence . Therefore, the above inequality becomes

which specifies the minimum disassembly quantity of item i in period t in order to keep the feasibility of the demand constraint of item i in period t-1. Then, the disassembly quantity N_it required should be 0 for the root item and for non-root parent items,

and the disassembly quantity to be moved can be calculated as

where

is the overloaded capacity in period t and denotes the smallest integer that is greater than or equal to . Note that _it implies the quantity that can eliminate the overloaded capacity in period t or the maximum quantity that can be moved without violating the demand constraint in period t-1.

Now, the cost increase B_it for the backward move of _it from period t to t-1 can be expressed as

where ()=1 if >0, and 0 otherwise. The first term represents the cost changes of the marginal disassembly operation costs and the other two terms represent the set-up cost changes in periods t-1 and t, respectively. Then, among the parent items assigned to period t, we select the best item i^* that results in the minimum cost increase, that is, i^*=argmin iB_it, where ={i|X_it>0 for all i}. Also, the disassembly quantity of item i^* should be updated as

Forward move

Unlike the backward move, this move assigns the overloaded disassembly quantity of an item to one period later, and hence starts from the first overloaded period. Consider a parent item i assigned to the overloaded period t. According to the definition of the forward move, a portion of disassembly quantity X_it of parent item i in period t is moved to period t+1. In this case, the demand constraint (7') of its child items in period t+l_i should be satisfied, and those in the other periods (including period t+l_i+1) are not changed. The resulting inequality of child item kH(i) in period t+l_i becomes

After rearranging the terms, we obtain

Then, the disassembly quantity to be moved can be obtained as

in which the maximum value is used to satisfy the demand requirements of all child items of item i. Based on this, the associated cost increase F_it can be calculated as

where _it=min {K_t/g_i, X_it-N_it}. Also, the disassembly quantity of the best item i^* that gives the minimum cost increase should be updated as

Based on the backward and forward moves described above, the procedure to obtain a feasible solution can be summarized below.

Step 1: Generating a feasible solution for demand constraints

 Solve the subproblem [SP2_i] from item i_l-1 to 1 using the algorithm suggested by Wagelmans et al (1992).

Step 2: Generating a feasible solution for capacity constraints

 Step 2–1: Set b=T. (b is the starting period of the backward move).

 Step 2–2: (Backward move)

  (1) Set t=b.

  (2) Calculate K_t using . If K_t>0, perform the backward move. If the capacity constraint in period t is not satisfied, set f=t, that is, the starting period of the forward move.

  (3) Set t=t-1. If t>1, go to (2). If capacity constraints in all the periods are satisfied, stop and save the solution. Otherwise, go to Step 2–3.

 Step 2–3. Forward move

  (1) Set t=f.

  (2) Calculate K_t. If K_t>0, perform the forward move. If the capacity constraint in period t is not satisfied, set b=t, that is, the starting period of the back move.

  (3) Set t=t+1. If t<T, go to (2). If capacity constraints in all the periods are satisfied, stop and save the solution. Otherwise, go to Step 2–2.

Based on the above procedure, the Lagrangean heuristic suggested in this paper can be summarized as follows. In the procedure, the upper bound implies the solution value of the feasible solution obtained at each iteration of the Lagrangean heuristic. The algorithm is terminated after a predetermined number of iterations, that is, when the iteration count (w) reaches a predetermined limit (W).

Step 1:

Let w=0, _itk⁰=0 for i=1, 2, ... i_l-1, kH(i), and t=1, 2, ... T, and _t⁰=0 for t=1, 2, ... T. Let the upper and lower bounds be an arbitrary large number and 0, respectively. Calculate the transformed demands, the transformed initial inventories, and the marginal disassembly operation costs.

Step 2:

Calculate the Lagrangean cost v_it for i=1, 2, ...i_l-1 and t=1, 2, ...T. and the constant value. With the Lagrangean cost, solve subproblem [SP1_i], i=1, 2, ...i_l-1 using the algorithm suggested by Wagelmans et al (1992).

Step 3:

Obtain a lower bound by computing the objective function value using the solution of [LR]. If the lower bound is improved, update the lower bound. Also, find an upper bound using procedure 1. If it is improved, update the upper bound and save the solution.

Step 4:

Update Lagrangean multipliers using (11) and (12) with the step sizes, _w and _w determined by (13) and (14). Set w=w+1. If w>W, stop and otherwise, go to Step 2.

Computational experiments

To show the performance of the heuristic algorithm suggested in this paper, computational tests were done on a number of randomly generated problems. We generated 750 problems, that is, 25 problems for each combination of two levels of capacity tightness (loose and tight), five levels of the number of items (10, 20, 30, 40, and 50) and three levels of the number of periods (10, 20, and 30). For each level of the number of items, five disassembly product structures (and hence totally 15) were randomly generated. In the disassembly structures, the number of child items for each parent and its yield were generated from DU(2, 5) and DU(1, 3), respectively. Here, DU(a, b) is the discrete uniform distribution with [a, b].

For each disassembly structure, five problems with different data were generated for each level of the number of periods. Disassembly operation costs were generated from DU(50, 100), inventory holding costs were generated from DU(5, 10), and set-up cost was generated from DU(500, 1000). Capacity per period was set to 400, 480, and 540 with probabilities, 0.2, 0.5, and 0.3, respectively. Disassembly time was generated from U(1, 4), where U(a, b) is the uniform distribution with [a, b]. The demand is generated using the following procedure:

1. Demand is initially generated from 0 or DU(50, 200) with probabilities 0.1 and 0.9, respectively;
2. Using the demands generated from Step (1), the uncapacitated problem is solved by the algorithm suggested by Gupta and Taleb (1994);
3. The overall capacity usage (CU) of its solution is calculated using , where X_it is the solution of the reverse MRP algorithm; and
4. Demand is regenerated using d_it=TC/CUd_it', where denotes the largest integer that is less than or equal to , is a parameter that represents capacity tightness ( is set to 0.7 and 0.9 for the cases of loose and tight capacity tightness), TC is the sum of capacities over the planning horizon, that is, , and d_jt' is the demand generated initially in (1). Finally, disassembly lead times and initial inventories were set to 0 without loss of generality in the test problems.

The Lagrangean heuristic requires specific values for several parameters. In the experiments, these parameters after a preliminary experiment were set as follows: the iteration limit W was set to 5000; and _w was set to 2 initially and halved if the lower bound has not been improved in 90 iterations. To show the effectiveness of the Lagrangean heuristic algorithm, two performance measures were used in the test: percentage deviation from a lower bound obtained by solving the Lagrangean dual problem; and percentage deviation from the optimal solution value obtained using CPLEX 8.1, commercial integer programming software. Here, we set the time limit as 7200 s for the run of CPLEX 8.1 due to the excessive computational burden to obtain the optimal solutions.

The test results are summarized in Table 1(a) and (b) that shows the minimum, mean, and maximum values of the percentage deviations from lower bounds or optimal solution values and the numbers of problems that the optimal solutions were obtained. The percentage deviations from optimal solution values were not reported for many problem sets since we could not obtain the optimal solutions using CPLEX 8.1 within 7200 s. It can be seen from the table that the Lagrangean heuristic suggested in this paper gives near optimal solutions. That is, the overall percentage deviations from lower bounds are 0.18 and 0.46% for the cases of loose and tight capacity. Also, the overall percentage deviations from optimal solutions (averaged over the problems of which the optimal solutions can be obtained using CPLEX 8.1 within 7200 s) are 0.08 and 0.19% for the cases of loose and tight capacity. (This implies that the deviation would be smaller if an optimal solution was used). While the performance of the suggested algorithm was not much affected by the number of items, it was inversely affected by the number of periods, that is, it was better as the number of periods increased. This implies that if the number of period increases, the algorithm can give better solutions. Also, the performance of the suggested algorithm was affected a little by the capacity tightness: 0.46% deviation for tight capacity, 0.18% deviation for loose capacity. Computation times for the Lagrangean heuristic were significantly shorter than those for CPLEX 8.1, that is, less than 17 s were required while CPLEX for many problems requires more than 7200 s. This implies that the Lagrangean heuristic suggested in this paper can be used to solve practical-sized problems within a reasonable amount of computation times.

Table 1 - Test results for the suggested algorithm (a) Case of loose capacity and (b) case of tight capacity.

Full table

Concluding remarks

We considered the problem of determining the disassembly schedule of products in order to satisfy the demands of their parts or components over a finite planning horizon. The capacitated case with single product type without parts commonality is considered for the objective of minimizing the sum of set-up, disassembly operation, and inventory holding costs. The problem is solved using a Lagrangean relaxation approach in which the relaxed problem becomes the single item lot-sizing problem after decomposition. To find an upper bound (which is feasible with respect to the original problem), we suggest a backward and forward move method together with methods maintaining the feasibility, while considering the cost trade-offs. Test results on a number of randomly generated problems showed that the heuristic can give near optimal solutions within very short computation time.

There are several ways to extend this research. First, it is interesting to consider more general capacitated problems, that is, those with parts commonality or multiple product types. Second, like other disassembly problems, uncertainties such as stochastic demands and lead times, and defective parts and/or components are important considerations.

References

1. Boothroyd G and Alting L (1992). Design for assembly and disassembly. CIRP Ann: Manufac Technol 41: 625–636.
2. Erdös G, Kis T and Xirouchakis P (2001). Modeling and evaluating product end-of-life options. Int J Prod Res 39: 1203–1220.
3. Goffin JL (1977). On convergence rates of subgradient optimization methods. Math Program 13: 329–347. | Article |
4. Gupta SM and Taleb KN (1994). Scheduling disassembly. Int J Prod Res 32: 1857–1886.
5. Held M, Wolfe P and Crowther HP (1974). Validation of subgradient optimization. Math Program 6: 63–68. | Article |
6. Jovane F et al (1993). A key issue in product life cycle: disassembly. CIRP Ann: Manufac Technol 42: 651–658.
7. Kang J-G, Lee D-H and Xirouchakis P (2003). Disassembly sequencing with imprecise data: a case study. Int J Ind Eng 10: 407–412.
8. Kang J-G, Lee D-H, Xirouchakis P and Lambert AJD (2002). Optimal disassembly sequencing with sequence dependent operation times based on the directed graph of assembly states. J Korean Ins Ind Eng 28: 264–273.
9. Kang J-G, Lee D-H, Xirouchakis P and Persson J-G (2001). Parallel disassembly sequencing with sequence-dependent operation times. CIRP Ann: Manufac Technol 50: 343–346.
10. Kim H-J, Lee D-H, Xirouchakis P and Züst R (2003). Disassembly scheduling with multiple product types. CIRP Ann: Manufac Technol 52: 403–406.
11. Kim H-J, Lee D-H and Xirouchakis P (2005). A two-phase heuristic for disassembly scheduling with multiple product types and parts commonality. Int J Prod Res (in press).
12. Lambert AJD (2003). Disassembly sequencing: a survey. Int J Prod Res 41: 3721–3759. | Article |
13. Lee D-H (2005). Disassembly scheduling for products with assembly structure. Int J Mngt Sci 11: 63–78.
14. Lee D-H, Kang J-G and Xirouchakis P (2001). Disassembly planning and scheduling: review and further research. Proc Inst Mech Eng: J Eng Manufac – Part B 215: 695–710. | Article |
15. Lee D-H, Kim H-J, Choi G and Xirouchakis P (2004). Disassembly scheduling: integer programming models. Proc Inst Mech Eng: J Eng Manufac – Part B 218: 1357–1372. | Article |
16. Lee D-H and Xirouchakis P (2004). A two-stage heuristic for disassembly scheduling with assembly product structure. J Opl Res Soc 55: 287–297. | Article |
17. Lee D-H, Xirouchakis P and Züst R (2002). Disassembly scheduling with capacity constraints. CIRP Ann: Manufac Technol 51: 387–390.
18. Neuendorf K-P, Lee D-H, Kiritsis D and Xirouchakis P (2001). Disassembly scheduling with parts commonality using Petri-nets withtimestamps. Fundamenta Informaticae 47: 295–306.
19. O'Shea B, Grewal SS and Kaebernick H (1998). State of the art literature survey on disassembly planning. Concurrent Eng: Res Appl 6: 345–357.
20. Santochi M, Dini G and Failli F (2002). Computer aided disassembly planning: state of the art and perspectives. CIRP Ann: Manufac Technol 51: 1–23.
21. Taleb KN and Gupta SM (1997). Disassembly of multiple product structures. Comput Indus Eng 32: 949–961. | Article |
22. Taleb KN, Gupta SM and Brennan L (1997). Disassembly of complex product structures with parts and materials commonality. Prod Plan Control 8: 255–269. | Article |
23. Wagelmans A, Hoesel SV and Kolen A (1992). Economic lot sizing: an O(n log n) algorithm that runs in linear time in the Wagner–Whitin case. Opns Res 40: 145–156.
24. Xirouchakis P and Kiritsis D (1996). A generic Petri net model for disassembly planning processes. Proceedings of Symposium on Tools and Methods for Concurrent Engineering. Budapest, Hungary, pp 523–529.
25. Xirouchakis P and Kiritsis D (1997). Petri net model for disassembly process planning. Proceedings of ASME Conference on Concurrent Product Design and Environmentally Conscious Manufacturing. Dallas, Texas, USA, pp 255–267.

Acknowledgements

The financial supports from the Swiss National Science Foundation (SNF) under contract number 2000-066640 and the Korea Research Foundation grant (KRF-2004-03-D00468) are gratefully acknowledged.