Time-variant lot sizing models for the warehouse scheduling problem

Abstract

We consider the problem of scheduling the delivery of n products into a warehouse with limited space under the assumptions of continuous demands at constant rates, infinite horizon, and no backorders. The delivery schedule is described by a cyclic schedule with time-varying lot sizes. The order frequencies and the order sequence are assumed to be given. We formulate a linear program that determines delivery times relative to the cycle length to minimize the relative maximum space used and show that the optimal solution is characterized by filling the warehouse at each order. We bound the optimal solution by using a worst-case analysis and give conditions under which the linear program has the same optimal solution as a quadratic program that minimizes the holding cost. Under general conditions, we derive a bound on the cost penalty that results when using the optimal solution of the linear program as a solution to the quadratic program. Finally, we complete a solution to the nonlinear lot-sizing model by determining the best cycle length corresponding to the solution to the linear program and present a bound on a quality of this solution.