Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems

DOI10.1287/moor.26.2.339.10552zbMath1082.90532OpenAlexW2165465282MaRDI QIDQ5704043

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

Publication date: 11 November 2005

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://cris.maastrichtuniversity.nl/en/publications/aaca34b5-a2dd-4ce5-9a16-2b6d8ae3115e

zbMATH Keywords

Analysis of algorithms, fully polynomial approximation scheme, lot-sizing model, single-item capacitated lot-sizing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Inventory, storage, reservoirs (90B05) Approximation algorithms (68W25)

Related Items (35)

Using geometric techniques to improve dynamic programming algorithms for the economic lot-sizing problem and extensions ⋮ A linear description of the discrete lot-sizing and scheduling problem ⋮ Dynamic programming approximation algorithms for the capacitated lot-sizing problem ⋮ Single item lot-sizing problems with backlogging on a single machine at a finite production rate ⋮ A GLNPSO for multi-level capacitated lot-sizing and scheduling problem in the poultry industry ⋮ Polynomial-Time Solvability of Dynamic Lot Size Problems ⋮ Meta-heuristics for dynamic lot sizing: a review and comparison of solution approaches ⋮ Analysis of bounds for a capacitated single-item lot-sizing problem ⋮ Single-item lot-sizing with quantity discount and bounded inventory ⋮ Solving single-product economic lot-sizing problem with non-increasing setup cost, constant capacity and convex inventory cost in \(O(N \log N)\) time ⋮ Primal-Dual Schema for Capacitated Covering Problems ⋮ An FPTAS for the single-item capacitated economic lot-sizing problem with supply and demand ⋮ Allocating procurement to capacitated suppliers with concave quantity discounts ⋮ Greedy algorithms for the single-demand facility location problem ⋮ Lot-sizing with non-stationary cumulative capacities ⋮ A bilinear reduction based algorithm for solving capacitated multi-item dynamic pricing problems ⋮ Production and Transportation Integration for Commit-to-Delivery Mode with General Shipping Costs ⋮ Easy capacitated facility location problems, with connections to lot-sizing ⋮ Improved algorithms for dynamic lot sizing problems with incremental discount ⋮ NP-hard and polynomial cases for the single-item lot sizing problem with batch ordering under capacity reservation contract ⋮ Solving knapsack problems with \(S\)-curve return functions ⋮ Optimal solutions for the economic lot-sizing problem with multiple suppliers and cost structures ⋮ A single-item economic lot-sizing problem with a non-uniform resource: Approximation ⋮ An FPTAS for SM‐CELS problem with monotone cost functions ⋮ An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure ⋮ A polynomial time algorithm for convex cost lot-sizing problems ⋮ Discrepancies in solutions between traditional and net present value formulations of finite horizon, discrete-time economic lot size problems ⋮ Grouping in decomposition method for multi-item capacitated lot-sizing problem with immediate lost sales and joint and item-dependent setup cost ⋮ Primal-dual schema for capacitated covering problems ⋮ Constant Approximation Algorithm for Nonuniform Capacitated Multi-Item Lot Sizing via Strong Covering Inequalities ⋮ A simple FPTAS for a single-item capacitated economic lot-sizing problem with a monotone cost structure ⋮ Single item lot sizing problems ⋮ Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs ⋮ A Lagrangian heuristic for capacitated single item lot sizing problems ⋮ Economic lot-sizing problem with remanufacturing option: complexity and algorithms

This page was built for publication: Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems