On the Optimality of s, S Inventory Policies:

Volume 2008, Article ID 158193,9pages doi:10.1155/2008/158193

Research Article

On the Optimality of s, S Inventory Policies:

A Quasivariational Approach

Lakdere Benkherouf

Department of Statistics and Operations Research, College of Science, Kuwait University, P.O. Box 5969, Safat 13060, Kuwait

Correspondence should be addressed to Lakdere Benkherouf,[email protected] Received 22 February 2008; Revised 9 June 2008; Accepted 17 July 2008

Recommended by Ho Lee

This paper revisits the classical discrete-time stationary inventory model. A new proof, based on the theory of quasivariational inequalityQVI, of the optimality ofs, Spolicy is presented. This proof reveals a number of interesting properties of the optimal cost function. Further, the proof could be used as a tutorial for applications of QVI to inventory control.

Copyrightq2008 Lakdere Benkherouf. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

Consider an inventory model which consists in controlling the level of stock of a single product where the demandsD₁, D₂, . . .for the product in periods 1,2, . . .are independently and identically distributedi.i.drandom variables with density functionψ, and finite mean μ <∞.

Assume that at the beginning of each period the system is reviewed and we are allowed to increase the level of stock to any level we wish. Orders are assumed to be delivered immediately.

Letfbe a real-valued function representing the holding and shortage cost withf0 0 andfx>0 forx /0. The costcxof ordering an amountxis given by

cx

⎧⎨

⎩

kcx, x >0,

0, x0, 1.1

wherecis the unit cost of the item andkis the set-up costc >0, k >0. Costs are assumed to be additive and geometrically discounted at a rateα, 0< α <1, and that unmet demand is completely backlogged.

An admissible replenishment policy consists of a sequenceti, ξi, i1, . . . , whereti

represents theith time of ordering andξ_i>0 represents the quantity ordered at timet_i. Write Vn{ti, ξi, i1, . . . n},

V∞ lim

n→∞VnV. 1.2

Letxndenote the level of stock at timen, n0,1, . . . ,and letFn σ{xs, s≤ n}

be theσ-algebra generated by the history of the inventory level up to timen. Assume that for eachn∈N, VnisFn-measurable. Then for a given initial inventory levelxand an ordering policyV, the infinite horizon discounted cost is defined by

yx,V:E_{V ∞}

t0

α^tfxt ⁿ

i1

α^ticξi

, 1.3

where the expectation is taken with respect to all possible realizations of the process xt under policyV. Set

yx:inf

V yx,V. 1.4

The objective is to find an admissible policyV^∗ such thatyx,V^∗ yx.

Scarf 1 considered a finite horizon version of the problem described in 1.3. He showed using dynamic programming that if the one period expected holding plus shortage cost function is convex, then the optimal policy for periodnis ansn, S_npolicy. The principal tool used by Scarf was a concept of K-convexity which he introduced in the same paper.

Subsequently, Iglehart 2extended Scarf’s result to the infinite horizon case by showing that the property ofK-convexity holds for the infinite period stationary model. Veinott3 replaced the requirement of the convexity of the one period expected holding plus shortage cost by a quasiconvexity requirement and added other conditions. Again using dynamic programming, he showed the optimality of ans, Spolicy.

In this paper, we approach the problem of determining the optimal inventory policy as an impulse control problem, the theory which has been developed by Bensoussan and Lions4. Under this theory, the Bellman equation of dynamic programming for the inventory problem leads to a set of quasivariational inequalities QVIswhose solution leads to the optimal inventory policy. This approach leads to a new proof of the result which does not useK-convexity and is based on the examination of some properties of an integral equation.

Previous applications of QVI to inventory control revolved around diffusion processes from which the machinery needed to prove optimality ofs, Spolicy was not simple. This paper we hope can serve as a tutorial of applications of QVI to inventory control. Readers interested in applications of QVI to inventory control may consult5–8.

Before we embark on the proof we will first formulate the problem described in1.3 as a QVI.

Recall thatxtrefers to the level of stock at timet, and consider all possible actions at timet.

iIf no order is made, then it follows from1.3and1.4that

yxt≤Efxt−D αEyxt−D 1.5

or

yxt−αEyxt−D≤Efxt−D, 1.6

whereDrefers to the demand in a period.

iiIf an order of sizeξis made, then the level of stock jumps fromxttoxt ξ, and yxt≤kinf

ξ>0cξyxt ξ. 1.7

Forx∈R, define the operatorsAandMby

Ayx:yx−αEyx−D, Myx:kinf

ξ>0cξyxξ. 1.8

It follows that the problem of finding the optimal solution to1.3reduces to solving the following QVI problem:

Ay≤F, y≤My, Ay−Fy−My 0,

1.9

where

Fx:Efx−D. 1.10

