Computational complexity of uncapacitated multi-echelon production planning problems

DOI10.1016/0167-6377(89)90001-1zbMath0674.90044OpenAlexW2092681793MaRDI QIDQ1121774

Dev Joneja, Robin Roundy, Esther M. Arkin

Publication date: 1989

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(89)90001-1

zbMATH Keywords

computational complexityproduction planningNP-completeassembly systemPolynomial time algorithmsjoint replenishment systemmulti-echelon production-distribution systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Production models (90B30)

Related Items

On reformulations for the one-warehouse multi-retailer problem ⋮ On the computational complexity of uncapacitated multi-plant lot-sizing problems ⋮ Improved Approximation Algorithms for Inventory Problems ⋮ Statistical search methods for lotsizing problems ⋮ Approximation algorithms for \(k\)-echelon extensions of the one warehouse multi-retailer problem ⋮ The submodular joint replenishment problem ⋮ Stochastic Dual Dynamic Programming for Multiechelon Lot Sizing with Component Substitution ⋮ Constant approximation algorithms for the one warehouse multiple retailers problem with backlog or lost-sales ⋮ Distribution-free approach for stochastic joint-replenishment problem with backorders-lost sales mixtures, and controllable major ordering cost and lead times ⋮ Heuristics based on genetic algorithms for the capacitated multi vehicle production distribution problem ⋮ Approximation algorithms for inventory problems with submodular or routing costs ⋮ Combinatorial Heuristics for Inventory Routing Problems ⋮ Extended formulation and valid inequalities for the multi-item inventory lot-sizing problem with supplier selection ⋮ Improved approximation for the capacitated inventory access point problem ⋮ Relaxations for two-level multi-item lot-sizing problems ⋮ Complexity of inventory routing problems when routing is easy ⋮ Controlling lead times and minor ordering costs in the joint replenishment problem with stochastic demands under the class of cyclic policies ⋮ <scp>Decomposition‐based</scp> approximation algorithms for the <scp>one‐warehouse multi‐retailer</scp> problem with concave batch order costs ⋮ Simultaneous scheduling of replacement and repair of common components in operating systems. A multi-objective mathematical optimization model ⋮ Joint replenishment meets scheduling ⋮ Single-item dynamic lot-sizing problems: an updated survey ⋮ A heuristic algorithm to solve the one‐warehouse multiretailer problem with an emission constraint ⋮ An online joint replenishment problem combined with single machine scheduling ⋮ Modeling and solving the constrained multi-items lot-sizing problem with time-varying setup cost ⋮ Approximation algorithms for the joint replenishment problem with deadlines ⋮ A MODIFIED JOINT INVENTORY POLICY FOR VMI SYSTEMS ⋮ Approximation algorithms for supply chain planning and logistics problems with market choice ⋮ Online Algorithms for Multilevel Aggregation ⋮ A survey of lower bounding methodologies for production/inventory models ⋮ Scheduling multimodal transportation systems. ⋮ The dynamic-demand joint replenishment problem with approximated transportation costs ⋮ Two-stage absolute semi-deviation mean-risk stochastic programming: an application to the supply chain replenishment problem ⋮ A review of the joint replenishment problem literature: 1989--2005 ⋮ The joint replenishment problem involving multiple suppliers offering quantity discounts ⋮ Terminal inventory level constraints for online production scheduling ⋮ A genetic algorithm for joint replenishment based on the exact inventory cost ⋮ A periodic review policy for a coordinated single vendor-multiple buyers supply chain with controllable lead time and distribution-free approach ⋮ A comparative study of modeling and solution approaches for the coordinated lot-size problem with dynamic demand ⋮ New results on multi-level aggregation ⋮ A variable neighborhood search with an effective local search for uncapacitated multilevel lot-sizing problems ⋮ MIP formulations and heuristics for two-level production-transportation problems ⋮ The one-warehouse multi-retailer problem: reformulation, classification, and computational results ⋮ Supply Chain Management with Online Customer Selection ⋮ Unnamed Item ⋮ Decentralized supply chain coordination through auction markets: dynamic lot-sizing in distribution networks ⋮ The joint replenishment problem with resource restriction ⋮ Models and algorithms for the dynamic-demand joint replenishment problem ⋮ Single‐warehouse multi‐retailer inventory systems with full truckload shipments ⋮ Multi-product lot-sizing with a transportation capacity reservation contract ⋮ A comparison of formulations for a three-level lot sizing and replenishment problem with a distribution structure ⋮ Integrating facility location and production planning decisions ⋮ Decentralized multi-level uncapacitated lot-sizing by automated negotiation ⋮ Uncapacitated two-level lot-sizing ⋮ An extension of the stochastic joint-replenishment problem under the class of cyclic policies ⋮ The one-warehouse multiretailer problem with an order-up-to level inventory policy ⋮ A supplier-selection model with classification and joint replenishment of inventory items ⋮ On the coordination of maintenance scheduling for transportation fleets of many branches of a logistic service provider ⋮ A stochastic multi-item replenishment and delivery problem with lead-time reduction initiatives and the solving methodologies ⋮ Models and Lagrangian heuristics for a two-level lot-sizing problem with bounded inventory ⋮ The Periodic Joint Replenishment Problem Is Strongly 𝒩𝒫-Hard ⋮ New search algorithm for solving the maintenance scheduling problem for a family of machines ⋮ Multi-period lot-sizing with supplier selection: structural results, complexity and algorithms ⋮ Modeling and optimization of stochastic joint replenishment and delivery scheduling problem with uncertain costs ⋮ APPROXIMATING THE JOINT REPLENISHMENT PROBLEM WITH DEADLINES ⋮ The coordinated replenishment dynamic lot-sizing problem with quantity discounts ⋮ Lot sizing and scheduling -- survey and extensions ⋮ Efficient and effective heuristics for the coordinated capacitated lot-size problem ⋮ A global optimum search algorithm for the joint replenishment problem under power-of-two policy.

Cites Work

• Unnamed Item
• Dynamic Version of the Economic Lot Size Model
• Deterministic Production Planning: Algorithms and Complexity
• Computational Complexity of the Capacitated Lot Size Problem
• A Multi-Product Dynamic Lot-Size Model with Individual and Joint Set-up Costs
• A Deterministic Multiproduct, Multi-Facility Production and Inventory Model
• Minimum Concave-Cost Solution of Leontief Substitution Models of Multi-Facility Inventory Systems
• A Facilities in Series Inventory Model with Nested Schedules
• A Simple Continuous Review Deterministic One-Warehouse N-Retailer Inventory Problem

This page was built for publication: Computational complexity of uncapacitated multi-echelon production planning problems