A branch and bound algorithm for a single item nonconvex dynamic lot sizing problem with capacity constraints
The following model of a single item \(T\)-period lot sizing problem is considered: Minimize \(f(x,I)\) subject to \((x,I)\in G\cap C\), where \((x,I)=(x_1, \dots, x_ T,I_1, \dots,I_ T) \in R^{2T}\), \(f(x,I)=\sum^{T}_{i=1}f_ i(x_ i) + \sum^{T}_{i=1}h_ i I_ i\), \(G =\{(x,I)\in R^{2T}: x_ i + I_{i-1} - I_ i = d_ i\), \(i=1, \dots, T\), \(I_ 0=0\}\), \(C=\{(x,I)\in R^{2T}: 0\leq x_ i\leq u_ i\), \(0\leq I_ i\leq S_ i\), \(i=1, \dots, T\}.\) The cost function \(f_ i(x_ i)\) for period \(i\), \(i=1, \dots, T\), is of the fo rm \[ f_ i(x_ i) = \begin{cases} 0 & \text{if } x_ i = 0, \\ F_ i + c_ i x_ i & \text{if } 0<x_ i\leq r_ i, \\ F_ i + r_ i c_ i + o_ i(x_ i -r_ i) & \text{if } r_ i < x_ i \leq u_ i. \end{cases} \] So, it is neither convex nor concave. It is a composite function with a fixed setup cost to start the production and a piecewise linear and convex variable production cost. The authors present a branch and bound algorithm which finds a global optimum solution for the problem after solving a finite number of linear knapsack problems with bounded variables. The results of computational experiments performed on the algorithm, which have been presented in the paper, suggest that it is computationally efficient both in terms of CPU time and storage requirements.
- An effective algorithm for the capacitated single item lot size problem
- Solving single-product economic lot-sizing problem with non-increasing setup cost, constant capacity and convex inventory cost in \(O(N \log N)\) time
- An efficient algorithm for the capacitated single item dynamic lot size problem
- A new dynamic programming algorithm for the single item capacitated dynamic lot size model
- An O(T2) Algorithm for the NI/G/NI/ND Capacitated Lot Size Problem
- A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System—A Network Approach
- A capacity constrained singlefacility dynamic lot-size model
- A Deterministic Multi-Period Production Planning Model with Piecewise Concave Production and Holding-Backorder Costs
- A Transportation Type Aggregate Production Model with Backordering
- A transportation type aggregate production model with bounds on inventory and backordering
- A Weighted Selection Algorithm for Certain Tree-Structured Linear Programs
- An algorithm for indefinite integer quadratic programming
- An algorithm for solving a structured class of linear programming problems
- An Algorithm for the Dynamic Lot-Size Problem with Time-Varying Production Capacity Constraints
- Bounded Production and Inventory Models with Piecewise Concave Costs
- Computational Complexity of the Capacitated Lot Size Problem
- Deterministic Production Planning with Concave Costs and Capacity Constraints
- Deterministic Production Planning: Algorithms and Complexity
- Dynamic version of the economic lot size model
- scientific article; zbMATH DE number 192986 (Why is no real title available?)
- Multiproduct dynamic lot-sizing model with coordinated replenishments
- Planning Horizons for the Dynamic Lot Size Model with Backlogging
- Planning Horizons for the Dynamic Lot Size Model: Zabel vs. Protective Procedures and Computational Results
- Production scheduling by the transportation method of linear programming
- Sequential production planning over time at minimum cost
- A simple FPTAS for a single-item capacitated economic lot-sizing problem with a monotone cost structure
- Primal-dual approach to the single level capacitated lot-sizing problem
- A dynamic programming algorithm for dynamic lot size models with piecewise linear costs
- A joint chance-constrained programming approach for the single-item capacitated lot-sizing problem with stochastic demand
- Single-item dynamic lot-sizing problems: an updated survey
- Two-stage absolute semi-deviation mean-risk stochastic programming: an application to the supply chain replenishment problem
- A hybrid polynomial-time algorithm for the dynamic quantity discount lot size model with resale
- A polynomial time algorithm for convex cost lot-sizing problems
- Lower bound on size of branch-and-bound trees for solving lot-sizing problem
- A single-item economic lot-sizing problem with a non-uniform resource: Approximation
- Linear-programming extended formulations for the single-item lot-sizing problem with backlogging and constant capacity
- Modeling industrial lot sizing problems: a review
- Algorithms for Single-Item Lot-Sizing Problems with Constant Batch Size
- An approximate dynamic programming approach for multi-stage stochastic lot-sizing under a decision-hazard-decision information structure
- On the stochastic uncapacitated dynamic single-item lotsizing problem with service level constraints
This page was built for publication: A branch and bound algorithm for a single item nonconvex dynamic lot sizing problem with capacity constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q583078)
