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

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, A Mathematical Model for the Optimization of the Airport Check-In Service Problem, A dynamic model for serial supply chain with periodic delivery policy, Capacitated disassembly scheduling with random demand, Polynomial-Time Solvability of Dynamic Lot Size Problems, METAHEURISTIC APPROACHES FOR THE MULTILEVEL RESOURCE-CONSTRAINED LOT-SIZING PROBLEM WITH SETUP AND LEAD TIMES, Unnamed Item, Predictive Search for Capacitated Multi-Item Lot Sizing Problems, Data-driven branching and selection for lot-sizing and scheduling problems with sequence-dependent setups and setup carryover, Multifacility in-series production-planning model with capacity constraints, Polynomial-time algorithms to solve the single-item capacitated lot sizing problem with a 1-breakpoint all-units quantity discount, A branch-and-price algorithm for parallel machine campaign planning under sequence dependent family setups and co-production, Discrete multi-module capacitated lot-sizing problems with multiple items, A cash‐constrained dynamic lot‐sizing problem with loss of goodwill and credit‐based loan, Tactical Production and Lot Size Planning with Lifetime Constraints: A Comparison of Model Formulations, A dynamic programming approach for the two-product capacitated lot-sizing problem with concave costs, Just-in-Time Planning and Lot-Sizing, Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems, Economic lot sizing problem with tank scheduling, Learning optimal solutions via an LSTM-optimization framework, A genetic algorithm heuristic approach to general outsourcing capacitated production planning problems, Multiechelon Lot Sizing: New Complexities and Inequalities, Capacitated production planning with outsourcing in an OKP company, Integrated production planning and preventive maintenance in deteriorating production systems, The multi-item capacitated lot-sizing problem with setup times and shortage costs, Unnamed Item, A linear-time algorithm for finding optimal vehicle refueling policies, A single-item economic lot-sizing problem with a non-uniform resource: Approximation, An FPTAS for SM‐CELS problem with monotone cost functions, DLSP for two-stage multi-item batch production, Unnamed Item, Decentralized supply chain coordination through auction markets: dynamic lot-sizing in distribution networks, An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure, An efficient dynamic programming algorithm for a special case of the capacitated lot-sizing problem, Multi-item dynamic production-distribution planning in process industries with divergent finishing stages, MIP-based heuristics for multi-item capacitated lot-sizing problem with setup times and shortage costs, Peak Shaving through Resource Buffering, Lot sizing with bounded inventory and lost sales, Grouping in decomposition method for multi-item capacitated lot-sizing problem with immediate lost sales and joint and item-dependent setup cost, Constant Approximation Algorithm for Nonuniform Capacitated Multi-Item Lot Sizing via Strong Covering Inequalities, Évaluation de la fiabilité d'un système de prévision de la demande dans le cas d'une politique de regroupement des besoins, On the Computational Complexity of Minimum-Concave-Cost Flow in a Two-Dimensional Grid, Solving Multi-Level Capacitated Lot Sizing Problems via a Fix-and-Optimize Approach, Variable neighborhood formulation search approach for the multi-item capacitated lot-sizing problem with time windows and setup times, On Robust Lot Sizing Problems with Storage Deterioration, with Applications to Heat and Power Cogeneration, A user interactive heuristic procedure for solving the multiple product cycling problem, Single item lot sizing problems, A polynomial time algorithm for a deterministic joint pricing and inventory model