تعیین اندازه دسته تولیدی پویا برای یک فرآیند سرد و گرم : ابتکارات و بینش ها
کد مقاله | سال انتشار | تعداد صفحات مقاله انگلیسی |
---|---|---|
22836 | 2013 | 14 صفحه PDF |
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : International Journal of Production Economics, Volume 145, Issue 1, September 2013, Pages 53–66
چکیده انگلیسی
We consider the dynamic lot sizing problem for a warm/cold process where the process can be kept warm at a unit variable cost for the next period if more than a prespecified quantity has been produced. Exploiting the optimal production plan structures, we develop nine rule-based forward solution heuristics. Proposed heuristics are modified counterparts of the heuristics developed previously for the classical dynamic lot sizing problem. In a numerical study, we investigate the performance of the proposed heuristics and identify operating environment characteristics where each particular heuristic is the best or among the best. Moreover, for a warm/cold process setting, our numerical studies indicate that, when used on a rolling horizon basis, a heuristic may also perform better costwise than a solution obtained using a dynamic programming approach.
مقدمه انگلیسی
In this paper, we consider the problem of dynamic lot sizing for a special type of production processes. The dynamic lot sizing problem is defined as the determination of the production plan which minimizes the total (fixed setup, holding and variable production) costs incurred over the planning horizon for a storable item facing known demands. Recently, the notion of a “warm/cold process” has been introduced into the scheduling literature (Toy and Berk, 2006). A warm/cold process is defined as a production process that can be kept warm for the next period if a minimum amount (the so-called warm threshold) has been produced in the current period and would be cold, otherwise. Production environments where the physical nature of the production technology dictates that the processes be literally kept warm in certain periods to avoid expensive shutdown/startups are typical in glass, steel and ceramic production. Robinson and Sahin (2001) provide other examples in food and petrochemical industries where certain cleanup and inspection operations can be avoided in the next period if the quantity produced in the current period exceeds a certain threshold. Production processes where production rates can be varied also fall into the warm/cold process category. The upper bound on the production rate is the physical capacity of the production process and the lower bound corresponds to the warm threshold, below which the process cannot be kept running into the next period without incurring a setup. Such variable production rates can be found in both discrete item manufacturing and process industries. Change in production rate can be obtained at either zero or positive cost depending on the characteristics of the employed technology. The additional variable cost is, then, the variable cost of keeping the process warm onto the next period. As the above examples illustrate, the dynamic lot-sizing problem in the presence of production quantity—dependent warm/cold processes is a common problem. This problem, in the presence of no shortages, has been formulated and solved optimally by Toy and Berk (2006) using a dynamic programming approach with an O(N3)O(N3) forward algorithm where N denotes the problem horizon length. Later, they extend their results to the case where some of the demands may be lost under a profit maximization objective ( Berk et al., 2008). The dynamic lot sizing problem for a warm/cold process is a generalization of the so-called classical problem which was first analyzed by Wagner and Whitin (1958). The classical problem assumes uncapacitated production and no shortages. Wagner and Whitin (1958) provide a dynamic programming solution algorithm and structural results on the optimal solution. Their fundamental contribution lies in establishing the existence of planning horizons, which makes forward solution algorithms possible. Although the optimal solution structure is known, the complexity of obtaining it (shown to be View the MathML sourceO(NlogN) in general by Federgruen and Tzur, 1991, Wagelmans et al., 1992 and Feng et al., 2011 for constant capacities) has stimulated a stream of research that focuses on developing lot sizing heuristics based on simple stopping rules, such as Silver–Meal (Silver and Meal, 1973), Part-Period Balancing (DeMatteis, 1968), Least Unit Cost, Economic Order Interval, McLauren's Order Moment (Vollmann et al., 1997), Least Total Cost (Narasimhan and McLeavy, 1995), Groff's Algorithm (Groff, 1979). (See also Sahin et al., 2008 and Narayanan and Robinson, 2010.) Further results on the lot sizing problem are found in the literature on its extension to the capacitated production settings. The capacitated lot sizing problem (CLSP) is related to the lot sizing problem for a warm/cold process under certain conditions (see Toy and Berk, 2006). The CLSP has been first studied by Manne (1958) and has been shown to be NP-hard by Florian et al. (1980). Reviews of the works on CLSP (along with the uncapacitated versions) are by Brahimi et al. (2006) and Quadt and Kuhn (2008), who include extensions of the problem, and Buschkühl et al. (2010). Recent analytical studies have focused on novel solution approaches. Heuvel and Wagelmans (2006) develop an O(T2)O(T2) algorithm. Pochet and Wolsey (2010) provide a mixed integer programming reformulation that can be solved with LP-relaxation to optimality under reasonable conditions. Chubanov et al. (2008) and Ng et al. (2010) introduce polynomial approximations. Hardin et al. (2007) analyze the quality of bounds by fast algorithms. Reviews of meta-heuristic approaches to the CLSP can be found in Staggemeier and Clark (2001), Jans and Degraeve (2007) and in Guner Goren et al. (2010) on genetic algorithms for lot sizing. A recent review of related works appears also in Glock (2010). Rule-based heuristics in rolling horizon environments have been studied by Stadtler (2000), Simpson (2001), and Heuvel and Wagelmans (2005). The work herein joins this stream by considering the dynamic lot sizing problem for a warm/cold process. Specifically, we propose rule-based lot sizing heuristics for the problem and examine the efficacy of such rules. To the best of our knowledge, this is the first work that studies lot sizing rules for the operating environment where the production process can be kept warm at some cost if production quantity in a period exceeds a threshold value. We believe that our contributions lie in developing a number of heuristics which perform well in certain operational environments and in identifying such regions for selecting a particular heuristic. We consider the application of the proposed heuristics in a static setting as well as on a rolling horizon basis as it is the practice. The available commercial ERP software (e.g., SAP) still offer well-known heuristics for the classical lot sizing problem as options for decision-makers along with the ‘optimal’ solution algorithms in their manufacturing modules. For the conventional production environments, the benefits of heuristics include the ease of use, smoother production schedules and more intuition for the trade-offs. Moreover, for a warm/cold process setting, our numerical studies indicate that, when used on a rolling horizon basis, a heuristic may also perform better costwise than a solution obtained using a dynamic programming approach. This finding is consistent with similar studies on the classical problem ( Stadtler, 2000 and Heuvel and Wagelmans, 2005). Hence, investigation of heuristics for warm/cold process settings may be financially beneficial in practice as well as from a purely theoretical perspective. Our work extends the heuristics literature on the dynamic lot sizing problem. The rest of the paper is organized as follows: In Section 2, we introduce the basic assumptions of our model, formulate the optimization problem and present some key results. In Section 3, we present some theoretical results on an economic production quantity (EPQ) model that we use as a continuous counterpart of a warm/cold process to develop some of our heuristics. In Section 4, we introduce and construct nine lot sizing heuristics for a warm/cold process. In Section 5, we present a numerical study and discuss our findings in regards to the cost performance of the proposed heuristics. In our numerical study, we provide results on the performance distribution of individual heuristics, on the rankings of the heuristics, on identifying the operating environment where a particular heuristic may perform best and on the impact of planning horizon lengths when production plans are made and executed on a rolling horizon basis.
نتیجه گیری انگلیسی
In this work, we have proposed nine rule-based lot sizing heuristics for a warm/cold process (defined as the one which can be kept warm for the next period at an additional linear cost if the production quantity in the current period is at least a positive threshold amount). Due to the nature of the stopping rules, the proposed heuristics fall into two categories: quantity based and cost based. For quantity based heuristics, we use an adaptation of the EPQ model. The stopping rule determines the size of the production lots. For all heuristics, the production schedule (over possibly consecutive production periods) within a production lot is determined by the optimal results obtained for the warm/cold process which minimize the total costs. In a numerical study, we have examined the performance of the proposed heuristics. We find that, overall, EPQ-based heuristics are dominated by those constructed on the basis of costs. Our findings further indicate that there is not a single heuristic that is best for all parameter settings. In terms of total cost, Heuristics #1 and #9 perform best for the static case but for rolling horizon settings, Heuristic #1 is clearly the best. In terms of fraction of experiment instances where a particular heuristic dominates others, Heuristic #1 is the best followed by #9 and #3. In the numerical study, we have also identified operating environments for which the proposed heuristics would perform best. In general, but especially for large demand variability (σ/μ)(σ/μ), the heuristics constructed via EPQ-based rules (Heuristics #5 through #8) perform badly. As the warm/cold process approaches the classical problem setting, Heuristic #9 starts to dominate Heuristic #1. This happens for small J , large αα and large γ/ωγ/ω (with resulting large R ). We observe that Heuristic #9 is replaced by Heuristic #3 for relatively medium to large values of αα. The intuition behind these performance behavior may be as follows. The heuristics are constructed in two steps: (i) determination of the production lot size (according to the specified stopping rule), and (ii) determination of the production schedule (according to Proposition 1). The second decision is always optimal by construct. Thus, the performance of the heuristics primarily depends on how well the lot size is determined. The Wagner–Whitin solution (resulting in Heuristic #9) is, by definition, optimal for the static classical problem; our findings indicate that this uncapacitated solution provides also very good approximations for the lot size in a warm/cold process. In the case of Heuristic #1, it is the only one that uses a stopping rule that is based on cost rate optimization. Its good performance indicates that this criterion results in good lot sizes for a warm/cold process, as well. A similar explanation may be valid for the performance of Heuristic #3 which is based on a stopping rule minimizing costs per unit. An important result of our numerical studies is that, when used on a rolling horizon basis, a heuristic solution for a warm/cold process may also perform better costwise than a solution obtained using a dynamic programming approach especially for short planning horizons and small J. This finding is consistent with similar studies on the classical problem ( Stadtler, 2000 and Heuvel and Wagelmans, 2005). Hence, investigation and implementation of heuristics for warm/cold process settings may be economically beneficial in practice as well as important from a purely theoretical perspective.