Deterministic Production Planning: Algorithms and Complexity

DOI10.1287/MNSC.26.7.669zbMath0445.90025OpenAlexW2061538120WikidataQ115188674 ScholiaQ115188674MaRDI QIDQ3890384

Alexander H. G. Rinnooy Kan, Jan Karel Lenstra, Michael Florian

Publication date: 1980

Published in: Management Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/mnsc.26.7.669

zbMATH Keywords

algorithmscomputational complexityfinite horizonNP-hard problemsdeterministic production planningminimum total costs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Production models (90B30) Inventory, storage, reservoirs (90B05) Dynamic programming (90C39)

Related Items (only showing first 100 items - show all)

A dynamic programming algorithm for dynamic lot size models with piecewise linear costs ⋮ A simple heuristic for the multi-item single level capacitated lotsizing problem ⋮ A new heuristic approach for the multi-item dynamic lot sizing problem ⋮ A linear description of the discrete lot-sizing and scheduling problem ⋮ An effective algorithm for the capacitated single item lot size problem ⋮ Statistical search methods for lotsizing problems ⋮ Dynamic programming approximation algorithms for the capacitated lot-sizing problem ⋮ Multi-item capacitated lot-sizing by a cross decomposition based algorithm ⋮ Solving large-scale profit maximization capacitated lot-size problems by heuristic methods ⋮ Integrating deterioration and lifetime constraints in production and supply chain planning: a survey ⋮ Lot sizing with storage losses under demand uncertainty ⋮ Scheduling with few changes ⋮ A dynamic production scheduling model with lost-sales or backlogging ⋮ Cost-based filtering techniques for stochastic inventory control under service level constraints ⋮ Capacitated Arc Stabbing ⋮ Dynamic capacitated lot-sizing problems: a classification and review of solution approaches ⋮ Single item lot-sizing with non-decreasing capacities ⋮ The economic lot-sizing problem with perishable items and consumption order preference ⋮ Dual-mode production planning for manufacturing with emission constraints ⋮ Dynamic lot-sizing model for major and minor demands ⋮ Meta-heuristics for dynamic lot sizing: a review and comparison of solution approaches ⋮ Minimizing the error bound for the dynamic lot size model ⋮ The green capacitated multi-item lot sizing problem with parallel machines ⋮ Partial objective inequalities for the multi-item capacitated lot-sizing problem ⋮ A hybrid Lagrangian-simulated annealing-based heuristic for the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times ⋮ Integrated cost optimization in a two-stage, automotive supply chain ⋮ Stochastic program for disassembly lot-sizing under uncertain component refurbishing lead times ⋮ A heuristic method for lot-sizing in multi-stage systems ⋮ An integrated model for lot sizing with supplier selection and quantity discounts ⋮ Lot-size scheduling of two types of jobs on identical machines ⋮ An integrated economic disposal and lot-sizing problem for perishable inventories with batch production and corrupt stock-dependent holding cost ⋮ Computational complexity of uncapacitated multi-echelon production planning problems ⋮ Long range planning in the process industries: A projection approach ⋮ A metaheuristic approach to solving a multiproduct EOQ-based inventory problem with storage space constraints ⋮ Capacitated dynamic lot-sizing problem with delivery/production time windows ⋮ A computational analysis of lower bounds for big bucket production planning problems ⋮ Dynamic capacitated lot sizing with random demand and dynamic safety stocks ⋮ Single-item dynamic lot-sizing problems: an updated survey ⋮ Planning for demand failure: a dynamic lot size model for clinical trial supply chains ⋮ Production planning with time-dependent capacity bounds ⋮ Analysis of relaxations for the multi-item capacitated lot-sizing problem ⋮ A multiobjective optimization algorithm to solve the part feeding problem in mixed-model assembly lines ⋮ Set partitioning and column generation heuristics for capacitated dynamic lotsizing ⋮ Economic lot sizing: the capacity reservation model ⋮ A dual algorithm for the economic lot-sizing problem ⋮ Greedy algorithms for the single-demand facility location problem ⋮ Primal-dual approach to the single level capacitated lot-sizing problem ⋮ Economic lot sizing problem with inventory dependent demand ⋮ Lot-sizing with non-stationary cumulative capacities ⋮ Distance and matching-induced search algorithm for the multi-level lot-sizing problem with substitutable bill of materials ⋮ Capacitated lot sizing problems with inventory bounds ⋮ An algorithm for single-item economic lot-sizing problem with general inventory cost, non-decreasing capacity, and non-increasing setup and production cost ⋮ Easy capacitated facility location problems, with connections to lot-sizing ⋮ Hybrid matheuristics to solve the integrated lot sizing and scheduling problem on parallel machines with sequence-dependent and non-triangular setup ⋮ Production lot-sizing with dynamic capacity adjustment ⋮ Capacitated lot-sizing and scheduling by Lagrangean relaxation ⋮ Improved exact algorithms to economic lot-sizing with piecewise linear production costs ⋮ NP-hard and polynomial cases for the single-item lot sizing problem with batch ordering under capacity reservation contract ⋮ An efficient algorithm for the 2-level capacitated lot-sizing problem with identical capacities at both levels ⋮ A heuristic approach for big bucket multi-level production planning problems ⋮ Comparative study of dynamic lot sizing heuristics with backlogging ⋮ A relax-and-fix with fix-and-optimize heuristic applied to multi-level lot-sizing problems ⋮ Two-level lot-sizing with inventory bounds ⋮ A robust lot sizing problem with ill-known demands ⋮ Polynomial time algorithms for the constant capacitated single-item lot sizing problem with stepwise production cost ⋮ Heuristic approaches for master planning in semiconductor manufacturing ⋮ Analysis of the maximum level policy in a production-distribution system ⋮ Inventory replenishment model: lot sizing versus just-in-time delivery. ⋮ Greedy algorithm for local heating problem ⋮ Convex hull results for generalizations of the constant capacity single node flow set ⋮ Integrated market selection and production planning: complexity and solution approaches ⋮ A single-item lot-sizing problem with a by-product and inventory capacities ⋮ Scheduling injection molding operations with multiple resource constraints and sequence dependent setup times and costs ⋮ Rounding heuristics for multiple product dynamic lot-sizing in the presence of queueing behavior ⋮ Minimum concave-cost network flow problems: Applications, complexity, and algorithms ⋮ A branch and bound algorithm for a single item nonconvex dynamic lot sizing problem with capacity constraints ⋮ A polynomial time algorithm for convex cost lot-sizing problems ⋮ Integrated inventory routing and freight consolidation for perishable goods ⋮ Dynamic economic lot size model with perishable inventory and capacity constraints ⋮ The single-item lot-sizing problem with two production modes, inventory bounds, and periodic carbon emissions capacity ⋮ Warehouse location with production, inventory, and distribution decisions: a case study in the lube oil industry ⋮ Multi-item lot-sizing with joint set-up costs ⋮ An efficient algorithm for the capacitated single item dynamic lot size problem ⋮ A global chance-constraint for stochastic inventory systems under service level constraints ⋮ Multi-period lot-sizing with supplier selection: structural results, complexity and algorithms ⋮ Valid inequalities for the single-item capacitated lot sizing problem with step-wise costs ⋮ Models for the schedule optimization problem at a public transit terminal ⋮ A dynamic quantity discount lot size model with resales ⋮ Stability of the constant cost dynamic lot size model ⋮ Lot sizing and scheduling -- survey and extensions ⋮ Facets and algorithms for capacitated lot sizing ⋮ Capacitated dynamic lot sizing problems in closed-loop supply chain ⋮ A simple FPTAS for a single-item capacitated economic lot-sizing problem with a monotone cost structure ⋮ Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs ⋮ Capacity expansion planning for a single facility product line ⋮ A new dynamic programming algorithm for the single item capacitated dynamic lot size model ⋮ Multilevel capacitated lotsizing complexity and LP-based heuristics ⋮ Economic lot-sizing problem with remanufacturing option: complexity and algorithms ⋮ A new characterization for the dynamic lot size problem with bounded inventory ⋮ A dynamic inventory model with supplier selection in a serial supply chain structure

This page was built for publication: Deterministic Production Planning: Algorithms and Complexity