A Greedy Algorithm for Capacitated Lot-Sizing Problems
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.
- An efficient dynamic programming algorithm for a special case of the capacitated lot-sizing problem
- An effective algorithm for the capacitated single item lot size problem
- Polynomial time algorithms for the constant capacitated single-item lot sizing problem with stepwise production cost
- An efficient algorithm for the capacitated single item dynamic lot size problem
- An \(O(T\log T)\) algorithm for the dynamic lot size problem with limited storage and linear costs
- A Simple Forward Algorithm to Solve General Dynamic Lot Sizing Models with n Periods in 0(n log n) or 0(n) Time
- An O(T3) Algorithm for the Economic Lot-Sizing Problem with Constant Capacities
- Computational Complexity of the Capacitated Lot Size Problem
- scientific article; zbMATH DE number 194516 (Why is no real title available?)
- Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
- Submodular functions and optimization
- An efficient algorithm for the 2-level capacitated lot-sizing problem with identical capacities at both levels
- An exact algorithm for the capacitated total quantity discount problem
- A linear-time algorithm for finding optimal vehicle refueling policies
- An O(T2) Algorithm for the NI/G/NI/ND Capacitated Lot Size Problem
- An \(O(T^{3})\) algorithm for the capacitated lot sizing problem with minimum order quantities
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)