Cost minimising order schedules for a capacitated inventory system

Abstract

In this paper, we study an inventory system with multiple retailers under periodic review and stochastic demand. The demand is modelled as a discrete random variable. Linear holding and backorder costs as well as fixed order costs are assumed. Orders to replenish inventories can be placed at a manufacturer with a limited capacity according to a cyclic order schedule. A fixed portion of the total available capacity in a period is allocated to each retailer, who follows a modified base-stock policy to determine the order quantities. Thus, the order policy consists of four policy parameters for each retailer: the length of the review period, the first order point within a planning horizon, the individual capacity limit, and the modified base-stock level. We present an algorithm to compute the exact optimal policy parameters and two heuristics. In a numerical study, we compare the results of these approaches and derive insights into the performance of the heuristics. In addition, we introduce three different schedule types and identify the situations, in which they perform best.

1 Introduction

In the modern global society, many products are manufactured in one part of the world and sold in several others. This can be seen in the electronic industry, e.g. many companies manufacture their goods in Asia but sell them globally. It can therefore be assumed that there are central retail inventories for big market areas like America, Europe or Australia which are characterised by different consumer behaviours and demand forecasts. The inventories have to be replenished and orders placed with the manufacturer. Since production capacity is limited, it is possible that not all orders can be satisfied or that machines are not fully utilised. To avoid these situations, contracts can be used for fixing the order times and maximum order quantities for each retailer.

In this paper, we study a single item, multi retailer system with one manufacturing facility with limited production capacity. At the manufacturing facility, a make-to-order policy is implemented and retailers place their orders to replenish their inventories and satisfy stochastic demand. We assume that holding and backorder costs are charged for each unit at each retailer as well as fixed order costs for each shipment. To operate the system, we assume the use of a cyclic schedule for the order points of the retailers at the production facility and a maximal order quantity, which is customized for each retailer. This assignment leads to a capacitated order system for each individual retailer, by using modified base-stock policies to determine the order quantities. Thus, the order policy for each retailer is determined by four parameters: length of the review interval, the first order point within a planning period, the allocated capacity, and the modified base-stock level.

In the sequel, we model the problem as a mixed integer problem and present an approach to compute cost optimal policy parameters. The main idea is similar to branch and bound procedures because we reduce the number of possible parameter combinations based on a lower bound for the average costs. However, this algorithm is only suitable for small systems, therefore we also present two heuristics based on a greedy approach for the capacity allocation, an approximation of the cost function, and a less restrictive elimination rule.

Based on the analysis and a numerical study performed in the last part of the paper, we are able to characterise optimal or near optimal order schedules to support decision makers. The presented approaches perform very well and the heuristics are able to reduce the computation time consumption by more than 75 %. Furthermore, we are able to describe certain properties of the assigned policy parameters and, in particular, identify different schedule types.

The remainder of the paper is organised as follows: In the next section, we present a literature review for adjacent network problems, before describing the problem in detail and formulating a mixed integer model in Sect. 3. In Sect. 4, an exact approach for computing all the policy parameters is presented and two heuristics are introduced in Sect. 5. We conclude with the results of a numerical study in Sect. 6 and a summary in Sect. 7.

2 Literature review

Our work is closely related to two different streams of literature based on inventory systems with stochastic demand under periodic review. We start our discussion with the research on systems with a single resource constraint and distinguish between the number of different products and the types of costs considered see Table 1.

For the simplest capacitated system consisting of a single stock point for a single product, Federgruen and Zipkin (1986) have shown the optimality of the modified base-stock policy under linear holding and backorder costs. This policy is a natural extension of the base-stock policy for an uncapacitated system (Scarf 1963) and differs only in the case of limited available capacity. If the inventory position is below the base-stock level, an order is placed to raise the inventory position up to the base-stock level or as close to it as possible.

Table 1 Optimal policy structures

Shaoxiang and Lambrecht (1996) have shown that in the case of an additional fixed order cost, the optimal policy for the capacitated single product single stock point inventory system is not the natural extension of the $(s,S)$ policy known to be optimal under infinite capacity (Scarf 1963). The optimal policy shows a systematic pattern, which is called the $X{-}Y$ band structure, where no order is placed if the inventory position is above the critical value $Y$ and an order with a maximum possible quantity is placed if the inventory position is below $X$. If the inventory level is between the critical values $X$ and $Y$, the optimal decision depends on the problem parameters. Further insights on the optimal decisions for this region are presented in Gallego and Scheller-Wolf (2000) or in Chan and Song (2003).

If an inventory system with multiple different products or several retailers selling the same products is considered, the optimal policy structure is very complex under a common shared resource constraint. Besides the order quantities, an allocation policy for the scarce capacity also has to be determined. For the finite planning horizon as well as for linear holding and backorder cost, Evans (1967) proved the optimality of a modified base-stock level type policy, while DeCroix and Arreola-Risa (1998) studied the same problem with an infinite planning horizon. In addition, they derived the optimal allocation policy in the case of homogeneous products.

To the best of our knowledge, the combination of both aspects, fixed ordering cost and multiple products sharing the same resource, has not been studied up to now. The optimal policy structure is unknown and can be expected to be very complex. Therefore, in this paper we consider a heuristic ordering policy where each retailer orders according to a modified base-stock policy with an individual capacity limit. In contrast to systems with a minimum order quantity (see also Zhao and Katehakis 2006; Zhou et al. 2009; Kiesmüller et al. 2011), the retailers do not have to order the complete amount guaranteed to be available to them.

In order to take into account the fixed ordering cost, we allow different review periods for each retailer. A detailed description of the ordering policy is given in the next section of the paper.

