On the effectiveness of zero-inventory-ordering policies for the economic lot-sizing model with a class of piecewise linear cost structures

Abstract

We consider an economic lot-sizing problem with a special class of piecewise linear ordering costs, which we refer to as the class of modified all-unit discount cost functions. Such an ordering cost function represents transportation costs charged by many less-than-truckload carriers. We show that even special cases of the lot-sizing problem are NP-hard and therefore analyze the effectiveness of easily implementable policies. In particular, we demonstrate that there exists a zero-inventory-ordering (ZIO) policy, i.e., a policy in which an order is placed only when the inventory level drops to zero, whose total inventory and ordering cost is no more than 4/3 times the optimal cost. Furthermore, if the ordering cost function does not vary over time, then the cost of the best ZIO policy is no more than 5.6/4.6 times the optimal cost. These results hold for any transportation and holding cost functions that satisfy the following properties: (i) they are nondecreasing functions, and (ii) the associated cost per unit is nonincreasing. Finally, we report on a numerical study that shows the effectiveness of ZIO policies on a set of test problems.