ALCOMFT-TR-02-78

K.M.J. De Bontridder
A purchase lot sizing problem with quantity discounts
Utrecht. Work package 3. May 2002.

Abstract: In this paper we present a local search algorithm for a purchase lot sizing problem, which is an extended version of the classical lot sizing problem. The problem is to find a purchase plan for several items in such a way that the sum of the purchase costs and the inventory costs is minimized. We assume that we know how much of each item we need and the time at which we need it; we must decide in which period and from which supplier we buy each purchased item, where each supplier has its own prices and discounts. We present two mixed integer programming formulations and a local search algorithm. The local search algorithm consist of two stages. In the first stage we determine an initial solution on the basis of the linear programming relaxation of one of the mixed integer programming formulations. In the second stage we try to improve this solution by applying local search techniques. To determine the value of the neighbors we solve generalized nonlinear knapsack problems. We tested our approaches on randomly generated test instances. Our local search approach gives good results in a small amount of time.

Postscript file: ALCOMFT-TR-02-78.ps.gz (78 kb).