The second stream of research related to our work is about two-echelon inventory systems, where the replenishment quantities are limited by the inventory available at the central warehouse. Therefore, besides the order quantities, an allocation rule also has to be determined. The basic model in this area was presented by Eppen and Schrage (1981), in which the central warehouse is not allowed to keep stock, the holding and backorder costs charged are independent of the stock point, and the retailers are identical and face normally distributed demand. Under the balance assumption, it is shown that it is optimal to allocate quantities such that the non-stockout probabilities are equalised. Several model extensions are discussed, such as systems with a warehouse that is allowed to keep stock as in Diks and de Kok (1998). Federgruen and Zipkin (1984a, b) presented policies, including different holding and backorder costs at different stock points as well as additional demand distributions. A recent survey including many of these extensions can be found in Simichi-Levi and Zhao (2012). However, the focus is on policies for systems with stochastic service times at all stages and thereby stochastic lead times.

What most of these contributions have in common is that the fixed ordering costs are negligible and retailer orders can be placed every review period. If fixed ordering cost are charged, then continuous review $(R,Q)$ policies are usually assumed for the retailers. For an overview of the most relevant literature, see Axsäter (2003). In the recent literature, several extensions can be found, such as in Kiesmüller and de Kok (2005), who compute the relevant performance characteristics under a consolidation policy. However, the allocation decision does not have to be made under continuous review because the first-come, first-served rule is usually applied to ration the inventory at the central stock point. As alternatives to this rule, Axsäter (2007), Axsäter and Marklund (2008) and Howard and Marklund (2011) show the benefits of choosing different allocation rules at the central stock point. The first two works concentrate on the base system, whereas the latter extends this system with regular dispatch times for deliveries of the central stock point to the retailers. One major difference between the divergent inventory systems and the model studied in this paper concerns the limited replenishment quantity. While we assume a constant given capacity restriction, the available inventory at the central warehouse in a one-warehouse N-retailer system is influenced by the order policy of the warehouse and thereby is not exogenous. Furthermore, we explicitly forbid the commonly allowed transshipments between retailers, which is called allocation assumption or balanced inventory assumption as more often referred to today (see Eppen and Schrage (1981) for the first introduction of this topic and Dogru et al. (2009) for a critical review).

3 Problem description

We consider an inventory system for a single product where one manufacturer has to replenish the inventories of $M$ different retailers. The total available production capacity at the manufacturer in each period is limited due to exogenous circumstances like the number of machines or restricted transport or storage space. Without loss of generality, we assume that the production capacity of the manufacturer is normalised to one capacity unit per one production unit and that the sum of all the retailers’ expected period demand is smaller than the available production capacity in each period $CP$. Every incoming order at the production facility causes fixed administration and transportation costs of $K$ and is delivered after a lead time of $L$ periods after the order has been placed.

Each retailer $m \; (m=1,2,\ldots ,M)$ is facing stochastic customer demand, which is modelled as a sequence of discrete independently and identically distributed random variables with known distribution function. The demand of $r$ consecutive periods at retailer $m$ is denoted as $D_{m,r}$, with the corresponding cumulative distribution function $F_{m,r}$ and probability mass function $f_{m,r}$ for positive integer values of $r$. Without loss of generality, we assume a discrete distribution because each continuous distribution can easily be discretized to apply our approach. We number the retailers such that the first one ($m=1$) has an expected demand per period not smaller than the expected demand of any other retailer. Unsatisfied demand is backlogged until the retailer is supplied with new units. We note the number of backlogged units of retailer $m$ at the end of a period $t$ with $I^-_{m,t}$. Backlogging costs of $b_m$ per unit missing are charged for retailer $m$ at the end of period $t$ and for each unit on stock, recorded as $I^+_{m,t}$, the holding costs of $h$ per unit have to be paid. We assume that each retailer $m$ operates under a modified base-stock policy with an individual order interval $R_m$ and an individual capacity limit $CP_m$. A modified base-stock policy is chosen since it is known from Federgruen and Zipkin (1986) that such a policy is optimal with respect to average holding and backorder cost for a simple supply chain with only one retailer. Furthermore, the modified base-stock level type policy is also optimal for multiple retailers (see DeCroix and Arreola-Risa 1998). However, the optimal allocation policy, if the capacity is insufficient to reach all base-stock levels, is very complex and therefore we have to rely on a heuristic. Similar to Glassermann (1996), in this case we assume a constant allocation policy where a fraction of the total capacity is permanently dedicated to a retailer. This means that the manufacturer allocates an order time and a fixed amount of capacity to each retailer, such that a specific order quantity is always guaranteed.

Thus, the quantity to be ordered by retailer $m$ at the beginning of period $t$ is the minimum of the individual capacity limit $CP_m$ and the difference between the modified base-stock level $S_m$ and the actual inventory position $YP_{m}$ (defined as stock on hand minus backorders plus outstanding orders) before ordering, which is expressed as:

$$\begin{aligned} Q_{m,t} = \min \{S_{m}-YP_{m},CP_m\} \end{aligned}$$

(1)

Since each order induces a fixed cost, the retailers may not order in each period. Furthermore, due to the global capacity limit, it is also important that not all retailers order at the same time. Thus, besides the order frequency $R_m$, the first point in time within a given planning horizon where retailer $m$ is allowed to place an order ($fO_m$) also has to be determined carefully. Since such a combination $(fO_m, R_m)$ defines the point of all orders for retailer $m$, we denote one or more of these tuples as cyclic schedules. A cyclic schedule is complete if the variables $(fO_m, R_m)$ for all $M$ retailers of a system are given, otherwise we speak of a partial cyclic schedule. A cyclic schedule can be denoted by a matrix $X=\left( x_{m,t}\right)$, with $x_{m,t}$ having the value one if retailer $m$ is allowed to order in period $t$ and the value zero otherwise. The dimension of the matrix depends on the number of retailers and the number of periods considered. Since the length of the order intervals are whole numbers, there exists a smallest cycle length $T$, such that in each period $t$ the same combination of retailers is allowed to order as in period $t+T$. Therefore, we focus on cyclic schedules of this length $T$, where we start the schedule over every $T$ periods. Thus, the ordering policy for a retailer $m$ is defined by the four policy parameters described: the order interval $R_m$, the point of first order $fO_m$, the individual capacity limit $CP_m$ and the modified base-stock level $S_m$.

