الگوریتم ژنتیک اکتشافی برای مشکلات ظرفیت برنامه ریزی تولید با پردازش دسته ای و بازسازی

In this paper, we analyze a version of the capacitated dynamic lot-sizing problem with substitutions and return products. Both batch manufacturing and batch remanufacturing are considered within the framework of deterministic time-varying demands in a finite time horizon, where the option of emergency procurement/outsourcing subject to a subcontract is also allowed. Setup costs are taken into account when batch manufacturing or batch remanufacturing takes place. We first apply a genetic algorithm to determine all periods requiring setups for batch manufacturing and batch remanufacturing, then develop a dynamic programming approach to provide the optimal solution to determine how many new products are manufactured or return products are remanufactured in each of these periods. The objective is to minimize the total cost, including batch manufacturing, batch remanufacturing, emergency procurement, holding and setup costs. Numerical examples illustrate the effectiveness of the approach.

Due to both economic incentives and legal pressures, more and more companies engage in the product recovery business, which entails activities to regain materials and value adding in return products. A very important field of product recovery is remanufacturing. It involves activities that make remanufactured products or major modules be marketable again and potentially as good as new. This is a widespread phenomenon for high-valued industrial products like copiers, computers, vehicle engines or medical equipment. The traditional models of production planning and inventory control (see Orlicky, 1975) usually do not take into account the multiple uses of products. Only recently research has been started to integrate so-called product recovery management into production planning systems (see Schrady, 1969, Richter, 1997, Richter and Sombrutzki, 2000, Richter and Weber, 2001 and Beltran and Krass, 2002) as one of the approaches of an ecologically oriented production management. These approaches endeavor to model product recovery management activities under several assumptions including, in particular, the assumption of deterministic demands. Although some underlying assumptions, in particular, deterministic demand and finite-horizon, are quite restrictive, the model has seen numerous applications in a variety of areas in operations management. These range from production planning/inventory control settings to capacity expansion problems (Luss, 1982), product assortment, batch queuing, investment-consumption and reservoir-control problems (Veinott, 1969). The deterministic models can primarily be subdivided into static and dynamic models. The former corresponds to the classical economic order quantity (EOQ) seeking an optimal tradeoff between fixed setup and variable holding costs. Several authors have proposed extensions to this model that take return flows into account. A first model of this type has been proposed by Schrady (1969). Mabini et al. (1992) have extended the model to multi-item system where all items share a common repair facility. Subsequently, Richter (1994) considered Schrady's model for alternating procurement and recovery batches. Richter, 1996 and Richter, 1997 extended the analysis to multiple consecutive procurement and recovery batches. Furthermore, Teunter (2001) considered the same model for a modified disposal policy. Rather than assuming a constant disposal rate, he assumed all returns that occur during a certain time span are disposed. Expressions for the optimal lot-sizing are derived under this policy. Besides the above static models, several dynamic lot-sizing models similar to the classical Wagner and Whitin (1958) one have been proposed in the reverse logistics context. Richter and Sombrutzki (2000) discussed applicability of the original Wagner/Whitin model in reverse logistics situations. By reversing the time axis they showed that the traditional model could be interpreted as looking for optimal recovery batches for accumulating return products. Note that this interpretation includes neither an alternative procurement option nor disposal. Beltran and Krass (2002) considered a dynamic lot-sizing problem for an inventory point facing both demand and returns. This transpires to the original Wagner/Whitin model with the exception that (net) demand may be positive or negative. Moreover, the inventory may both be raised by procurement and be decreased by disposal. The authors have shown that the zero-inventory-production property, which is well known for the original model, needs to be modified. A procurement order may sometimes be delayed beyond the first occurrence of inventory depletion due to returns. The authors have proposed a dynamic programming approach in the general case. Demand substitution in inventory management is envisaged in a variety of contexts for traditional production planning. Most papers concentrate mainly on the problem in a single period. A detailed literature review can be found in Smith and Agrawal (2000). Balakrishnan and Geunes (2000) considered a requirement planning problem with substitutions in a multi-period horizon. A dynamic programming method was derived to find the production and substitution quantities that satisfy given multi-period downstream demands at a minimum total setup, production, conversion and holding cost. However, few authors, except Inderfurth, considered the production planning problem with consideration of remanufacturing and product substitution at the same time. Inderfurth (2003) has derived optimal policies for hybrid manufacturing/remanufacturing systems with product substitution. A new product is offered in place of a remanufactured one when there is a remanufactured product shortage. In Li et al. (2006), we analyzed a version of the dynamic lot-sizing model with substitution and return products. A dynamic programming approach has been proposed to derive the optimal solution in the case of a large quantity of return products. Then a heuristic approach for the general problem has been presented to determine feasible production plans. In this paper, we deal with a multi-period production planning problem with return products under substitution and capacity constraints. Product demands should be fulfilled either by manufacturing new products or by remanufacturing the products returned from customers in batches. Otherwise, emergency procurement/outsourcing subject to a subcontract is adopted to meet the unfulfilled demands when needed. A substitution takes place whenever the demand for a type of product is met using stocks of another product type. Although various substitution structures arise in real life, our study focuses on downward substitution where product i can be substituted by product j, but not vice versa. Downward substitution happens, for instance, in a semiconductor industry producing similar integrated circuits with varying performance characteristics, where circuits with higher-performance characteristics (such as, speed) could substitute for circuits with lower-performance characteristic, but not vice versa. Another example (Leachman, 1987) in the same industry relates to memory chips where a higher capacity (16 Mbytes) chip can be used to meet demands for a lower capacity memory (8 Mbytes) chip. The problem we formulate and solve in this paper can be characterized as follows: (1) two product types are considered and substitution of one product by another one may take place when needed; (2) the capacity constraints may include the capacity limitations of multiple resources and the capacity limitations of available return products that can be remanufactured; (3) batch manufacturing and remanufacturing are considered together in production activities; (4) emergency procurement/outsourcing is allowed if needed when demands cannot be fulfilled by batch manufacturing and remanufacturing; and/or (5) all the parameters in the problem are time-varying. Our model has been motivated by manufacturing systems with substitutable and returned products. Consider the following example: a manufacturer produces two types of electronic appliance (e.g., a cordless telephone set). Type 2 has more functions and is therefore considered substitutable to type 1. There is a warrant period given to a customer who purchased a product, within which the product can be returned to the retailer if it is found to be malfunctioning. The retailer usually sends back the returned products as a batch to the manufacturer, and the manufacturer will then repair/remanufacture the returned products in a batch manner. Besides, the new products are also manufactured in a batch manner because of production capacity and also due to the high setup cost in production. To meet the demands in peak periods because of the capacity limitations of resources, the manufacturer may have to outsource a certain number of products emergently to a subcontractor, which is regarded as emergency procurement. This is an example that falls in the model we formulate in this paper. A genetic algorithm (GA) for the capacitated lot-sizing problem with substitution and remanufacturing is proposed in this paper. The basic concepts of GA, introduced by Grinold and Marshall (1977), have been successfully applied to solve many combinatorial optimization problems. A GA tries to mimic the natural evolution. The biggest difference with other meta-heuristics (e.g., Tabu search or simulated annealing) is that GA maintains a population of solutions rather than only one current solution. GA has been recognized as a powerful and widely applicable optimization method, especially for global optimization problems and NP-hard problems (Michalewicz, 1994). Recently, a number of researchers have studied the applications of GA to solve lot-sizing problems with unlimited capacity (e.g., Dellaert et al., 2000) and with capacity constraints (e.g., Hung and Chien, 2000 and Xie and Dong, 2002). Numerical results obtained through the method show that GA (combined with other meta-heuristics) is an effective approach to deal with the lot-sizing problems. However, only the lot-sizing problems without remanufacturing have been discussed till now. Observing the successful applications of GA to the lot-sizing and other operations management problems, we expect that GA, if designed appropriately and enhanced and supplemented by other optimization approaches, should also be well applicable to solve the capacitated lot-sizing problem with substitution and remanufacturing as we model in this paper. The rest of this paper is organized as follows. In Section 2, we develop a general capacitated production planning model with remanufacturing and substitution for a multi-period two-product problem. In Section 3, we propose an approach for a feasible production plan without allowing any emergency procurement, where a GA is applied to determine the periods that need setups in a feasible plan. In Section 4, we propose a computation procedure to compute the lot size based on a dynamic programming approach. In Section 5, we generalize the approach to the case where emergency procurement is allowed. In Section 6, we present the general computation procedure of our approach. In Section 7, numerical results are presented to illustrate the performance of the GA approach. Section 8 concludes the study with a summary, extensions and directions for future research.

We have studied a production planning problem with substitution and remanufacturing. A general production model with substitution and remanufacturing has been presented and a GA has been proposed to solve the problem. Our model subsumes several well-known production planning problems that have been commonly studied in the area of operations management, e.g., when dit=0dit=0 for i=1,2i=1,2 and t∈Tt∈T, it is a capacitated production planning problem without remanufacturing; when MCkt=0MCkt=0 and RCktRCkt are large enough for k=1,2,…,Kk=1,2,…,K and t∈Tt∈T, it is a pure reverse Wagner/Whitin model. Moreover, the approach proposed in this paper can be extended to solve some more complicated lot-sizing problems, e.g., the problem with sequence-dependent setup costs, the problem with any general form of the objective function and the problem in a rolling horizon situation. We can deal with these problems following the same structure of our approach in this paper: we can still use a GA to determine the periods of setups, and then use a dynamic program to determine the production quantities, which can be modified to handle sequence-dependent setups and other types of costs. Note that the model addressed in this paper is a deterministic one. In general, the demand may be a stochastic process which varies randomly over time. Generalizations of our model and solution approach to the stochastic situations will be interesting topics for further research.