On the computational complexity of uncapacitated multi-plant lot-sizing problems

DOI10.1007/S11590-020-01615-XzbMATH Open1466.90054arXiv2003.04438OpenAlexW3102124631MaRDI QIDQ828705FDOQ828705

Jesus Ossian Cunha, Hugo Harry Kramer, Rafael A. Melo

Publication date: 5 May 2021

Published in: Optimization Letters (Search for Journal in Brave)

Abstract: Production and inventory planning have become crucial and challenging in nowadays competitive industrial and commercial sectors, especially when multiple plants or warehouses are involved. In this context, this paper addresses the complexity of uncapacitated multi-plant lot-sizing problems. We consider a multi-item uncapacitated multi-plant lot-sizing problem with fixed transfer costs and show that two of its very restricted special cases are already NP-hard. Namely, we show that the single-item uncapacitated multi-plant lot-sizing problem with a single period and the multi-item uncapacitated two-plant lot-sizing problem with fixed transfer costs are NP-hard. Furthermore, as a direct implication of the proven results, we also show that a two-echelon multi-item lot-sizing with joint setup costs on transportation is NP-hard.

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

Recommendations

• Computational complexity of uncapacitated multi-echelon production planning problems
• Multi-item uncapacitated lot sizing problem with inventory bounds
• Lagrangian heuristics for the capacitated multi-plant lot sizing problem with multiple periods and items
• The single item uncapacitated lot-sizing problem with time-dependent batch sizes: NP-hard and polynomial cases
• Multiechelon Lot Sizing: New Complexities and Inequalities

zbMATH Keywords

computational complexityNP-hardproduction planningmulti-plant lot-sizing

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Abstract computational complexity for mathematical programming problems (90C60) Mixed integer programming (90C11)

Cites Work

• Production Planning by Mixed Integer Programming
• Computational complexity of uncapacitated multi-echelon production planning problems
• MIP formulations and heuristics for two-level production-transportation problems
• A Lagrangean-based heuristic for multi-plant, multi-item, multi-period capacitated lot-sizing problems with inter-plant transfers
• On reformulations for the one-warehouse multi-retailer problem
• An integrated approach for production and distribution planning in supply chain management
• A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System—A Network Approach
• Uncapacitated two-level lot-sizing
• Title not available (Why is that?)
• Dynamic version of the economic lot size model
• Modeling industrial lot sizing problems: a review
• Lagrangian heuristics for the capacitated multi-plant lot sizing problem with multiple periods and items
• Computational Complexity of the Capacitated Lot Size Problem
• GRASP heuristic with path-relinking for the multi-plant capacitated lot sizing problem
• A heuristic procedure for solving multi-plant, multi-item, multi-period capacitated lot-sizing problems
• Multi-item uncapacitated lot sizing problem with inventory bounds
• Single-item dynamic lot-sizing problems: an updated survey
• A kernel search to the multi-plant capacitated lot sizing problem with setup carry-over

Cited In (2)

• Computational complexity of uncapacitated multi-echelon production planning problems
• A modified variable neighborhood search algorithm for dynamic lot-sizing with supplier selection under varying delivery time quotation

This page was built for publication: On the computational complexity of uncapacitated multi-plant lot-sizing problems

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