We are interested in obtaining the optimal numerical values for the ordering policies $(R_m, fO_m, CP_m, S_m)$ of all retailers $(m=1,2,\ldots ,M)$, minimising the resulting total average order, holding and backorder costs for the whole system. The average holding and backorder costs per period for retailer $m$ are denoted as $C_m(CP_m, R_m, S_m)$ and can be computed as:

$$\begin{aligned} C_m(CP_m,R_m,S_m)&= \frac{1}{R_m} \sum \limits ^{R_m}_{r=1} \Big ( h\cdot E[(IP_m-D_{m,L+r})^+]\nonumber \\&\quad +\,b\cdot E[(D_{m,L+r}-IP_m)^+] \Big ) \end{aligned}$$

(2)

where $IP_m$ denotes the inventory position of retailer $m$ after placing an order. For the computation of the expectations, the distribution of the inventory position is needed. Instead of $IP_m$, we modelled the undershoot $U_{m}$ as the Markov chain. $U_{m}$ is defined as the difference between $IP_m$ and $S_m$ after ordering. Computing its steady state probabilities $\pi _u$, the following expression can be derived for the average holding and backorder costs:

$$\begin{aligned} C_m(CP_m,R_m,S_m)&= \frac{1}{R_m}\sum \limits ^{R_m}_{r=1} \sum \limits _{u=0}^{\infty } \pi _u \Big \{h \cdot \sum \limits ^{S_m-u}_{i=0} (S_m-u-i)f_{m,L+r}(i) \nonumber \\&\quad +\,\,b \cdot \sum \limits ^{\infty }_{i=S_m-u} (i-(S_m-u))f_{m,L+r}(i)\Big \} \end{aligned}$$

(3)

A detailed derivation can be found in Appendix I. It is easy to see that the cost function $C_{m}$ has the following properties:

P1:

For fixed $CP_m, R_m$, the cost function $C_{m}$ is convex in $S_m$

P2:

For fixed $R_m$ and increasing $CP_m$, the cost function $C_{m}$ is non-increasing

Besides the holding and backorder costs, ordering costs are also considered. Adding both types of costs leads to the objective function (4.1) of the following mixed integer program:

$$\begin{aligned}&\text{ min } \quad \frac{1}{T} \sum \limits ^{T}_{t=1}\sum \limits ^M_{m=1} x_{m,t}\cdot K + \sum \limits ^M_{m=1} C_m(CP_m,R_m,S_m) \end{aligned}$$

(4.1)

$$\begin{aligned}&\text{ S.t. } \quad x_{m,fO_m+k\cdot R_m} = 1 \quad \forall m\in \{1 \ldots M\}, \forall k \in \mathbb {N}_0\end{aligned}$$

(4.2)

$$\begin{aligned}&\qquad \sum \limits ^M_{m=1} x_{m,t} \cdot CP_m \le CP \quad \forall t \in \{1 \ldots T\}\end{aligned}$$

(4.3)

$$\begin{aligned}&\qquad \frac{1}{T}\sum \limits ^{T}_{t=1} x_{m,t} \cdot CP_m > E[D_{m,1}] \quad \forall m \in \{1 \ldots M\}\end{aligned}$$

(4.4)

$$\begin{aligned}&\qquad T = {\mathrm{{Lcm}}}(R_1, R_2, \ldots , R_M)\end{aligned}$$

(4.5)

$$\begin{aligned}&\qquad fO_m \le R_m \quad \forall m \in \{1 \ldots M\} \end{aligned}$$

(4.6)

$$\begin{aligned}&\qquad R_m \; , \; CP_m\; , \; fO_m \; , \; T \in \mathbb {N} \quad \forall m \in \{1 \ldots M\}\end{aligned}$$

(4.7)

$$\begin{aligned}&\qquad S_m \in \mathbb {Z} \quad \forall m \in \{1 \ldots M\} \end{aligned}$$

(4.8)

$$\begin{aligned}&\qquad x_{m,t} \in \{0,1\}\quad \forall m\in \{1 \ldots M\}, \forall t \in \{1 \ldots T\} \end{aligned}$$

(4.9)

Note that the costs depend on $fO_m$ via the capacity allocation $CP_m$ only. The constraint (4.2) assures the coherency between the decision variables $R_m , \; fO_m$ and the variables $x_{m,t}$. With constraint (4.3), we model that the global capacity limit $CP$ is not exceeded in any period; and with constraint (4.4) that enough capacity is allocated to each retailer to satisfy his demand in the long run. Constraint (4.5) specifies the length of the periodic schedule, with $Lcm$ standing for the least common multiplier. Constraints (4.6)–(4.9) define the domain of definition for the decision variables. We are interested in the optimal ordering policies $(R_m, fO_m, CP_m, S_m)$ for all retailers $m \; (m=1,2,\ldots ,M)$. In particular, we would like to learn more about the optimal scheduling of order moments.

4 Optimal order schedules

Our approach to computing the optimal policy parameters is divided into several parts as shown in Fig. 1. In the first part, presented in Sect. 4.1, we determine feasible combinations $(R_m, fO_m)$ for all retailers $(m=1,\ldots ,M)$. The second part is further divided into two steps. As in branch and bound algorithms, we eliminate schedules that do not have good cost performance in comparison with a lower bound for the average cost, as derived in Sect. 4.2. The capacity allocation as described in Sect. 4.3 is only conducted for the remaining schedules.

