Using geometric techniques to improve dynamic programming algorithms for the economic lot-sizing problem and extensions

DOI10.1016/0377-2217(94)90077-9zbMath0806.90125OpenAlexW2163313667MaRDI QIDQ1331605

Albert P. M. Wagelmans, Bram Moerman, Stan P. M. van Hoesel

Publication date: 19 February 1995

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: http://repub.eur.nl/pub/2307

zbMATH Keywords

geometric techniquescomputational analysiseconomic lot-sizingdynamic programs

Mathematics Subject Classification ID

Inventory, storage, reservoirs (90B05) Dynamic programming (90C39)

Related Items

Subcontracting and lot-sizing with constant capacities ⋮ Meta-heuristics for dynamic lot sizing: a review and comparison of solution approaches ⋮ Unbounded batch scheduling with a common due window on a single machine ⋮ Solving single-product economic lot-sizing problem with non-increasing setup cost, constant capacity and convex inventory cost in \(O(N \log N)\) time ⋮ Combined replenishment and warehousing with contract commitments and flexibilities ⋮ Relaxations for two-level multi-item lot-sizing problems ⋮ Scheduling with batching: A review ⋮ Scheduling the production of two-component jobs on a single machine ⋮ Scheduling with centralized and decentralized batching policies in concurrent open shops ⋮ A simultaneous and iterative approach for parallel machine scheduling with sequence-dependent family setups ⋮ Family scheduling with batch availability in flow shops to minimize makespan ⋮ Improved algorithms for dynamic lot sizing problems with incremental discount ⋮ Single machine group scheduling with resource dependent setup and processing times ⋮ SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES BY SUBMODULAR OPTIMIZATION ⋮ Improved dynamic programs for some batching problems involving the maximum lateness criterion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved complexity bounds for location problems on the real line
• Sensitivity analysis of the economic lot-sizing problem
• Dynamic Version of the Economic Lot Size Model
• The Deterministic Dynamic Product Cycling Problem
• The Dynamic Lot-Sizing Problem with Startup and Reservation Costs
• Speed-Up in Dynamic Programming
• A Dynamic Lot Sizing Model with Learning in Setups
• 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
• An improved algorithm for the dynamic lot-sizing problem with learning effect in setups
• An O(T³) Algorithm for the Economic Lot-Sizing Problem with Constant Capacities
• Contraction Mappings in the Theory Underlying Dynamic Programming
• 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