Constant approximation algorithm for nonuniform capacitated multi-item lot sizing via strong covering inequalities

DOI10.1287/MOOR.2019.1018zbMATH Open1451.90012arXiv1610.02056OpenAlexW3016784372MaRDI QIDQ3387909FDOQ3387909

Authors: Shi Li 

Publication date: 8 January 2021

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

Abstract: We study the non-uniform capacitated multi-item lot-sizing (lotsizing) problem. In this problem, there is a set of demands over a planning horizon of $T$ time periods and all demands must be satisfied on time. We can place an order at the beginning of each period $s$, incurring an ordering cost $K_s$. The total quantity of all products ordered at time $s$ can not exceed a given capacity $C_s$. On the other hand, carrying inventory from time to time incurs inventory holding cost. The goal of the problem is to find a feasible solution that minimizes the sum of ordering and holding costs. Levi et al. (Levi, Lodi and Sviridenko, Mathmatics of Operations Research 33(2), 2008) gave a 2-approximation for the problem when the capacities $C_s$ are the same. In this paper, we extend their result to the case of non-uniform capacities. That is, we give a constant approximation algorithm for the capacitated multi-item lot-sizing problem with general capacities. The constant approximation is achieved by adding an exponentially large set of new covering inequalities to the natural facility-location type linear programming relaxation for the problem. Along the way of our algorithm, we reduce the lotsizing problem to two generalizations of the classic knapsack covering problem. We give LP-based constant approximation algorithms for both generalizations, via the iterative rounding technique.

Full work available at URL: https://arxiv.org/abs/1610.02056

Recommendations

• Constant approximation algorithm for non-uniform capacitated multi-item lot-sizing via strong covering inequalities
• Approximation algorithms for the capacitated multi-item lot-sizing problem via flow-cover inequalities
• Approximation Algorithms for the Multi-item Capacitated Lot-Sizing Problem Via Flow-Cover Inequalities
• Lot-sizing with non-stationary cumulative capacities
• A single-item economic lot-sizing problem with a non-uniform resource: Approximation

zbMATH Keywords

approximationlot sizingcapacitated

Mathematics Subject Classification ID

Linear programming (90C05) Approximation algorithms (68W25) Inventory, storage, reservoirs (90B05)

Cites Work

• Production Planning by Mixed Integer Programming
• Title not available (Why is that?)
• Approximation algorithms for the capacitated multi-item lot-sizing problem via flow-cover inequalities
• Deterministic Production Planning: Algorithms and Complexity
• Lot-Sizing with Constant Batches: Formulation and Valid Inequalities
• Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems
• Valid Linear Inequalities for Fixed Charge Problems
• On column-restricted and priority covering integer programs
• Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
• Multi-item lot-sizing with joint set-up costs
• On uniform capacitated \(k\)-median beyond the natural LP relaxation
• Approximating capacitated \(k\)-median with \((1 + \epsilon)k\) open facilities

Cited In (4)

• The Multi-Item Capacitated Lot Size Problem: Error Bounds of Manne's Formulations
• Approximation Algorithms for the Multi-item Capacitated Lot-Sizing Problem Via Flow-Cover Inequalities
• Approximation algorithms for the capacitated multi-item lot-sizing problem via flow-cover inequalities
• Constant approximation algorithm for non-uniform capacitated multi-item lot-sizing via strong covering inequalities

This page was built for publication: Constant approximation algorithm for nonuniform capacitated multi-item lot sizing via strong covering inequalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3387909)