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.90011OpenAlexW2153518835MaRDI QIDQ613509

Bing Lin, Arun Kumar, Yi Feng, Shaoxiang Chen

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 programmingdynamic programminginventoryalgorithm complexity

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Stochastic programming (90C15) Inventory, storage, reservoirs (90B05) Dynamic programming (90C39)

Related Items

Polynomial-time algorithms to solve the single-item capacitated lot sizing problem with a 1-breakpoint all-units quantity discount, Single-item dynamic lot-sizing problems: an updated survey, LQ optimal sliding mode control of periodic review perishable inventories with transportation losses, 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