An Algorithm for Infinite Horizon Lot Sizing with Deterministic Demand ()
Keywords:Natural Asset; Financial Value; Neural Network
1. Introduction
Standard finite horizon inventory models with deterministic but non-stationary demand (see, for example, [1]). Chapter 4, for their description) equate the planning horizon with the life cycle of the purchased product. Thus, for any optimal procurement strategy, inventories at the end of the last period are zero. Nevertheless, a purchasing firm usually continues its operations after the end of the planning horizon of the model. Therefore, the procurement decision in each period should be optimal with respect to demands in the following periods. Hence, the optimal procurement strategy should result from an infinite horizon model with discounting of cost in future periods. The discount factor can be arbitrarily close to but lower than one. From the point of view of business practice, discounting of future cost is a more natural approach than limit of means evaluation relation or overtaking evaluation relation (see, for example, [2], pp. 137-139 for the characterization of the latter two criteria).
If demands and other characteristics of the environment that differ between periods exhibit some finite cycle, we can obtain a numeric solution of an infinite horizon inventory model. In this case, after a finite number of periods, the same finite cycle of characteristics of the environment is repeated (Stationary characteristics of the environment are a special case of this, with cycle length equal to one). In the present paper, we deal with such a case. We allow fixed ordering cost, variable procurement cost, and holding cost that differ between periods. We develop an algorithm for computing of an optimal procurement strategy in this model that minimizes the sum of discounted total costs over the infinite horizon of the model. The optimal procurement strategy determines the optimal procurement cycle, at the end of which the inventory is zero. That is, except for a finite number of periods at the beginning of the model, the optimal procurement strategy is an infinite repetition of the procurement strategy over the optimal procurement cycle.
Throughout the paper,
denotes the set of positive integers and
denotes the set of real numbers. We endow each finite dimensional space with the Euclidean topology and
with the product topology (i.e., the topology of point-wise convergence).
2. Results and Discussion
2.1. Motivating Example
Consider the inventory system with the length of the planning horizon equal to five periods used in [1], pp. 92- 94. The fixed ordering cost is
and holding cost is
(Variable procurement cost is not specified. It is assumed to be the same in each period. Therefore, the cumulative purchasing cost over the planning horizon is independent of the decision variables and it can be excluded from the objective function). Denoting the projected demand in period
by
, we have
,
,
,
, and
.
Without discounting of future cost, the unique optimal procurement strategy is
. Since it is unique, it remains the unique optimal procurement strategy also for discount factors less than but close to one. Now suppose that, since period six, the demand cycle
is repeated for ever. That is, for each
and each
,
. Then, for discount factor close enough to one, it is optimal to purchase 120 units in period 5 and in each period
(because holding cost of 10 units for one period is lower than
but holding cost of 60 units for two periods exceeds
), 75 units in each period
(because holding cost of 15 units for one period is lower than
but holding cost of 150 units for two periods exceeds
; shifting order from period
to period
decreases the sum of incurred discounted fixed ordering cost and, for discount factor close to one, decreases the sum of discounted holding cost), and 150 units in each period
(because holding cost of 110 units for one period exceeds
). Thus, the optimal procurement strategy prescribes purchasing 85 units in the first period, nothing in periods 2 and 3, and, since period 4, it is the infinite repetition of procurement cycle
. That is, the optimal procurement cycle consists of five periods and its first occurrence starts in period 4 (In order to save space, we do not give the computation of the optimal strategy for this problem as an example of the application of the algorithm described in Section 4). Clearly, (for discount factor close enough to one) the sum of discounted total cost cannot be minimized by the infinite repetition of the optimal procurement strategy from the finite horizon model.
2.2. Model
We consider an infinite horizon discrete time inventory model. Periods are numbered by positive integers. Each period
is characterized by quadruple
(1)
where
is the deterministic demand,
is the fixed ordering cost,
is the variable procurement cost, and
is the holding cost in period
. We call this quadruple “environmental vector” (a shortening of the term “vector of characteristics of the environment”). We assume that there exist
and
such that
(2)
That is, the environmental vectors exhibit the finite cycle of length
that is repeated since period
. We assume that this is the shortest cycle of environmental vectors, durability of the purchased good is no lower than
periods and warehouse capacity does not prevent the firm from storing it for at least
periods. Of course, we assume that there exists
such that
.
We assume that
(3)
and
(4)
It follows from (2) and (3) that the sum of procurement and holding cost in each period is not lower than procurement cost in the immediately following period. Inequality (4) implies that there does not exist a period
such that it is optimal to satisfy strictly positive demand in
by an order placed in
. If (4) does not hold, there exists finite
such that
![](https://www.scirp.org/html/htmlimages\1-7401851x\478b87ac-8bda-47e4-b668-15850a1a827c.png)
This follows from the fact that
and
are bounded from above over all periods and
. Then all arguments used in the present paper that rely on (4) continue to hold with
replaced by
.
All arguments used in this paper remain valid and the algorithm described in Section 4 can be used when (4) does not hold but Conditions 1 and 2 given below the definition of
following (13) are satisfied.
We denote by
the quantity ordered in period
and by
the inventory at the beginning of period
. Then the inventory at the end of period
(for which the firm has to pay holding cost) is
. In accordance with lot sizing models in the literature, we assume that lead time is zero (i.e., the ordered quantity is delivered without delay) and
. If the latter assumption is not satisfied, we can modify demands in a finite number of periods at the beginning of the time horizon of the model in such a way that the inventory at the beginning of the first period with a positive demand in the modified model equals zero (see, for example, [1], p. 89, for details). We also assume, without loss of generality, that
. If this assumption is not satisfied, we omit each period
such that
for each
from the model and identify period
with period 1.
The purchasing firm discounts future cost by discount factor
, without discounting the cost in the current period. It wants to minimize the sum of discounted total cost over the infinite horizon of the model subject to satisfying demand in each period. Thus, it solves the following mathematical programming problem:
(5)
subject to
(6)
(7)
(8)
We will use the term “optimal procurement strategy” for an optimal solution to the problem (5)-(8) and the term “feasible procurement strategy” for a procurement strategy that satisfies constraints (6)-(8). In the construction of the algorithm in the next section, we will use the following lemma. It is an analogue of a well known result from the analysis of finite horizon lot sizing models without discounting of future cost that was used in [3].
Lemma 1 Let
be an optimal procurement strategy. Then
for each
.
Proof. Suppose that the claim of the lemma does not hold for some optimal procurement strategy
. Let
be the first period in which
and
. Since
,
. Let
be the last period before period
in which an order was placed (Since
and
implies
, such
exists).
Thus,
. We can decrease, without violation of any constraint, the value of objective function (5)
by reducing
by
and increasing
by
. This allows satisfaction of demands in periods
, leaves the quantity of good available in period
(after receiving the quantity ordered in period
) unchanged, and leaves the fixed ordering costs in each period unchanged. Using (2) and (3),
![](https://www.scirp.org/html/htmlimages\1-7401851x\c5468959-ed6d-4670-8864-959ae65b51d7.png)
Thus,
. This implies that
![](https://www.scirp.org/html/htmlimages\1-7401851x\739e8b7c-d4db-4e02-b1a5-916ec1b318f2.png)
Therefore, the sum of discounted procurement and holding cost is decreased.
Lemma 1 has an obvious corollary.
Corollary 1 Let
be an optimal procurement strategy. If demand in period
is satisfied from the order placed in period
, then the latter order satisfies demand in each period
;
i.e., ![](https://www.scirp.org/html/htmlimages\1-7401851x\453e9cb6-1204-4d9e-9072-4404bb201190.png)
2.3. Algorithm
We begin this section with formulation of criteria that we will use in the description of the algorithm for solving the problem (5)-(8).
The sufficient condition for not placing an order in period
, irrespective of whether an order was placed in period
, has the form
(9)
If (9) holds then it is cheaper to satisfy demand in period
or the sum of demands in period
and
following periods by an order placed in period
than by an order placed in period
(With respect to (4), we need not consider more than
periods following period
). Thus, in an optimal procurement strategy an order will not be placed in period
. The inequality (9) is equivalent to
(10)
Taking into account (3) and the fact that
and
,
. Thus, (10) is equivalent to
(11)
If an order was placed in period
, conditions (11) reduces to
(12)
Let
be the set of periods in which (according to the knowledge that we have before solving the problem (5)-(8)) an order will not be placed. That is,
belongs to
if and only if it satisfies (11) and
if and only if it satisfies (12). For
, let
be the set of periods that follow period
and belong to
without interruption (i.e., if
and
, then
.) Note that, with respect to (4),
. For
, let
![](https://www.scirp.org/html/htmlimages\1-7401851x\c31028e5-bbfe-41bf-ba6b-91fa649524b7.png)
Throughout the paper, we assume that, whenever the firm is indifferent between placing an order in two periods, it places it in the later one. Then the sufficient condition for placing an order in period
has the form
(13)
Denote by
the set of periods in which an order should be placed (according to the knowledge that we have before solving the problem (5)-(8)). That is,
(because
and
) and
belongs to
if and only if it satisfies (13).
All arguments used in this paper remain valid and the algorithm described in Section 4 can be used when (4) does not hold but the following conditions are satisfied. We illustrate their use in the example at the end of this section.
Condition 1 There exists
such that
and
.
Condition 2 For each
, there exists
such that
.
We let
![](https://www.scirp.org/html/htmlimages\1-7401851x\32538b5e-6b78-4d89-8e43-99d7c0e2be5d.png)
It follows from the assumption that there exists
such that
and (4) that
and
are infinite sets. We define function
by
![](https://www.scirp.org/html/htmlimages\1-7401851x\7aa2e182-b559-41ba-8ad2-3dcc928276d1.png)
For each
, we denote by
the optimally determined period in which the order covering the demands in periods
is placed (i.e., the latest period in
, in which an order is placed) when we consider only the first
periods and require that
.
denotes the set of periods from which we can choose
.
denotes the sum of discounted total cost of satisfying demands in the first
periods when the order satisfying demands in periods
is placed in period
.
is the minimized sum of discounted total cost in the problem with the first
periods and constraint
. The following lemma reveals restrictions on the choice of
that a succession of optimal procurement strategies for problems with a finite number of periods should satisfy. Analogous intermediate result was used in the derivation of Wagner—whitin algorithm [4]. Nevertheless, since we work with discounting of future costs, Lemma 2 is not a consequence of their intermediate result. Moreover, Lemma 2 is stronger than their intermediate result. It says that each optimal procurement strategy for the first
periods has the described property, not only that there exists an optimal procurement strategy for the first
periods that has the described property (Compare also Lemma 2 and Theorem 4.2 in [1], p. 96).
Lemma 2 Let
and
be an optimal procurement strategy for the first
periods under which the demands in periods
are satisfied from the order placed in period
. Set
![](https://www.scirp.org/html/htmlimages\1-7401851x\55ca3b43-45c2-4c9a-8f98-7a0c36835552.png)
Then, for each optimal procurement strategy for the first
periods,
, the demands in periods
are satisfied from the order placed in period
.
Proof. Take (arbitrary)
. Suppose that
. Then, using Lemma 1 and Corollary 1 to it,
and
, where
is the inventory at the beginning of period
generated by
(Lemma 1 is formulated for an optimal strategy in the infinite horizon model. Nevertheless, the argument in its proof concerns only changes in orders in the first
periods, subject to the constraint that the quantity of the good available in period
,
, remains unchanged. The same argument applies to changes in orders in the first
periods, subject to the constraint that the quantity of the good available in period
remains unchanged. Thus, Lemma 1 and Corollary 1 to it are valid also for the case considered here). Clearly(since
)
cannot decrease the sum of discounted total cost of satisfying demands in the first
periods in comparison with
. The difference in the sum of total cost discounted to the end of period
between satisfying demands in periods
from the order placed in period
and satisfying them from the order placed in period
is
(14)
The optimality of
implies that satisfying the demands in periods
from the order placed in period
leads to lower or the same sum of discounted total cost than satisfying them from the order placed in period
(keeping the way of satisfying demands in periods
, unchanged) i.e.
(15)
Since (using (3))
![](https://www.scirp.org/html/htmlimages\1-7401851x\b67e2bb0-db8f-43bf-a4b9-0956907be048.png)
and
(15) implies that the expression (14) is strictly positive. Therefore, the assumption that
is false.
Of course,
,
, and
,
if
and
if
. We formally set
.
Consider period
. Suppose that we have already solved the problem for the first
periods for each
such that
. The choice of
in the algorithm is based on comparing the sum of discounted total cost only for adjacent elements of
or of a set
obtained from
by elimination of elements in which it is not optimal to place an order. Consider
and
. Let
be the sum of demands in period
that can be satisfied from an order placed either in period
or in period
. We have
if and only if
(16)
(17)
Inequality (16) is equivalent to
(18)
and (17) is equivalent to
(19)
From inequalities (18) and (19) we can compute the critical value of
of
for which
. This critical value plays an important role in the algorithm. If
, then
and we can eliminate period
from consideration for determination of
. Right hand sides of (18) and (19) are independent of
. It follows from (3) that
. Therefore, if (18) or (19) holds for
, then it holds as a strict inequality for any
. Thus, if
, then ![](https://www.scirp.org/html/htmlimages\1-7401851x\dc32eb01-2b0e-4689-925a-3a79309f8e46.png)
for each
with
. Hence, if we eliminate period
from consideration for determination of
, we should eliminate it also from consideration for determination of
. This reduces the number of periods that we have to consider in the following iterations of the algorithm.
Suppose that set
resulted from iterative elimination of elements, which need not be considered for determination of
, from
, and we cannot eliminate any element from
. Then
for each
and
with
. Therefore,
In the following iteration, in which we want to determine
for
, we need to consider only periods in
![](https://www.scirp.org/html/htmlimages\1-7401851x\30325b1c-d468-4be0-9317-3201588a24ee.png)
For each
, let
be the optimal procurement strategy for the first
periods. We will use the following proposition in the construction of the algorithm.
Proposition 1 Assume that there exist
and
such that
![](https://www.scirp.org/html/htmlimages\1-7401851x\b1c91170-98a7-46e1-a40a-729c85c15602.png)
satisfies
and
Then
defined by
for each
and
for each
and each
, is an optimal procurement strategy.
Proof. Using Lemma 1, the optimal procurement strategy for the first
periods generates
. Consider
. By Lemma 2,
. Therefore,
and
. (If the choice of
does not cancel the placement of order in period
, then
. Otherwise,
). Let
. Since
and
is the length of the cycle of environmental vectors,
. Using Lemma 2,
. Therefore,
. and
. Using Lemma 1, the optimal procurement strategy for the first
periods generates
. In order to solve the problem with the first
periods, it is enough to compute optimal orders in periods
. Since
and
for each
, we have
for each
and, if
,
for each
(If the problem with the first
periods has more than one optimal solution, we choose the one specified in the preceding sentence). Repeating this argument for period
(computing optimal orders in periods
) for each
, we obtain the strategy
described in Proposition 1. Note that, for each
,
and, hence,
is the optimal procurement strategy for the first
periods.
Suppose that there exists feasible procurement strategy
such that
.
Taking into account (4), we can assume without loss of generality that
for each
(If this condition is not satisfied, we can replace
by another feasible procurement strategy that satisfies it and gives lower value of objective function
). Thus, taking into account (2), there exists
such that for
we have
![](https://www.scirp.org/html/htmlimages\1-7401851x\38c6fd77-2c7a-4eec-89a5-eaef1371b657.png)
(where
is the sequence of inventories at the beginning of periods generated by
and
is the sequence of inventories at the beginning of periods generated by
). Therefore,
![](https://www.scirp.org/html/htmlimages\1-7401851x\d8aa6681-1a5f-4fdb-a470-32d23f94b8e6.png)
This contradicts the fact that
is the optimal procurement strategy for the first
periods.
The algorithm is based on solving a succession of problems with a finite number of periods. Proposition 1 implies that we can stop when we find
for which
(20)
exists. The following lemma shows that such
exists.
Lemma 3 There is
for which
defined by (20) exists.
Proof. For each
, define
by
for each
and
for each
. For each
, if there are
and
such that
and
, then
for each
and each
with
. Using (4) and the assumption that there exists
such that
, for each
there exists
such that
and
and
for some
and some
. Therefore,
exists. Let
. Using (4) and the assumption that there exists
such that
,
is an infinite set. Consider sequence
.
Taking into account (4), (2), Lemma 1, and Corollary 1, there is a finite set to which element of
belongs. Therefore, there exist
and
with
such that
. Using (2), there is
such that
. Then, using (4) and the fact that
, there exists
such that
. (This implies that
). We have either
or ![](https://www.scirp.org/html/htmlimages\1-7401851x\3f6ffdd1-59eb-4c1e-91a1-e2bb0862acfc.png)
The stopping rule in the algorithm can be simplified if there exists
such that
and
. Then
and
for each
with
. Clearly, there exists
such that
and
.
In the algorithm, we use the equality sign for the assignment of a new value to the variable whenever such expression is correct from the mathematical point of view. Otherwise, we use the symbol
.
Algorithm 1 Step 1: Set
,
,
,
,
,
, and
![](https://www.scirp.org/html/htmlimages\1-7401851x\cb3d1cff-2598-47a1-aaba-5f15de6cc2d8.png)
![](https://www.scirp.org/html/htmlimages\1-7401851x\a4e1514a-89a7-410f-ab7f-d86687fd48f3.png)
Step 2: Set
. If
, and
, set
, set
for each
if
, and go to step 9. Otherwise, go to step 3.
Step 3: If
, set
,
, and go to step 7. Otherwise, set
![](https://www.scirp.org/html/htmlimages\1-7401851x\e66aef5b-8104-460e-b9d3-0fc1271b9232.png)
, and go to step 4.
Step 4: For each
satisfying
let
,
, compute
![](https://www.scirp.org/html/htmlimages\1-7401851x\8839f26c-e140-41c3-b6b8-53dbb1bb2e60.png)
![](https://www.scirp.org/html/htmlimages\1-7401851x\715735fa-71c5-4197-8eab-3844ac0d8a77.png)
and let
for each
with
. Set
and
.
Step 5: Let
![](https://www.scirp.org/html/htmlimages\1-7401851x\fb8f8df9-cf05-44fb-b4df-2f2c17a1c5f7.png)
If
or
, set
,
, and go to step 7. Otherwise, let
![](https://www.scirp.org/html/htmlimages\1-7401851x\a615baa7-ba92-46d6-9d36-6128f4ece1c1.png)
If
, set
,
, and go to step 7. Otherwise, go to step 6.
Step 6: Let
, compute
![](https://www.scirp.org/html/htmlimages\1-7401851x\06efc357-73af-4803-819a-ffc3b7c71a8b.png)
set
and
. If
, set
and go to step 5. Otherwise, return to step 6.
Step 7: Let
,
,
,
for each
. If
, set
. Otherwise, set
. Let
![](https://www.scirp.org/html/htmlimages\1-7401851x\9ca1e367-0424-4438-bdce-81835279be47.png)
![](https://www.scirp.org/html/htmlimages\1-7401851x\b6ce0abc-f703-47c7-acf9-c5d07bc28ed7.png)
If
or
, go to step 8. If
and
, set
, and go to step 8. If
and
, set
,
, and go to step 8.
Step 8: If there exists
such that
![](https://www.scirp.org/html/htmlimages\1-7401851x\0f876f86-d3b2-494d-abd4-2eab86ac4fe1.png)
go to step 9. Otherwise, go to step 2.
Step 9: Set
for each
and each
. Stop.
The algorithm does not give the optimal value of the objective function (5). Using values computed by the algorithm and setting
if
and
if
, the optimal value of the objective function (5) equals
![](https://www.scirp.org/html/htmlimages\1-7401851x\2484e117-f65d-475a-a61f-f4c7409b5277.png)
We could use the stopping rule specified in the algorithm and solve finite horizon problems by the WagnerWhitin algorithm, modified for the case of discounting of future cost. Nevertheless, our algorithm has several advantages in comparison with their algorithm. Firstly, it saves calculations by identifying periods in which an order should be placed. Secondly, it saves calculations by identifying periods in which an order will not be placed. Thirdly, when a period is removed from the set of candidates for placing an order in some iteration, it is no longer considered in the following iterations. Moreover, it is enough to compare only successive elements of the set of candidate periods. From the point of view of elimination of candidate periods, our algorithm is similar to Wagner-Whitin algorithm [4]. Fourthly, comparison of successive elements of the set of candidate periods is based on the critical sum of demands in the relevant following periods. Unless some period is eliminated from the set of candidate periods and at least one of its predecessors is kept, these critical sums of demands can be easily updated in the future iterations. Even when some period is eliminated from the set of candidate periods and at least one of its predecessors is kept, calculation of new critical sums of demands requires only calculations used in the recursive relations in Wagner-Whitin algorithm.
3. Conclusion
We have constructed an algorithm for computing an optimal procurement strategy in an infinite horizon inventory model with non-stationary deterministic demand, a finite cycle of environmental vectors, and discounting of future cost. It is based on solving a succession of finite horizon inventory optimization problems. The formulation of the stopping rule is made possible by the fact that the cycle of environmental vectors is finite.
It is worth noting that our algorithm can also be used to solve a finite horizon problem. This also holds when future cost is not discounted (i.e.,
provided that inequality (3) is strict.
Acknowledgements
The research reported in this paper was supported by the grant VEGA 1/0181/12 from the Slovak Ministry of Education, Science, Research, and Sport. VEGA did not play any role in the study design or in the writing of the article or in the decision to submit it for publication.