Fig. 1

Optimisation procedure

4.1 Feasibility of schedules

At first, the domain of the reorder intervals for each retailer $(m=1,2,\ldots ,M)$ is bounded because the individual capacity limit $CP_m$ per period may not exceed the global capacity limit $CP$. Furthermore, on average it must be possible to order the demand of $R_m$ periods. This leads to the following constraint for $R_m$:

$$\begin{aligned} R_m \in \left\{ 1, \ldots , \left\lfloor \frac{CP}{E[D_{m,1}]}\right\rfloor \right\} \end{aligned}$$

(5)

The floor function $\lfloor (\ldots ) \rfloor$ returns the largest integer number that is smaller than or equal to the term $(\ldots )$.

The point of the first order $fO_m$ of retailer $m$ needs to be earlier than $R_m$, which results in the domain:

$$\begin{aligned} fO_m \in \{1, \ldots , R_m \} \end{aligned}$$

(6)

We use a complete enumeration of all the combinations of reorder intervals and points of first order, which satisfy (5) and (6) to construct the partial schedules $(R_1,fO_1, R_2, fO_2, \ldots , R_{lm},fO_{lm})$, $(lm = 1,2,\ldots ,M)$. Since the following inequality (7), which results from restriction (4.3), has to hold for each partial schedule, the number of feasible schedules can be further reduced.

$$\begin{aligned} \sum ^{lm}_{m=1} (x_{m,t}\cdot R_m \cdot E[D_{m,1}]+1)\le CP \;\; \forall \; t \in \{1 \ldots T\} \end{aligned}$$

(7)

We eliminate all schedules where inequality (7) does not hold in at least one period for the corresponding partial schedule. The resulting schedules guarantee sufficient capacity, however cost arguments have not been considered up to now.

4.2 Lower bound for the average costs

In the next step, further solution candidates are eliminated based on cost aspects. For a given schedule $(R_1,fO_1,R_2, \ldots ,R_M,fO_M)$, we compute a lower bound for the average costs $Lb(R_1,fO_1,R_2,\ldots ,R_M,fO_M)$ and compare it with the minimum cost corresponding to the best policy $(R^\star _m,fO^\star _m,CP^\star _m,S^\star _m)$ obtained up to this step. Thus, we avoid solving the capacity allocation problem for non-optimal schedules and proceed only for those cyclic schedules satisfying the following condition:

$$\begin{aligned} Lb(R_1,fO_1,R_2,\ldots ,R_M,fO_M) <\sum ^M_{m=1}\frac{K}{R_m^\star }+ \sum ^M_{m=1}C_m(CP^\star _m,R^\star _m,S^\star _m) \end{aligned}$$

(8)

It is obvious that the unconstrained base-stock levels equivalent to setting $CP_m$ to infinity result in a lower bound for the average holding and backorder cost. However, since this bound may be not very tight, we compute the average cost under another upper bound for the capacity limit $\widehat{CP}_m$. We determine the maximum available capacity for retailer $m$ as follows: If retailer $m$ has no joint order moment with another retailer during $T$ periods, then the whole capacity $CP$ can be allocated to him. Otherwise, the available capacity has to be reduced by the minimum amount needed by the other retailers, given as the expected demand during the replenishment cycle plus one more unit to guarantee system stability. Due to the static allocation rule, all joint ordering moments have to be considered. Thus, the maximum available capacity to be allocated to retailer $m$ is determined as follows:

$$\begin{aligned} \widehat{CP}_m := \min _{\{t|t=1,\ldots ,T,x_{m,t}=1\}} \left\{ CP - \sum _{\tilde{m} \ne m} x_{\tilde{m},t} \cdot \Big (E[D_{\tilde{m},1}]R_{\tilde{m}} +1 \Big ) \right\} \end{aligned}$$

(9)

Since a smaller available capacity leads to larger holding and backorder costs (P2), we obtain the following lower bound for the average cost:

$$\begin{aligned} Lb(R_1,fO_1,R_2,\ldots ,R_M,fO_M) = \sum ^M_{m=1}\frac{K}{R_m}+ \sum ^M_{m=1}C_m(\widehat{CP}_m,R_m,S_m(\widehat{CP}_m)) \end{aligned}$$

(10)

4.3 Exact capacity allocation

As mentioned above, for all schedules $(R_1,fO_1,R_2,\ldots ,R_M,fO_M)$ satisfying (8), the optimal capacity allocation and the corresponding modified order-up-to levels are determined, and the average costs are computed by solving the following mixed integer problem:

$$\begin{aligned}&\min \limits _{CP_m,S_m} \quad \sum \limits _{m=1}^{M} C_m(CP_m,R_m,S_m) \end{aligned}$$

(11.1)

$$\begin{aligned}&\text{ s.t. } \quad \qquad \sum \limits _{m=1}^{M} x_{m,t} \cdot CP_m \le CP \quad \forall t \in \{1 \ldots T\} \end{aligned}$$

(11.2)

$$\begin{aligned}&\quad \qquad \qquad CP_m \ge E[D_{m,1}] \cdot R_m +1 \quad \forall m \in \{1 \ldots M\} \end{aligned}$$

(11.3)

$$\begin{aligned}&\quad \qquad \qquad CP_m \le \widehat{CP}_{m}\quad \forall m \in \{1 \ldots M\} \end{aligned}$$

(11.4)

$$\begin{aligned}&\quad \qquad \qquad S_m \in \mathbb {Z} \quad \forall m \in \{1 \ldots M\} \end{aligned}$$

(11.5)

