|
Article Excerpt
We consider the single-product lot-sizing problem over a finite planning horizon. Demand at each period is constant, and excess demand is completely backlogged. Holding and backlogging costs are proportional to the amount of inventory stocked or backlogged, while ordering cost is fixed, independent of the quantity ordered. The optimal policy targets to minimize the total relevant costs over the planning horizon. The key results of this paper are: (1) an explicit formula for the optimal total cost as a function of the model parameters and the number of cycles of the policy; (2) a new, polynomial-time algorithm which determines the overall optimal policy; and (3) stability regions for any solution considering simultaneous variations on all cost and demand parameters. The proposed algorithm is easy to implement and therefore is suitable for practical use.
Subject classifications: inventory/production: lot-sizing problem with backlogging; inventory/production: stability regions.
Area of review: Manufacturing, Service, and Supply Chain Operations.
**********
1. Introduction
The single-product dynamic lot-sizing problem continues to attract research interest. In their seminal paper, Wagner and Whitin (1958) proposed an efficient dynamic-programming algorithm to solve the problem. Zangwill (1966, 1969) extended the problem by introducing backlogging and proposed algorithms for its solution. Blackburn and Kunreuther (1974) and Morton (1978) have further contributed to the backlogging problem by analyzing its solution under various operating conditions. Recently, Aggarwal and Park (1993) and Federgruen and Tzur (1993) developed very efficient algorithms to solve the backlogging problem.
Richter (1987) introduced another direction of research for the single-product dynamic lot-sizing problem, namely, the construction of stability regions. A stability region is defined as the set of all values of the problems' parameters, for which a solution remains optimal. He studied the problem assuming constant cost parameters, varying demand, and no backlogging, and constructed stability regions for its optimal solution valid for variations of the ratio "setup over holding cost." Research in this direction has been continued by Chand and Voros (1992), Papachristos and Ganas (1998), Richter (1994a, b), and Van Hoesel and Wagelmans (1991, 2000).
In this paper, we extend the model of Papachristos and Ganas (1998) to the case where complete backlogging is allowed. The key results of this paper include: (1) a closed-form function for the optimal cost; (2) a new, polynomial-time algorithm which computes the optimal policy; and (3) stability regions for the optimal policy valid for simultaneous variations of all parameters involved in the problem. The approach used in this paper is completely different from the one used by Chand and Voros (1992). These authors extended the results of Richter (1987) and developed setup cost stability regions for the problem with complete backlogging, constant setup cost and varying demand, and holding and backlogging costs.
This paper is organized as follows: Section 2 contains notation, the mathematical formulation of the problem, and some preliminary work. This preliminary work includes the partition of the set of all admissible policies P([bar.z]) into subsets P(n), each of which contains policies with n cycles. In [section]3, we find the optimal policy in the set of policies P(n) and obtain an initial formula giving the corresponding optimal cost as an explicit function of n. We then prove that these results are valid not only for a given n, but also for any n belonging to certain sets [B.sub.i]. The paper continues with [section]4, where we introduce a partition of the region defined by the holding and backlogging cost parameters. Based on this partition, we further expand the formula already established in [section]3, and obtain the total optimal cost as a closed-form function of all parameters involved in the problem. We then prove that the optimal total cost function is convex with respect to n. Convexity makes it relatively simple to calculate the overall optimal policy. In [section]5, we present an algorithm, which computes the number of cycles in the overall optimal policy, and indicate how to construct the corresponding stability region. The paper closes with a summary of results and suggestions for future research.
2. Problem Formulation
We consider the single-product lot-sizing problem with the following characteristics:
(1) The planning horizon is composed of T time periods of equal length.
(2) The demand D in every period is known, constant, and is satisfied at the beginning of each period.
(3) The ordering (setup) cost is S per order, and is independent of the quantity ordered.
(4) The holding cost is h per unit of product per period, and it is charged against the end-of-period stock.
(5) Shortages are allowed and excess demand is completely backlogged.
(6) The backlogging cost is b per unit backlogged per period,...
|
