مشکل تعیین اندازه دسته تولید پویا با هزینه های تولید اقتصادی برآمده و راه اندازی

In this work the uncapacitated dynamic lot-sizing problem is considered. Demands are deterministic and production costs consist of convex costs that arise from economic production functions plus set-up costs. We formulate the problem as a mixed integer, non-linear programming problem and obtain structural results which are used to construct a forward dynamic-programming algorithm that obtains the optimal solution in polynomial time. For positive setup costs, the generic approaches are found to be prohibitively time-consuming; therefore we focus on approximate solution methods. The forward DP algorithm is modified via the conjunctive use of three rules for solution generation. Additionally, we propose six heuristics. Two of these are single-stepSilver–Meal and EOQ heuristics for the classical lot-sizing problem. The third is a variant of the Wagner–Whitin algorithm. The remaining three heuristics are two-step hybrids that improve on the initial solutions of the first three by exploiting the structural properties of optimal production subplans. The proposed algorithms are evaluated by an extensive numerical study. The two-step Wagner–Whitin algorithm turns out to be the best heuristic.

In this paper, we consider the problem of dynamic lot-sizing in the presence of polynomial-type convex production functions and non-zero setup costs. The dynamic lot-sizing problem is defined as the determination of the production plan that minimizes the total (fixed setup, holding and variable production) costs incurred over the planning horizon for a single, storable item facing deterministic demands. The so-called classical dynamic lot-sizing problem was first analyzed by Wagner and Whitin (1958). They established that, in an optimal plan with positive fixed setup costs and linear production and holding costs, production is done in a period only if its net demand (actual demand less inventories) is positive, and a period׳s demand is satisfied entirely by production in a single period (that is, integrality of demand is preserved.) For linear production costs, extensions include Zangwill (1966), Blackburn and Kunreuther (1974), Lundin and Morton (1975), Federgruen and Tzur (1991), Wagelmans et al. (1992), Aggarwal and Park (1993), Azaron et al. (2009), Ganas and Papachristos (2005), Okhrin and Richter (2011) and Toy and Berk (2013). The fundamental properties of the optimal plans for linear costs hold for piecewise linear and concave cost structures, as well. For details on such results, we refer the reader to the reviews in Brahimi et al. (2006), Karimi et al. (2003), Jans and Degraeve (2007), Buschkühl et al. (2010) and Jans and Degraeve (2008). There is also a parallel stream of research that focuses on developing lot sizing heuristics based on simple stopping rules. (See Vollmann et al. (1997), Simpson (2001), and Jeunet and Jonard (2000) for a full list and review.) The advantages of such approximate solution methodologies are their ease-of-use, smoother production schedules and providing more intuition to practitioners about the fundamental trade-offs. Hence, the available commercial ERP software (e.g., SAP) offers the well-known heuristics for the classical lot sizing problem as options for decision-makers in theirmanufacturing modules. These include the Silver–Meal and economic order quantity (EOQ) based heuristics among others ( Silver and Meal, 1973, Harris, 1913 and Erlenkotter, 1989). Most of the existing works on the dynamic lot-sizing problem deal with linear and/or concave production functions rather than convex functions. For convex cost functions and zero setup costs, a parametric algorithm was developed by Veinott (1964) for the problem, which can be solved by an incremental approach satisfying each unit of demand as cheaply as possible. The algorithm has a computational complexity ofO(TD1,T)O(TD1,T) where T is the problem horizon length and D1,TD1,T stands for the total demand over the problem horizon. Works by Meyer (1977) and Khachian (1979) render this problem solvable in strictly polynomial time. Our work differs from the existing literature in our main assumption about the structure of production costs. Specifically, we consider variable production costs in period t of the polynomial form View the MathML source∑n=1mwtnqtrtn where qt denotes the quantity produced in the period, wtn and rtn are positive constants and m is the number of resources. The assumed non-linearity aims to capture the externalities in production activities that are encountered in a number of industrial settings as briefly discussed below: (i) Productive assets require maintenance and repair activities over their lifetimes and almost all production processes generate undesirable wastes, which must be disposed of and/or whose negative ecological impact must be mitigated. As additional resources are required or legal penalty rates become progressive, the costs associated with such auxiliary activities exhibit a convex behavior. To the best of our knowledge, the only attempt to incorporate such non-linear costs in production planning is performed by Heck and Schmidt (2010) who proposed a heuristic which is a variant of the incremental solution approach in Veinott (1964). (ii) Non-linear production functions also arise from production activities that use a number of substitutable resources such as materials, labor, machinery, capital, energy, etc . One of the most common production functions is the Cobb–Douglas production function, which was introduced at a macroeconomic level for the US manufacturing industries for the period 1899–1922 but has been widely applied to individual production processes at the microeconomic level, as well. For example, Shadbegian and Gray (2005) use the Cobb–Douglas production function to model production processes in the paper, steel and oil industries, Hatirli et al. (2006) to model agricultural production, and Kogan and Tapiero (2009) to model logistics/supply chain operations. The Cobb–Douglas production function assumes that multiple (m ) resources are needed for output, Q and they may be substituted to exploit the marginal cost advantages. In general, it has the form View the MathML sourceQ=A∏i=1mx(i)α(i) where A is the technology level for the production process, x (i ) denotes the amount of resource i used and α(i)>0α(i)>0 is the resource elasticity. Assuming that resource i has a unit cost of p (i ), the total cost for output Q is given by wQrwQr where View the MathML sourcew=(1/r)A−r∏i=1m(p(i)/α(i))α(i)r and View the MathML source1/r=∑i=1mαi ( Heathfield and Wibe, 1987). The total elasticity parameter 1/r1/r may be greater than (smaller than) or equal to 1 depending on whether there is diminishing (increasing) returns to resources, resulting in convex (concave) variable production costs. Despite its widespread occurrence, the impact of the Cobb–Douglas production function on dynamic lot-sizing problems has not been studied. (iii) Another commonly used economic production function is the Leontieff function introduced by Leontieff (1947). Its main difference from the Cobb–Douglas function is that it assumes that resources are not substitutable but complementary. The applications include Haldi and Whitcomb (1967) for refining of petroleum and primary metals, Ozaki (1976) for large-scale assembly production, Lau and Tamura (1972) for ethylene production, and Nakamura (1990) for iron and steel production. The Leontieff production function has the form Q=mini{x(i)α(i)}Q=mini{x(i)α(i)} for a given set of resources where x (i )denotes the amount of resource i used and α(i)>0α(i)>0 is the resource elasticity. Assuming that resource i has a unit cost of p (i ), the total cost for output Q is given by View the MathML source∑i=1mwiQ1/α(i) where wi=p(i)wi=p(i). Typically, it is assumed that α(i)≤1α(i)≤1 so that the variable cost of production is convex in output. Similarly, there are no studies on the dynamic lot-sizing problem in the presence of Leontieff production functions. The general structure for variable production costs assumed above subsumes the above three classes of costs of production externalities. For m>1m>1, each term View the MathML sourcewtiqtrti corresponds either directly to the cost of using resource i in a complementary fashion in order to produce q t units in period t through a Leontieff-type production function or to the individual polynomial terms of the cost of efforts to mitigate the ecological impact. For m =1, the only term View the MathML sourcewt1qtrt1 corresponds to the effective cost of using all resources to produce qt units in period t through a Cobb–Douglas type production function. To avoid confusion, we remind the reader that the above discussion of multiple resources is to motivate the form of the variable production cost functions. Once we have them, we focus on the production plan of the single item. In this paper, we formulate the dynamic lot-sizing problem first as a mixed integer non-linear programming (MINLP) problem and obtain fundamental properties of the optimal solution. In particular, we characterize the optimal solution structure for the case of zero setup costs and establish the property that shows how the optimal solution for a T -period problem can be updated to give the solution for a (T +1)-period problem. This property leads us later to develop a forward dynamic programming (DP) formulation which obtains the optimal production plan in O(T22T)O(T22T) run time in general. For positive setup costs, we also show that the same optimal production plan structure (consisting of G -class subplans) is retained when periods are pre-specified in which production is done. Based on this property, we modify the forward DP algorithm by means of three simple set-construction rules so that O(T2)O(T2) computational complexity is achieved. This constitutes our benchmark algorithm for large sized problems. In addition, we propose six new heuristics for the lot sizing problem at hand. Heuristics H1 and H2 are based on stopping rules and variants of the Silver–Meal and EOQ based heuristics for the classical lot sizing problem. Heuristic H3 is a variant of the Wagner–Whitin solution that employs the forward DP algorithm while imposing demand integrality on the production quantities. The first three heuristics are single step heuristics. The remaining three heuristics, which we call the G-heuristics, are two-step hybrids that use the set of production periods of the solutions obtained by the first three heuristics and improve them via G-class production subplans. An extensive numerical study establishes that a forward DP algorithm wherein production periods within generations are selected via simple rules provides a reasonably fast and efficient solution methodology. Among the proposed heuristics, the Wagner–Whitin heuristic (H3) performs best among the single step heuristics and the hybrid G-heuristics exploiting the optimal production plan structure outperform the single step heuristics significantly. The best heuristic among all those proposed turns out to be the hybrid one that improves on the Wagner–Whitin solution, namely, heuristic H6. These are followed in performance by the single step heuristic H2, which is based on the EOQ model, and the G-heuristic H5, which improves on that. The sensitivity analysis on the optimal solutions (obtained by the benchmark DP algorithm) reveals two fundamental tendencies which are in accordance with intuition. Higher production cost non-linearities and lower average unit production costs force production to be spread over a larger number of periods to exploit the marginal cost benefits. Thus, unlike the classical lot-sizing model with the non-speculative cost structure, production functions generate a tendency to produce in earlier periods when setup costs are zero. This results in production smoothing – production decisions in more periods with smaller quantities. Positive setup costs, on the other hand, introduce the batching tendency, as expected; for larger setup costs, larger production quantities emerge to compensate for a setup in a period. The interaction between these two tendencies is not always straightforward for particular cost parameter values but the fundamental trade-offs could be observed in all experiment instances. The production smoothing tendency revealed in our study is of interest from a practical perspective, as well; it supports the managerial attitudes toward dedicated facilities and high asset utilization rates in practice. The remainder of the paper is organized as follows: Section 2 describes the model and provides the MINLP formulation. Section 3 presents the structural results on the optimal solution. In Section 4, we discuss possible solution approaches that can be applied to the problem at hand, formulate both backward and forward DP algorithms based on the fundamental structural properties of optimal solutions and develop our additional heuristics. We present our findings from an extensive numerical study in Section 5. Specifically, we compare the performance of the heuristics and the forward DP algorithm in terms of attained costs and corresponding computational times; and, discuss some sensitivity results. Finally, in Section 6 we briefly summarize our findings and suggest future research directions.

