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

In this paper we consider the important special case of the economic lot-sizing problem in which there are no speculative motives to hold inventory. We analyze the effects of varying all setup costs by the same amount. This is equivalent to studying the set of optimal production periods when the number of such periods changes. We show that this optimal set changes in a very structured way. This fact is interesting in itself and can be used to develop faster algorithms for such problems as the computation of the stability region and the determination of all efficient solutions of a lot-sizing problem. Furthermore, we generalize two related convexity results which have appeared in the literature.

In 1958 Wagner and Whitin published their seminal paper on the “Dynamic Version of the Economic Lot-Size Model”, in which they showed how to solve the problem considered by a dynamic programming algorithm. It is well known that the same approach also solves a slightly more general problem to which we will refer as the economic lot-sizing problem (ELS). Recently, considerable improvements have been made with respect to the complexity of solving ELS and some of its special cases (see [1], [2] and [3]). Similar improvements can also be made for many extensions of ELS (see [4]). In this paper we consider the important special case of ELS in which there are no speculative motives to hold inventory, i.e., the marginal cost of producing one unit in some period plus the cost of holding it until some future period is at least the marginal production cost in the latter period. For this model we analyze the effects of varying all setup costs by the same amount. This is equivalent to studying the set of optimal production periods when the number of such periods changes. We will show that this optimal set changes in a very structured way. This fact is interesting in itself and can be used to develop faster algorithms for such problems as the computation of the stability region and the determination of all efficient solutions of a lot-sizing problem. Furthermore, we will generalize two related convexity results which have appeared in the literature. The paper is organized as follows. In Section 2 we state several useful results about the economic lot-sizing problem without speculative motives. In Section 3 we perform a parametric analysis of the problem. We will characterize how the optimal solution changes when all setup costs are reduced by the same amount and we will present a linear time algorithm to calculate the minimal reduction for which the change actually occurs. In Section 4 we discuss applications of the results of Section 3. Finally, Section 5 contains some concluding remarks.

By carrying out a parametric analysis of the setup costs in the economic lot-sizing problem, we have obtained new results about the structure of optimal solution for given number of setups, we have been able to design fast algorithms for several related problems and we have obtained additional theoretical results which may be useful. Our analysis and the algorithms which we have proposed differ significantly from existing approaches. We think that the characterization given in Theorem 1 and the algorithm it suggests are particularly interesting. An interesting topic for future research is the question whether similar results hold if we allow backlogging.