A Greedy Algorithm for Capacitated Lot-Sizing Problems

Authors: Girlich E.¹; HÖding M.¹; Zaporozhets A.²; Chubanov S.²

Source: Optimization, Volume 52, Number 2, 2003 , pp. 241-249(9)

Buy & download fulltext article:

Price: $56.94 plus tax (Refund Policy)

Abstract:

We show that the convex hull of the set of feasible solutions of single-item capacitated lot-sizing problem (CLSP) is a base polyhedron of a polymatroid. We present a greedy algorithm to solve CLSP with linear objective function. The proposed algorithm is an effective implementation of the classical Edmonds' algorithm for maximizing linear function over a polymatroid. We consider some special cases of CLSP with nonlinear objective function that can be solved by the proposed greedy algorithm in O(n) time.

Keywords: Lot-sizing problem; Greedy algorithm; Polymatroid

Document Type: Research article

DOI: http://dx.doi.org/10.1080/023319303763845409

Affiliations: 1: Otto-von-Guericke University of Magdeburg, Department of Mathematics/IMO, Universitätsplatz 2, PSF 4120, 39106 Magdeburg, Germany 2: Belarussian State University, Department of Economics, Karl Marx Str. 31, Minsk, Belarus

Publication date: 2003-01-01