Rounding procedures for the discrete version of the capacitated economic order quantity problem

Rounding procedures for the discrete version of the capacitated economic order quantity problem

0.00 Avg rating0 Votes
Article ID: iaor20023120
Country: Netherlands
Volume: 107
Issue: 1
Start Page Number: 33
End Page Number: 49
Publication Date: Oct 2001
Journal: Annals of Operations Research
Authors: ,
Keywords: economic order
Abstract:

The capacitated Economic Order Quantity problem (capacitated EOQ) is a well-known problem where products have to be shipped between two points with a vehicle of given capacity. Each shipment has a fixed cost, independent of the shipped quantity, and an inventory cost is generated in the two points. The problem consists in finding the optimal time between consecutive shipments, which minimizes the total cost. The problem is a capacitated variant of the EOQ problem and has a closed form solution. Since such solution is often irrational, it is often rounded to an integer value. In this paper we investigate the errors which are generated by rounding procedures to integer and powers-of-two values. We show that, although in the worst case a tight general relative error of 2 is generated by all the considered rounding procedures, the procedure which rounds to the best between the lower and upper values (integer or powers-of-two) has a performance of 1/2>(√(2) + 1/√(2)) ≈ 1.06 on classes of instances of high practical relevance.

Reviews

Required fields are marked *. Your email address will not be published.