This problem formulation is easier to solve than the original MIP (4) because the number of decision variables is reduced. However, a solution has to be determined for all feasible schedules satisfying (8). For the numerical results in Sect. 6, we used complete enumeration approach for $CP_m$ and computed the corresponding modified base-stock levels according to (3) to solve the problem.

5 Near optimal order schedules

For large problem instances, the exact approach as presented in Sect. 4 results in very long computation times. Therefore, we present different possibilities in this section to speed up the computation, which results in near optimal solutions.

5.1 Coordinated schedules

In the first part of the algorithm (Sect. 4.1), we introduced the domain of definition for the review periods and the first point of order to eliminate infeasible schedules. The remaining number of schedules is still quite large, therefore we suggest an additional restriction. We propose using coordinated schedules and allowing only review periods which are a multiple integer of the review interval of the first retailer with the largest average demand as follows:

$$\begin{aligned} R_m \in \Big \{R_1 \cdot k | k \in \mathbb {N}, R_1 \cdot k \le \frac{CP}{E[D_{m,1}]} \Big \} \quad m =2,3 \ldots ,M \end{aligned}$$

(12)

Given that in a cyclic schedule the first periods can be placed at the end of the schedule without a cost change, we also reduce the possible points of first order to:

$$\begin{aligned} fO_m \in \{1,\ldots ,\min \{R_m , R_1 \cdot (m-1)\} \} \quad m = 1,2, \ldots ,M \end{aligned}$$

(13)

5.2 Comparison of lower bounds

In Sect. 4.2, we derived a lower bound for the average cost of a schedule for selecting the promising solution candidates. We assume a close relation between the lower bound and the actual cost and suggest eliminating schedules based on the following rule:

$$\begin{aligned} Lb(R_1,fO_1,R_2,\ldots ,R_M,fO_M) < Lb(R_1^\star ,fO_1^\star ,R_2^\star , \ldots , R_M^\star ,fO_M^\star ) \end{aligned}$$

(14)

The capacity allocation is only conducted for schedules whose lower bound is smaller than the lower bound of the optimal schedule determined up to this step. This rule restricts the solution domain; however we cannot guarantee that the optimal solution still remains in the set of possible schedules. Furthermore, the resulting schedule depends on the order, the schedules are evaluated in. Here we have chosen the following approach: Since large reorder intervals result in smaller order costs, we started with the schedules with the longest order interval for each retailer. In the process, we reduced the length of the intervals one at a time, starting with the last retailer, followed by the second to last and so on, until all combinations are evaluated. The same procedure was used on the first order points within a group of schedules involving the same combination of order intervals.

5.3 Capacity allocation with a greedy approach

Greedy approaches have already been proven to work very well in many situations. Therefore, we propose allocating the capacity with an iterative algorithm based on a reduction of the average holding and backorder cost, which is defined as follows:

$$\begin{aligned} \varDelta _m(CP_m):=\Big ( \begin{array}{l} C_m(CP_m,R_m,S_m(CP_m)) \\ - C_m(CP_m+1,R_m,S_m(CP_m+1)) \end{array} \Big )\quad m = 1,2, \ldots ,M \end{aligned}$$

(15)

We start the algorithm with the allocation of the minimum amount of capacity necessary to guarantee a stable system ($CP_m = R_m E[D_m]+1$). Then, further capacity is allocated to the retailer $\tilde{m}$ with the largest cost improvement according to (15). Note that an additional capacity unit is allocated to retailer $\tilde{m}$ at each order point, such that the remaining available capacity is reduced by $T/R_{\tilde{m}}$ units. During the algorithm, we keep track of the current capacity still available for allocation, and only allow an allocation to a retailer if restriction (2.3) is not violated.

Furthermore, in order to avoid unnecessary computational effort, we monitor whether the algorithm can find a capacity allocation, which results in a schedule that is even better than the one obtained up to now. Under the assumption that the marginal cost reduction (15) is decreasing, we estimate the maximum possible cost reduction by the product of the maximum possible cost reduction in one greedy step $\varDelta _{\tilde{m}}(CP_{\tilde{m}})$ multiplied by the maximum number of such steps remaining. To estimate the maximum remaining number of steps until the greedy algorithm stops, we divide the free capacity by the minimum units of capacity allocated in each step. We obtain the following expression for the maximum possible cost reduction:

$$\begin{aligned} \varDelta _{\tilde{m}} \cdot \frac{\sum ^T_{t=1}( CP- \sum ^M_{m=1} x_{m,t} \cdot CP_m)}{T / \max _{m \in \mathsf M }R_m} \end{aligned}$$

(16)

5.4 Approximation for the average cost

During the optimisation, many schedules are evaluated with (3). Thus, the density for the inventory position has to be determined using a Markov chain model and the convolutions of distributions have to be computed quite often. Therefore, we propose an approximation of the cost function based on a simplification of the undershoot $(\tilde{U}_m = (D_{m,R_m} - CP_m)^+)$ and a replacement of the exact convolution with a fitted distribution. For $r=1,2,\ldots ,R_m$, we fit the same type of distribution used for the demand distribution on the moments

$$\begin{aligned} E[D_{m,L+r}+\tilde{U}_{m}]&= E[D_{m,L+r}] + E[\tilde{U}_{m}]\nonumber \\ Var[D_{m,L+r}+\tilde{U}_{m}]&= Var[D_{m,L+r}]+Var[\tilde{U}_{m}] \end{aligned}$$

(17)

and propose the following approximation for the average holding and backorder cost:

$$\begin{aligned} \widetilde{C_m}(CP_m,R_m,S_m)&= \frac{1}{R_m} \sum \limits ^{R_m}_{r=1} \Big (h\sum \limits ^{S_m}_{x=0}(S_m-x) f_{fit,r}(x) \nonumber \\&+\,\, b\sum \limits ^{\infty }_{x=S_m}(x-S_m)f_{fit,r}(x)\Big ) \end{aligned}$$

