Approximation Algorithm for the Capacitated Multi-Item Lot Sizing Problem

Dr. Liron Yedidsion - Faculty of Industrial Engineering and Management, Technion

Abstract:

We study the Capacitated Multi-Item Lot sizing Problem. That is, given a set of items where each item has a unique sequence of demands over a deterministic planning horizon. Backlogging and lost sales are not allowed, i.e., all of the demands must be fully satisfied on time. Our goal is to satisfy the demand to all items in the planning horizon while minimizing the total ordering and handling cost of all items. However, there is a capacity constraint on the combined amount of items ordered at each time period. Those capacities are unique to each time period.

This problem is known to be strongly -hard and results in related literature have provided approximation algorithms for special cases of this problem such as the Capacitated Single-Item Lot sizing Problem and the Uniformly Capacitated Multi-Item Lot sizing Problem. We use a Linear Program (LP) relaxation that is based on an exponentially large subset of the well-known flow-cover inequalities; We provide a polynomial time algorithm that introduces only a subset of flow cover inequalities to the original LP one at a time until a feasible integer solution is achieved with cost that is at most twice the optimal cost. We show that the size of this subset is polynomial with respect to the size of the original LP. This provides a -approximation algorithm which is the first constant approximation algorithm for the problem. Moreover, as a generalization of both the Capacitated Single-Item Lot sizing Problem and the Uniformly Capacitated Multi-Item Lot sizing Problem, our algorithm is a -approximation algorithm for those problems as well.

(This research is a joint work with Retsef Levi and Maxim Sviridenko).