بلوک های زنجیره ای مقاوم بر اساس ممنوعیت فعالیت الگوریتم جستجو برای مشکل تعیین اندازه دسته تولید پویا با بازده محصول و بازسازی

This paper studies the dynamic lot sizing problem with product returns and remanufacturing (DLRR). Given demands and returns over a planning horizon, DLRR is to determine a production schedule of manufacturing new products and/or remanufacturing returns such that demand in each period is satisfied and the total cost (set-up cost plus holding cost of inventory) is minimized. Since DLRR with general cost functions for set-ups of manufacturing and remanufacturing is NP-hard, we develop a tabu search to produce high-quality solutions. To generate a good initial solution, we use a block-chain based method where the planning horizon is split into a chain of blocks. A block may contain either a string of manufacturing set-ups, a string of remanufacturing set-ups, or both. Given the cost of each block, an initial solution corresponding to a best combination of blocks is found by solving a shortest-path problem. Neighboring operators aim at shifting integer variables for manufacturing and remanufacturing set-ups. We evaluate our algorithm on 6480 benchmark problems and compare it with other available algorithms. Computational results demonstrate that our algorithm produces an optimal solution in 96.60% of benchmark problems, with an average deviation of 0.00082% from optimality and it is a state-of-the-art method for DLRR.

Traditional manufacturing is unsustainable because it has produced significant adverse environmental impacts. Manufacturing generates more than 60% of annual non-hazardous waste [1] and causes challenges including pollution, natural resource depletion and shortages, and therefore high cost of landfill space and virgin materials [2] and [3]. Now, increasing international legislation and social pressure requires manufacturers to reduce the environmental impacts of their products and production process. Furthermore, global and mounting competition also requires companies to reduce product price while maintaining product quality. Remanufacturing is defined as a process of returning a used product to at least the original equipment manufacturer (OEM) performance specification from the customers’ perspective and giving the resultant product a warranty that is at least equal to that of a newly manufactured equivalent [4] and [5]. Remanufacturing is different from other product recovery options such as repair, refurbishing, cannibalization, and recycling [5] and [6]. Among these recovery types, repair, refurbishing, and remanufacturing upgrade the used products. But remanufacturing obtains the largest upgrade in quality and/or technology. Remanufacturing is able to help companies address the legislative, environmental, and competitive pressures [7], [8] and [9]. For instance, it can simultaneously improve competitiveness and limits environmental damage due to production by reducing production costs via reductions in processing and raw material usage. By integrating waste back into the production cycle, remanufacturing limits landfill and cost of waste disposal. Other benefits of remanufacturing include reductions in the level of virgin materials and energy used in production. As suggested, the weight of a remanufactured product may be obtained from used components, and such products have comparable quality to equivalent new products but require 50% to 80% less energy to produce [5]. In addition, remanufacturing may obtain 20% to 80% production savings in comparison to conventional manufacturing [10]. Remanufactured products include automotive and aircraft parts, compressors and electrical motors, office furniture, tires, toner cartridges, office equipment, machine tools, cameras and others [6] and [11]. Research papers on remanufacturing have grown extensively over the past two decades. For an overview, we refer the reader to [12], [13], [14], [15], [16], [17], [18] and [19]. During the past few years, there is an increasing and widespread attention to the operation system, where manufactured and remanufactured products are identical. In the literature, identical manufactured and remanufactured products are also referred to as serviceable products or serviceables [20]. In this paper, we consider the problem where manufactured and remanufactured products are identical. The presence of both set-up cost and holding cost gives rise to the lot sizing problem, which aims to determine the optimal timing and quantity of production over a number of future periods. In general, the lot sizing problem can be categorized into static and dynamic. The static lot sizing problem has a constant demand and continuous time scale. This category includes the famous economic lot scheduling problem (ELSP) and the economic order quantity (EOQ) model. When the demand is dynamic and deterministic, and the time scale is discrete, we get a dynamic lot sizing problem. Both the static lot sizing problem and the dynamic lot sizing without returns have been widely studied in the field of production and inventory control. However, the dynamic lot sizing problem with returns and remanufacturing has received relatively less attention. When a manufacturer has the choice of both manufacturing and remanufacturing, the manufacturer has to plan and monitor both serviceable products and returns. Teunter et al. [20] introduce the dynamic lot sizing problem with returns and remanufacturing (DLRR), and point out a new challenge brought by the separate set-up costs for manufacturing and remanufacturing in addition to the holding costs for carrying serviceable products and returns. Many production planning and decision problems are very hard to solve [9], [21], [22] and [23]. Proofs from complexity theory as well as computational experiments have also indicated that most lot sizing problems are hard to solve [24]. The existence of remanufacturing makes the dynamic lot sizing problem much more harder to solve. Teunter et al. [20] conjecture that the DLRR with separate set-up costs for manufacturing and remanufacturing is NP-hard. In a previous work, we have proven that this problem is an NP-hard combinatorial optimization problem [25]. Therefore, it is impractical to use exact algorithms to optimally solve the DLRR within an acceptable CPU time. Alternatively, it is interesting and valuable to quickly produce good, although not necessarily optimal, solutions by implementing metaheuristics. To the best of our knowledge, there is no existing metaheuristic in the literature for the DLRR, although some heuristics have been proposed (see Section 2). In this paper, we intend to fill this gap. The purpose of this paper is to develop an efficient and robust tabu search (TS) based algorithm to produce high-quality solutions for the DLRR in terms of minimizing the total costs of setups and holding inventory. Henceforth, we refer to this new proposed tabu search approach as TS-DLRR. In recent years, tabu search has been applied with a high degree of success to a variety of hard combinatorial optimization problems including vehicle routing problems [26], [27], [28] and [29], lot sizing problems [30], [31] and [32], crane scheduling problem [33], and network design problems [34] and [35]. As demonstrated, the overall performance of TS and other local search (LS) methods, to some extent, depends on the quality of the initial solution. For this purpose, we first discuss a new block-chain based method to get a starting solution, from which the TS-DLRR performs consecutive search in the solution space. The underlying principle is to view each feasible DLRR solution as a chain of blocks. The block-chain based method splits the planning horizon into a chain of blocks. Each block consists of a set of consecutive periods. A block may contain either a string of manufacturing set-ups, a string of remanufacturing set-ups, or both. If a block contains both manufacturing and remanufacturing set-ups, then the string of manufacturing set-ups precede the string of remanufacturing set-ups (see Section 4.3.2 for detailed definition). If we know the cost of each block, which is composed of set-up cost and holding cost of inventory, then a solution can be obtained using a shortest path algorithm. This initial solution corresponds to a best combination of blocks, of which the total cost of set-up and holding inventory is minimum. To compute the cost of each block, we propose a linear programming (LP) model, which can be quickly and efficiently solved by solvers such as CPLEX and LINGO. Note that although this LP model is a heuristic and does not guarantee integral values for the binary variables associated with manufacturing and remanufacturing set-ups (e.g., “1” denotes an occurrence of set-up, and “0” means no set-up), our computational experiments demonstrate that the solution to this LP model has the desirable property that when the 0–1 restrictions on the variables indicating whether a manufacturing/remanufacturing occurs or not in a period are relaxed, a large number of these variables assume integer values at the optimal solution. This was the case in most of the 6480 benchmark instances we tested. In the TS-DLRR, four simple, but very efficient neighboring operators are designed to explore the neighborhood of the current solution and to generate neighboring solutions. These operators generate neighbors of the current solution by shifting binary variables for set-ups of manufacturing, remanufacturing, or both. For instance, if a manufacturing set-up occurs in some period, this set-up may be eliminated altogether, or replaced with a manufacturing setup, or shifted to another period and so on. In detail, these operators include one-shift operator, two-shift operator, exchange operator, and cross two-shift operator. Further, as a diversification strategy, a restart based strategy is considered to force the search into previously unexplored regions in the search space, when no solution improvement is found within some consecutive iterations. Finally, a series of computational experiments are carried out to systematically evaluate the performance of the TS-DLRR by comparing it with other best available algorithms in the literature. Computational results demonstrate that our TS approach is the best method over a wide range of benchmark instances.

