A branch and bound algorithm for a single item nonconvex dynamic lot sizing problem with capacity constraints
type: Item
instance of: scholarly article
title: A branch and bound algorithm for a single item nonconvex dynamic lot sizing problem with capacity constraints
zbMATH Open document ID: 0691.90018
DOI: 10.1016/0305-0548(90)90043-7
author: S. Selcuk Erenguc
author: Yasemin Aksoy
published in: Computers \& Operations Research
publication date: 1990-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90B05
Mathematics Subject Classification ID: 90C57
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90B30
Mathematics Subject Classification ID: 90C30
zbMATH DE Number: 4131912
zbMATH Keywords: single item T-period lot sizing
zbMATH Keywords: branch and bound algorithm
zbMATH Keywords: linear knapsack problems
reviewed by: Stefan Chanas
MaRDI profile type: Publication
full work available at URL: 0305-0548(90)90043-7
OpenAlex ID: W1964452956
cites work: Production Scheduling by the Transportation Method of Linear Programming
cites work: Sequential production planning over time at minimum cost
cites work: A transportation type aggregate production model with bounds on inventory and backordering
cites work: A Transportation Type Aggregate Production Model with Backordering
cites work: Dynamic version of the economic lot size model
cites work: Planning Horizons for the Dynamic Lot Size Model with Backlogging
cites work: Planning Horizons for the Dynamic Lot Size Model: Zabel vs. Protective Procedures and Computational Results
cites work: A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System—A Network Approach
cites work: Computational Complexity of the Capacitated Lot Size Problem
cites work: Deterministic Production Planning with Concave Costs and Capacity Constraints
cites work: Deterministic Production Planning: Algorithms and Complexity
cites work: Bounded Production and Inventory Models with Piecewise Concave Costs
cites work: A Deterministic Multi-Period Production Planning Model with Piecewise Concave Production and Holding-Backorder Costs
cites work: An Algorithm for the Dynamic Lot-Size Problem with Time-Varying Production Capacity Constraints
cites work: A capacity constrained singlefacility dynamic lot-size model
cites work: An algorithm for solving a structured class of linear programming problems
cites work: Q4039868
cites work: A Weighted Selection Algorithm for Certain Tree-Structured Linear Programs
cites work: Multiproduct dynamic lot-sizing model with coordinated replenishments
cites work: An algorithm for indefinite integer quadratic programming
description: scientific article; zbMATH DE number 4131912