To solve the QVI given in1.9, we examine an integral equation problem related to the QVI.

This is done inSection 2. The properties obtained of the integral equation are then used to show the optimality ofs, Spolicy inSection 3.

2. An integral equation problem

Consider the space of continuous functionsCR. Assume that we are given a nonnegative functionhinCR.

Further, suppose that

A1there exists γh,−∞ < γh < ∞, such that h is decreasing on −∞, γh and nondecreasing onγh,∞;

A2 hx→ ∞, as|x| → ∞.

ForLinCR, define the convolution operator∗by ψ∗Lx

_∞

0

Lx−tψtdt. 2.1

Now, consider the integral equation

Lx−αψ∗Lx hx, x > s,

Lx 1

1−αhs, x≤s. 2.2

Here,s < γ_h, and it is a free parameter.

Under assumption thathis inCR, the integral equation2.2has a unique solution inCR see9. LetL_sdenote this solution. In what follows, there is a list of properties of L_swhich will prove useful in showing the optimality of thes, Spolicy:

L_sx 1

1−αhs ∀x≤s, 2.3

L_s is decreasing ons, γh, 2.4

Lsx≥ 1

1−αhγh ∀xinR, 2.5

L_sx−→ ∞ asx−→ ∞. 2.6

Property2.3is the boundary condition of2.2.

Proof of Property2.4. To show2.4argue by contradiction. Assume thatLsinitially does not decrease. In other words, there existsΔ,s <Δ< γ_hsuch thatL_sis nondecreasing ons,Δ. It follows that forxandtsatisfyings≤x≤Δandt≥0,L_sx−L_sx−t≥0; but2.2gives

1−αLsΔ α _∞

0

LsΔ−LsΔ−tψtdthΔ. 2.7

Therefore,1−αLsΔ ≤ hΔorL_sΔ ≤ 1/1−αhΔ. This leads toL_sΔ < 1/1− αhsby AssumptionA1. Property2.3then implies thatLsΔ< Lss, which leads to a contradiction.

To complete the proof, we again argue by contradiction and assume that there exists η, andΔ,s < η <Δ< γh, such thatLsis decreasing ons, ηand nondecreasing onη,Δ. Let xbe such thatη < x <Δ, andL_sx< L_ss. We claim that fort≥0,

Lsx−Lsx−t≥Lsη−Lsη−t. 2.8 We have by2.2

1−αLsx α _∞

0

Lsx−L_sx−tψtdthx. 2.9

Now, use2.8and the fact thatL_sx≥L_sηto get from2.9that hx≥1−αLsη α

_∞

0

Lsη−L_sη−tψtdthη, 2.10

buthx< hηby AssumptionA1. This leads to a contradiction. This ends the proof.

Proof of Property2.5. Assume that Property2.5is not true. Using Property 2.4and the fact thatL_sis continuous, letx^∗be the firstsmallestsolution ofL_sx^∗ 1/1−αhγh. Clearly,x^∗ > s, andLsattains its minimum atx^∗on−∞, x^∗. Using2.2, AssumptionA1, and recalling thatψis a density function, we get

L_sx^∗ hx^∗ α _∞

0

L_sx^∗−tψtdt > hx^∗ αL_sx^∗. 2.11 Therefore, Lsx^∗ > 1/1−αhγh. This leads to a contradiction. Whence Property 2.4 holds.

Proof of Property2.6. Using2.2, we get Lsx hx α

_∞

0

Lsx−tψtdt≥hx α

1−αhγh. 2.12

The last inequality follows from Property 2.5. The result is then immediate from AssumptionA2by taking the limit asx→ ∞. This completes the proof.

We will next present further properties ofL_s.

Theorem 2.1. For a givens < γ_h, there exists anSs, γh < Ss<∞, which minimizesL_sxfor xinR.

Proof. The proof follows from Properties2.3–2.6and the continuity ofL_s. We remark here thatSsmay not be unique.

Fors < γh, define

Ks L_ss−min

x∈RL_sx. 2.13

Clearly,Kis a well-defined function on−∞, γhand is nonnegative.

Lemma 2.2. The functionKis decreasing ins.

Proof. Lett < s < γ_h, and forxinR, define

Dx:Ltx−Lsx. 2.14

It is easy to show thatDis a solution of2.2with the right-hand side changed to

gx

⎧⎪

⎪⎨

⎪⎪

⎩

ht−hs, x≤t, hx−hs, t≤x≤s,

0, x > s.

The functiong is constant on −∞, t, decreasing ont, s, and is equal to zero forx > s.

Therefore, a similar argument to that used to show properties2.4and2.5shows thatDis decreasing onRand is nonnegative. SinceSs> s > t, it follows fromTheorem 2.1that

