Solving single-product economic lot-sizing problem with non-increasing setup cost, constant capacity and convex inventory cost in \(O(N \log N)\) time

DOI10.1016/j.cor.2010.08.009zbMath1202.90011MaRDI QIDQ613509

Yi Feng, Shaoxiang Chen, Arun Kumar, Bing Lin

Publication date: 20 December 2010

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2010.08.009

zbMATH Keywords

stochastic programming; dynamic programming; inventory; algorithm complexity

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90C15: Stochastic programming

90B05: Inventory, storage, reservoirs

90C39: Dynamic programming

Related Items

LQ optimal sliding mode control of periodic review perishable inventories with transportation losses, Single-item dynamic lot-sizing problems: an updated survey, A hybrid polynomial-time algorithm for the dynamic quantity discount lot size model with resale, A polynomial time algorithm for convex cost lot-sizing problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm for single-item economic lot-sizing problem with general inventory cost, non-decreasing capacity, and non-increasing setup and production cost
• Lot sizing and scheduling -- survey and extensions
• A new dynamic programming algorithm for the single item capacitated dynamic lot size model
• A dynamic programming algorithm for dynamic lot size models with piecewise linear costs
• Using geometric techniques to improve dynamic programming algorithms for the economic lot-sizing problem and extensions
• An effective algorithm for the capacitated single item lot size problem
• Progress with single-item lot-sizing
• Single item lot sizing problems
• Dynamic Version of the Economic Lot Size Model
• An Algorithm for Single-Item Capacitated Economic Lot Sizing with Piecewise Linear Production Costs and General Holding Costs
• A Fully Polynomial Approximation Scheme for Single-Product Scheduling in a Finite Capacity Facility
• TECHNICAL NOTE—Solving Linear Cost Dynamic Lot-Sizing Problems in O(n log n) Time
• The Infinite Horizon Periodic Review Problem with Setup Costs and Capacity Constraints: A Partial Characterization of the Optimal Policy
• Approximation Formulations for the Single-Product Capacitated Lot Size Problem
• An O(T²) Algorithm for the NI/G/NI/ND Capacitated Lot Size Problem
• An Algorithm for the Dynamic Lot-Size Problem with Time-Varying Production Capacity Constraints
• Computational Complexity of the Capacitated Lot Size Problem
• A Simple Forward Algorithm to Solve General Dynamic Lot Sizing Models with n Periods in 0(n log n) or 0(n) Time
• Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case
• Improved Algorithms for Economic Lot Size Problems
• X-Y Band and Modified (s, S) Policy
• An O(T³) Algorithm for the Economic Lot-Sizing Problem with Constant Capacities
• Deterministic Production Planning with Concave Costs and Capacity Constraints
• Primal-Dual Algorithms for Deterministic Inventory Problems
• A Deterministic Multi-Period Production Scheduling Model with Backlogging
• A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System—A Network Approach
• Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems