A Greedy Algorithm for Capacitated Lot-Sizing Problems

DOI10.1080/0233193031000079801MaRDI QIDQ4430673zbMATH OpenOpenAlexFDO

Authors Eberhard Girlich, Michael Höding, Alexander Zaporozhets, Sergei Chubanov

Publication date 12 October 2003

Published in Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/0233193031000079801

zbMATH Keywords

greedy algorithmpolymatroidlot-sizing problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10)

Recommendations

• 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

Cites work

• scientific article; zbMATH DE number 194516 (Why is no real title available?)
• 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(T³) Algorithm for the Economic Lot-Sizing Problem with Constant Capacities
• Computational Complexity of the Capacitated Lot Size Problem
• Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
• Submodular functions and optimization

Cited in

(5)

• A linear-time algorithm for finding optimal vehicle refueling policies
• An exact algorithm for the capacitated total quantity discount problem
• An \(O(T^{3})\) algorithm for the capacitated lot sizing problem with minimum order quantities
• An O(T²) Algorithm for the NI/G/NI/ND Capacitated Lot Size Problem
• An efficient algorithm for the 2-level capacitated lot-sizing problem with identical capacities at both levels

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)