On the Effectiveness of Zero-Inventory-Ordering Policies for the Economic Lot-Sizing Model with a Class of Piecewise Linear Cost Structures
Authors:
- 1 December 2002
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 50 (6) , 1058-1067
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 non decreasing functions, and (ii) the associated cost per unit is non increasing. Finally, we report on a numerical study that shows the effectiveness of ZIO policies on a set of test problems.Keywords
This publication has 10 references indexed in Scilit:
- Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing ProblemsMathematics of Operations Research, 2001
- THEORIES AND REALITIES OF QUANTITY DISCOUNTS: AN EXPLORATORY STUDYProduction and Operations Management, 1998
- An Algorithm for Single-Item Capacitated Economic Lot Sizing with Piecewise Linear Production Costs and General Holding CostsManagement Science, 1998
- The dynamic lot size model with quantity discount: Counterexamples and correctionNaval Research Logistics (NRL), 1998
- The Logic of Logistics1997
- Improved Algorithms for Economic Lot Size ProblemsOperations Research, 1993
- Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin CaseOperations Research, 1992
- A Simple Forward Algorithm to Solve General Dynamic Lot Sizing Models with n Periods in 0(n log n) or 0(n) TimeManagement Science, 1991
- The dynamic lot size model with quantity discountNaval Research Logistics (NRL), 1990
- Dynamic Version of the Economic Lot Size ModelManagement Science, 1958