A branch and bound algorithm for a single item nonconvex dynamic lot sizing problem with capacity constraints (Q583078): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / 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. | |||
Property / 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Stefan Chanas / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90B05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C57 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C10 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65K05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90B30 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C30 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 4131912 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
single item T-period lot sizing | |||
Property / zbMATH Keywords: single item T-period lot sizing / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
branch and bound algorithm | |||
Property / zbMATH Keywords: branch and bound algorithm / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
linear knapsack problems | |||
Property / zbMATH Keywords: linear knapsack problems / rank | |||
Normal rank |
Revision as of 19:16, 1 July 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A branch and bound algorithm for a single item nonconvex dynamic lot sizing problem with capacity constraints |
scientific article |
Statements
A branch and bound algorithm for a single item nonconvex dynamic lot sizing problem with capacity constraints (English)
0 references
1990
0 references
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.
0 references
single item T-period lot sizing
0 references
branch and bound algorithm
0 references
linear knapsack problems
0 references