یک روش ثابت و بهینه برای مشکل تعیین اندازه دسته تولید ایجاد شده چند سطحی
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|22756||2010||10 صفحه PDF||سفارش دهید||7405 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : International Journal of Production Economics, Volume 123, Issue 2, February 2010, Pages 247–256
This paper presents an optimization-based solution approach for the dynamic multi-level capacitated lot sizing problem (MLCLSP) with positive lead times. The key idea is to solve a series of mixed-integer programs in an iterative fix-and-optimize algorithm. Each of these programs is optimized over all real-valued variables, but only a small subset of binary setup variables. The remaining binary setup variables are tentatively fixed to values determined in previous iterations. The resulting algorithm is transparent, flexible, accurate and relatively fast. Its solution quality outperforms those of the approaches by Tempelmeier/Derstroff and by Stadtler.
This paper treats the problem to determine time-phased production quantities (lot sizes) for multi-level production systems in which a changeover at a resource from one product type to another requires a setup time and/or causes setup cost. The capacity of the resources is limited. The time-phased demand is assumed to be given and has to be satisfied. To date, this type of lot sizing problem cannot be solved satisfactorily within computerized Material Requirements Planning (MRP) modules of Enterprise Resource Planning (ERP) systems. The reason is that these systems often ignore the capacity limits of the production system while computing the lot sizes. This leads to infeasible production schedules which result in long and unpredictable lead times and large in-process inventories. The problem of finding capacity-feasible production quantities for a multi-stage production system that minimize setup and holding cost has been formally stated as the multi-level capacitated lot sizing problem (MLCLSP), see Billington et al. (1983). For capacitated production systems with non-zero setup times, the question whether a feasible production plan (without overtime) exists has shown to be already NPNP-complete, see Maes et al. (1991). Several authors have therefore developed heuristics for the problem. Multi-level capacitated lot sizing is hence both practically important and scientifically challenging. From a practical point of view, generic lot sizing approaches for ERP systems should meet several requirements. First, they should be adaptable to specific aspects of a concrete production system. This favors flexible approaches based on mathematical programming as opposed to “hard-wired” procedural heuristics that follow a highly problem-specific logic. Second, they should enable the planner to find feasible solutions of acceptable quality quickly and then let him decide to invest additional computation time to improve the solution. Third, if lot sizing on the one hand and sequencing/scheduling on the other hand are treated separately, it should always be possible to disaggregate the (aggregated) lot sizes into a detailed production schedule in continuous time. In a multi-level production system, this can only be guaranteed if positive lead times between the production stages are considered. Assume a serial product structure with one end product that requires a single component. Both items are produced on different resources. Furthermore, assume that the resource for the end product is fully loaded to produce a single unit of the end product in a period. In this case, it is not feasible to produce a unit of the component in the same period so that it enters the unit of the end product at the beginning of the same period. Therefore, this unit of the component must be produced at least one period ahead. For this reason, a positive lead time is required. Reviews of the literature on dynamic lot sizing are given by Bahl et al. (1987), Maes and van Wassenhove (1988), Gupta and Keung (1990), Salomon et al. (1991) and Buschkühl et al. (2008). Kuik et al. (1994) relate lot sizing to batching and comment on some general criticism of batching analysis. The progress with single-item lot sizing is analyzed by Wolsey (1995) and Brahimi et al. (2006). Drexl and Kimms (1997) discuss models that consider both lot sizing and scheduling. Karimi et al. (2003) give a review of solution approaches for single-stage capacitated lot sizing problems and Jans and Degraeve (2007) focus on metaheuristics for dynamic lot sizing. Quadt and Kuhn (2008) review capacitated lotsizing problems with extensions. Table 1 classifies papers on the MLCLSP by the general solution approach, i.e. mathematical programming-based approaches, Lagrangean relaxation and decomposition, decomposition and aggregation, local search and metaheuristics and finally greedy heuristics. Some of these papers are discussed below in more detail. In Tempelmeier and Helber (1994), Helber (1995) and Tempelmeier and Derstroff (1996), early product-oriented decomposition approaches for the MLCLSP are presented. The Tempelmeier/Destroff-heuristic (TDH) is until now the fastest available method for the MLCLSP. It is based on a Lagrangean relaxation of the MLCLSP which then decomposes into single-product uncapacitated lot sizing problems of the type studied by Wagner and Whitin (1958). The Lagrangean relaxation leads to a lower bound on the objective function value. A heuristic finite scheduling procedure is used to create a feasible solution and to compute an upper bound on the optimal objective function value. While the algorithm is fast, it is difficult to describe and implement as well as inflexible with respect to modifications of the underlying problem. The solution quality especially for large problem instances offers opportunities for improvement. Katok et al. (1998) present a linear-programming (LP)-based approach that works with a heuristic modification of the coefficients of the production quantities in both the objective function and the constraints. Tempelmeier (2008, p. 342) shows that this concept is very vulnerable when setup times occur and capacity limits are tight. In these situations existing feasible solutions (without overtime) are not found. Stadtler (2003) proposes a mixed-integer programming-based heuristic that solves a series of subproblems through internally rolling schedules with time windows. For the periods within the time window of a particular subproblem, the simple plant location variant of the lot sizing problem is used to speed up the optimization process. Stadtler's approach delivers high-quality solutions for problems with zero lead times, but cannot deal with positive lead times (Stadtler, 2003, p. 501). The reason is that in a general product structure multiple relations with different lead times between end product quantities and time-phased resource requirements can occur. Hence, this makes a consistent disaggregation into a detailed production schedule in continuous time impossible. In addition, solution times for his approach increase substantially as the problem size (number of binary setup variables) increases. A variant of Stadtler's general approach of internally rolling schedules for the Capacitated Lot Sizing Problem with Linked Lot Sizes (Haase, 1994 and Haase, 1998) is presented by Sürie and Stadtler (2003). It is based on an extended model formulation and valid inequalities to yield a tight formulation that speeds up the branch&bound process. Belvaux and Wolsey (2001) show how to develop tight formulations for several special problem features occurring in practice. Rossi (2005) develops a time-oriented decomposition similar to the one by Stadtler where some of the setup variables are initially relaxed while others are iteratively fixed. Unfortunately, the author provides no direct comparison to the procedures by Stadtler and by Tempelmeier. Pitakaso et al. (2006) present a decomposition algorithm for the MLCLSP based on a limited subset of products and periods. Each problem in the decomposition is solved to optimality and a capacity reservation mechanism is used to reflect products and periods “outside” of the current problem. The decomposition itself is controlled by an “ant colony optimization” algorithm. The computation times that are necessary to find better results than with Stadtler's method appear to be quite high (20–30 min) and then the average improvement is small. Berretta and Rodrigues (2004) describe a memetic algorithm which is also population-based. However, they compare their results to those presented by Tempelmeier only for tiny problems with 40 binary variables. The picture is similar for a similar algorithm by Berretta et al. (2005): Relatively large deviations from optimal solutions occur already for problems with only 60 binary variables. In this paper we present a mathematical programming-based algorithm for the MLCLSP that is flexible and transparent that allows to trade in solution time for solution quality and that can deal with positive lead times. In an iterative fix-and-optimize approach (Pochet and Wolsey, 2006, p. 113, call this “Exchange”), a sequence of mixed-integer programs (MIPs) is solved over all real-valued decision variables and a subset of the binary setup variables. The solution with respect to the binary variables is a fixed parameter for the next MIPs that optimize other binary variables. The optimization of the algebraic decision model is done within the MIP solver and therefore the approach is flexible. The user can trade in solution time for solution quality by deciding about the number of binary variables to be treated within a single MIP and about the number of iterations in which these are optimized and fixed again. Even large problem instances from the literature can be solved with a high solution quality within seconds or few minutes. We study both the cases of zero and of positive lead times and compare our results to those for the approaches by Tempelmeier and Derstroff (1996) and Stadtler (2003) in an extensive numerical study. While the method by Tempelmeier and Derstroff (1996) is extremely fast (and much faster than ours), our method yields a substantially higher solution quality. It outperforms the one presented by Stadtler (2003) with respect to both solution quality and computation time. The remainder of this paper is organized as follows: in Section 2 we give a formal definition of the MLCLSP. The algorithm to solve the problem is presented in Section 3. Numerical results comparing our method to those developed by Tempelmeier and by Stadtler are reported in Section 4. The paper ends with some conclusions and suggestions for further research (Section 5).
نتیجه گیری انگلیسی
We have presented a mathematical-programming-based approach to solve the MLCLSP with lead times. Modeling lead times is necessary, if one wants to be able to disaggregate the time-phased lot sizes into a detailed production schedule in continuous time. Our method is based on an iterative optimization of a series of subproblems. Each of them includes all the real-valued decision variables, but only a specific limited set of “free” binary variables. The approach is easy to describe and to implement and delivers high-quality solutions. In our view, the most important aspect of our method is its flexibility: it is straightforward to change or add constraints such as maximum inventory levels, minimum lot sizes, parallel machines, etc. to the standard formulation of the MLCLSP. These changes of the model would require a substantial re-design of the complex decomposition method by Tempelmeier and Derstroff (1996), the only other method so far that can efficiently solve larger instances of the MLCLSP with positive lead times. In addition, our method is quite easy to modify by defining different subsets and sequences of subproblems to be treated in the different phases of the algorithm. By defining larger subproblems (with a larger (absolute or relative) number of binary variables), one can trade in solution time to get more solution quality and vice versa. However, the results show that it may be sufficient to treat less than 10% of the binary setup variables in any one instance of the problem MLCLSP-SUB and still find high quality solutions, similar to two-opt and three-opt approaches for the Traveling Salesman Problem. We consider the flexibility with respect to both the lot sizing model and the algorithm to be an important aspect of our work. Further research should address other dynamic multi-level lot sizing problems like those with linked lot sizes where the setup state of a resource can be carried over to a subsequent period.