(18)

We refer to Kleintje-Ell and Kiesmüller (2013) for more details about this approximation.

6 Comparison of the approaches

In this section, we present the results of our numerical study. For a system with three retailers, we computed the optimal policy parameters for several instances with the algorithm presented in Sect. 4. We also consider two heuristics and compute order schedules for systems with four or five retailers. For the first method, denoted as $(HeurSNI)$, only coordinated schedules are considered (see Sect. 5.1), the cost function is approximated as described in Sect. 5.4, and the capacity allocation is determined using the greedy approach (see Sect. 5.3). This method is further extended by the strict elimination rule as presented in Sect. 5.2, which yields the second heuristic called $(HeurSNIe)$. Thus, three different approaches are studied, which are denoted as $APP = \{ Exact, \; HeurSNI, \; HeurSNIe\}$

We are interested in the performance of the heuristic approaches. Furthermore, we want to get insights in the structure of the optimal order schedules.

6.1 Performance indicators and numerical design

To measure the performance of the approaches, the total average cost $C_{ap}$ $(ap \in APP)$ of the obtained policies and the relative cost deviation is computed as follows:

$$\begin{aligned} \varDelta _{ap1, ap2} = \Big (\frac{C_{ap1}}{C_{ap2}}-1\Big )\cdot 100\,\% \quad ap1,ap2 \in APP, \end{aligned}$$

(19)

In addition, relative computation time deviation is measured according to

$$\begin{aligned} \delta _{ap1, ap2} = \left( \frac{tC_{ap1}}{tC_{ap2}}\right) \cdot 100\,\% \quad \quad ap1,ap2 \in APP. \end{aligned}$$

(20)

where $tC_{ap}$ denotes the computation time for approach $ap$. All the computations were performed on an Inter(R) Core(TM) I7 with a 3.40 GHz CPU and 16 GB RAM with MATLAB Version (R2012b). As an aggregate performance measure, we compute the average of the relative deviations over a set of instances. We refer to these measures as $\overline{\varDelta }_{ap1, ap2}$ and $\overline{\delta }_{ap1, ap2}$.

For the numerical study, the following input was chosen: Period demand $D_{m,1}$ is assumed to be distributed according to a discretized gamma distribution, similar to the one in Kiesmüller et al. (2011). This means that the probability distribution function of the demand is defined as $P(D= i):=F_{\gamma }(i+0.5)-F_{\gamma }(i-0.5)$, where $F_{\gamma }$ denotes the cumulative distribution function of the continuous gamma distribution. For the computations, the demand distribution has to be truncated such that $P(D \ge D_{max})$ is negligible. The average demand for the first retailer is set to 25 $(E[D_{1,1}] = 25)$ and the average demand of all other retailers is not larger. However, all other retailers $(m > 1)$ are assumed to be identical. The only difference between them and the first retailer is the expected demand. The chosen values correspond to shares of the first retailer of between 33 % and more than 80 % of the total demand. The coefficient of variation of the demand ($cv_m = \frac{\sqrt{Var[D_{m,1}]}}{E[D_{m,1}]}$) is varied between $0.3$ and $0.7$.

The capacity limit $CP$ can be expressed as $CP = mCP \sum _{m=1}^M E[D_{m,1}]$ and we vary the factor $mCP$ in steps of 20 % between 130 and 170 %. Lower capacity restrictions lead to very high inventory levels and larger capacity restrictions are similar to an uncapacitated system.

For the fixed order costs $K$, five different levels between 0 and 100 are considered. We have included the case of no ordering costs in order to gain insights into the trade-off between holding cost and capacity pooling. The holding cost $h$ is fixed to a value of $0.1$ and the backorder costs $b_m$ correspond to critical ratios $\frac{b_m}{h+b_m}$ of 90 and 95 %. The lead time is equal for all retailers and set to $L=2$.

A summary of all the possible input values is given in Table 2. We use a full factorial design and investigate 450 instances for three different systems with $M=3,4,5$.

Table 2 Numerical values of the input parameters

6.2 Performance of the heuristics

In Table 3, we summarise the results for the system with three retailers.

Table 3 Mean relative cost deviation

It can be seen that, on average, the first heuristic $(HeurSNI)$ performs extremely well. The average cost deviation is only 0.25 % and in 79.33 % of the instances $HeurSNI$ also yields the optimal policy parameters. Near optimal schedules are mainly obtained in situations where the average demand at the retailers differs significantly. While the second heuristic ($HeurSNIe$) is able to find optimal schedules in 76.23 % of the instances and also performs well for identical retailers, on average the results for different retailers are slightly worse with an aggregate deviation of 2.06 %. It can be generally observed that the second heuristic has problems finding optimal and near optimal schedules if there are significant differences between retailers with respect to the average demand size. Furthermore, the relative cost deviation decreases as the fixed cost increases (excluding the case $K=0$), thereby increasing available capacity and decreasing demand variability. In all instances computed with the exact approach, the reorder intervals of the retailers $m=2,3$ are an integer multiple of $R_1^*$. This means that only allowing coordinated schedules, as described in 5.1, does not influence the cost performance of the heuristics. Due to the excellent performance of $HeurSNI$, we can also conclude that the approximation of the cost function as well as the greedy approach work well. Eliminating schedules based on rule (14) induces the non-consideration of optimal and near optimal schedules in situations with low fixed cost, high demand variability, little available capacity or different demand volumes at the retailers. Although $HeurSNI$ has a better cost performance than $HeurSNIe$, its one disadvantage is the computation time. The average computation time for $HeurSNI$ is 24.26 % of the exact approach while $HeurSNIe$ is a bit faster with a 22.35 % computation time of the exact approach. Therefore, $HeurSNIe$ may be preferable, especially for the parameter ranges where it leads to very good results. In order to gain more insights into the cost performance of both approaches for larger systems ($M=4$ and $M=5$), we also computed the order policies for them and compared the resulting costs. For this set, the average computation time of $HeurSNIe$ is 93.29 % of the average computation time for $HeurSNI$, which is further reduced to 78.61 % for 4 retailers and 62.62 % for 5 retailers. The outcome with regard to the average costs is presented in Table 4.

