Zurück zu den Preprints des Jahres 2000


A Greedy Algorithm for Capacitated Lot-Sizing Problems

by Girlich, E., Hoeding, M., Zaporozhets, A., Chubanov, S..

Series: 2000-32, Preprints

90C05 Linear programming
90C10 Integer programming
90C27 Combinatorial optimization
65K05 Mathematical programming methods

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 and present
an O(n) 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.

lot-sizing problem, greedy algorithm, polymatroid