On the Effectiveness of Zero-Inventory-Ordering Policies for the Economic Lot-Sizing Model with a Class of Piecewise Linear Cost Structures

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.