Table 4 Comparison of the heuristics

For identical retailers, both approaches lead to the same order schedules in many instances, regardless of the number of retailers. For non-identical retailers, it is difficult to draw conclusions about the impact that retailers have on the performance of the heuristics. We are only able to observe that for all systems, the difference in average demand of the retailers has the largest impact on cost performance. Furthermore, if the retailers are similar with respect to their demand, then both heuristics have nearly the same cost performance.

6.3 Properties of optimal and near optimal order schedules

In order to gain insights into the structure of optimal order schedules, we created the following classifications:

Single Order Point Schedules (SOPS):

The cycle length of a single order point schedule is equal to the number of retailers $T=M$. Furthermore, in every period exactly one retailer orders and each retailer orders exactly once per cycle, which means that all retailers have the same review interval.

No Simultaneous Orders Schedules (NSOS) :

The cycle length of such a schedule is larger than the number of retailers $T>M$. In addition, in every period a maximum of one retailer orders. It is therefore possible that no retailer orders in a given period, or that a retailer orders more than once per cycle length $T$.

Complex Schedules (CS):

Complex schedules are obtained if more than one retailer place orders in at least one period . In that case, the global capacity needs to be allocated between two or more retailers in such periods.

We determined the schedule portions in each class for our data set and present the results in Table 5.

Table 5 Classification of schedules

First, we can conclude that the heuristics have no significant impact on the partitioning of schedules according to our classification.

Second, the size of the system and number of retailers also do not have a significant impact on the partitioning of schedules. This seems to be reasonable since the relation between demand and capacity is not changed and another schedule length $T$ also determines the classification of the schedule.

Third, the (near) optimal schedule type is mainly dependent on the average demand of the retailers. In the case of identical retailers, no allocation of capacity is needed in most of the instances and order schedules where only one retailer is allowed to order in each period (SOPS and NSOS) are preferred. Complex schedules are needed if the fixed costs require small review periods or if the capacity limit restricts the order intervals to $(R_i < M)$.

The influence of the capacity restriction on the schedule type is presented in Table 6 for the results obtained with $HeurSNI$.

Table 6 Impact of the capacity restriction on the schedule type

A capacity extension in the case of non-identical retailers leads to more simple schedules, especially for small systems with only a few number of retailers. In contrast, more capacity in the case of identical retailers does not always reduce the number of complex schedules. This can be observed for the parameter set $M=3,\;ED_{m>1}=25,\; c_v = 0.3,\; K=5,\; b_m = 1.9$, by increasing the global capacity limit from $CP =113 \Leftrightarrow mCP =1.5$ to $CP =128 \Leftrightarrow mCP =1.7$. The optimal schedules are presented in Fig. 2.

Fig. 2

Example of changing from SOPS to CS with increasing $CP$

Such behaviour can only be found in settings with small fixed order costs in relation to the holding and backorder costs.

6.4 Influence of the number of retailers on costs

A comparison of the results for three retailers ($HeurSNI3$), 4 ($HeurSNI4$) and 5 retailers ($HeurSNI5$) is presented in Table 7.

Table 7 Mean relative cost difference $\varDelta _{approach}$

It is not surprising that the mean costs per instance increase as the number of retailers increases, because each retailers needs to order and has holding and backorder costs. The average increase in costs with $\overline{\varDelta }_{HeurSNI4,HeurSNI3}= 14.09\,\%$ and $\overline{\varDelta }_{HeurSNIe5,HeurSNIe3} = 27.71\,\%$ is much smaller than expected. The number of retailers and corresponding number of orders per period expected increases by one-third or two-thirds for the NSOS and CS, which is much more than the mean increase in costs. Especially in the instances where the expected demand of retailers $m>1$ is very small $E[D_{m>1}]= 5/3$, it can even be observed that there is a decrease in costs in $23/24$ of the instances.

Along with the stronger cost increase with increasing capacity, this observations supports the assumption that the interdependence between the order interval of the first retailer and the absolute value of the global capacity limit is much more important than the relative utilisation of the global capacity. The increase in the number of retailers and concomitant increase in global $CP$ may result in better schedules, however, the relative utilisation would remain on a similar level.

7 Summary

In this paper, we studied an inventory system where a capacitated manufacturer has to replenish the inventories of different retailers facing stochastic demand. To do this, we took the holding, backorder and fixed costs at the retailers into account, and presented an exact algorithm as well as two heuristics to obtain (near) optimal order schedules.

As the parameter computation for the proposed policy is very time consuming, even for small examples, we accelerated the exact process and compared the obtained heuristics in a numerical study with the results of the exact computation. The study shows that, compared to the exact procedure, one of our approaches saves more than 75 % in computation time with acceptable results.

In our numerical study, we could show that the length of the order intervals in the schedule should be coordinated; in particular, we demonstrated that all order intervals are multiples of the smallest interval. Furthermore, we identified three different types of order schedules, and based on our problem instances we were able to conclude that, if possible, order points should be chosen such that only one retailer is allowed to order in each period.

Appendices

Appendix I: Derivation of the cost functions

1.1 The exact cost function