In this paper, we consider the problem of dynamic lot-sizing in the presence of polynomial-type convex production functions and non-zero setup costs. The dynamic lot-sizing problem is defined as the determination of the production plan that minimizes the total (fixed setup, holding and variable production) costs incurred over the planning horizon for a single, storable item facing deterministic demands. The so-called classical dynamic lot-sizing problem was first analyzed by Wagner and Whitin (1958). They established that, in an optimal plan with positive fixed setup costs and linear production and holding costs, production is done in a period only if its net demand (actual demand less inventories) is positive, and a period׳s demand is satisfied entirely by production in a single period (that is, integrality of demand is preserved.) For linear production costs, extensions include Zangwill (1966), Blackburn and Kunreuther (1974), Lundin and Morton (1975), Federgruen and Tzur (1991), Wagelmans et al. (1992), Aggarwal and Park (1993), Azaron et al. (2009), Ganas and Papachristos (2005), Okhrin and Richter (2011) and Toy and Berk (2013). The fundamental properties of the optimal plans for linear costs hold for piecewise linear and concave cost structures, as well. For details on such results, we refer the reader to the reviews in Brahimi et al. (2006), Karimi et al. (2003), Jans and Degraeve (2007), Buschkühl et al. (2010) and Jans and Degraeve (2008). There is also a parallel stream of research that focuses on developing lot sizing heuristics based on simple stopping rules. (See Vollmann et al. (1997), Simpson (2001), and Jeunet and Jonard (2000) for a full list and review.) The advantages of such approximate solution methodologies are their ease-of-use, smoother production schedules and providing more intuition to practitioners about the fundamental trade-offs. Hence, the available commercial ERP software (e.g., SAP) offers the well-known heuristics for the classical lot sizing problem as options for decision-makers in theirmanufacturing modules. These include the Silver–Meal and economic order quantity (EOQ) based heuristics among others ( Silver and Meal, 1973, Harris, 1913 and Erlenkotter, 1989). Most of the existing works on the dynamic lot-sizing problem deal with linear and/or concave production functions rather than convex functions. For convex cost functions and zero setup costs, a parametric algorithm was developed by Veinott (1964) for the problem, which can be solved by an incremental approach satisfying each unit of demand as cheaply as possible. The algorithm has a computational complexity ofO(TD1,T)O(TD1,T) where T is the problem horizon length and D1,TD1,T stands for the total demand over the problem horizon. Works by Meyer (1977) and Khachian (1979) render this problem solvable in strictly polynomial time. Our work differs from the existing literature in our main assumption about the structure of production costs. Specifically, we consider variable production costs in period t of the polynomial form View the MathML source∑n=1mwtnqtrtn where qt denotes the quantity produced in the period, wtn and rtn are positive constants and m is the number of resources. The assumed non-linearity aims to capture the externalities in production activities that are encountered in a number of industrial settings as briefly discussed below: (i) Productive assets require maintenance and repair activities over their lifetimes and almost all production processes generate undesirable wastes, which must be disposed of and/or whose negative ecological impact must be mitigated. As additional resources are required or legal penalty rates become progressive, the costs associated with such auxiliary activities exhibit a convex behavior. To the best of our knowledge, the only attempt to incorporate such non-linear costs in production planning is performed by Heck and Schmidt (2010) who proposed a heuristic which is a variant of the incremental solution approach in Veinott (1964). (ii) Non-linear production functions also arise from production activities that use a number of substitutable resources such as materials, labor, machinery, capital, energy, etc . One of the most common production functions is the Cobb–Douglas production function, which was introduced at a macroeconomic level for the US manufacturing industries for the period 1899–1922 but has been widely applied to individual production processes at the microeconomic level, as well. For example, Shadbegian and Gray (2005) use the Cobb–Douglas production function to model production processes in the paper, steel and oil industries, Hatirli et al. (2006) to model agricultural production, and Kogan and Tapiero (2009) to model logistics/supply chain operations. The Cobb–Douglas production function assumes that multiple (m ) resources are needed for output, Q and they may be substituted to exploit the marginal cost advantages. In general, it has the form View the MathML sourceQ=A∏i=1mx(i)α(i) where A is the technology level for the production process, x (i ) denotes the amount of resource i used and α(i)>0α(i)>0 is the resource elasticity. Assuming that resource i has a unit cost of p (i ), the total cost for output Q is given by wQrwQr where View the MathML sourcew=(1/r)A−r∏i=1m(p(i)/α(i))α(i)r and View the MathML source1/r=∑i=1mαi ( Heathfield and Wibe, 1987). The total elasticity parameter 1/r1/r may be greater than (smaller than) or equal to 1 depending on whether there is diminishing (increasing) returns to resources, resulting in convex (concave) variable production costs. Despite its widespread occurrence, the impact of the Cobb–Douglas production function on dynamic lot-sizing problems has not been studied. (iii) Another commonly used economic production function is the Leontieff function introduced by Leontieff (1947). Its main difference from the Cobb–Douglas function is that it assumes that resources are not substitutable but complementary. The applications include Haldi and Whitcomb (1967) for refining of petroleum and primary metals, Ozaki (1976) for large-scale assembly production, Lau and Tamura (1972) for ethylene production, and Nakamura (1990) for iron and steel production. The Leontieff production function has the form Q=mini{x(i)α(i)}Q=mini{x(i)α(i)} for a given set of resources where x (i )denotes the amount of resource i used and α(i)>0α(i)>0 is the resource elasticity. Assuming that resource i has a unit cost of p (i ), the total cost for output Q is given by View the MathML source∑i=1mwiQ1/α(i) where wi=p(i)wi=p(i). Typically, it is assumed that α(i)≤1α(i)≤1 so that the variable cost of production is convex in output. Similarly, there are no studies on the dynamic lot-sizing problem in the presence of Leontieff production functions. The general structure for variable production costs assumed above subsumes the above three classes of costs of production externalities. For m>1m>1, each term View the MathML sourcewtiqtrti corresponds either directly to the cost of using resource i in a complementary fashion in order to produce q t units in period t through a Leontieff-type production function or to the individual polynomial terms of the cost of efforts to mitigate the ecological impact. For m =1, the only term View the MathML sourcewt1qtrt1 corresponds to the effective cost of using all resources to produce qt units in period t through a Cobb–Douglas type production function. To avoid confusion, we remind the reader that the above discussion of multiple resources is to motivate the form of the variable production cost functions. Once we have them, we focus on the production plan of the single item. In this paper, we formulate the dynamic lot-sizing problem first as a mixed integer non-linear programming (MINLP) problem and obtain fundamental properties of the optimal solution. In particular, we characterize the optimal solution structure for the case of zero setup costs and establish the property that shows how the optimal solution for a T -period problem can be updated to give the solution for a (T +1)-period problem. This property leads us later to develop a forward dynamic programming (DP) formulation which obtains the optimal production plan in O(T22T)O(T22T) run time in general. For positive setup costs, we also show that the same optimal production plan structure (consisting of G -class subplans) is retained when periods are pre-specified in which production is done. Based on this property, we modify the forward DP algorithm by means of three simple set-construction rules so that O(T2)O(T2) computational complexity is achieved. This constitutes our benchmark algorithm for large sized problems. In addition, we propose six new heuristics for the lot sizing problem at hand. Heuristics H1 and H2 are based on stopping rules and variants of the Silver–Meal and EOQ based heuristics for the classical lot sizing problem. Heuristic H3 is a variant of the Wagner–Whitin solution that employs the forward DP algorithm while imposing demand integrality on the production quantities. The first three heuristics are single step heuristics. The remaining three heuristics, which we call the G-heuristics, are two-step hybrids that use the set of production periods of the solutions obtained by the first three heuristics and improve them via G-class production subplans. An extensive numerical study establishes that a forward DP algorithm wherein production periods within generations are selected via simple rules provides a reasonably fast and efficient solution methodology. Among the proposed heuristics, the Wagner–Whitin heuristic (H3) performs best among the single step heuristics and the hybrid G-heuristics exploiting the optimal production plan structure outperform the single step heuristics significantly. The best heuristic among all those proposed turns out to be the hybrid one that improves on the Wagner–Whitin solution, namely, heuristic H6. These are followed in performance by the single step heuristic H2, which is based on the EOQ model, and the G-heuristic H5, which improves on that. The sensitivity analysis on the optimal solutions (obtained by the benchmark DP algorithm) reveals two fundamental tendencies which are in accordance with intuition. Higher production cost non-linearities and lower average unit production costs force production to be spread over a larger number of periods to exploit the marginal cost benefits. Thus, unlike the classical lot-sizing model with the non-speculative cost structure, production functions generate a tendency to produce in earlier periods when setup costs are zero. This results in production smoothing – production decisions in more periods with smaller quantities. Positive setup costs, on the other hand, introduce the batching tendency, as expected; for larger setup costs, larger production quantities emerge to compensate for a setup in a period. The interaction between these two tendencies is not always straightforward for particular cost parameter values but the fundamental trade-offs could be observed in all experiment instances. The production smoothing tendency revealed in our study is of interest from a practical perspective, as well; it supports the managerial attitudes toward dedicated facilities and high asset utilization rates in practice. The remainder of the paper is organized as follows: Section 2 describes the model and provides the MINLP formulation. Section 3 presents the structural results on the optimal solution. In Section 4, we discuss possible solution approaches that can be applied to the problem at hand, formulate both backward and forward DP algorithms based on the fundamental structural properties of optimal solutions and develop our additional heuristics. We present our findings from an extensive numerical study in Section 5. Specifically, we compare the performance of the heuristics and the forward DP algorithm in terms of attained costs and corresponding computational times; and, discuss some sensitivity results. Finally, in Section 6 we briefly summarize our findings and suggest future research directions.