This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Chan, L. M. A. Articles by Simchi-Levi, D. Search for Related Content

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

School of Management, University of Toronto, Toronto, Ontario, Canada M5S 3E6
Department of Mechanical and Industrial Engineering, University of Massachusetts, Amherst, Massachusetts 01106
Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611
The Engineering Systems Division and the Department of Civil and Environmental Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
achan{at}rotman.utoronto.ca
muriel{at}ecs.umass.edu
shen{at}ise.ufl.edu
dslevi{at}mit.edu

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.

Subject classifications: Analysis of algorithms: computational complexity; economic lot-sizing problem. Inventory/production: approximations for economic lot-sizing problem.Transportation: less than truckload cost.
History: Received September 1999; revision received October 2001; accepted October 2001.

This article has been cited by other articles:

				H.-C. Hwang Inventory Replenishment and Inbound Shipment Scheduling Under a Minimum Replenishment Policy Transportation Science, May 1, 2009; 43(2): 244 - 264. [Abstract] [PDF]

				C.-L. Li, V. N. Hsu, and W.-Q. Xiao Dynamic Lot Sizing with Batch Ordering and Truckload Discounts Operations Research, July 1, 2004; 52(4): 639 - 654. [Abstract] [PDF]