A holding cost bound for the economic lot-sizing problem with time-invariant cost parameters

Abstract

We show that in an optimal solution of the economic lot-sizing problem the total holding cost in an order interval is bounded from above by a quantity proportional to the setup cost and the logarithm of the number of periods in the interval. We present two applications of this result.

Introduction

In this work we consider the well-known economic lot-sizing (ELS) model introduced in the seminal paper by Wagner and Whitin [1]. The model has a finite and discrete time horizon of $T$ periods and there is a known demand stream $d_t$ for the periods $t=1,\dots ,T$. The problem is to determine the order periods and order quantities such that total costs are minimized. Costs include a fixed setup cost $K$ for every order placed, and a unit holding cost $h$ per period for every item held in stock. (Note that the terms setup cost and order cost are both used in the literature, depending on the context of the problem.)

Although the ELS problem can be solved efficiently (see [2], [3], [4]), many heuristics have been proposed in the literature and are still used in material requirements planning (MRP) software. A number of those heuristics utilize some optimality property of the economic order quantity (EOQ) model. In contrast to the ELS model, the EOQ model assumes a constant demand rate $D$ over a continuous and infinite horizon. Having the same fixed order cost $K$ and holding cost $h$, the average cost per time unit for the EOQ model equals

$$\frac{K}{T}+\frac{1}{2}ThD\text{,}$$

if an order is placed every $T$ periods. The first part of this expression represents the average order cost, and the second part represents the average holding cost, per unit time. The optimal time between two orders that minimizes the average cost equals $T^{\ast }=\sqrt{2K/\left(Dh\right)}$. It is a well-known property that the average setup and holding cost are perfectly balanced in an optimal solution, i.e., $K/T^{\ast }=\sqrt{KDh/2}=\frac{1}{2}{T}^{\ast }hD$.

The Part Period Balancing (PPB) algorithm is a heuristic for the ELS model that is based on this property (see, for example, [5] for a description of the heuristic); the PPB algorithm tries to construct a solution wherein setup cost and holding are balanced. Other heuristics that try to exploit some optimality property of the EOQ model include the Silver–Meal (SM) heuristic, which minimizes the average cost per period, and the Least Unit Cost (LUC) heuristic, which minimizes the average cost per item. For an overview of how the different rules for the ELS problem relate to the properties of an optimal solution to the EOQ model, see [6].

In this work we are interested in the question of to what extent the property of balancedness between setup and holding cost also holds for the ELS model, and hence, whether it is advisable to apply heuristics based on this property. In particular, we are interested in the relation between holding cost and setup cost in an optimal solution of the ELS model. Clearly, we can have zero holding cost for instances in which setup cost is sufficiently small (resulting in an optimal solution with an order in each period). This raises the question of whether there also exist problem instances for which the total holding cost is relatively large compared to the total setup cost.

In this work we will show that the total holding cost in an optimal order interval is bounded from above by a quantity proportional to the setup cost and the logarithm of the number of periods in the interval, where an order interval is defined as the number of consecutive periods for which demand is satisfied by a single order. We also show that this bound is tight. This is in contrast with the optimality property of the EOQ model and so the result shows that the rationale behind the PBB algorithm does not hold true in general.

The remainder of the work is organized as follows. In Section 2 we will derive the holding cost bound. In Section 3 we show how this property can be used for the design of a new heuristic. We analyze the worst case performance of the heuristic, and derive a property on the number of setups in a solution. Furthermore, we show that the heuristic performs well on a small test set. Finally, Section 4 shows how the result can be used for worst case analysis.