:: Industrial Engineering & Management Systems ::
Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.17 No.2 pp.259-266
DOI : https://doi.org/10.7232/iems.2018.17.2.259

Dynamic Waste Collection and Multi-Product Remanufacturing Planning with Multiple Finite Remanufacturing Rates

Minsoo Kim, Woon-Seek Lee*
Division of Systems Management & Engineering, Pukyong National University, Busan, Republic of Korea
Corresponding Author, iewslee@pknu.ac.kr
January 17, 2017 February 27, 2018 March 5, 2018

ABSTRACT


This paper considers a waste collection and remanufacturing planning problem. Wastes are collected by a single container type and remanufacturing rate is any amount in the set {0,P,⋯, mP} where m is a nonnegative integer. Multiple products are remanufactured by each taking a fixed portion of the input wastes to satisfy dynamic demands of each product over a discrete and finite time horizon. The waste collection cost is proportional to the number of containers used. Also, a start-up cost is only incurred at the first period of consecutive remanufacturing periods. It is assumed that the related cost functions are concave and backlogging is not allowed. The objective of this paper is to simultaneously determine the optimal waste collection and remanufacturing plans that minimize the total cost. In this paper, the optimal solution properties are characterized and then, based on these properties, a dynamic programming algorithm is presented to find the optimal plan. Also, a network model is proposed to efficiently find the optimal solution for (u, v)-subproblems. Finally, the procedure for applying the proposed algorithm is illustrated by a numerical example.



