A Greedy Algorithm for Capacitated Lot-Sizing Problems

From MaRDI portal





The single-item capacitated lot-sizing problem, called CLSP, is considered. It is shown that the convex hull of the set of feasible solutions of CLSP represents the base polyhedron of polymatroid. Combining the algorithm of \textit{J. Edmonds} [in: Combinat. Struct. Appl., Proc. Calgary internat. Conf. combinat. Struct. Appl., Calgary 1969, 69--87 (1970; Zbl 0268.05019)] and the idea of a vector of unsatisfied demand by \textit{D. S. Hochbaum} [Math. Oper. Res. 19, 390--409 (1994; Zbl 0820.90082)] the authors propose \(O(n \log n)\) greedy algorithm to obtain an optimal solution for CLSP with linear objective. The authors also indicate some special cases of CLSP with nonlinear objective function solvable by the proposed algorithm in \(O(n)\) time.











This page was built for publication: A Greedy Algorithm for Capacitated Lot-Sizing Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4430673)