In today's circular economy, remanufacturing has become a promising and economic practice in the production and manufacturing. In this paper, we study the dynamic lot sizing problem with product returns and remanufacturing (DLRR). In the planning horizon, both manufacturing new products and remanufacturing returned products can be used to meet the demands. This lot sizing problem with general set-up cost functions for manufacturing and remanufacturing is an NP-hard problem. We develop a new tabu search metaheuristic to produce high-quality solution. This new algorithm includes some new features. To generate a high-quality initial solution, we present a block-chain based method, which splits the planning horizon into a chain of blocks. A block is a set of periods with either a string of manufacturing set-ups, a string of remanufacturing set-ups, or both. A new LP formulation is used to get the block cost. With cost of each block, we then find the best production schedule (best combination of blocks) by solving a shortest path problem. This block-chain based method can also be implemented as a heuristic for solving the DLRR. The neighboring operators are defined as shifting integer variables for set-ups of manufacturing and remanufacturing in the planning horizon. We carried out a computational study to evaluate the efficiency of the proposed tabu search metaheuristic. The computational results first show that the block-chain method can generate high-quality initial solutions, compared with the economic lot sizing based method. Over a set of 6480 benchmark instances, we experimentally compare the performance of the proposed TS method with other available methods from the literature and show that our TS approach outperforms other algorithms. Our proposed algorithm has produced an optimal solution in 96.60% of benchmark problems, with an average deviation of 0.00082% from optimality. We also demonstrated that the proposed approach was a robust method for larger DLRR instances. In summary, our proposed algorithms are applicable to the DLRR with a joint set-up cost as well as separate set-up costs for manufacturing and remanufacturing. In the future work, an interesting research avenue is to study other metaheuristics and exact algorithms for the DLRR with general set-up cost function.