Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case
From MaRDI portal
Publication:3990573
DOI10.1287/opre.40.1.S145zbMath0771.90031OpenAlexW2057593340MaRDI QIDQ3990573
Albert P. M. Wagelmans, Antoon W. J. Kolen, Stan P. M. van Hoesel
Publication date: 28 June 1992
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.40.1.s145
Abstract computational complexity for mathematical programming problems (90C60) Inventory, storage, reservoirs (90B05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items
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 ⋮ Subcontracting and lot-sizing with constant capacities ⋮ Inventory lot-sizing with supplier selection ⋮ Single item lot-sizing problems with backlogging on a single machine at a finite production rate ⋮ The economic lot-sizing problem with an emission capacity constraint ⋮ Dynamic lot sizing with stochastic demand timing ⋮ Lot sizing in capacitated production planning and control systems ⋮ Dynamic capacitated lot-sizing problems: a classification and review of solution approaches ⋮ A Lagrangian heuristic for an integrated lot-sizing and fixed scheduling problem ⋮ The lockmaster's problem ⋮ Improving the efficiency of decentralized supply chains with fixed ordering costs ⋮ Dynamic lot-sizing model for major and minor demands ⋮ Economic lot-sizing games ⋮ Lot-sizing with fixed charges on stocks: the convex hull ⋮ Effective replenishment policies for the multi-item dynamic lot-sizing problem with storage capacities ⋮ Meta-heuristics for dynamic lot sizing: a review and comparison of solution approaches ⋮ A heuristic solution procedure for the dynamic lot sizing problem with remanufacturing and product recovery ⋮ Minimizing the error bound for the dynamic lot size model ⋮ The stochastic lot-sizing problem with quantity discounts ⋮ Dynamic lot sizing with random demand and non-stationary costs ⋮ Centralized and decentralized inventory policies for a single-vendor two-buyer system with permissible delay in payments ⋮ Solving a constrained economic lot size problem by ranking efficient production policies ⋮ An efficient procedure for dynamic lot-sizing model with demand time windows ⋮ On the stochastic uncapacitated dynamic single-item lotsizing problem with service level constraints ⋮ Loss of customer goodwill in the uncapacitated lot-sizing problem ⋮ Perspectives of Monge properties in optimization ⋮ Two-stage stochastic lot-sizing problem under cost uncertainty ⋮ A note on ``The economic lot sizing problem with inventory bounds ⋮ Capacitated dynamic lot-sizing problem with delivery/production time windows ⋮ Stochastic lot-sizing problem with deterministic demands and Wagner-Whitin costs ⋮ Stochastic lot-sizing problem with inventory-bounds and constant order-capacities ⋮ Solving single-product economic lot-sizing problem with non-increasing setup cost, constant capacity and convex inventory cost in \(O(N \log N)\) time ⋮ Progress with single-item lot-sizing ⋮ Two-stage minimax regret robust uncapacitated lot-sizing problems with demand uncertainty ⋮ Planning for demand failure: a dynamic lot size model for clinical trial supply chains ⋮ An algorithm for general infinite horizon lot sizing with deterministic demand ⋮ Solving the electricity production planning problem by a column generation based heuristic ⋮ A polyhedral study of the static probabilistic lot-sizing problem ⋮ Approximation algorithms for supply chain planning and logistics problems with market choice ⋮ The multiscenario lot size problem with concave costs. ⋮ Economic lot sizing: the capacity reservation model ⋮ Remanufacturing planning for the reverse Wagner/Whitin models ⋮ A dual algorithm for the economic lot-sizing problem ⋮ Economic lot sizing problem with inventory bounds ⋮ Lot-sizing with non-stationary cumulative capacities ⋮ Improved complexity bounds for location problems on the real line ⋮ Capacitated lot sizing problems with inventory bounds ⋮ An \(O(n^2)\) algorithm for lot sizing with inventory bounds and fixed costs ⋮ An algorithm for single-item economic lot-sizing problem with general inventory cost, non-decreasing capacity, and non-increasing setup and production cost ⋮ On stochastic lot-sizing problems with random lead times ⋮ A comparative study of modeling and solution approaches for the coordinated lot-size problem with dynamic demand ⋮ Valid inequalities, preprocessing, and an effective heuristic for the uncapacitated three-level lot-sizing and replenishment problem with a distribution structure ⋮ A cross entropy-lagrangean hybrid algorithm for the multi-item capacitated lot-sizing problem with setup times ⋮ Multi-level multi-item lot size planning with limited resources and general manufacturing structure. ⋮ Efficient approximation schemes for economic lot-sizing in continuous time ⋮ An efficient algorithm for the 2-level capacitated lot-sizing problem with identical capacities at both levels ⋮ Two-level lot-sizing with inventory bounds ⋮ A dynamic uncapacitated lot-sizing problem with co-production ⋮ Joint pricing and inventory management with deterministic demand and costly price adjustment ⋮ An efficient algorithm for the dynamic economic lot size problem ⋮ Multi-item uncapacitated lot sizing problem with inventory bounds ⋮ Stochastic lot-sizing with backlogging: computational complexity analysis ⋮ Solving the stochastic dynamic lot-sizing problem through nature-inspired heuristics ⋮ Polyhedral analysis for the two-item uncapacitated lot-sizing problem with one-way substitution ⋮ Note on ``An efficient approach for solving the lot-sizing problem with time-varying storage capacities ⋮ Inventory replenishment model: lot sizing versus just-in-time delivery. ⋮ Integrating process optimization and inventory planning in cutting-stock with skiving option: an optimization model and its application ⋮ Multi-product lot-sizing with a transportation capacity reservation contract ⋮ Integrated market selection and production planning: complexity and solution approaches ⋮ A single-item lot-sizing problem with a by-product and inventory capacities ⋮ Rounding heuristics for multiple product dynamic lot-sizing in the presence of queueing behavior ⋮ Extended formulations for stochastic lot-sizing problems ⋮ Capacitated lot-sizing problem with outsourcing ⋮ Uncapacitated two-level lot-sizing ⋮ Polyhedral and Lagrangian approaches for lot sizing with production time windows and setup times ⋮ Four equivalent lot-sizing models ⋮ Coordination of a two-level supply chain with contracts ⋮ Polyhedra for lot-sizing with Wagner-Whitin costs ⋮ A primal-dual algorithm for the economic lot-sizing problem with multi-mode replenishment ⋮ Lotsizing with backlogging and start-ups: The case of Wagner-Whitin costs ⋮ Multi-item lot-sizing with joint set-up costs ⋮ A holding cost bound for the economic lot-sizing problem with time-invariant cost parameters ⋮ Models and Lagrangian heuristics for a two-level lot-sizing problem with bounded inventory ⋮ The multi-item capacitated lot-sizing problem with safety stocks and demand shortage costs ⋮ Lot sizing and scheduling -- survey and extensions ⋮ Lower bound on size of branch-and-bound trees for solving lot-sizing problem ⋮ Dynamic lot-sizing with price changes and price-dependent holding costs ⋮ Minimum concave cost flow over a grid network ⋮ Improved dynamic programs for some batching problems involving the maximum lateness criterion ⋮ Sensitivity analysis of the economic lot-sizing problem ⋮ On scheduling to minimize earliness-tardiness and batch delivery costs with a common due date ⋮ A note on Stability of the constant cost dynamic lot size model by K. Richter ⋮ The single-item discrete lotsizing and scheduling problem: Optimization by linear and dynamic programming ⋮ Sequential stability of the constant cost dynamic lot size model- searching for monotonicity ⋮ A new dynamic programming algorithm for the single item capacitated dynamic lot size model ⋮ A Lagrangian heuristic for capacitated single item lot sizing problems ⋮ A new characterization for the dynamic lot size problem with bounded inventory ⋮ The single item uncapacitated lot-sizing problem with time-dependent batch sizes: NP-hard and polynomial cases ⋮ Dynamic re-order point inventory control with lead-time uncertainty: analysis and empirical investigation ⋮ Polynomial-Time Solvability of Dynamic Lot Size Problems ⋮ DECISION ANALYSIS FOR SUPPLIER IN TWO-ECHELON SUPPLY CHAIN WITH DISCRETE DEMAND VIA DYNAMIC GAME ⋮ Combining Polyhedral Approaches and Stochastic Dual Dynamic Integer Programming for Solving the Uncapacitated Lot-Sizing Problem Under Uncertainty ⋮ Minimizing setups and waste when printing labels of consumer goods ⋮ A Polynomial Time Algorithm for the Stochastic Uncapacitated Lot-Sizing Problem with Backlogging ⋮ A cash‐constrained dynamic lot‐sizing problem with loss of goodwill and credit‐based loan ⋮ New construction heuristic for capacitated lot sizing problems ⋮ Just-in-Time Planning and Lot-Sizing ⋮ Economic lot sizing problem with tank scheduling ⋮ Multiechelon Lot Sizing: New Complexities and Inequalities ⋮ Dynamic lot-sizing problem with demand time windows and container-based transportation cost ⋮ Reformulation by discretization: application to economic lot sizing ⋮ Lot sizing with inventory gains ⋮ Improved algorithms for dynamic lot sizing problems with incremental discount ⋮ An efficient approach for solving the lot-sizing problem with time-varying storage capacities ⋮ A comparison of methods for lot-sizing in a rolling horizon environment ⋮ Unnamed Item ⋮ Decentralized supply chain coordination through auction markets: dynamic lot-sizing in distribution networks ⋮ Dynamic lot-sizing model with demand time windows and speculative cost structure ⋮ An efficient dynamic programming algorithm for a special case of the capacitated lot-sizing problem ⋮ Multi-item capacitated lot-sizing problems with setup times and pricing decisions ⋮ Cross-facility management of production and transportation planning problem ⋮ Integrating facility location and production planning decisions ⋮ Disassembly scheduling: literature review and future research directions ⋮ Discrepancies in solutions between traditional and net present value formulations of finite horizon, discrete-time economic lot size problems ⋮ Lot sizing with bounded inventory and lost sales ⋮ Polynomial cases of the economic lot sizing problem with cost discounts ⋮ ارائه یک روش برنامه ریزی پویا کارا جهت بهینه سازی مسئله اندازه سفارش با محدودیت ظرفیت ⋮ Competition under time‐varying demands and dynamic lot sizing costs ⋮ Fast algorithms for convex cost flow problems on circles, lines, and trees ⋮ Scheduling multiple products on parallel machines with setup costs ⋮ Grouping in decomposition method for multi-item capacitated lot-sizing problem with immediate lost sales and joint and item-dependent setup cost ⋮ A branch and bound method for stochastic integer problems under probabilistic constraints ⋮ Unnamed Item ⋮ On the Computational Complexity of Minimum-Concave-Cost Flow in a Two-Dimensional Grid ⋮ Single item lot sizing problems ⋮ A polynomial time algorithm for a deterministic joint pricing and inventory model ⋮ A two-echelon inventory optimization model with demand time window considerations ⋮ A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem ⋮ ECONOMIC PRODUCTION LOT SIZING MODEL WITH STOCHASTIC DEMAND
