﻿ An Algorithm for Infinite Horizon Lot Sizing with Deterministic Demand

Applied Mathematics
Vol.5 No.2(2014), Article ID:42155,9 pages DOI:10.4236/am.2014.52023

An Algorithm for Infinite Horizon Lot Sizing with Deterministic Demand

Milan Horniaček

Faculty of Social and Economic Sciences, Institute of Public Policy and Economics, Comenius University in Bratislava, Mlynske luhy 4, Bratislava, Slovakia

Email: milan.horniacek@fses.uniba.sk

Received September 19, 2013; revised October 19, 2013; accepted October 26, 2013

ABSTRACT

We analyze an infinite horizon discrete time inventory model with deterministic but non-stationary demand for a single product at a single stage. There is a finite cycle of vectors of characteristics of the environment (demand, fixed ordering cost, variable procurement cost, holding cost) which is repeated after a finite number of periods. Future cost is discounted. In general, minimization of the sum of discounted total cost over the cycle does not give the minimum of the sum of discounted total cost over the infinite horizon. We construct an algorithm for computing of an optimal strategy over the infinite horizon. It is based on a forward in time dynamic programming recursion.

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

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),

Thus,. This implies that

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.,

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

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

It follows from the assumption that there exists such that and (4) that and are infinite sets. We define function by

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

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))

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

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

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

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

(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,

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

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

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

, and go to step 4.

Step 4: For each satisfying let, , compute

and let for each with. Set and.

Step 5: Let

If or, set, , and go to step 7. Otherwise, let

If, set, , and go to step 7. Otherwise, go to step 6.

Step 6: Let, compute

set and. If, set and go to step 5. Otherwise, return to step 6.

Step 7: Let, , , for each. If, set

. Otherwise, set. Let

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

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

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.

REFERENCES

1. J. A. Muckstadt and A. Sapra, “Principles of Inventory Management,” Springer-Verlag, Berlin, 2010. http://dx.doi.org/10.1007/978-0-387-68948-7

2. M. J. Osborne and A. Rubinstein, “A Course in Game Theory,” The MIT Press, Cambridge, 1994.

3. A. Wagelmans, S. V. Hoesel and A. Kolen, “Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in Wagner-Whitin Case,” Operations Research, Vol. 40, 1992, pp. S145-S156. http://dx.doi.org/10.1287/opre.40.1.S145

4. H. M. Wagner and T. M. Whitin, “Dynamic Version of the Economic Lot Size Model,” Management Science, Vol. 5, No. 1, 1958, pp. 89-96. http://dx.doi.org/10.1287/mnsc.5.1.89