L_tt−L_st≥L_tSs−L_sSs≥L_tSt−L_sSs, 2.15 butLst Lss. Therefore,Ltt−LtSt≥ Lss−LsSs, which leads to the required result.

Lemma 2.3. The functionKis continuous.

Proof. Fix >0. Sincehis continuous, there existsδ >0 such that|hs−ht|<1−α/2 whenever|s−t|< δ. Pickt < γ_hsuch that|s−t|< δ. To make things simple, assumet < s. It was shown in the proof ofTheorem 2.1thatL_tSt−L_sSs≤L_tt−L_ss. Now, use the definition ofLttandLssto get thatLtSt−LsSs≤ 1/1−αht−hs < /2;

but

|Kt−Ks| ≤ |LtSt−LsSs||Ltt−Lss|<

2

2 . 2.16

Therefore,Kis continuous.

Lemma 2.4. (i)Ks→0 ass→γh. (ii)Ks→ ∞as s→ −∞.

Proof. iRecall thatKs≥0 and thatL_sx≥1/1−αhγhby Property2.5. In particular, LsSs ≥ 1/1−αhγh. It follows that Lss−1/1−αhγh ≥ Ks ≥ 0 or1/1− αhs−hγh ≥ Ks ≥ 0. The result is then immediate from the continuity of hand AssumptionA2by lettings→γ_h.

iiDefine

L_sx:g_sx, 2.17

where

g_sx

⎧⎪

⎪⎨

⎪⎪

⎩

hx α

1−αhs, x > s, 1

1−αhs, x≤s.

2.18

The functionL_sis decreasing on−∞, γh. Therefore, forxin−∞, γh, Lsx<

_∞

0

Lsx−tψtdt. 2.19

Write

Gs:Ls−Ls. 2.20

It is not difficult to show thatGssatisfies the following:

G_sx−αψ∗G_sx α

1−αhs−αψ∗L_sx, x > s, G_sx 0, x≤s.

2.21

Again, a similar argument used to prove Property2.4can be used to show thatG_sis increasing on−∞, γh. Therefore,G_sγh ≥ G_ss 0. This in turn leads toL_sγh ≥ L_sγh. Now,

Ks L_ss−L_sSs≥L_ss−L_sγh≥L_ss−L_sγh. 2.22 The right-hand side of2.22is equal tohs−hγh with limit∞ass→ −∞. This completes the proof of the lemma.

Now consider the problem of finding a solutionsto the problem

Ks k. 2.23

Theorem 2.5. There exits a unique numbers < γhsuch thatKs k.

Proof. The proof is immediate fromTheorem 2.1and Lemmas2.2–2.4.

3. Optimality ofs, Spolicy

Recall the definitions of the functionsyandFin1.9and let Lx:yx cx,

hx: 1−αcxFx αcμ. 3.1

It is an easy exercise to see that for x > s, Ay F is equivalent to AL h, which is the integral equation2.2forx > s.

Assume that h satisfies Assumptions A1 and A2 and let s < 0 be the unique solution of2.23. This value ofsleads to a value ofSswhich minimizesLsthis may not be unique. Further, letSdenote the generic value ofSs. We will next show that the policy which asserts that if the level of stockx < s, order up to levelS: else do not order, solves the QVI given by1.9. The proof of optimality relies on the concept of non-k-decreasing functions which may be found in10, page 137.

Definition 3.1. A functionv:R→Ris non-k-decreasing ifx≤yimplies that

vx≤kvy. 3.2

Note that the concept of non-k-decreasing is weaker than the concept ofk-convexity which is a standard tool for showing optimality ofs, Spolicy; see10for more details.

Our objective is to show that the functionL_sis non-k-decreasing. Note from Properties 2.3–2.6 that Ls is constant on −∞, s, then decreases at least down to γh, reaches its minimum at someS, and eventually goes to∞as x → ∞. Non-k-decreasing means that the functionL_scannot have a drop bigger thankbeyondS. Let

Δhmin{x > γh, Lsx Lss}. 3.3 Note thatΔexists and is unique. Set

Ks L_ss−min

x≤Δh

L_sx. 3.4

Theorem 3.2. Fors < γ_h,the solutionL_sof2.2satisfies

Lsx−Lsy≤ Ks ∀x≤y. 3.5

Proof. The proof is by contradiction and only a sketch of the proof will be given. Consider the set

RKs {x≥Δh, L_sx−L_sy>Ks, for somey≥x}. 3.6 IfRsis empty, there is nothing to prove and theorem is true. Assume thatRKsis not empty, in which case it can be shown that there exists a tripletS1, S2, S3such thatγh< S1 <

Δ< S₂< S₃such that on the intervals, S3, Lsattains its minimum atS₁, and its maximum atS₂as shown inFigure 1with

Lss−LsS1 LsS2−LsS3:Ks. 3.7

