A discrete EOQ problem is solvable in O(logn) time

The Economic Order Quantity problem is a fundamental problem of inventory management. An optimal solution to this problem in a closed form exists under the assumption that time and the product are continuously divisible and demand occurs at a constant rate λ. We prove that a discrete version of this problem, in which time and the product are discrete is solvable in O(logn) time, where n is the length of the time period where the demand takes place. The key elements of our approach are a reduction of the original problem to a discrete minimization problem of one variable representing the number of orders and a proof that the objective function of this problem is convex. According to our approach, optimal order sizes can take at most two distinct values: λnk∗ and λnk∗, where k∗ is the optimal number of orders.