یک رویکرد مبتنی بر آرام سازی لاگرانژی برای مشکل ظرفیت زیادی اندازه در زنجیره تامین حلقه بسته

This paper investigates the capacitated lot sizing problem in closed-loop supply chain considering setup costs, product returns, and remanufacturing. We formulate the problem as a mixed integer program and propose a Lagrangian relaxation-based solution approach. The resulting Lagrangian subproblems are then solved by polynomial time algorithms. Compared to existing solution methods in the literature, our Lagrangian relaxation based approach is advantageous in that it naturally provides a lower bound on the optimal objective function value, which allows us to assess the quality of solutions found. Numerical experiments using synthesized data demonstrate that our approach can find quality solutions efficiently.

In recent years, the lot sizing problem (LSP) in closed-loop supply chain has received growing attention (Jr. and Wassenhove, 2009). Unlike traditional supply chain, where products flow from manufacturers to customers, in closed-loop supply chain, the manufacturers often setup a program to collect used products from customers and further process them to make a profit or reduce their environmental impacts. Such collection programs then incur reverse product flows from customers back to manufacturers and form what is called a closed-loop supply chain. In closed-loop supply chain, the lot sizing problem needs to take into consideration not only time-varying demands for a set of products over certain periods but also the inventory costs and processing costs associated with collected used products. The goal is to produce a cost-minimizing production schedule, that is, the production quantities for each product at each period (Brahimi et al., 2006b). In this paper, we study the capacitated lot sizing problem in closed-loop supply chain where setup costs, product returns and remanufacturing are considered. Our research originated from the collaboration with a paper product manufacturer. Besides making newly manufacturers paper product from virgin pulp, the manufacturer also utilizes deinked pulp processed from collected recyclable paper to make remanufactured product. The two paper products made from virgin pulp and deinked pulp are branded differently to serve different market segments. In its plant, the production using virgin pulp and that using deinked pulp are subject to an overall production capacity limit. When recyclable paper products can not be processed into deinked pulp fast enough, they incur inventory cost at the warehouse. The manufacturing cost for virgin pulp and the remanufacturing cost for de-inked pulp are different and so are the demands and prices of the final paper products made from the two types of pulps. Since the pioneering work of Wagner and Whitin (1958), there has been a growing interest in lot sizing problem. For a review of lot sizing problems, their extensions and solution approaches, please refer to Karimi et al. (2003), Brahimi et al. (2006b), Degraeve and Jans (2007), Quadt and Kuhn (2008) and Buschkühl et al. (2010). Recent research can be referred to Hop and Tabucanon (2005), Brahimi et al. (2006a), Pan et al. (2009), Süral et al. (2009), Smith et al. (2009), Cárdenas-Barrón (2010), Önal and Romeijn (2010), Piñeyro and Viera (2010), Helber and Sahling (2010), Sancak and Salman (2011), Kenné et al. (2011). Existing literature on capacitated closed-loop lot-sizing problem is limited. Li et al. (2007) examine the capacitated lot sizing problem with substitutions and return products. They first develop a heuristic genetic algorithm (GA) to determine all periods requiring production setup and then take a dynamic programming approach to determine the quantities produced for new products and remanufactured products. The performance of their heuristic genetic algorithm is compared to a branch-and-bound algorithm implemented in Lingo. Although genetic algorithm can produce good feasible solutions, it is difficult to gage its optimality. More recently, Pan et al. (2009) study the capacitated lot sizing problem in closed-loop supply chain where returned products are collected from customers. They look at several variants of the problem and take a dynamic programming (DP) approach to solve the models. In the variant where both production and remanufacturing are capacitated, a pseudo polynomial time algorithm is proposed. Experiments show that their approach can find optimal solutions for small problem instances, however, for large-scale problems, dynamic programming based approaches suffer from the renowned problem of ”curse of dimensionality” and it is difficult, if not impossible, to solve the model. In this paper, we study a variant of the capacitated lot sizing problem in closed-loop supply chain. The problem context in our mind is as follows. A factory produces two types of products, one manufactured from raw materials and the other remanufactured from collected used products. The demands for these two products are separate, deterministic, and time varying during a finite planning horizon, and should be satisfied without backlogging. The total production capacity for manufacturing new product and remanufacturing used product are limited. We formulate the problem as a mixed integer programming model and develop a Lagrangian relaxation (LR) based solution approach. The Lagrangian subproblems are solved by polynomial time algorithms. Compared to existing GA or DP based algorithms, our approach is advantageous in that: (a) the LR approach can provide a lower bound to assess the quality of solutions found while GA approach cannot; and (b) although the DP approach can find optimal solutions to small size problems, it often fails for larger instances. Computational experiments demonstrate that our approach can find satisfactory solutions efficiently. The remainder of the paper is organized as follows. In Section 2, we define notations used in this paper and present our model. We discuss the details of our Lagrangian relaxation based approach in Section 3. In Section 4, we perform extensive computational experiments to evaluate the performance of the algorithm. Finally, we conclude this paper and outline future research directions in Section 5.

In this paper, we propose a Lagrangian relaxation-based solution algorithm to solve a capacitated lot sizing problem with setup costs, product returns and remanufacturing, which has received a growing attention in recent years. The lower bound is calculated by decoupling the relaxed problem into two subproblems, which are solved by two polynomial-time algorithms, respectively. Two efficient and effective heuristics are proposed to find the good upper bound. Numerous computational experiments show that the proposed algorithm is capable of solving the problem efficiently. The impact of capacity on the performance and the behavior of the model are investigated as well. There are some extensions of this work. First, manufacturing and remanufacturing activities are only considered in the model. There exist more activities in a closed-loop supply chain, for instance, refurbuishing, recycling, etc, all of them have a closed relation with production planning. It is interesting to consider more general planning scenarios. Second, handling returned products is a strongly random activity. Therefore, it is our future work to study the stochastic counterpart of the model.