Generating order policies by SDP: non-stationary demand and service level constraints

SDP in Inventory Control: Non-Stationary Demand and Service Level Constraints Karin G.J. Pauls-Worm1and Eligius M.T. Hendrix2 1Operations Research and Logistics, Wageningen University [email protected] 2Computer Architecture, Universidad de M´alaga [email protected] Abstract. Inventory control implies dynamic decision making. Therefore, dynamic programming seems an appropriate approach to look for order policies. For finite horizon planning, the implementation of service level constraints provides a big challenge. This paper illustrates with small instances the implementation of stochastic dynamic programming (SDP) to derive order policies in a straightforward way for systems with non-stationary demand and service level constraints. The small instances allow to perform a full enumeration of possible policies and show that the SDP derived policies are not necessarily optimal. Keywords: Stochastic Dynamic Programming ·inventory control ·nonstationary demand ·service level constraint 1 Introduction This study is motivated by practical cases of inventory management. In the practical case, a retailer or a producer faces non-stationary demand for a product and has to determine when and how much to order or to produce to meet a certain service level. The decision maker, hereafter manager, uses a periodic review, meaning that on fixed moments in time, e.g. every day or every week, the manager decides on the order quantity. Many products in retail face a nonstationary demand [10]. The decision on the order quantity is inherently a multistage problem, and therefore Stochastic Dynamic Programming (SDP) seems an appropriate approach to attempt to solve the problem [1]. An earlier application of SDP to a problem with non-stationary demand and a service level constraint [8] has shown that it does not necessarily generate an optimal solution for this case. This motivates a further study on this phenomenon. SDP has been used for perishable products with stationary demand by [13] to derive an optimal order-up-to policy. His work was extended by [7], who also used SDP. [11] studied a system for non-perishable products with combined variable deterministic and non-stationary stochastic demand using SDP to find an optimal policy. The above models typically use penalty costs when demand exceeds the stock level. In practice however, often a service level constraint is 2 Karin G.J. Pauls-Worm and Eligius M.T. Hendrix imposed. [4] show that in general it is not possible to transform a service level model into a cost model, above a certain “critical” service level. In this paper, we consider two types of service levels used in practice, the αservice level, also called cycle service level, and the β-service level, also called fill rate. [5] define cycle service level as the probability of not having a stock-out in a replenishment cycle. A replenishment cycle is the time between two orders. The fill rate indicates that a predefined percentage of the demand per replenishment cycle has to be fulfilled from stock. [4] define the difference between mean service level constraints and minimal service level constraints. Mean service level constraints measure the service level over the time horizon, whereas minimal service level constraints measure the service level in every period. [9] show for inventory systems with stationary demand the conditions for a one-to-one relation between cost and service models, where they consider a mean service level. [2] formulated a lost-sales inventory model with an average fill rate requirement as a constrained dynamic programming problem for stationary demand. They solved the problem with Lagrange relaxation by a value-iteration algorithm to find optimal replenishment policies. In this paper we focus on minimal service level constraints for the non-stationary demand case and we investigate whether SDP is a suitable method if a service level constraint applies. One stylized example is elaborated for different situations. It shows how in general SDP handles service level constraints and does not necessarily provide the optimal solution. Section 2 introduces a stylized example of variable demand. It has a finite time horizon of 6 periods representing the possibility of a manager in retail to order at most six times a week. This simple instance shows the application of Dynamic Programming (DP) to solve the deterministic variable discrete demand case. In Section 3 the example is extended to a stochastic uniform discrete demand case and solved with SDP to generate Qt(I) order policies, where the order quantity Qdepends on the inventory level Ion hand. Section 4 adds an α-service level constraint and Section 5 a fill rate constraint. The derived SDP solution for both cases is compared to an optimal policy fulfilling the service level constraints found by full enumeration. Section 6 illustrates the SDP approach for a continuous distribution of demand by a Gamma distribution. Section 7 concludes the paper. 2 Dynamic programming We consider a small inventory problem with a deterministic variable demand. The problem has a finite time horizon of T= 6 and demand is dt= 3,1,2,4,3,2. The set-up cost is k= 5 and holding cost h= 1. Holding cost is paid over the inventory that is carried over to the next period. The unit variable cost is c= 0 and the starting inventory is I0= 0. An order is placed and delivered at the beginning of the period, demand occurs during the period, and the inventory level is calculated at the end of the period. The question is when to order and Inventory control subject to service levels by SDP 3 how much. This problem can be formulated as follows: min TC = T X t=1 g(Qt) + hIt(1) where procurement cost is given by the function g(x) = k+cx, if x > 0,and g(0) = 0.(2) Subject to It=It−1+Qt−dt, t = 1, . . . , T (3) I0= 0 (4) It, Qt≥0, t = 1, . . . , T (5) The objective function (1) represents the total relevant costs, consisting of ordering and holding costs. In (2) the ordering costs are specified by a fixed set-up cost when an order is placed and variable procurement cost. Equations (3) are balance equations stating that the inventory level at the end of period tequals the inventory level at the end of the period before, increased with the order quantity minus the demand in period twhere (4) gives the initial inventory level. Equations (5) are non-negativity constraints. [12] derived properties of the optimal solution to this problem and developed an efficient algorithm to solve the problem. The algorithm they developed is a modification of Dynamic Programming. This paper applies DP in order to develop towards SDP with service level constraints. In the example, the first order Q1fulfils the accumulated total demand for a number of future periods from one to six, i.e. Q1= 3,4,6,10,13 or 15. After demand d1= 3 is realized, the possible inventory level is I1= 0,1,3,7,10 or 12. In period t= 2, demand d2= 1 will be fulfilled from the available inventory, or, in case I1= 0, there will be an order to fulfil demand of period 2 up to 6, or to fulfil demand of period 2 up to 5, 4 or 3 or just period 2. The same reasoning holds for periods 3 to 5, so either Qt= 0, or Qt=PN j=tdjfor some N, t ≤N≤T. The beginning of a period, when the decision about the order quantity has to be made, is called a stage in DP. A stage starts with the inventory level at the end of the previous period which is called the state. The set of possible values is called the state space. DP has the property that the optimal decision on time t (stage t) with state It−1, does not depend on the decisions made leading to state It−1. This means that the problem can be decomposed into sub-problems. The stages and states of this small instance are depicted in Fig. 1. A path from the start (stage 1) to the end of period 6 models the timing and quantity of ordering and the inventory levels at the end and beginning of each period (stage). Given the possibility to order for all future periods, we have T! = 720 possible paths for this inventory problem. DP generally starts with a backward procedure, followed by a forward procedure. The backward procedure assigns a valuation to each state, called a value function Vt(I) to each state in the system. Stage 4 Karin G.J. Pauls-Worm and Eligius M.T. Hendrix 6 ends with I6= 0 at the end of the time horizon. Vt(I) equals the costs that have to be made from stage tat state Ito the end of the final stage 6 with state I= 0. The so-called recursive Bellman equation for the value function Vt(I) can be written as Vt(I) = min Q{g(Q) + h·(I+Q−dt) + Vt+1(I+Q−dt)}for t=T, . . . , 1.(6) We illustrate the backward procedure for this small instance. Consider V6(2) = Stage 1 Stage 4Stage 3Stage 2 Inventory level 12 8 4 0 d= 3 d= 2d= 1 d= 4 I= 7 I= 0 I= 1 I= 3 I= 7 I= 10 I= 12 I= 0 I= 0 I= 2 I= 6 I= 9 I= 11 I= 0 d= 2d= 3 I= 9 I= 0 I= 2 I= 0 I= 5 I= 3 I= 0 I= 4 Stage 6Stage 5 Optimal path Fig. 1. All possible states of inventory levels and all possible paths 0. Holding cost is paid at the end of the previous period, so no cost has to be paid in this state; no order takes place. V6(0) = k+cQ6= 5 + 0 = 5. An order of Q6=d6= 2 is placed at a cost of k= 5. V5(5) = h·(5 + 0 −3) + V6(5 + 0 −3) = 2 + 0 = 2. No order takes place, but at the end of stage 5, there is an inventory level of 2 that incurs holding cost. V5(3) = minQ∈{0,2}h·(3 + Q−3) + V6(3 + Q−3) = min{(0 + 5),(7 + 0)}= 5. For I4= 3, the choice is not to order, or to order for demand of period 6. The minimum cost corresponds to not ordering. V5(0) = minQ∈{3,5}{k+h·(0+Q−3)+V6(0+Q−3)}= min{5+0+5,5+2+0}= 7. Here the minimum costs are obtained for Q5=d5+d6. Continuing this process provides finally the minimum total cost of V1(0) = 22. The path leading to the minimum cost can be determined in a forward procedure. The minimum cost at V1(0) is obtained via I1= 1, I2= 0, I3= 4, I4= 0, I5= 2 and I6= 0, so the optimal ordering path is Q1= 4, Q2= 0, Q3= 6, Q4= 0, Q5= 5 and Q6= 0 represented by the dashed red path in Fig. 1. 3 Stochastic Dynamic Programming We continue the example from Section 2, but now demand is stochastic and nonstationary, with expected demand µt= 3,1,2,4,3,2. Demand has a discrete Inventory control subject to service levels by SDP 5 Uniform distribution with dt∼U{0,2µt}. All demand has to be met. Notice that one can set this target as the support of the distribution is finite. Demand in period t= 1 can take the values d1j∈ {0,1,2,3,4,5,6}, where the index is j= 1, . . . , Ntwith Nt= 2µt+1. Every outcome dtj has probability of occurrence pt=1 Nt, so p1=1 7, p2=1 3, etc. The maximum possible inventory level equals Imax =PT t=1 2µt= 30. In this model, this number bounds the state space. In the optimal solution of the deterministic example, ordering only takes place when the inventory level equals zero, and the inventory level is always the sum of demand in upcoming periods. In this stochastic example demand is uncertain, so ordering might be necessary even if the inventory is not zero. That results in many more possible inventory paths. The value function for this problem is defined by Vt(I) = min Q∈Ft(I) g(Q) + pt h Nt X j=1 (I+Q−dtj  + +pt Nt X j=1 Vt+1(I+Q−dtj )+ , (7) where the feasible area of Qis given by Ft(I) = [0,(dtNt+. . . +dT NT−I)+] (8) and x+= max{x, 0}. Optimal order quantity as function of inventory level Iis Qt(I) = arg min Q∈Ft(I) g(Q) + h·pt Nt X j=1 (I+Q−dtj)++pt Nt X j=1 Vt+1(I+Q−dtj )+ . (9) The SDP approach has been implemented in matlab. Table 1 shows the geneTable 1. SDP order quantities given the inventory level It−1Q1Q2Q3Q4Q5Q6 0 624864 1 013753 2 002642 3 001531 4 000420 5 000310 6 000200 7 000100 8 000000 rated optimal order quantity Qt(I) for each stage and inventory level. One can observe that the optimal order quantities follow in fact from order-up-to levels, i.e. there are values St, such that Qt(I)=(St−I)+. As all demand has to be fulfilled, the order-up-to levels have the size St= 2µt. The expected total costs 6 Karin G.J. Pauls-Worm and Eligius M.T. Hendrix are V1(0) = 38.49. The introduction of uncertainty gives a 75% cost increase when compared to the corresponding deterministic variant of the problem. The objective function value of expected costs of the optimal order quantities Qt(I) follows from the generation of all possible demand paths as illustrated in Fig. 2. There are N1×N2×N3×N4×N5×N6= 33075 possible paths. The evaluation computes exactly the same expected total costs of E(T C) = 38.49 as the value of V1(0) in the SDP approach. Fig. 2. Possible inventory development given demand paths 4 SDP with an α-Service Level Constraint In Section 3, 100% of the demand has to be fulfilled. Now we add an α-service level constraint to the problem. We define the α-service level as a minimum probability αof not being out of stock at the end of a period, so P(It≥0) ≥α, t = 1, . . . , T. (10) This means that at the start of a period holds P(It−1+Qt−dt≥0) ≥α=⇒P(dt≤It−1+Qt)≥α, t = 1, . . . , T. (11) The total quantity It−1+Qtcan be seen as a basic order quantity, which we will call ˆ Qt. The cumulative distribution function of d∼U{a, b}is F(k) := P(d≤k) = bkc − a+ 1 b−a+ 1 Inventory control subject to service levels by SDP 7 for k∈ {a, a + 1, . . . , b −1, b}. For dt∼U{a, b}we have a= 0, b = 2µtand b−a+ 1 = Nt= 2µt+ 1. Elaboration of (11) for this case gives P(dt≤ˆ Qt) = bˆ Qtc+ 1 Nt ≥α, t = 1, . . . , T. (12) This results in ˆ Qt=bαNtc, t = 1, . . . , T. (13) The basic order quantity is a lower bound for the order quantity, or the starting inventory in a period, necessary to meet the α-service level requirement. Consider the case of Section 3 with k= 5 or k= 50, α= 0.8 and expected demand µt= 3,1,2,4,3,2. Recursion 7 is still valid, but the feasible area is now Ft(I)=[ˆ Qt,(ddtNt+. . . +dT NT−I)+].(14) Demand that is not met will be lost. An SDP approach has been implemented in matlab. The results of the SDP approach and the evaluated service levels are listed in Table 2. Table 2. SDP order policy and its reached service levels (required α= 0.8) k= 5; E(T C) = 37.95 k= 50; E(T C) = 129.01 ˆ Qt5 2 4 7 5 4 5 2 4 7 5 4 It−1Q1Q2Q3Q4Q5Q6It−1Q1Q2Q3Q4Q5Q6 0 5 2 4 7 5 4 0 18 16 16 15 10 4 1 0 1 3 6 4 3 1 0 15 15 14 9 3 2 0 0 2 5 3 2 2 0 0 14 13 8 2 3 0 0 1 4 2 1 3 0 0 13 12 7 1 4 0 0 0 3 1 0 4 0 0 0 11 6 0 5 0 0 0 2 0 0 5 0 0 0 10 0 0 6 0 0 0 1 0 0 6 0 0 0 9 0 0 7 0 0 0 0 0 0 7 0 0 0 0 0 0 8 0 0 0 0 0 0 : 0 0 0 0 0 0 9 0 0 0 0 0 0 18 0 0 0 0 0 0 service 0.86 1.00 1.00 0.89 0.89 1.00 1.00 1.00 1.00 0.999 0.989 1.00 Table 2 shows that in case of k= 5 one orders on average (almost) every period where Qtat inventory level It−1= 0 equals the basic order quantity ˆ Qt. Basic order quantity ˆ Qtand the order quantities Qtbehave as order-up-to levels. In case k= 50, one can observe in the different periods different reorder points. When the inventory level is at the reorder point or lower, one orders up to the level Qt(0), otherwise there is no order. E.g. in period 4, the reorder point equals 3. If I= 4 or more, this is enough to meet demand and service level in period 4. If I= 3 or less, there is an order to meet demand and service level in period 4 and the upcoming periods. In three of the six periods, the service levels 8 Karin G.J. Pauls-Worm and Eligius M.T. Hendrix are slightly higher than required. The difference is due to the discrete and small numbers of demand. In the other periods, as well as in all periods of the case of k= 50, the evaluated service levels are much higher. Inventorylevel Inventorylevel Periods Periods SDPalphaservicelevel Fig. 3. Inventory development for all demand paths of the SDP solution with α-service level constraint for k= 5 (left) and k= 50 (right). Inventory levels below zero represent lost sales. Fig. 3 shows inventory development for all possible demand paths. Also inventory levels below zero (lost sales) are depicted. These are virtual inventory levels to show out-of-stocks, but lost sales is assumed, so the inventory level never drops below zero. Notice that the different inventory levels have different chances of occurrence. From all possible starting inventory levels, no matter how small the chance of occurrence, SDP wants to meet the α-service level requirement. This results in an overall over-achievement of the service level. The SDP approach due to the definition of the feasible area tightens the α-service level constraint in (10) towards the conditional variant P(It≥0|It−1)≥α, t = 1, . . . , T. (15) The SDP policies taught us that an optimal policy may consist of order-up-to levels for every period t, i.e. there is an order-up-to value Stfor each period such that the policy chooses as order quantity Qt(I)=(St−I)+, t = 1, . . . , T. (16) Although such a policy does not necessarily lead to the lowest possible expected costs, we can look for the best values such that the α-service level constraint (10) is met. The optimal order-up-to level policy can then be compared to the SDP policy. The small instance allows us to perform a full enumeration to find the best feasible values for (S1, . . . , ST). The enumeration procedure uses bounds for the order-up-to levels St, being S1∈"ˆ Q1, T X t=1 2µt#and St∈ 0, T X j=t 2µj , t = 2, . . . , T. (17) Inventory control subject to service levels by SDP 9 Systematically Stis lowered and checked for feasibility of the service level conAlgorithm 1 Order-up-to(µ1, . . . , µT, α): Determines Stfor dt∼U{0,2µt} fulfilling (10) via (16) 1: Determine all possible demand path for d1,...,dT 2: Determine upper bounds on St 3: Evaluate all combinations S1,...,STwithin the bounds and keep the lowest cost solution straint. The minimum expected total costs order-up-to levels are determined in Algorithm 1. The number of possible combinations of the order-up-to levels within this range is large, about ΠT t=1 PT j=tNj. For the case this are around 107 combinations. To compare, SDP evaluates in each stage t= 1, . . . , T, for each value of Iless than PT j=tNjpossibilities for the value of Q. The generated order Table 3. Optimal order-up-to policy and its reached service levels (required α= 0.8) k= 5; E(T C) = 32.79 k= 50; E(T C) = 108.37 ˆ Qt5 2 4 7 5 4 5 2 4 7 5 4 It−1Q1Q2Q3Q4Q5Q6It−1Q1Q2Q3Q4Q5Q6 0 603843 01800 700 1 0 0 2 7 3 2 1 0 0 0 6 0 0 2 0 0 1 6 2 1 2 0 0 0 5 0 0 3 0 0 0 5 1 0 3 0 0 0 4 0 0 4 0 0 0 4 0 0 4 0 0 0 3 0 0 5 0 0 0 3 0 0 5 0 0 0 2 0 0 6 0 0 0 2 0 0 6 0 0 0 1 0 0 7 0 0 0 1 0 0 7 0 0 0 0 0 0 : 0 0 0 0 0 0 : 0 0 0 0 0 0 10 0 0 0 0 0 0 18 0 0 0 0 0 0 service 1.00 0.86 0.86 1.00 0.83 0.86 1.00 1.00 1.00 0.996 0.90 0.80 policy is listed in Table 3. The expected total costs E(TC) of the SDP policy are respectively 12.7% and 19.0% higher than those of the optimal order-up-to policy. Fig. 4 shows the inventory development for all possible demand paths. Compared to the SDP solution, more out-of-stocks are allowed represented by a negative inventory level. 5 Fill Rate Constraint Instead of an α-service level constraint we now consider a β-service level or fill rate constraint in the problem. The fill rate indicates that a predefined percent- 16 Karin G.J. Pauls-Worm and Eligius M.T. Hendrix To conclude: SDP generates order policies that meet a conditional service level constraint. Given a minimal expected service level requirement, the resulting policy is not necessarily optimal. Acknowledgments This work has been funded by grants from the Spanish Ministry (TIN2012-37483-C03-01) and Junta de Andaluc´ıa (P11-TIC-7176), in part financed by the European Regional Development Fund (ERDF). References 1. Bellman, R., Stanley, L.E.: Functional equations in dynamic programming. aequationes mathematicae 17(1), 1–18 (1978) 2. Bijvank, M., Vis, I.F.A.: Lost-sales inventory systems with a service level criterion. European Journal of Operational Research 220(3), 610 – 618 (2012) 3. Burgin, T.A.: The gamma distribution and inventory control. Operational Research Quarterly 26(3), 507 – 525 (2012) 4. Chen, F.Y., Krass, D.: Inventory models with minimal service level constraints. European Journal of Operational Research 134(1), 120 – 140 (2001) 5. Chopra, S., Meindl, P.: Supply Chain Management: Strategy, Planning, and Operation. Pearson, New Yersey (2010) 6. van Dijk, D., Hendrix, E.M.T., Haijema, R., Groeneveld, R.A., van Ierland, E.C.: On solving a bi-level stochastic dynamic programming model for analyzing fisheries policies: Fishermen behavior and optimal fish quota. Ecological Modelling 272, 68 – 75 (2014) 7. Fries, B.: Optimal ordering policy for a perishable commodity with a fixed lifetime. Operations Research 23(1), 46 – 61 (1975) 8. Hendrix, E., Haijema, R., Rossi, R., Pauls-Worm, K.G.J.: On solving a stochastic programming model for perishable inventory control. In: B. Murgante et al. (ed.), Proceedings of ICCSA 2012. Lecture Notes in Computer Science, vol. 7335, pp. 47–65. Springer, Heidelberg (2012) 9. van Houtum, G.J., Zijm, W.H.M.: On the relationship between cost and service models for general inventory systems. Statistica Neerlandica 54(2), 127–147 (2000) 10. Pauls-Worm, K.G.J., Hendrix, E.M.T., Haijema, R., van der Vorst, J.G.A.J.: An MILP approximation for ordering perishable products with non-stationary demand and service level constraints. International Journal of Production Economics 157, 133–146 (2014) 11. Sobel, M.J., Zhang, R.Q.: Inventory policies for systems with stochastic and deterministic demand. Operations Research 49(1), 157–162 (2001) 12. Wagner, H.M., Whitin, T.M.: Dynamic version of the economic lot size model. Management Science 5(1), 89–96 (1958) 13. van Zyl, G.: Inventory control for perishable commodities. Ph.D. thesis, University of North Carolina, Chapel Hill (1964)