In order to be able to compute the average stock on hand or backorders, we need information about the distribution of the inventory position, which can be obtained using a Markov chain approach. The state space of the Markov chain is given by the undershoot $U_t$, which is defined as the difference between the modified base-stock level $S_m$ and the inventory position $IP_m$ at the beginning of a period $t$ after an order has been placed. The dynamic of the system is described by the following recursive equation for the undershoot:

$$\begin{aligned} U_{t} = \left\{ \begin{array}{ll} 0 &{} \quad U_{t-R_m} +D_{m,R_m} \le CP_m\\ U_{t-R_m} +D_{m,R_m} - CP_m &{}\quad U_{t-R_m} +D_{m,R_m} > CP_m\\ \end{array} \right. \end{aligned}$$

(21)

The equilibrium distribution $\pi$ defined as

$$\begin{aligned} \lim _{t \rightarrow \infty } P(U_{t}=u) =: \pi _u \; \forall \; u \in \mathbb {N}_0 \end{aligned}$$

(22)

can be computed by solving the system of equations

$$\begin{aligned} \begin{array}{l} \pi _u = \sum \nolimits _{\check{u} = 0,1,2, \ldots } \pi _{\check{u}} \cdot p_{\check{u},u} \; \forall \; u \in \mathbb {N}_0\\ \sum \nolimits _{u=0,1, \ldots } \pi _u = 1\\ \end{array} \end{aligned}$$

(23)

where $P$ denotes the transition matrix given as

$$\begin{aligned} \begin{array}{l} P = (p_{i,j}) \text{ with } p_{i,j} = P(U_{t} = j| U_{t-R_m} = i)\\ \end{array} \end{aligned}$$

(24)

With Eq. (2), this results in the following expression for the average holding and backorder cost:

$$\begin{aligned} C_m(CP_m,R_m,S_m)&= \frac{1}{R_m} \sum _{u=0,1, \ldots } \pi _u \sum ^{R_m}_{r=1} \Big (h \cdot \sum ^{S_m-u}_{i=0} (S_m-u-i)f_{m,L+r}(i) \nonumber \\&\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad +\,\,b \cdot \sum ^{\infty }_{i=S_m-u} (i-(S_m-u))f_{m,L+r}(i)\Big )\qquad \end{aligned}$$

(25)

For the given values of $CP_m, R_m$, the cost function depends on the modified base-stock level $S_m$ only. The optimal modified base-stock level $S^*_m$ then has to satisfy the following Newsboy like condition:

$$\begin{aligned} S^*_m = \arg \min _{S_m} \left\{ \frac{b_m}{h+b_m} \le \sum _u \frac{\pi _u}{R_m} \sum ^{R_m}_{r=1} F_{m,L+r}(S_m-u)\right\} \end{aligned}$$

(26)

1.2 The approximated cost function

During the optimisation, many combinations of policy parameters have to be evaluated. Since for each $(R_m,CP_m)$ combination a system of equations has to be solved to determine $S_m$, this may result in long computation times. Therefore, in some parts of the heuristic approaches, we use an approximated cost function where the Eq. (21) for the undershoot is replaced by

$$\begin{aligned} U_{t} = (D_{m,R_m} - CP_m)^+ \end{aligned}$$

(27)

and the convolution of the resulting probability mass function with the probability mass function for the period demand is replaced by a two-moment fit of these. Both assumptions correspond to those found in Kleintje-Ell and Kiesmüller (2013). With the fitted probability mass function $f_{fit}$, the cost function results in:

$$\begin{aligned} \widetilde{C_m}(CP_m,R_m,S_m)&= \frac{1}{R_m} \sum ^{R_m}_{r=1}\left\{ \sum ^{S_m}_{x=0}(S_m-x) f_{fit}(x)\right. \nonumber \\&\left. +\,\, \sum ^{\infty }_{x=S_m}(x-S_m)f_{fit}(x)\right\} \end{aligned}$$

(28)

Appendix II Upper bound for $R_m$

In the following section, we show why $(E[D_i]+1)\cdot R_m$ is the lowest capacity for the other retailers that needs to be taken into account of all schedules $X$ with any length $T$ containing the order interval $R_m$ for retailer $m$. The following distinction of cases for the possible order intervals of the retailers $i \ne m$ demonstrates this:

$R_i < R_m$ :

We determine the highest possible number of orders of retailer $i$ for an interval $R_m: count:= \max _{\bar{t}<T} \sum ^{\bar{t}+R_m}_{t=\bar{t}} x_{i,t}$. In this case, it holds that: $R_m \cdot (E[D_i]+1)\le count \cdot R_i \cdot (E[D_i]+1)$ as $count \ge \frac{R_m}{R_i}$.

$R_i = R_m$ :

We assume the correct minimum capacity with $(E[D_i]+1)\cdot R_m$.

$R_m<R_i$ :

If there exists an order interval of length $R_m$, in which both retailer $m$ and retailer $i$ place an order, the capacity limit of a retailer is the same at each of his orders. In this case, it holds that $R_m \cdot (E[D_i]+1) < R_i \cdot (E[D_i]+1)$ and we even underestimate the amount required by retailer $i$.

$R_i,R_j \ge 2 \cdot R_m\; , \; R_i = R_j$ :

There may be certain combinations of order intervals in these cases, such that the three retailers $m,i,j$ never order all together in an interval of length $R_m$, but rather in intervals in which $i$ orders, the distance to the order points of $m$ are the same as for $j$ in the corresponding intervals. If we assume w.l.o.g. $E[D_i]\le E[D_j]$, it holds that $(E[D_i]+1)\cdot R_m + (E[D_j]+1)\cdot R_m \le (E[D_j]+1)\cdot 2 \cdot R_m \le (E[D_j]+1)\cdot R_j$ and in these cases as well, the assumed capacity does not overestimate the amount needed by other retailers in an interval of length $R_m$.