s S1 Δh S2 S3

x Lsx

Ks

Ks

Figure 1: Plot of the functionLs.

We will next show that this cannot happen. Using2.2, we get

L_sS2 hS2 α _∞

0

L_sS2−tψtdt, 3.8

L_sS3 hS3 α _∞

0

L_sS3−tψtdt. 3.9

It follows that fort≥0,

LsS2−t−LsS3−t≤ Ks. 3.10 Using3.7–3.9, we get

Ks hS2−hS3 α _∞

0

LsS2−t−L_sS3−tψtdt

≤hS2−hS3 αKs.

3.11

This leads to1−αKs≤hS2−hS3<0 sincehis increasing onγh,∞by Assumption A1. Therefore, we have a contradiction that Ks > 0. Therefore, Rs is empty. This completes the proof.

As a corollary ofTheorem 3.2, we have the following.

Corollary 3.3. Fors < γ_h, a solutionSsof the equationL_ss−L_sSs kis a global minimum of the functionLs.

Note that the proof of Theorem 3.2 revealed that the value of S belongs to some intervalγh,Δh. Further, the results of the previous section should make a numerical search for the values, San easy exercise.

Theorem 3.4. The functionL_sdefined from the pairs, Swhich solves2.23solves1.9.

Proof. We need to show thaty < Myforx ≥sandAy ≤ F forx ≤ s. To showAy ≤ F for x≤s, letx≤s; therefore,L_sx L_ss, andAyx≤Fxis equivalent toAL_s ≤hx; but L_ss 1/1−αhs. Therefore,AL_ss≤hxis equivalent tohs≤hx, which is true sincehis decreasing forx≤γh.

To show thaty≤Myxforx≥s, note that

Myx kcS−x yS fors≤x≤S,

Myx kyx forx≥S. 3.12

Ifs ≤x≤S, thenyx≤ Myxcan be written asLsx ≤kLsS. This is true sinceLsis non-k-decreasing. This completes the proof.

It is worth noting that AssumptionA1is equivalent to saying thathis quasiconvex.

Also, AssumptionA2can be weakened by replacing it by lim_|x|→∞hx > hγh k. The limit whenx→ −∞can be inferred from2.22and the limit whenx→ ∞can be obtained from the proof of Property2.6. The optimality ofs, Spolicy remains true.

In this short paper, an alternative proof of the optimality ofs, Spolicy was given.

The proof also revealed that finding optimal values ofs, Sis a simple exercise in numerical analysis. It is hoped that this new proof will lead to new insights in the examination of some stochastic inventory models.

Acknowledgments

The author would like to thank Michael Johnson for useful discussions on the topic of quasivariational inequalities. He also benefited from the comments of two anonymous referees.

References

1 H. Scarf, “The optimality of s, S policies in the dynamic inventory problem,” in Mathematical Methods in the Social Sciences, 1959, K. Arrow, S. Karlin, and P. Suppes, Eds., chapter 13, pp. 196–202, Stanford University Press, Stanford, Calif, USA, 1960.

2 D. L. Iglehart, “Optimaility ofs, S policies in the infinite horizon dynamic inventory problem,”

Management Science, vol. 9, no. 2, pp. 259–267, 1963.

3 A. F. Veinott Jr., “On the optimality ofs, Sinventory policies: new conditions and a new proof,”

SIAM Journal on Applied Mathematics, vol. 14, no. 5, pp. 1067–1083, 1966.

4 A. Bensoussan and J.-L. Lions, Impulse Control and Quasivariational Inequalities, Gauthier-Villars, Paris, France, 1984.

5 A. Bensoussan and C. S. Tapiero, “Impulsive control in management: prospects and applications,”

Journal of Optimization Theory and Applications, vol. 37, no. 4, pp. 419–442, 1982.

6 A. Sulem, “A solvable one-dimensional model of a diffusion inventory system,” Mathematics of Operations Research, vol. 11, no. 1, pp. 125–133, 1986.

7 L. Benkherouf and L. Aggoun, “On a stochastic inventory model with deterioration and stock- dependent demand items,” Probability in the Engineering and Informational Sciences, vol. 16, no. 2, pp.

151–165, 2002.

8 A. Bensoussan, R. H. Liu, and S. P. Sethi, “Optimality of ans, Spolicy with compound Poisson and diffusion demands: a quasi-variational inequalities approach,” SIAM Journal on Control and Optimization, vol. 44, no. 5, pp. 1650–1676, 2005.

9 A. D. Polyanin and A. V. Manzhirov, Handbook of Integral Equations, CRC Press, Boca Raton, Fla, USA, 1998.

10 E. L. Porteus, Foundations of Stochastic Inventory Theory, Stanford University Press, Stanford, Calif, USA, 2002.