초록


    1. INTRODUCTION

    Nowadays to minimize the wastes and thus reduce the impacts on environment, the concept of recycling is widely accepted by the public. Many governments usually set strict regulations to facilitate recycling of wastes in the wide industry sectors. Manufacturing industry is not an exception from these trends, too. This study is motivated from a single-facility multi-product problem in the recycling or remanufacturing industry in which byproducts such as kerosene oils, bunker C oils, and cokes are remanufactured by each taking a fixed portion of the input waste oils.

    This paper considers a waste collection and remanufacturing planning problem, in which the wastes are collected by a single type of container and can be remanufactured at each period by any amount in the set {0,P,…, mP} where the rate P is the increment of a remanufacturing capacity and m is a nonnegative integer. Multiple products are remanufactured by each taking a fixed portion ( 0 < α i < 1 ,     i = 1 M α i = 1 ) of the input wastes to satisfy dynamic demands of each product over a discrete and finite time horizon. The waste collection cost is proportional to the number of containers used. Also, start-up cost is only incurred at the first period of a remanufacturing block which is consecutively remanufactured. It is assumed that the related cost (collection and inventory holding costs of the wastes, and remanufacturing and inventory holding costs of the remanufactured products) functions are concave and backlogging is not allowed.

    The dynamic lot-sizing problem, as is originated by Wagner and Whitin (1958), is associated with a production system where a fixed setup cost is incurred at every production period. Dynamic lot-sizing problems with production capacity are considered by Florian and Klein (1971), Love (1973), and Swoveland (1975). The assumption of such production capacity does not capture the case of the finite production rate because it charges a setup cost at every period with a positive production regardless of any production in the previous period. However, in production scheduling environments, many production systems involve start-up costs incurred from switching on a machine such as a changeover costs between items or modes of production. Sobel (1970) analyzed a dynamic lot-sizing model with start-up and shutdown costs. Sethi and Chand (1981) considered a dynamic lot-sizing model with finite production rate in which the production in a period is restricted to be an amount in the set {0,P,…, mP} where m is a positive integer. They assumed that the setup cost was charged only once for a block of consecutive producing periods. Sung and Lee (1993) dealt with rolling schedules for a dynamic lotsizing model with start-up costs. Sung and Lee (1995) analyzed the setup cost reduction for a dynamic lot-sizing model with a finite production rate.

    The dynamic remanufacturing planning problem is originated by Richter and Sombrutzki (2000) who reinterpreted the study of Wagner and Whitin (1958) from the standpoint of reverse logistics. Richter and Sombrutzki (2000) considered the manufacturing and remanufacturing system where it was assumed that the input wastes are given enough to satisfy dynamic demands over a discrete and finite time horizon. Yang et al. (2005) proved that the manufacturing and remanufacturing hybrid problem with dynamic demands is an NP-hard problem when related cost functions are concave. Lee (2009) analyzed a dynamic remanufacturing planning problem with a discount purchasing option to simultaneously find the optimal purchasing and remanufacturing polices for used items (or wastes). Baki et al. (2014) considered a lot sizing problem of product returns and remanufacturing and proposed a dynamic programming algorithm based heuristic that exploits the block structure of the optimal solution. However, the aforementioned articles do not have considered a remanufacturing planning problem with multiple products and finite remanufacturing rate. Recently, Cunha et al. (2017) and Sifaleras and Konstantaras (2017) analyzed multi-product dynamic lot sizing problems with remanufacturing. Sifaleras and Konstantaras (2017) proposed an efficient variable neighborhood descent heuristic algorithm. Cunha et al. (2017) showed that high quality feasible solutions and bounds can be obtained by solving each item separately. However, they do not have considered a case with finite remanufacturing rate whereas they considered uncapacitated production and remanufacturing environments.

    Seo and Lee (2014) studied a dynamic model for waste withdrawing and remanufacturing planning, in which wastes are collected by single type of container and can be remanufactured at each period by any amount in the set {0, P}where the rate P is the remanufacturing capacity. Multiple products are remanufactured by each taking a fixed portion of the input wastes to satisfy dynamic demands of each product over a discrete and finite time horizon. Lee and Noh (2018) considered a dynamic waste withdrawing and remanufacturing planning problem where wastes can be collected at a period and also remanufactured by a finite remanufacturing rate like Seo and Lee (2014). But the withdrawal fee is occurred as a profit term that is proportional to the withdrawing container size. Also, the inventory amounts of wastes can be disposed at the end of a period by incurring a disposal cost.

    This study extends the previous work of Seo and Lee (2014) to the case with multiple finite remanufacturing rates which can be remanufactured at each period by any amount in the set {0,P,…, mP} where m is a nonnegative integer. The objective of this study is to determine the optimal waste collection and remanufacturing plans of wastes that minimize the total cost to satisfy dynamic demands of multiple products. Firstly, the optimization model is formulated for the given problem and the optimal solution properties are characterized. Secondly, a dynamic programming algorithm is proposed to efficiently find the optimal solution based on the solution properties. Also, an acyclic network approach is proposed to efficiently find the optimal solution for (u, v)-subproblems. Finally, the procedure for applying the proposed algorithm is illustrated by a numerical example.

    2. THE MODEL

    In the study, the related costs involving collection and inventory holding costs of the wastes, and remanufacturing and inventory holding costs of each remanufactured product are given as follows.

    2.1. Waste Collection Cost Function

    The waste collection cost is proportional to the number of containers used and it incurs multiple setup costs. As zt denotes the amount of wastes collected at time period t by a container of size W, the related cost function is defined as follows:

    P t ( z t ) = A z t / W

    where A and W denote the cost charged for each container used and the capacity of container, respectively. Here the symbol ⎡a⎤ denotes the smallest integer value that is greater than or equal to a. This cost function becomes a concave function with multiple setup costs.

    2.2. Remanufacturing Cost Function

    In the remanufacturing industry with refinery facilities, start-up costs are incurred usually to warm-up or setup those refinery facilities. Let Xt and x t i = ( α i X t ) denote the amount of input wastes at period t and the amount of remanufacturing for product i at period t, respectively. Then the related cost function is defined as follows:

    R t ( δ ( X t ) δ ( X t 1 ) ) + + i = 1 M r i x t i

    where Rt and ri denote start-up cost at period t and unit remanufacturing cost for product i, respectively, and M is the number of multiple products. Here both δ (a) and (a)+ are step functions that produce 1 when a > 0 and otherwise produce 0.

    2.3. Inventory Holding Cost Function

    As wastes and remanufactured products are stored, inventory holding costs for both wastes and products are incurred. Let Yt and Iti be the inventoried amount of wastes and remanufactured products at the end of period t, respectively. Also, let ht (Yt) and Hti (Iti) denote inventory holding cost functions for waste and product i during period t, respectively. It is assumed that inventory holding cost functions for waste and each remanufactured product are concave.

    In this study, the optimization model can be formulated by using the aforementioned notations as the following mixed integer programming model.(3)(4)(5)

    ( P )   M i n    T t = 1 [ ( P t ( z t ) + R t ( ( δ ( X t ) δ ( X t 1 ) ) + + M i = 1 r i x t i + h t ( Y t ) + M i = 1 H t i ( I t i ) ]

    s.t.

    Y t = Y t 1 + z t X t
    (1)

    x t i = α i X t , i = 1 , 2 , , M ; t = 1 , 2 , , T
    (2)

    I t i = I t 1 , i + x t i D t i , i = 1 , 2 , , M ; t = 1 , 2 , , T
    (3)

    X t { 0 , P , 2 P , , m P } , t = 1 , 2 , , T
    (4)

    Y 0 = I 0 i = Y T = 0 , i = 1 , 2 , , M
    (5)

    z t , Y t , I t i   0 , i = 1 , 2 , , M ; t = 1 , 2 , , T
    (6)

    Here, Dti and T denote the demand of remanufactured product i at period t and the length of planning horizon, respectively.

    The constraints of the above problem (P) form the closed and bounded set because all constraints are linear equalities and inequalities. Also, as the objective function is concave, the optimal solution shall be appeared on one of extreme points. Therefore, an efficient algorithm for searching optimal solution can be developed by characterizing the special structure of these extreme points.

    3. THE OPTIMAL SOLUTION PROPERTIES

    In the problem (P), it is assumed that m i n { H t i ,     i } h t for all t, because the inventory holding cost of each remanufactured product is generally greater than that of waste unit. Let L(t) be the minimum requirement of cumulative remanufacturing amounts to satisfy the demands of multiple remanufactured products from period 1 to period t. That is, L ( t ) = m a x { k = 1 t D k i / α i , i } . Also, it is assumed that the following condition is satisfied for the problem (P) to have feasible solutions.

    k m P max { L ( k ) } , k = 1 , 2 , , T
    (7)

    The total remanufacturing amounts i = 1 M r i x t i can be removed from the objective function of problem (P), since it is a constant. Also, the following property can be obtained because backlogging is not allowed from the assumption of the problem (P).

    [Theorem 1] The problem (P) can be transformed into the problem satisfying the followings:

    m P L ( t ) L ( t 1 ) , t = 1 , 2 , , T

    [Proof] Let’s assume that there exists a period t that satisfies mP < L(t) − L(t − 1). The amount of demands L(t) − L(t −1) − mP is transferred and added to the demands of the latest period s that satisfies m P > L ( s ) L ( s 1 ) . . That is, D s i = D s i + α i ( L ( t ) L ( t 1 ) m P ) for all i. If mP < L(s) − L(s − 1) is satisfied at period s, repeat the previous procedure. Therefore, the problem (P) can be transformed into the problem that mPL(t) − L(t −1) is satisfied for all period t by the condition of feasible solution (7). This completes the proof.

    To clearly define the optimal solution properties, the terminologies such as inventory point of remanufactured product, inventory point of waste, regeneration point, remanufacturing block, remanufacturing point, waste collection point, partial shipment point, full shipment point, and waste collection-remanufacturing sequence are defined as follows. Let E ( t ) = { i | m a x ( k = 1 t D k i / α i , i ) } . .

    [Definition 1]

    • 1) Let I ^ t i = α i L ( t ) / P P D i ( t ) , , where y de notes the smallest integer value that is more than or equal to y and D i ( t ) = j = 1 t D j i .

    • 2) Period t is an inventory point of remanufactured product if the following conditions are satisfied.

      • (i) Xt = 0

      • (ii) I t i < min ( α i P , D t + 1 , i ) for iE(t)

      • (iii) L(t) − L(t −1) < P

    • 3) Period t is an inventory point of waste if Yt < W

    • 4) Period t is a regeneration point if it is simultaneously an inventory point of remanufactured product and an inventory point of waste.

    • 5) The time interval from period r to period t is a remanufacturing block if the following conditions are satisfied.

      • (i) Xr−1 = 0

      • (ii) X k > 0 , k = r , r + 1 , , s ( r s < t )

      • (iii) X k = 0 , k = s + 1 , s + 2 , , t

    • 6) Period t is a remanufacturing point if it is the first period of a remanufacturing block.

    • 7) Period t is a waste collection point if zt > 0

    • 8) Period t is a partial shipment point if nW < zt < (n + 1)W, where n is a nonnegative integer value.

    • 9) Period t is a full shipment point if zt = (n + 1)W, where n is a nonnegative integer value.

    • 10) A waste collection-remanufacturing plan is a waste collection-remanufacturing sequence if the following is satisfied:

    S u v ( k , l ) = { z t , X t , u < t v | Y u = k , I u i = I ^ u i a n d Y v = l , I v i = I ^ v i , X u + 1 > 0 a n d X v = 0 }
    (5a)

    A feasible waste collection-remanufacturing plan can be partitioned into one or more waste collection-remanufacturing sequences. Because Y0 = YT = 0 and I0i = 0 for all i, the inventory level at the final period T shall be I T i = I ^ T i for iE(t) by the minimization feature of objective function. Thus, there exists at least one waste collectionremanufacturing sequence S0T (0, 0), because the final period T is both inventory points of remanufactured product and waste. Generally, if one feasible waste collectionremanufacturing plan includes k regeneration points, then the waste collection-remanufacturing plan can be partitioned into (k −1) waste collection-remanufacturing sequences. If a feasible waste collection-remanufacturing plan R includes a waste collection-remanufacturing sequence Smn (k,l and there exist two different waste collectionremanufacturing sequences S m n 1 ( k ,   l ) and S m n 2 ( k ,   l ) which can make S m n ( k , l ) = 1 2 { S m m 1 ( k , l ) + S m n 2 ( k , l ) } , then that waste collection-remanufacturing plan R is not an extreme point because it can make two different feasible waste collection-remanufacturing plans R 1 = ( z 1 1 , , z T 1 , X 1 1 , , X T 1 ) and R 2 = ( z 1 2 , , z T 2 , X 1 2 , , X T 2 ) that are same to the original plan R except the only difference that they include S m n 1 ( k , l ) and S m n 2 ( k , l ) , Using these properties of extreme points, the optimal solution property can be effectively identified.

    Defining E as the set of extreme points, the following optimal solution property is identified.

    [Theorem 2] Period t−1 is an inventory point of remanufactured product if period t is a remanufacturing point from the feasible waste collection-remanufacturing plan R that is within E.

    [Proof] Assume that there exists an optimal solution with a feasible waste collection-remanufacturing plan as is depicted in Figure 1. Because it can be assumed that D1i > 0 for at least one remanufactured product i, period 1 is a remanufacturing point and period 0 is an inventory point of remanufactured product by the assumption of this problem. Period l(≥ 1) denotes the last period of the first remanufacturing block in Figure 1. Period m and t denote the first period of the second and third remanufacturing blocks, while period n and u denote the last period of the second and third remanufacturing blocks, respectively. Let’s assume that period t − 1 is not an inventory point of remanufactured product. This implies that I t 1 ,   i α i P and I t 1 ,   i D t i , for i E ( t ) , and L ( t 1 ) L ( t 2 ) P .

    When I t 1 ,   i α i P for i E ( t ) , a new waste collection- remanufacturing plan can be made that decreases remanufacturing amounts at period n by P and increases remanufacturing amounts at period t−1 by P. This adjustment does not change either the waste collection plan or the remanufacturing costs. By moving the remanufacturing amounts from period n to period t−1, the inventory level of wastes and the total inventory level of remanufactured products are increased and decreased by P, respectively, between period n+1 and period t −1. Because m i n { H t i ,   i } h t , for all t by the definition of this problem, this adjustment makes a better waste collection- remanufacturing plan that decreases total cost.

    When I t 1 ,   i D t i for i E ( t ) , a better waste collection- remanufacturing plan can be obtained that has Xt = XtP, and thus reduces the total cost. Consider following two cases: (1) X j = m P , j > t , (2) X j < m P , for some j > t. For the case (1), set X u + 1 = X u + 1 + P . For the case (2), let s be the first period that satisfies Xs < mP. Transfer remanufacturing amounts P from period t into period s. Repeat this procedure until I t 1 ,   i < D t i is satisfied. Then a better waste collection-remanufacturing plan can be obtained.

    When L(t −1) − L(t − 2) ≥ P, a new waste collectionremanufacturing plan can be obtained that makes Xn = XnP and X t 1 = X t 1 + P . In this case, there is no change either to the waste collection plan or to the remanufacturing costs. By moving the remanufacturing amounts from period n to period t−1, the inventory level of wastes and the total inventory level of remanufactured products are increased and decreased by P, respectively, from period n to period t−1. Since m i n { H t i ,   i } h t , for all t by the definition of this problem, the total inventory cost of this new waste collection-remanufacturing plan is decreased. Therefore the proof is completed.

    From the result of [Theorem 2], if period t is a remanufacturing point, then the inventory level of remanufactured product iE(t) at period t−1 satisfies following equation.

    I ^ t i = α i L ( t ) / P P D i ( t )
    (8)

    As a result, the above property actually reduces the number of regeneration points.

    [Theorem 3] Under a feasible waste collectionremanufacturing plan R in E, the optimal waste collection plan satisfies following properties between two consecutive inventory points of waste s(s < t) and t.

    • (i) If Ys = 0, then it has at most one partial shipment point.

    • (ii) If Ys > 0, then it has no partial shipment point.

    [Proof] (i) Assume that there exists a waste collection- remanufacturing plan that has two partial shipment points s1 and t 1 ( s < s 1 < t 1 t ) with Ys = 0. Let’s define R m i n = m i n { z s 1 , Y s 1 , Y s 1 + 1 , , Y t 1 , z t 1 / W W z t 1 } . . A new waste collection-remanufacturing plan can be made by setting the amounts of wastes collected at period s1 to z s 1 =   z s 1 R m i n , the inventory level of wastes at period k ( s 1 + 1 k t 1 1 ) to Y k =   Y k R m i n , , and the amounts of wastes collected at period t1 to z t 1 =   z t 1 + R m i n . . This becomes a better waste collection-remanufacturing plan with the reduced inventory cost for wastes at the same waste collection cost.

    (ii) Consider a waste collection-remanufacturing plan that has one partial shipment point t 1 ( s < t 1 t ) and the last waste collection point s 1 ( s 1 < s )   with Ys > 0. Define R m i n = m i n { Y s , Y s + 1 , , Y t 1 , z t 1 / W W z t 1 } . A new waste collection-remanufacturing plan can be made by setting the amounts of wastes collected at period s1 to z s 1 =   z s 1 R m i n , , the inventory level of wastes at period k ( s 1 + 1 k t 1 1 ) to z t 1 =   z t 1 + R m i n . , and the amounts of wastes collected at period t1 to z t 1 =   z t 1 + R m i n . . This leads to a better waste collection-remanufacturing plan with the reduced inventory cost for wastes at the same waste collection cost. In this case, either the period t1 becomes a full shipment point or a new inventory point of waste that sets the level to 0 occurs between periods s and t1. This completes the proof.

    Also, the following property describes the relation between waste collection and remanufacturing points.

    [Theorem 4] On a feasible waste collection-remanufacturing plan R in E, if Xt = 0, then it should be zt = 0.

    [Proof] Assume that there exists a waste collectionremanufacturing plan with Xt = 0, zt > 0 and the first remanufacturing point after period t is t′, that is, Xt′ > 0. We can build a new waste collection-remanufacturing plan by setting the value zt = 0 and zt′ = zt′ + zt. This new plan becomes a better waste collection-remanufacturing plan with the reduced inventory cost for wastes at the same waste collection cost. Thus, the proof is completed.

    4. A DYNAMIC PROGRAMMING ALGORITHM

    With the properties of optimal solution that are clarified above, we can obtain following key characteristics that demonstrate the problem (P) can be solved by decomposition.

    [Theorem 5] (The Inventory Decomposition Property)

    Let’s consider that the following constraint is added to original constraints (1) - (6).(9)

    Y k = l   ( < W ) and I k i = I ^ k i for some k { 1 , 2 , , T 1 }
    (9)

    The optimal solution for the problem (P) can be obtained by solving the first k period’s problem and the remaining Tk period’s problem independently.

    [Proof] Waste collection costs and remanufacturing costs occur in accordance with the collected waste amounts and the remanufactured amounts for those corresponding periods. By equation (8), it is clear that the inventory costs for wastes and remanufactured products for the last Tk periods also occur only in accordance with the decision on waste collection and remanufacturing during those periods. Equation (7) guarantees the existence of feasible solution for the problem of remaining Tk periods. Therefore, the proof is completed.

    By using the properties of optimal solution that are identified above, an efficient dynamic programming algorithm for searching optimal solution of the problem (P) can be suggested as follows:

    f 0 ( 0 ) = 0 , f v ( l ) = min 0 u < v { d u v ( k , l ) + f u ( k ) } for  v = 1 , 2 , , T ; k = 0 , 1 , , W 1 ; l = 0 , 1 , , W 1
    (10)

    Here, fv (l) is the cost related with an optimal solution for the period 1, 2,…, v when Y v = l , I v i = I ^ v i (   i ) . And duv (k, l) is the cost related with an optimal solution for the period u + 1,…, v when Yu = k. I u i = I ^ u i ( i ) and Yv = l, I v i = I ^ v i ( i ) .

    The cost value duv (k, l) that is needed to apply dynamic programming algorithm (10) corresponds to the minimum cost of the waste collection-remanufacturing sequence among the Suv (k, l) that satisfies [Theorem 2], [Theorem 3], and [Theorem 4].

    The calculation of cost value duv (k, l) for the dynamic programming algorithm (10) becomes a combinatorial problem between the waste collection amounts and the remanufacturing amounts that meet the demands of multiple products over the (u, v) -subproblem which is partitioned by consecutive regeneration points u and v. The properties of optimal waste collection and remanufacturing amounts that are needed to calculate the cost value duv (k, l) can be clarified as follows.

    [Corollary 1] For a (u, v) -subproblem, the optimal waste collection-remanufacturing sequence includes one remanufacturing block where the period u + 1 is a remanufacturing point. If the inventory level of wastes and remanufactured products at regeneration points u and v are Yu = k, I u i = I ^ u i and Y v = l , I v i = I ^ v i , , respectively, then the cumulative waste collection amounts satisfy the following:

    Z u + 1 ,   v = n P k + l

    Here, n = u + m a x { ( j = u + 1 v D j i I ^ u i + I ^ v i ) / α i } / P and m a x { ( j = u + 1 v D j i I ^ u i + I ^ v i ) / α i } / P is an integer value by the definition of I ^ t i . The cumulative waste collection amounts Zst is defined as Z s t = j = s t z j . .

    It is obvious that [Corollary 1] is satisfied by [Theorem 2], [Theorem 3], and [Theorem 4].

    [Corollary 2] For a (u, v) -subproblem, the optimal waste collection plan in the optimal waste collectionremanufacturing sequence has following properties over all periods t(utv).

    • (i) If Yu = 0, then n 1 W z t + 1 < ( n 1 + 1 ) W . Here, n1 is a nonnegative integer.

    • (ii) If Yu > 0, then z t + 1 = n 1 W . . Here, n1 is a nonnegative integer.

    It is obvious that [Corollary 2] is satisfied by [Theorem 3].

    [Corollary 3] For a (u, v) -subproblem, the optimal remanufacturing plan can be established as follows.

    • Step 1: For t = u, set I t i = I ^ t i and X ^ t + 1 ,   v = ( I ^ v i I ^ t i ) / α i + L ( v ) L ( t ) . . Assign S = 0 and t = t + 1.

    • Step 2: Calculate the value k t = m i n { r { 1 ,   2 , | r P L ( t ) L ( t 1 ) I t 1 ,   i / α i , for i E ( t ) } .

    • Step 3: If S < X ^ t v , then set t = t + 1 and go to [Step 2].

    • Step 4: Set Xj = 0 , for j = t + 1, t + 2,…, v. Finish all steps.

    Above [Corollary 3] provides the optimal remanufacturing plan that reduces the costs by minimizing the inventory level of remanufactured products. By the properties of optimal solution identified above, the calculation method for cost value duv (k, l) is the same to find minimum cost route from an acyclic network. With [Corollary 3], the cumulative remanufacturing amounts from period u + 1 to v, X ^ t = j = u + 1 t X j   ( u + 1 t v ) has a value from { P , 2 P , , n P } , where n = u + m a x { ( j = u + 1 v D j i I ^ u i + I ^ v i ) / α i } / P . 1 {( ˆ ˆ ) v j u ji ui vi n u max D I I = + = + Σ − + /αi}/ P. Likewise, with [Corollary 2], the cumulative waste collection amounts from period u + 1 to v, Z ^ t = j = u + 1 t z j   ( u + 1 t v ) has a value from { 0 , W , 2 W , , if k > 0. Or it has a value from { ϵ , ϵ + W , ϵ + 2 W , , ϵ + n ^ W } , if k = 0. Here, ϵ = m o d ( ( n P k + l ) , W ) ( 0 ϵ < W ) , where mod(a, b denotes the remainder of division a by b. And n ^ = ( n P k + l ) / W .

    Therefore, for each t(t = u + 1,…, v), an acyclic network can be constructed that has the nodes of possible ( X ^ t , Z ^ t ) values with the arcs of ( ( X ^ t , Z ^ t ) , ( X ^ t + 1 , Z ^ t + 1 ) ) . From this acyclic network, since following cases do not provide a feasible solution, those cases can be excluded from the node generation and removed from the cost calculation of that arc.

    • 1) For u < t v , if X ^ t + 1 < X ^ t , then it becomes an infeasible solution. In this case, the arc is removed.

    • 2) For u < t v , if Z ^ t + 1 < Z ^ t , then the generation of all nodes that involve ˆXt is excluded.

    • 3) For u < t v , if Z ^ t < X ^ t , then it becomes an infeasible solution. In this case, the arc is removed.

    • 4) For u < t v , if Z ^ t < X ^ t , then for at least one remanufactured product i, it occurs to Iti < 0 and thus becomes an infeasible solution. In this case, the node ( X ^ t , Z ^ t ) is removed.

    In addition, by the definition of remanufacturing block, as remanufacturing is occurred for all periods from u to v when kv > 0, it becomes infeasible and thus leads to duv (k, l) = ∞. Here, k t = m i n { r 1 , 2 , , m } | r P L ( t ) L ( t 1 ) I t 1 , i / α i , for i E ( t ) } .

    This acyclic network has an artificial starting node ( X ^ s , Z ^ s ) with X ^ s = 0 and Z ^ s = 0. It also has a terminal node (Xˆ v , Zˆv ) that must satisfy X ^ v = m a x { ( j = u + 1 v D j i I ^ u i + I ^ v i ) / α i , i } and Z ^ v = n P k + l , where n = u + m a x { ( j = u + 1 v D j i I ^ u i + I ^ v i ) / α i } / P . All the routes from starting node ( X ^ s , Z ^ s ) to terminal node ( X ^ v , Z ^ v ) represent all the feasible waste collection-remanufacturing sequences, where the cost corresponding to each arc can be calculated as follows:

    g ( ( X ^ t , Z ^ t ) ,   ( X ^ t + 1 , Z ^ t + 1 ) ) = P t + 1 ( Z ^ t + 1 Z ^ t ) + R t + 1    ( δ ( X ^ t + 1 ) δ ( X ^ t ) ) + + h t + 1 ( Z ^ t + 1 X ^ t + 1 + k )    + i = 1 M H t + 1 , i ( α i X ^ t + 1 j = u + 1 t + 1 D j i + I ^ u i )    for t = s , u + 1 , , v 1

    Here, X ^ s = Z ^ s = 0 for s = u.

    As a result, the minimum cost route from starting node ( X ^ s , Z ^ s ) to terminal node ( X ^ v , Z ^ v ) becomes the optimal waste collection-remanufacturing sequence and the minimum cost becomes duv (k, l).

    5. A NUMERICAL EXAMPLE

    The procedure for applying the proposed dynamic programming algorithm and network model is illustrated by a numerical example with 2 products and 6 periods where m = 3, P = 2, W = 4, α 1 : α 2 = 2 5 : 3 5 as a remanufacturing ratios, A = 10, Rt = 20, ri = 0, h t ( Y t ) = Y t , H t i ( I t i ) = 2 I t i . . Table 1 shows the summary of demand data, Dmax (t), and I ^ t i . The candidate set of the inventory point of remanufactured product, j(T), can be {0, 3, 4, 6} from [Definition 1] and [Theorem 2]. That is, periods 1, 2, and 5 cannot be an inventory point of remanufactured product. Also, {Dmax (t)} = {0, 10, 10, 20} for ij(T) and the inventory level of wastes k and l have 0 or 2 because of W = 4.

    We also provide details of some representative calculations. Firstly, the calculation procedure of d04(0, 2) is described. Because D m a x ( 1 ) = 10 / 3 , D m a x ( 2 ) = 25 / 3 , D m a x ( 3 ) = D m a x ( 4 ) = 10 , and P = 2, the cumulative remanufacturing amounts X ^ 4 have a value of {4, 10}. That is, X1 = 4, X2 = 6, X3 = X4 = 0 is the optimal solution to satisfy demands, and then Z ^ 14 = X 14 k + l = 10 0 + 2 = 12 . Also, the cumulative waste collection amounts Z ^ 4 = Z 14 have a value of {0, 4, 8, 12} because ϵ = mod( Z 14 , W ) = mod(12, 4) = 0 and W = 4 . Therefore we can calculate the optimal waste collection amounts { z t * } for t = 1, …, 4 by using an acyclic network where takes the possible values of ( X ^ t , Z ^ t ) as the node and ( ( X ^ t 1 , Z ^ t 1 ) ( X ^ t , Z ^ t ) ) as the arc. Then we can obtain the optimal waste collection amounts z t * = 4 , z 2 * = 8 , z 3 * = z 4 * = 0 and the optimal cost value d04(0, 2) = 66 from Figure 2. Also, the cost value for the arc ((0, 0), (4, 4)) from the node (0, 0) to the node (4, 4) is calculated by the equation (11) as follows:

    g ( ( 0 , 0 ) , ( 4 , 4 ) ) = 10 × 1 + 1 × ( 4 4 ) + 20 + 2 × ( 4 × 2 5 1 ) + 2 × ( 4 × 3 5 2 ) = 32

    Therefore, we can see that the optimal plan is determined by a route to minimize the inventory costs of wastes and remanufactured products. We can obtain all the values of duv (k, l) and fv (l) for feasible inventory points of remanufactured product j(T) = {0, 3, 4, 6} and k = l ={0, 2} as Table 2. We can know that the optimal solution is determined by the combination of the two optimal waste collection-remanufacturing quences S04(0, 2) and S46(2, 0). Then the optimal waste collection-remanufacturing plan is ( { z t * } ; { x t * } ) = (4, 8, 0, 0, 4, 4 ; 4, 6, 0, 0, 6, 4) and the minimum cost is 108. Figure 3 shows the network representation for calculating f6(0) associated with the optimal solution.

    6. CONCLUSION

    In this paper, a new dynamic waste collection remanufacturing planning problem was dealt with. Here, wastes are collected by single type of container (W) to meet dynamic demands on multiple remanufactured products with minimum cost and are remanufactured at each period by any amount in the finite set of remanufacturing rate { 0 , P , , m P } . Multiple products are simultaneously remanufactured by taking their fixed portions from the input wastes. To solve this problem, a mathematical model for the waste collection-remanufacturing planning problem was suggested. And the properties of optimal solution were found by identifying the characteristics of extreme points for optimal solution. In addition, a dynamic programming algorithm that can build the optimal waste collection-remanufacturing plan was suggested by using the property of inventory decomposition. An acyclic network approach to efficiently find the cost value of d u v ( k , l ) was also presented, which is needed to apply the above dynamic programming algorithm. It is expected that the result of this research can provide a theoretical foundation for efficient remanufacturing planning in the industries for recycling and reuse.

    Further research direction is to consider the waste collection-remanufacturing planning problem where wastes are collected by multiple types of containers with herterogeneous capacities, and multiple by products are remanufactured with fixed proportions from the wastes.

    ACKNOWLEDGEMENT

    This research was supposted by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by Ministry of Education, Science, and Technology (NRF-2011-0013908).

    Figure

    IEMS-17-259_F1.gif

    An example of the optimal waste collectionremanufacturing plan.

    IEMS-17-259_F2.gif

    The acyclic network for calculating d04(0,2).

    IEMS-17-259_F3.gif

    The network representation for calculating f6 = 0.

    Table

    The summary of demand data and inventory levels

    The calculation summary of duv(k,l) and fv(l)

    REFERENCES

    1. M. F. Baki (2014) A heuristic solution procedure for the dynamic loot sizing problem with remanufacturing and product recovery., Comput. Oper. Res., Vol.43 ; pp.225-236
    2. J.O. Cunha , I. Konstantaras , R.A. Melo , A. Sifaleras (2017) On multi-item economic lot-sizing with manufacturing and uncapacitated production., Appl. Math. Model., Vol.50 ; pp.772-780
    3. M. Florian , M. Klein (1971) Deterministic production planning with concave costa and capacity constreaints., Manage. Sci., Vol.18 (1) ; pp.12-20
    4. W.S. Lee (2009) AA dynamic remanufacturing planning problem with a discount purchasing option., Journal of the Korean Operations Research and Management Science Society, Vol.34 (2) ; pp.711-784
    5. W.S. Lee , M.S. Noh A dynamic waste with drawing and multi-product remanufacturing planning problem with waste disposal and finite remanufacturing rate., Journal of the Korean Data Analysis Society, In Press
    6. S.F. Love (1973) Bounded production and inventory models with piecewise concave costs., Manage. Sci., Vol.20 (3) ; pp.313-318
    7. K. Richter , M. Sombbrutzki (2000) Remanufacturing planning for the reverse Wagner/Whitin models., Eur. J. Oper. Res., Vol.121 (2) ; pp.304-315
    8. W.C. Seo , W.S. Lee (2014) A dynamic waste withdrawing and multi-product remanufacturing planning problem with finite remanufacturing rate., Journal of Korean Management Enginersrs Society, Vol.19 (22) ; pp.1-13
    9. S. Sethi , S. Chand (1981) Multiple finite production rate dynamic lot size inventory models., Oper. Res., Vol.29 (5) ; pp.931-944
    10. A. Sifaleras , I. Konstantaras (2017) Variable neighborhood descent heuristic for solving reversse logistics multi-item dynamic lot-sizing problems., Comput. Oper. Res., Vol.78 ; pp.385-392
    11. M.J. Sobel (1970) Smoothing start-up and shut-down costs: Concave case., Manage. Sci., Vol.17 (1) ; pp.788-791
    12. C.S. Sung , W.S. Lee (1993) Rolling schedules for a dynamic lot-sizing problem with start-up costs., Eng. Optim., Vol.22 (2) ; pp.137-152
    13. C.S. Sung , W.S. Lee (1995) Setup cost reduction in a dynamic lot size model with multiple finite production rates., Eng. Optim., Vol.24 (1) ; pp.119-137
    14. C. Swoveland (1975) A deterministic multi-period production planning model with piecewise concave production and holding-backorder costs., Manage. Sci., Vol.21 (9) ; pp.1007-1013
    15. H.M. Wagner , T.M. Whitin (1958) Dynamic version of the economic lot size model., Manage. Sci., Vol.5 (1) ; pp.899-96
    16. J.B. Yang , B. Golany , G. Yu (2005) A concavecost production planning problem with remanufacturing options., Nav. Res. Logist., Vol.52 (5) ; pp.443-458
    오늘하루 팝업창 안보기 닫기